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

4.3 Merkle-Hellman Cryptosystem

191

M

1

1

1

1

X

X

(d) d2

P ( 1; 2 are coprime) = d=1;d is odd

+ O(N ) + O 0d M d2

M

(2d) + O(N

1

@

A

=

X

):

2

d

d=1;d is odd

Let us consider:

M

(d)

1

(d)

1

X

X

@1 X

A

d2

d=1;d is odd

= d=1;d is odd d2

+ O 0d M

d2 1

=

Y

(1

1

) + O(N

)

2

p2

p 3

4

Y

1

1

= 3

(1

p2 ) + O(N 2 )

p 2

=43 62 + O(N 21 )

=82 + O(N 21 )

Thus, P ( 1; 2 are coprime) is approximately 82 .

The RSA system is the most popular cryptosystem which can provide both privacy and authentication. It is widely used to secure communication passing through insecure networks such as the Internet. RSA is provides security of e-mail systems, Web-based applications, and many e-commerce applications. Since its birth in 1977, the RSA has been subject to many attacks but none of them was devastating. Boneh [48] de nes four categories of attacks that can be launched against RSA: elementary attacks, low private exponent attacks (private exponent must never be low), low public exponents, and implementation attacks.

4.3 Merkle-Hellman Cryptosystem

The knapsack decision problem belongs to the class NPC and its search equivalent to the class NP-hard. Merkle and Hellman [340] based their public-key cryptosystem on the knapsack problem. The Merkle-Hellman cryptosystem or MH system encrypts an n-bit message m = ( 1; : : : ; n) 2 M using a public key e = ( 1; : : : ; n) where i 2 f0; 1g and i 2 Zq; i = 1; : : : ; n and q is prime. The cryptogram c 2 C is calculated as

Pi 1 !j . j=1

192 4 PUBLIC-KEY CRYPTOSYSTEMS

	n
c =	X	i i:	(4.17)

i=1

The enciphering is simple and very eÆcient.

The public key and secret elements are generated by the receiver Bob who sets up the whole system. Bob rst selects a sequence of superincreasing integers w = (!1; : : : ; !n) where

	i 1
!i >	X	!j :	(4.18)

j=1

Note that initial condition w de nes an instance of the easy knapsack problem which is solvable in linear time. Now Bob selects a big enough eld Zq (q is prime) and a multiplier r 2 Zq. Both the prime q and r can be chosen at random provided that

n

q > X !i:

i=1

Next Bob transforms the superincreasing vector w according to the following congruence

i !i r (mod q)

(4.19)

for i = 1; : : : ; n. The sequence ( 1; : : : ; n) constitutes the public key of the system. Note that the vector w, multiplier r, and prime q are kept secret by the receiver.

Assume that Bob has received a cryptogram c created according to Equation (4.17). Bob converts the cryptogram as follows:

c0 c r 1 (mod q)

Using Equations (4.17) and (4.19), we have

		n			n
	c0	X	i ir 1		X	i!i	(mod q):
		i=1			i=1

The transformed cryptogram c0 corresponds to an instance of the easy knapsack so Bob nds bits i of the message m.

MH cryptosystem

Problems Used: Knapsack.

The secret easy knapsack is a superincreasing sequence of integers w = (!1; : : : ; !n) such that !i >

					4.3 Merkle-Hellman Cryptosystem 193
Message Space:		M	= n.
Cryptogram Space:			C = Z.
Public Key: e = ( 1; : : : ; n) where i !i r (mod q).
	Both the modulus q and the multiplier r are secret.
Secret Key: The easy knapsack w = (!1; : : : ; !n), q and r.
Encryption: c = Ee(m) =				P	in=1 i i where m = ( 1; : : : ; n).
Decryption: Conversion of the cryptogram c into an instance of easy knapsack
	c0 = c r 1	(mod q).

To illustrate the MH system, assume that 5-bit messages are to be transmitted. Bob initiates the algorithm by choosing the vector,

w = (!1; !2; !3; !4; !5) = (2; 3; 6; 12; 25):

Note that:

!2 > !1 !3 > !1 + !2

!4 > !1 + !2 + !3 !5 > !1 + !2 + !3 + !4

Next he chooses the pair (r; q) at random provided that q is prime and q >

P(mod 53). Subsequently, the receiver calculates the public key using Congruence (4.19), namely:

5	!i	= 48. Let q = 53 and r = 46. It is easy to check that r	1	= 15
i=1

1 !1r		(mod q) 39	(mod 53)
2	!2r	(mod q) 32	(mod 53)
3	!3r	(mod q) 11	(mod 53)
4	!4r	(mod q) 22	(mod 53)
5	!5r	(mod q) 37	(mod 53)

So, the public key e = ( 1; 2; 3; 4; 5) =(39; 32; 11; 22; 37) is sent to the sender Alice. Suppose now that Bob has received the cryptogram c = 119. To decrypt it, he rst transforms it as follows:

c0 = c r 1 = 119 15 = 36 (mod 53) and next solves the easy knapsack instance:

194 4 PUBLIC-KEY CRYPTOSYSTEMS

c0	c0 = 36 > !5 = 25 ) 5 = 1
	!5 = 11 < !4	) 4 = 0
c0	!5 = 11 > !3 = 6	) 3 = 1
c0 !5 !3 = 5 > !2 = 3		) 2 = 1
c0 !5 !3 !2 = 2 = !1 = 2		) 1 = 1
In other words, the receiver has recreated the message m = (1, 1, 1, 0, 1).

4.3.1 Security of Merkle-Hellman Cryptosystem

The MH system was broken by Shamir [466] who presented a polynomial-time algorithm, which calculates easy knapsack from the public key. Shamir used the superincreasing property of easy knapsack integers to derive a system of linear inequalities. The system was later eÆciently solved using Lenstra's integer programming algorithm.

There is also a version of the MH system which applies multiple modular multiplications to hide easy knapsacks. This version of the system is called the iterated MH system. Adleman [3] used the L3 algorithm [299] to analyze a doubly iterated knapsack system. Brickell [63] and Lagarias and Odlyzko [294] showed that any low density knapsack are solvable in polynomial time. Finally, Brickell [64] invented a polynomial time algorithm which for k-iterated MH systems, extracts easy knapsack integers from the public key. Readers interested in details of breaking the Merkle-Hellman system are referred to the review paper by Brickell and Odlyzko [65] and the book by O'Connor and Seberry [379].

4.4 McEliece Cryptosystem

McEliece suggested [330] that error correcting codes are excellent candidates for designing public-key cryptosystems. His work has not received the prominence or detailed study it deserves because error correcting codes are e ective by virtue of their redundancy. This leads to data expansion, which has not been considered desirable in cryptography. Other cryptosystems related to the McEliece design include the Niederreiter scheme and the Stern scheme [514].

Assume we have a message space	M = GF (2k) and a codeword space C =
GF (2n). For any message m 2 M,	a code assigns a codeword c 2 C and

G0 = SGP;

4.4 McEliece Cryptosystem 195

c = L(m). A code L is linear if the sum of any two codewords c1+c2 is equivalent to the codeword of the sum of their messages m1 + m2, i.e. L(m1 + m2) = L(m1) + L(m2) = c1 + c2. Any linear code can be described as

c = m G

where m 2 GF (2k), c 2 GF (2n), and G is the (k n) generating matrix. McEliece based his cryptosystem on the Goppa codes, a superset of the BCH

or the Hamming codes, because they are easy to implement in hardware and a fast decoding algorithm exists for the general Goppa codes while no such fast decoding algorithm exists for a general linear code. Goppa codes can be de ned by their generating polynomial

p(x) = xt + pt 1xt 1 + + p1x + 1

of degree t over GF (2u). For messages of length k, the Goppa code produces codewords of length n = 2u and the code is capable of correcting any pattern of t or fewer errors.

The receiver Bob chooses a desirable value of n and t and then randomly picks an irreducible polynomial of degree t over GF (2u). The probability that a randomly selected polynomial of degree t is irreducible is about 1=t and Berlekamp [27] describes a fast algorithm for testing irreducibility of polynomials. Next Bob produces a k n generator matrix G for the code, which is in canonical form, that is:

G = [Ik Fk(n k)]

where Ik is the identity matrix.

The usual error correction method would now multiply a message vector m = ( 1; : : : ; k ) onto G to form the codeword c which is transmitted via a noisy channel. The channel usually corrupts the codeword to c0 which must then be corrected and then the message recovered. If m were multiplied onto G in the canonical form, c would be:

c = ( 1; : : : ; k; f1(m); : : : ; fn k(m))

If there was no corruption, the message is trivially recovered as the rst k bits of c.

Thus McEliece \scrambles" G by selecting a random dense k k non-singular matrix S, and a random n n permutation matrix P. He then computes

196 4 PUBLIC-KEY CRYPTOSYSTEMS

which generates a linear code with the same rate and minimum distance as the code generated by G. G0 is called the public generator matrix and constitutes the public key.

To encrypt a binary message m 2 GF (2k), Alice uses the public key G0 and computes the corresponding cryptogram

c = m G0 + e

where e is a locally generated random vector of length n and weight t. The vector e is kept secret by Alice. The decryption is done by Bob who calculates

c0 = c P 1

where P 1 is the inverse of the permutation matrix P. The vector c0 will then be a codeword of the Goppa code previously chosen. The decoding algorithm is then used to nd m = m0S 1.

McEliece cryptosystem

Problems Used: General Coding.

A Goppa code characterized by its generating matrix G which speci es an instance.

Message Space: M = GF (2k). Cryptogram Space: C = GF (2n). Public Key: Public key G0 = SGP . Secret Key: Matrices S, G, P . Encryption: c = EK(m) = m G0 + e

where e is a secret random binary string of weight t generated by Alice. Decryption: Bob computes c0 = c P 1, decodes c0 and obtains m0.

Finally, Bob translates m0 into m applying m = m0S 1.

4.4.1 Security of the McEliece Cryptosystem

We need to determine the security of the system. If an opponent knows G0 and intercepts c, can they recover m? There are two possible attacks:

1.to try to recover G from G0 and therefore be able to use the decoding algorithm

2.to attempt to recover m from c without knowing G

4.5 ElGamal Cryptosystem

197

The rst attack is equivalent to the decomposition of G0 into three matrices S, G and P . Note that from the adversary point of view, the decomposition is not unique. The number of invertible matrices S is 0:29 2k2 . There are 2ut=t di erent Goppa codes (matrices G) and n! di erent permutation matrices P . We do not know a decomposition algorithm that is better than the exhaustive search of all Goppa codes.

The second attack seems more promising but the basic problem to be solved is that of decoding a more or less arbitrary (n; k) linear code in the presence of up to t errors. Berlekamp, McEliece and van Tilborg [26] have proved that the general coding problem for linear codes is NP-complete, so one can certainly expect that, if the code parameters are large enough, this attack will also be

infeasible.

If n = 1024 = 210 and t = 50 there are about 10149 possible Goppa polynomials and a vast number of choices for S and P . The dimensions of the code will

be about 524. Hence, a brute-force approach to decoding based on comparing C to each codeword has a work factor of about 2524 = 10158, and a brute-force

approach based on coset leaders has a work factor of about 2500 = 10151.

4.5 ElGamal Cryptosystem

In 1985 ElGamal [163] published a public-key cryptosystem which uses the discrete logarithm problem. Bob, the designer of the system, chooses a large enough prime p and selects an element g that generates the cyclic group Zp . The element g can be found quickly by choosing at random g many times until g(p 1)=2 = 1 which guarantees that g is primitive (assuming that g 6= 1).

The probability that a single random element generates Z is quite high and

p

equals to '(p 1)=(p 1), where '(p 1) is the Euler totient function. Later Bob picks up an integer k < p 1. Bob computes gk (mod p) and publishes the modulus p, primitive element g and integer gk. The exponent k is kept secret.

To encrypt a message m 2 GF (p), Alice selects rst her secret element s at random from Zp 1 and prepares a cryptogram which consists of two parts c = (c1; c2 ) where

c1	m	(gk)s (mod p)
c2	gs	(mod p):

(mod p), its inverse g sk and the

2 Zp 1. The exponent s ism (gk)s (mod p) and

ck2 gsk

198 4 PUBLIC-KEY CRYPTOSYSTEMS

The pair is dispatched to Bob. On receiving the cryptogram, Bob computes (mod p). Next he nds the inverse g ks and computes the message

m c1 g ks (mod p):

The steps in ElGamal systems are summarized below.

ElGamal cryptosystem

Problems Used: Discrete logarithm.

Bob selects the modulus p, primitive element g, and the exponent k. The modulus p and element g are public.

Message Space: M = GF (p). Cryptogram Space: C = GF (p) GF (p). Public Key: Public key gk (mod p). Secret Key: k 2 Zp 1.

Encryption: Alice selects at random an exponent s secret. The cryptogram is c = (c1; c2) where c1

c2 gs (mod p).

Decryption: Bob computes (gk)s = ck2 gsk message m c1 g sk (mod p).

4.5.1 Security of ElGamal Cryptosystems

The security of the system is related to the diÆculty of solving instances of the DH problem. To have a secure instance of the ElGamal system, the modulus needs to be larger than 200 decimal digits or 660 bits. The modulus p must be selected in such a way that p 1 has at least one large factor preferably p 1 = 2q where q is a prime. For p = 2n, using Mersenne numbers is recommended (as p 1 is prime). Readers interested in algorithms for solving discrete logarithm problem are directed to Odlyzko's paper [381].

4.6 Elliptic Cryptosystems

Both the RSA and ElGamal cryptosystems extensively use the cyclic groups which exist in the underlying algebraic structure. Elliptic curves can also be used to de ne cyclic groups which are suitable for cryptographic applications. There

4.6 Elliptic Cryptosystems

199

is a common belief that a cryptosystem based on elliptic curves provides the same security as a system based on multiplicative groups Zp with the advantage that the cryptographic keys used by elliptic curve systems are shorter. These systems are relatively new and they have not been subject to the same scrutiny as older systems. This could be perceived as the main weakness. The idea of applying elliptic curves in cryptography was rst suggested by Koblitz [284] and Miller [347]. Readers who want to study the subject in more detail are directed to the book by Menezes [336] and Koblitz [285].

4.6.1 Elliptic Curves

Elliptic curves are interesting geometric objects that exhibit remarkable algebraic properties. To present their application in cryptography, we need to introduce necessary de nitions and notations and brie y discuss their algebraic properties.

Assume we have two elds F and K. K is an extension eld of F if F is contained in K. The extension eld K is always a vector space over F. If the dimension of the vector space is nite than we deal with a nite extension. Theeld K and its vector structure is determined by a unique monic irreducible polynomial f(x) 2 F[x] such that f ( ) = 0 for an element 2 K ( 62 F). The polynomial f(x) is called minimal polynomial of .

If the degree of f(x) is d, the extension eld F( ), i.e. the smallest eld containing F and the element , is a vector space with the base

1; ; 2; : : : ; : : : d 1:

Consider the eld Q of all rational numbers. Take an element = p2. Then the minimal polynomial is

f (x) = x2 2 2 Q[x]:

It is easy to check that f( ) = 0. The extension eld Q(p2) is a vector space with the base (1; ). For example, the product of two elements (a + b ) and (c + d ) from Q(p2) is equal to

(a + b )(c + d ) = ac + ad + bc + bd 2

= (ac + 2bd) + (ad + bc) because f( ) = 0 implies that 2 = 2.

200 4 PUBLIC-KEY CRYPTOSYSTEMS

We say that F is algebraically closed if every polynomial with coeÆcients

from F factors into polynomials of degree one. The algebraic closure F is the smallest algebraically closed extension of F.

A eld F has the characteristic (denoted as char(F)):

{zero if repeated addition of the multiplicative identity never produces zero,

{nonzero and equal to p if adding the multiplicative identity p times produces zero.

A discriminant of a monic polynomial f(x) of degree d with roots ( 1; : : : ; d) is

= Y ( i j):

i6=j

A curve de ned over a eld F is a collection of points (x; y) 2 F2 satisfying
a generalized Weierstrass equation of the form:
y2 + a1xy + a3y = x3 + a2x2 + a4x + a6			(4.20)
where the coeÆcients ai F for i = 1; : : : ; 6. Equation (4.20) de nes an elliptic
curve if the equation is smooth, i.e. the two			partial derivatives of f(x; y) =
y2 + a1xy + a3y x3 a2x2 a4x a6 do not vanish simultaneously, or
@f = 0 or	@f	= 0
@x 6	@y	6

in any point of the curve.

The general form given by Equation (4.20) can be simpli ed if we know the

characteristic of the eld	. If char(			) = 2. Then we can apply the substitution
a1	F a3	;	F	6
(x; y) ! x; y 2 x	2
which produces an isomorphic curve
y2 = x3 + a20 x2 + a40 x + a60 :				(4.21)

If char(F) 6= f2;3g, then the elliptic curve (4.21) can further be subject to the following substitution:

(x; y)	!	2x 3a20	;	y
		36		216

The transformation reduces the curve to the one of the form y2 = x3 + ax + b: