Abstract: To solve the security problem of the ElGamal digital signature scheme which requires only one random number, an improved program is proposed by adding a random number to it so as to make the decryption more difficult. The security of the improved signature scheme is still based on the computation difficulty of discrete logarithm over finite domain. Then, how to enhance the complexity between the random number and the key due to adding a random number is discussed, as well as the security and time complexity of the improved signature scheme. The results show that the security of the improved signature scheme is enhanced with the time complexity increased little, in comparison with the original signature scheme.