# Re: Elliptic curves

• From: mm <nowhere@net>
• Date: Thu, 06 Aug 2009 19:57:16 +0200

a écrit :
mm <nowhere@net> wrote:
a écrit :
mm <nowhere@net> wrote:
But I was not writing a math paper, [...]
Correctness still matters.
Like telling me that we cannot use ECs to mimic RSA because computing
"e'th roots (at least for small e) on an elliptic curve over a finite
field" is easy?

Let me quote what you wrote: "All we need is a group whose order
is difficult to compute (except to the one who built this group)."
This is wrong. To prove this, I gave an example where you can compute
roots without using the group order.

Let me elaborate on the example:

In 1984, it was hard to compute the number of points on an elliptic curve.
If we believe you, an RSA-variant using elliptic curves over finite
fields would have been secure in 1984.

No. When I was talking of the order of a group based on an EC, I was not
talking of an EC over a finite field.

In my 2nd post to E. Söylemez, I wrote

|With a curve E(A,B)/N, N being the product of two "big" different
|primes, the order is not easy to compute (but we can build such a curve
|with a known order when we know the factorization of N).

I thought it made it clear that the computations are done with the curve
E(A,B)/N where N is not a prime.

In my previous post to you, I wrote

|Let's say, E(A,B)/N (E_N for short) is an elliptic curve modulo N.
|What I am thinking of is to use a bijection between E(A,B)/N and
|E(A mod P,B mod P)/P x E(A mod Q,B mod Q)/Q with N = PQ, P and Q
|primes and 3 < P < Q.
|This bijection maps a point (X,Y,Z) of E_N to the couple of points
|((X mod P,Y mod P,Z mod P),(X mod Q,Y mod Q,Z mod Q)) of E_P x E_Q.

This is not very complicated. One can build a curve E(A,B)/N with a
known order. Except for special cases, an attacker will not be able
to compute this order without factoring N. Once e and d are computed,
we have a RSA scheme with an EC. Just, so that it works, one has to
use projective or Jacobian coordinates but not affine ones.

We deal with 4 types of points that one can 'canonicalize' as
(x,y,0) = Identity
(x,y,1)
(x,y,P)
(x,y,Q)
and for all types ((x,y,z)*e)*d = (x,y,z).
.

## Relevant Pages

• Re: Elliptic curves
... You need a group where computing e'th roots is hard. ... elliptic curve over a finite field without computing the group order. ...
(sci.crypt)
• Re: Elliptic curves
... Like telling me that we cannot use ECs to mimic RSA because computing ... "e'th roots on an elliptic curve over a finite ...
(sci.crypt)
• Re: Elliptic curves
... roots without using the group order. ... it was hard to compute the number of points on an elliptic curve. ... an RSA-variant using elliptic curves over finite ...
(sci.crypt)
• Re: Elliptic curves
... roots without using the group order. ... it was hard to compute the number of points on an elliptic curve. ... talking of an EC over a finite field. ...
(sci.crypt)