The elgamal encryption scheme Let p be a prime and g∈Z * a primitive element Let p= C=Z d兴 X Zp and k-p, g, x,y): y=gx mod p j The values p, g, y are the public key. x is the private key
11 The ElGamal encryption scheme Let p be a prime and g Zp * a primitive element. Let P = Zp * , C = Zp * x Zp * and K = {(p,g,x,y): y = g x mod p }. • The values p,g,y are the public key. • x is the private key
The elgamal encryption scheme Encryption Letm∈ z be a message For k=((p, g, x, y): y=gx modp), and secret random number k E Z l, define: ek(m, k)=(s, t), where s=gmod P t= my modp Decryption For st∈Zn,, define:dk( Ks, t)=t(s -/mod 12
12 The ElGamal encryption scheme • Encryption Let m Zp * be a message. For K = {(p,g,x,y): y = g x modp }, and secret random number k Zp-1 , define: eK (m,k) = (s,t), where – s = gk modp – t = m y k modp • Decryption For s,t Zp * , define: dK (s,t) = t(s x ) -1mod p
An Example Letp=2357,g=2,x=1751,y≡g=2751=1185 (mod2357) System parameters: (p, g)=(2357, 2) Public key: y=1185, Private key: X=1751 Encryption: Say M=2035 1. Pick a random number k=1520 2.compUtes S=g=2150=1430mod2357) Myk=2035X1185150=697(mod2357) The ciphertext C=(s, t)=(1430, 697) Decryption 1. Computes u≡Sx≡1430175≡2084(mod2357) 2M=tu1=697X2084=2035(mod2357)
13 An Example • Let p =2357, g = 2, x = 1751, y g x 2 1751 1185 (mod 2357) • System parameters: (p, g) = (2357, 2) Public key: y = 1185, Private key: x = 1751 • Encryption:say M = 2035 1.Pick a random number k = 1520 2.Computes s = gk 2 1520 1430 (mod 2357) t = Myk 2035 x 11851520 697 (mod 2357) – The ciphertext C = (s, t) = (1430, 697) • Decryption: 1.Computes u s x 14301751 2084 (mod 2357) 2.M t u-1 697 x 2084-1 2035 (mod 2357)
The security of ElGamal The Dififie-Hellman problem Given a prime p,8 ndx, yez. find xloggy modp The security of the ElGamal encryption is reduced to the difficulty of breaking the diffie-Hellman problem
14 The security of ElGamal • The Diffie-Hellman problem. Given a prime p, g e Zp * , and x,y e Zp * , find x log g y mod p. The security of the ElGamal encryption is reduced to the difficulty of breaking the Diffie-Hellman problem
Remarks on El-Gamal Encryption Scheme EIGamal encryption scheme is non-deterministic Randomization is introduced to increase the effective size of the plaintext space i.e. one plaintext can map to a large set of possible ciphertexts decrease the effectiveness of chosen-plaintext attack by means of a one-to-many mapping in the encryption process Efficiency encryption requires two exponentiation operations exponentiation operations may be very expensive when implemented on some low-power devices. e.g. low-end PalmPilots. smart cards and sensors message expansion by two-fold Security: depends on the difficulty of solving DLp 15
15 Remarks on El-Gamal Encryption Scheme • ElGamal encryption scheme is non-deterministic • Randomization is introduced to – increase the effective size of the plaintext space i.e. one plaintext can map to a large set of possible ciphertexts – decrease the effectiveness of chosen-plaintext attack by means of a one-to-many mapping in the encryption process • Efficiency: – encryption requires two exponentiation operations – exponentiation operations may be very expensive when implemented on some low-power devices. e.g. low-end PalmPilots, smart cards and sensors. – message expansion by two-fold • Security:depends on the difficulty of solving DLP