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

1. Bob chooses two distinct large primes p, q with p ≡ q ≡ 2(mod3)and

computes n = pq .

2. Bob chooses integers e, d with ed 1(modlcm( p +1 ,q + 1)). (He could

use ( p +1)( q + 1) in place of lcm( p +1 ,q +1).)

≡

3. Bob makes n and e public (they form his public key) and he keeps d, p, q
private.

4. Alice represents her message as a pair of integers ( m 1 ,m 2 )(mod n ).
She regards ( m 1 ,m 2 )asapoint M on the elliptic curve E given by

y 2 = x 3 + b

mod n,

where b = m 2 − m 1 (mod n ) (she does not need to compute b ).

5. Alice adds M to itself e times on E to obtain C =( c 1 ,c 2 )= eM . She
sends C to Bob.

6. Bob computes M = dC on E to obtain M .

We'll discuss the security of the system shortly. But, first, there are several
points that need to be discussed.

1. Note that the formulas for the addition law on E never use the value of
b . Therefore, Alice and Bob never need to compute it. Eve can compute
it, if she wants, as b = c 2 − c 1 .

2. The computation of eM and dC on E are carried out with the formulas
for the group law on an elliptic curve, with all of the computations being
done mod n . Several times during the computation, expressions such
as ( y 2 − y 1 ) / ( x 2 − x 1 ) are encountered. These are changed to integers
mod n by finding the multiplicative inverse of ( x 2 − x 1 )mod n .This
requires gcd( x 2 − x 1 ,n ) = 1. If the gcd is not 1, then it is p , q ,or n .
If we assume it is very hard to factor n , then we regard the possibility
of the gcd being p or q as very unlikely. If the gcd is n , then the slope
is infinite and the sum of the points in question is ∞ . The usual rules
for working with ∞ are followed. For technical details of working with
elliptic curves mod n , see Section 2.11.
By the Chinese Remainder Theorem, an integer mod n may be regarded
as a pair of integers, one mod p and one mod q . Therefore, we can regard
a point on E in Z n as a pair of points, one on E mod p and the other
on E mod q . In this way, we have

E ( Z n )= E ( F p ) ⊕ E ( F q ) .

(6.1)

For example, the point (11 , 32) on y 2 = x 3 + 8 mod 35 can be regarded
as the pair of points

(1 , 2) mod 5 , (4 , 4) mod 7 .