Show that the El Gamal public key cryptosystem is malleable

Show that the El Gamal public key cryptosystem is malleable. (Hint: Show that an adversary having the El Gamal ciphertext of a message m (but not m itself), can construct the El Gamal ciphertext of the message 2m).

Solution

An encryption algorithm is malleable if it is possible for an adversary to transform a ciphertext into another ciphertext.

In EI Gamal cryptosystem ,a plain text \'m\' is encrypted as E(m)=(g^b,m.A^b) where (g,A)is piblic key.

from the given ciphertext (c1,c2) ,an advesary can easily calculate (c1,t.c2) which is valid encryption of \'tm\' for any t.

EI Gamal encryption consists of three components_

1)the key generation.

2)the encryption algorithm.

3) the decryption algorithm.

KEY GENERATION

1)- generate a cyclic group G of order q with generator g.

2)- choose an \'x\' randomly from (1.........q-1)

3)- compute h:=g^x

4)- publish h, with G,q,g, as public key and retain x as private key which must be secret.

ENCRYPTION

1)- choose arandom y from (1....q-1) ,then calculate G:=g^y.

2)- calculate s:=h^y

3)- map secret message m onto m\' of G.

4)-calculate c2:=m\'.s

5)- ciphertext (c1,c2)= (g^y,m\'.h^y)=(g^y,m\'.(g^x)^y)

HERE one can easily find h^y if one know m\' .

DECRYPTION

1)- calculate the shared secret s:=c1^x

2)- compute m\' :=c2.s^(-1)

c2.s^(-1) =m\' .h^y.(g^(xy))^(-1)=m\'.g^(x.y).g^(-xy)=m\'

EI Gamal encryption is unconditionally malleable and therefore is not secure under chosen ciphertext attack.

Given an encryption (c1,c2) of some message,one can easily construct a valid encryption (c1,2c2) of message 2m.