Nonlinearity analyses and adaptation of nonlinearity traits of key generation protocol of el-gamal AAß cryptosystem

This thesis documents nonlinearity analyses performed on the key generation protocol of El-Gamal AAß Cryptosystem. The main aim of this research is to improve the security of the cryptosystem with regards to its key generation protocol against linear cryptanalysis, and this is achieved through series of tests and evaluations of the strength of the protocol in terms of nonlinearity measurement and bijectivity evaluation. Basically, the work is done in two phases. In the first phase, the bijectivity of AAß function in the cryptosystem is evaluated. The process consisted of investigating the function in the protocol and inspecting bit distribution in the public key to determine whether it is balanced or not. In the second phase, a statistical approach based on the original work of Matsui (1993) is extended to perceive any possible linear relation between public key and ephemeral private key. There have been three major evolutional phases of the key generation protocol and the tests are done onto each of it. Though theoretically the key generation protocol is nonbijective, it still satisfies the bijectivity criterion. Also, the nonlinearity measurement of the key generation protocol is very high making it almost impossible to extend linear cryptanalysis onto it, especially for higher bit input size. Thus for 128-bit ephemeral key, it is conjectured that the success probability to guess the correct ephemeral private key using linear cryptanalysis is close to nil. However, it is easier to attack the key generation protocol using less complicated attack such as dictionary attack because only a single round of function is involved in it. Based on the findings, we propose two methods to improve the security of El-Gamal AAß cryptosystem against linear cryptanalysis. Since the nonlinearity level of the key generation protocol is phenomenal, the function in the protocol should be iterated at least twice to amplify its security. This is done not only to reduce the chance of guessing the correct ephemeral private key via linear cryptanalysis, but also to increase cryptanalysis work of dictionary attack. The second method is to multiply the generator point with a large number to increase the linear cryptanalysis work as well as obtain a better bit distribution in the public key