Weak-Keys in Public Key Cryptosystems Based on Discrete Logarithms

The discrete logarithm method is the foundation of many public key algorithms. However, one type of key, defined as a weak-key, reduces the security of public key cryptosystems based on the discrete logarithm method. The weak-key occurs if the public key is a factor or multiple of the primitive element, in which case the user's private key is not needed but can be obtained based on the character of the public key. An algorithm is presented that can easily test whether there is a weak-key in the cryptosystem. An example is given to show that an attack can be completed for the Elgamal digital signature if a weak-key exists, therefore validating the danger of weak-keys. Methods are given to prevent the generation of these weak-keys.