Sebery J.Cryptography.An introduction to computer security.1989

4.6 Elliptic Cryptosystems

201

			y
					R
			Q
P
|	|	|	|		x
				|	|
-3	-2	-1	1	2	3

P+Q

Fig. 4.2. Elliptic curve y2 = x3 8x + 6 over real numbers

which is smooth if the polynomial x3 + ax + b has no multiple roots or equivalently, if the discriminant = (4a3 + 27b2) 6= 0.

If char(F) = 2, we have two cases: if a1 = 0 or a1 6= 0 in Equation (4.20). 1. Supersingular elliptic curve (a1 = 0) { the transformation

(x; y) ! (x + a2; y) produces the curve of the form

y2 + a03y = x3 + a04x + a06:

2. Nonsupersingular elliptic curve (a1 6= 0) { the substitution
(x; y)	!	a12x + a3 ; a13y + a12a4 + a32		!
		a1	a13

gives the curve

y2 + xy = x3 + a20 x2 + a06:

4.6.2 Addition of Points

Elliptic curves can be graphically illustrated as shown in Figure 4.2. It is possible to de ne addition of points on elliptic curves. Moreover, the set of points on

202 4 PUBLIC-KEY CRYPTOSYSTEMS

the curve together with addition de nes an Abelian group. This point is crucial for our discussion and we are going to prove that the points on an elliptic curve form an Abelian group. We start from de nitions of the group structure.

{ The group identity element O is the point at in nity and for each point P , O + P = P + O:

{ The inverse of the point P = (x; y) is the point

P = (x; y):

{Two points P and Q with di erent x coordinates (see Figure 4.2) are added as follows:

1.Construct a line which intersects both P and Q. The line meets the curve in the third point R.

2. The inverse of the point R is the requested element P + Q or P + Q = R. { The point P can be added to itself. The line, which, in the previous case intersected the two points, is now replaced by the tangent line to the curve

at the point P.

The above de nition gives an explicit formula for addition. To derive this formula, assume that two points P and Q are given and

P = (x1; y1) and Q = (x2; y2):

We would like to nd a point P + Q = (x3; y3). Note that the line intersecting P and Q has the form

`(x) = `1x + `2

where `1 = y2 y1 and `2 = y1 `1x1. The line `(x) intersects the elliptic curve

x2 x1

in points (x; y) each of which satis es

f (x) = (`1x + `2)2 x3 ax b = 0:

(4.22)

The polynomial f(x) is of degree 3 and has three di erent roots for x 2 fx1; x2; x3g or, equivalently,

f (x) = (x x1)(x x2)(x x3) = 0

(4.23)

Comparison of Equations (4.22) and (4.23) leads us to the conclusion that

x1 + x2 + x3 = `21 or x3 = `21 x1 x2:

4.6 Elliptic Cryptosystems

203

The case for P = Q = (x1; y1 ) is similar, with the di erence that `1										= dxdy =
	3x2+a		at point P . The expression for addition of two points are therefore
	1
	2y1
	x3 2				x1			x2
	y3 (x1 x3 ) y1									(4.24)
where
				y1		y2		if P = Q
	= 8 x1					x2		6	:
			>	3x2+a				if P = Q
						1
			<		2y1
	From>now on, we denote an Abelian group generated by the points on the
			:
curve

y2 x3 + ax + b (mod p)

by Ep(a; b) where the eld F = Zp.

For example, consider an elliptic curve E7 (1; 6) with points satisfying the

congruence y2 x3 + x + 6 (mod 7). The collection of all points is

E7(1; 6) = f(1; 1); (1; 6); (2; 3);(2; 4); (3; 1); (3; 6); (4; 2); (4; 5); (6; 2); (6; 5);Og Because the order of the group is 11, the group is isomorphic to Z11 and any

point di erent from O generates the group. For instance,

2 (2;3) = (4; 2); 3 (2;3) = (3; 1); 4 (2;3) = (6; 5); 5 (2;3) = (1; 1); 6 (2;3) = (1; 6); 7 (2;3) = (6; 2); 8 (2;3) = (3; 6); 9 (2;3) = (4; 5); 10 (2; 3) = (2; 4);

11 (2; 3) = O:

4.6.3 Elliptic Curve Variant of RSA

Koyama, Maurer, Okamoto, and Vanstone [287] presented an implementation of RSA using elliptic curves. Demytko [134] showed a variant which is less restrictive as to the types of elliptic curves used in the cryptosystem.

204 4 PUBLIC-KEY CRYPTOSYSTEMS

We will describe the rst system by Koyama, Maurer, Okamoto, and Vanstone. Let the number of points in Ep(a; b) or the order of the group be #Ep(a; b). If we know Ep(a; b), then we can use the elliptic curve for encryption in very similar way as in the basic RSA system. To encrypt a message, we add the message e times. To decrypt the ciphertext, we need to add the ciphertext d times so we get back to the original message. It is easy to see that to do that, it is enough to choose e and d so their product is multiple of #Ep(a; b).

In general, we know that

#Ep(a; b) = p + 1 + t

where j t j 2pp. Schoof [454] invented an algorithm that computes the order of an elliptic curve in O((log p)8) steps. The algorithm becomes impractical for large p. However, the order of elliptic curves is known explicitly in the two cases:

(1)	If the modulus p is an odd prime p 2	(mod 3) and the parameter a = 0.
	The group Ep(0; b) is cyclic with the order p + 1 (0 < b < p).
(2)	If the modulus p is a prime satisfying p	3 (mod 4) and b = 0. The group
	Ep(a; 0) is cyclic with the order p + 1 if a is a quadratic residue modulo p
	(0 < a < p).

The RSA variant based on elliptic curves is described below. It is based on the elliptic curve EN (0; b) with N = p q and p q 2 (mod 3). Note that

#EN (0; b) = lcm(p + 1; q + 1).

Elliptic curve RSA cryptosystem

Problems Used: Factorization and discrete logarithm.

	The modulus N	= p q is public, the primes p; q are secret. The elliptic
	curve used is EN (0; b) (or			EN (a; 0)).
Message Space: M		= EN (0; b).
Cryptogram Space:		C = EN (0; b).
Public Key: e 2R f1; : : : ; #EN (0; b)g and gcd (e; #EN (0; b)) = 1.
Secret Key: d 2 f1; : : : ; #EN (0; b)g such that e d 1 (mod #EN (0; b)).
Encryption: Let m = (mx; my) be a point on the elliptic curve EN (0; b).
	c = Ee(m) = e	m over EN (0; b).
Decryption: m = Dd(c) = d				c over EN (0; b).

4.6 Elliptic Cryptosystems

205

The security of elliptic curve RSA systems is related to the diÆculty of factorization of the modulus N. Kurosawa, Okada, and Tsujii report that elliptic curve RSA is not secure with low exponents [293].

Let us illustrate the system for small parameters. The receiver Bob selects two primes p = 239 and q = 401. Note that the primes are congruent to 2 modulo 3. In other words, Bob has decided to use the group EN (0; b). Next he computes N = p q = 95839, #EN (0; b) = lcm(p + 1; q +1) = 16080 and selects at random a public key e. Let it be e = 5891 (gcd(N; e) = 1). A secret key d = 12971 satis es the congruence e d 1 mod 16080. Bob announces the modulus N and the public key e.

Alice takes her message m = (mx; my) = (66321;24115), which is a point on the elliptic curve EN (0; b). Alice may even compute b as for all points (x; y) on the curve y2 x3 +b mod N (b y2 x3 mod N). Addition in EN (0; b) does not depend on b. Sender computes the cryptogram c = e m mod N which for the assumed values is the point c = (79227; 19622). Bob can easily decrypt the cryptogram by multiplying it by the secret key so m = d c = 12971(79227; 19622) = (66321; 24115).

Multiplication of points on elliptic curves may be conveniently implemented using any system for algebraic computations such as MAPLE, MATHEMATICA or MAGMA that supports multiprecision arithmetic. An example of a MAPLE program for addition and multiplication over an elliptic curve in given below.

# To load it into MAPLE, type:

#	read`<namefile>`;

#where <namefile> is a file with the code in the same directory

#MAPLE software is run.

#---------------------------------------------------------------------------

#Program adds two points on the elliptic curve y^2 = x^3 + b modulo N.

#Point in infinity is represented by (0,0) and the inverse of

#any point (x,y) is (x,-y)

#---------------------------------------------------------------------------

ad := proc(x1,y1,x2,y2, N)

local lambda, x3, y3, result;

if x1=x2 then

if modp(y1+y2, N)=0 then RETURN( 0, 0 ); fi;

fi;

206 4 PUBLIC-KEY CRYPTOSYSTEMS

if x1=0 then

if y1=0 then RETURN( x2, y2 ); fi;

fi;

if x2=0 then

if y2=0 then

result[1] := x1; result[2] := y1; RETURN( x1, y1 );

fi;

fi;

if x1 <> x2 then

lambda := modp((y1-y2)/(x1-x2), N); else

lambda := modp((3*(x1^2))/(2*y1), N);

fi;

x3 := modp(lambda^2-x1-x2,N);

y3 := modp(lambda*(x1-x3)-y1, N); RETURN( x3, y3 );

end;

#---------------------------------------------------------------------------

#mult function multiplies a point (x,y) by k modulo N on the

#curve (the function calls ad function).

#---------------------------------------------------------------------------

mult := proc( k, x, y, N)

local a,i,j,alpha,beta,base,s,accum ;

a :=	array ( 1	..	1000 , sparse	);
base	:= array(	1	.. 1000, 1..2,	sparse);

if k=0 then RETURN( 0,0 ); fi; if k=1 then RETURN( x,y ); fi;

i := k; j	:=	1;
while i >	0 do
alpha		:= irem(i,2,'q');
beta		:= iquo(i,2,'r');
i	:=	beta; a[j] := alpha; j := j+1;
od;
base[1,1]	:=	x; base[1,2] := y;
accum[1] := 0; accum[2] := 0;
if a[1]=1	then
accum[1] := x; accum[2] := y;
fi;
for i from 2		to j-1 do
s :=		ad( base[i-1,1],base[i-1,2],base[i-1,1],base[i-1,2],N);

4.6 Elliptic Cryptosystems

207

base[i,1] := s[1]; base[i,2] := s[2];

if a[i]=1 then accum := ad( base[i,1],base[i,2],accum[1],accum[2],N); fi;

od;

RETURN( accum );

end;

The function mult() can be used directly for encryption and decryption. Note that the function performs an operation that is equivalent to the RSA exponentiation. It works relatively fast for moduli whose size is several hundreds of bits, making computations quite realistic.

4.6.4 Elliptic Curve Variant of ElGamal

The system described below was invented by Menezes and Vanstone [339].

Elliptic curve ElGamal cryptosystem

Problems Used: Discrete logarithm.

Bob selects a large prime p > 3 (the modulus), an elliptic curve Ep (the
corresponding discrete logarithm problem has to be intractable), and a point
P 2 Ep. The elliptic curve Ep, the modulus and the point P are public.
Message Space:	M	= Zp Zp.
Cryptogram Space:		C = Ep Zp Zp.
Public Key: a point d P 2 Ep.
Secret Key: an integer d 2 Z (d smaller than the order of the cyclic group).
Encryption: Alice selects at random a multiplier s 2 Zp, calculates the point
R = s P 2 Ep, and nds a point Q = s d P = ( x; y) 2 Ep. For the message
m = (mx; my), she computes the cryptogram c = Ee(m) = (R; cx; cy) where
cx = xmx	(mod p) and cy = ymy (mod p). The multiplier s is kept

secret by Alice.

Decryption: Bob uses the point R to recover the point Q as Q = dR = dsP = ( x; y) 2 Ep. Next m = Dd(c) = (cx x 1 (mod p); cy y 1 (mod p)).

For example, consider an ElGamal system on an elliptic curve Ep(0; b) for p = 71 (71 2 mod 3). Bob publishes p and a point on the curve P = (25; 33) and the public key dP = (33; 39) for his secret key d = 43. To encrypt a message m = (mx; my) = (22; 44), Alice rst selects her secret s at random. Assume that the secret s = 29. Then she nds two points R = sP = (33; 32)

208 4 PUBLIC-KEY CRYPTOSYSTEMS

and Q = s(dP ) = (25; 38). The message m is encrypted using coordinates of the point Q so cx mx 25 53 mod 71 and cy my 38 39 mod 71. The cryptogram c = (R; 53; 39) is communicated to Bob.

Bob reconstructs the point Q using his secret integer d as Q = dR = (25; 38), computes 25 1 54 mod 71 and 38 1 43 mod 71. Clearly mx 53 54 22 mod 71 and my 39 43 44 mod 71.

Menezes, Okamoto, and Vanstone [337] demonstrated that the discrete logarithm problem on a supersingular elliptic curve can be reduced to the (classical) logarithm problem in a nite eld. This result shows that a care must be exercised in selection of elliptic curves so the corresponding logarithm problems are harder than the (classical) logarithm problem.

4.7 Probabilistic Encryption

The concept of probabilistic encryption was introduced and studied by Goldwasser and Micali in [210]. Their gaol was to design an encryption that is semantically secure. Semantic security requires that a polynomially bounded attacker is not able to tell apart a ciphertext of one message from a ciphertext of the other. In other words, cryptograms provide no information about encryption. This requirement must hold even if encryption is used for binary messages only.

A probabilistic public key cryptosystem applies to the set of messages M = f0; 1g, the set of keys K, the set of cryptograms C, and the set R = R0 [ R1. The encryption proceeds using the encryption function c = Ee(m; r) where r 2R Rm and m 2 f0; 1g. During the decryption process, the message m = 0 if Dd(c) 2 R0 or m = 1, otherwise. The encryption function induces a pair of two ensembles: C0 = Ee(R0) and C1 = Ee(R1). The proof of security of a probabilistic public key cryptosystem can be reduced to the assertion that the two ensembles C0 and C1 are polynomially indistinguishable (or polynomially secure). It turns out that semantic security and polynomial indistiguishibility are equivalent and they are the corner stone of the theory of conditionally secure cryptosystems.

(0 if c 2 ZQ+

NQ .

1 if c 2 ZN

4.7 Probabilistic Encryption

209

4.7.1 GM Probabilistic Encryption

The Goldwasser-Micali (GM) probabilistic encryption assumes that the quadratic residuosity problem is intractable. The idea is to generate cryptograms which are either quadratic or nonquadratic residues modulo a composite N = p q with their Jacobi symbol equal to 1. Thus, the system applies two indistinguishable

Q+

Q

Q+

consists of all elements from ZN that are

sets: ZN

and ZN

. The set ZN

quadratic residues modulo N. The set ZNQ contains nonquadratic residues of

the form

ZNQ = fx 2 ZN : xp = xq = 1g:

Note that their Jacobi symbol

x

=

x

x

= 1. Other nonquadratic residues

N

p

q

are not used in the encryption.

Assume that whenever the message is 0, the GM system generates a random element from ZNQ+, otherwise it produces a random number from ZNQ . The sender can produce the quadratic residues by random selection of element r 2 ZN and then squaring it. To enable the sender to produce random nonquadratic residue from ZNQ , there must be a public integer uZNQ which is used for this purpose.

GM probabilistic encryption

Problems Used: The quadratic residuosity problem. Given a composite integer N with two factors p and q. The modulus N is public but the factors are secret. An element u 2 ZNQ is public.

Message Space: M = f0; 1g.

Cryptogram Space: C = ZN .

Encryption: For a message m 2 M, select r 2 ZN and compute c = Ee(m; r) = umr2 mod N.

Decryption: m = Dd(c) =

Clearly, all cryptograms c have their Jacobi symbol equal to 1. To distinguish

which one carries 0 bit, the receiver has to know the factorization of N and calculate pc = c(p 1)=2. If this is equal to 1, um = 1 so m = 0.

210 4 PUBLIC-KEY CRYPTOSYSTEMS

4.7.2 BG Probabilistic Encryption

Blum and Goldwasser [45] generalized the GM public key encryption. They used the BBS pseudorandom generator to design a probabilistic public key encryption for short binary messages (not necessarily single bits). Their system is further referred to as the BG probabilistic encryption.

The BG Probabilistic Encryption

Problems Used: The quadratic residuosity problem. Given a composite integer

N with two factors p and q such that p

q

3 mod 4. The modulus N is

public. The factors p and q are secret.

Message Space:

M = t.

Cryptogram Space:

C

= ZN .

Encryption:

1. For a given seed x0, generate (x1; : : : ; xt) using the BBS gen-

erator (Section 5.3.2).

2. For a given message m = (m1 : : : mt) 2 M compute ci xi + mi mod 2,

i = 1; : : : ; t.

3. Calculate ct+1 = x02t+1 mod N.

4. Send the cryptogram c = (c1; : : : ; ct+1).

Decryption:

1. Recover the seed x0 from ct+1.

2. For the seed x0, generate (x1; : : : ; xt) using the BBS generator.

3. Recreate the message string mi ci + xi

mod 2 for i = 1; : : : ; t.

The method to retrieve x0 from ct+1 needs some clari cation. Assume that

p+1

Q+, then has two square roots, namely,

p =

4 . Indeed,

2 ZNp+1

2

p+1

p 1

4

=

2

=

2

p+1

2

as 2 ZNQ+ so

p

= (p 1)=2 = 1 and

4

= . So the squaring has its

1

p+1

mod p

1. To recover x0 from ct+1, we need to rst compute

inverse 2

4

2 (t+1)

p

+ 1

t+1

(mod p 1)

4

2 (t+1)

q

+ 1

t+1

(mod q 1)

4

and later nd x0 such that

2 (t+1)

x0 ct+1

mod p

x0 c2t+1(t+1)

mod q