Cryptanalysis of El-Gamal AAs cryptosystem - Mandangan, Arif (2011)
In this research, we strengthen the security of the El-Gamal Cryptosystem, simply referred as the AAs cryptosystem. The key exchange protocol of the AAs cryptosystem is analogous to the Diffie-Hellman key exchange protocol. The encryption and decryption processes of the AAs -cryptosystem are efficient since the operations involved are the simple addition and subtraction modulo 1. Unfortunately, the AAs cryptosystem was successfully attacked by the passive adversary attack. This attack is manipulating the weaknesses of the public key and encrypting/decrypting keys structure. The hard mathematical problem of the AAs cryptosystem has been reduced to the Discrete Logarithm Problem Modulo 1 which can be solved by using the passive adversary attack. As a solution, we redefined the structure of the public key and encrypting/decrypting keys. We propose a new secret parameter that plays an important role in the computation of the encrypting/decrypting keys. Without the correct combination of the secret parameters, the adversary will not be able to compute the encrypting/decrypting keys. The Discrete Logarithm Problem Modulo 1 for the strengthened –cryptosystem is more difficult than the previous one. Now the adversary needs to find two secret parameters and this task could not be done via the passive adversary attack. Furthermore we propose some attacks which aim to get the secret parameters which are used in the calculation of the encrypting/decrypting keys. Those attacks are the exhaustive search attack on the secret parameters and the linear Diophantine equation attack. We show that these attacks fail to get the correct secret parameters efficiently. Finally we redefined the hard mathematical problem of the strengthened AAs cryptosystem. To break the security of the strengthened AAs cryptosystem, one needs to find the private key. By choosing sufficiently large private key size, it is computationally infeasible to reveal the value of the private key via the exhaustive search attack. Therefore, the AAs cryptosystem has a potential to be a secure cryptosystem.