The elGamal encryption scheme Let p be a prime and g e Zp a primitive element Let p=zp C=Z pXz and k-p, g, x,y):y=gx mod p) 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=i(p, g,x,y):y=g modp), and secret random number ke zp-l, define: exm, k)=(S,t), where s=gk modp t- m y modp Decryption For s, te Zp, define dx(s,t)=t(sr)mod p 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 etp=2357,g=2,x=1751,y=gX=21751=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=gk≡21520=1430(mod2357 t=My=2035X11851520697mod2357 The ciphertext C=(s, t)=(1430, 697) Decryption 1. Computes u≡s=1430175≡2084(mod2357) 2M=tu1=697X20841=2035(m0d2357)1
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 Dififiie-Hellman problem Given a prime p,g e zp, and x, y e zp, find xlog y moap 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 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 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