On the Selection of Random Numbers in the ElGamal Algorithm

The ElGamal algorithm, which can be used for both signature and encryption, is of importance in public-key cryptosystems. However, there has arisen an issue that different criteria of selecting a random number are used for the same algorithm. In the aspects of the sufficiency, necessity, security and computational overhead of parameter selection, this paper analyzes these criteria in a comparative manner and points out the insecurities in some textbook cryptographic schemes. Meanwhile, in order to enhance security a novel generalization of the ElGamal signature scheme is made by expanding the range of selecting random numbers at an acceptable cost of additional computation, and its feasibility is demonstrated.