Elliptic Curve Cryptography - Elliptic Curves: Number Theory and Cryptography - page 182

Any such pair of points can be combined to obtain a point mod n .There
is a technicality with points at infinity, which is discussed in Section 2.11.

3. Using (6.1), we see that the order of E ( Z n )is# E ( F p ) · # E ( F q ). By
Proposition 4.33, E is supersingular mod p and mod q , so we find (by
Corollary 4.32) that

# E ( F p )= p +1 and # E ( F q )= q +1 .

Therefore, ( p +1) M = (mod q ). This

means that the decryption works: Write de =1+ k ( p +1) for some
integer k .Then

∞ (mod p )and( q +1) M = ∞

dC = deM =(1+ k ( p +1)) M = M + k ( p +1) M = M + ∞ = M (mod p ) ,

and similarly mod q . Therefore, dC = M .

4. A key point of the procedure is that the group order is independent
of b . If Bob chooses a random elliptic curve y 2 = x 3 + Ax + B over
Z n , then he has to compute the group order, perhaps by computing it
mod p and mod q . This is infeasible if p and q are chosen large enough
to make factoring n infeasible. Also, if Bob fixes the elliptic curve,
Alice will have diculty finding points M on the curve. If she does
the procedure of first choosing the x -coordinate as the message, then
solving y 2 ≡ m 3 + Am + B (mod n )for y , she is faced with the problem

of computing square roots mod n . This is computationally equivalent to
factoring n (see [121]). If Bob fixes only A (the formulas for the group
operations depend only on A ) and allows Alice to choose B so that her
point lies on the curve, then his choice of e, d requires that the group
order be independent of B . This is the situation in the above procedure.

If Eve factors n as pq , then she knows ( p +1)( q + 1), so she can find d with
ed ≡ 1(mod( p +1)( q + 1)). Therefore, she can decrypt Alice's message.
Suppose that Eve does not yet know the factorization of n , but she finds
out the decryption exponent d . We claim that she can, with high probability,
factor n . She does the following:

1=2 k v with v odd and with k 1. Writes ed − ≥ 1( k =0since p +1 divides

ed − 1).

2. Picks a random pair of integers R =( r 1 ,r 2 )mod n ,lets b = r 2 − r 1 ,
and regards R as a point on the elliptic curve E given by y 2 = x 3 + b .

3. Computes R 0 = vR .If R 0 = ∞ mod n , start over with a new R .If R 0
is ∞ mod exactly one of p, q , then Eve has factored n (see below).

4. For i =0 , 1 , 2 ,...,k , computes R i +1 =2 R i .