On the Selection of Random Numbers in the ElGamal Algorithm

Generally speaking, parameter selection in all cryptographic algorithms and protocols is a mixture of art and science and exerts various subtle influences on a system, which is related to application requirements, security policies, the compromise between security and the overheads of computation, storage and communications, the balance between security and availability, and to the efficiency of software /hardware implementation, etc. Usually, simplistic, insecure or impractical textbook crypto…

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.