Question

After looking at the RSA algorithm for asymmetric key encryption and decryption. And after looking at Diffie-Hellman Exchange and at the Elgamal encryption scheme that can use the key derived from the exchange.

State the justification for having this alternate mechanism when RSA is already well established. Consider the security and the computational aspects of the schemes. Be as specific as possible.

Answer 1

ElGamal encryption is one of many encryption schemes which utilizes randomization in the encryption process. Others include McEliece encryption, and Goldwasser-Micali , and Blum-Goldwasser probabilistic encryption.

Deterministic encryption schemes such as RSA may also employ randomization in order to circumvent some attacks. The fundamental idea behind randomized encryption techniques is to use randomization to increase the cryptographic security of an encryption process through one or more of the following methods – Increasing the effective size of the plaintext message space;

•Precluding or decreasing the effectiveness of chosen plaintext attacks by virtue of a one-to-many mapping of plaintext to cipher-text; and

•Precluding or decreasing the effectiveness of statistical attacks by leveling the a priori probability distribution of inputs..

The problem of breaking the ElGamal encryption scheme, i.e., recovering m given p,g,(g^x) and a, b is equivalent to solving the Diffie-Hellman problem . Infact, the ElGamal encryption scheme can be viewed as simply comprising a D. Diffie-Hellman key exchange to determine a session key (g ^ (x*k)), and then encrypting the message by multiplication with that session key. For this reason, the security of the El-Gamal encryption scheme is said to be based on the discrete logarithm problem in Zp*, although such an equivalence has not been proven. It is critical that different random integers k be used to encrypt different messages. Suppose the same k is used to encrypt two mess ages m1 and m2 and the resulting cipher-text pairs are (a1,b1) and (a2,b2). Then b1/b2= m1/m2, and m2 could be easily computed if m1 were known.

The ElGamal algorithm can be use as RSA algorithm for public key encryption because: •

RSA encryption depends on the difficulty of factoring large integers while

ElGamal encryption depends on on the difficulty of computing dicrete logs in a large prime modulus.

ElGamal is nothing but the advance version of Diffie- Hellmen key exchange protocol. But , ElGamalis not good because its cipher text is two times longer than the plain text.

ElGamal is good because it gives different cipher text for same plain text each time.For image data, the size of the cipher text is very huge & reshaping the encrypted data was not understood.

ElGamal ‘s encryption is very simple because it is multiplication of message and symmetric key(i.e c=m*k).

The Diffie-Hellman algorithm is being used to establish a shared secret that can be used for secret
communications while exchanging data over a public network using the elliptic curve to generate points and get the secret key using the parameters.