SIGNATURE VERIFICATION FOR ELGAMAL SCHEMES

摘要

A signature verification protocol is provided for ElGamal-like signature schemes. The digital signature verification scheme allows the signor of the message to verify the digital signature without using the public key. Generally the signors computer system has a private key d and a public key y derived from an element g and the private key d. The method comprises the steps of in the computer system signing a message m by generating a first signature component by combining the element g, the signature parameter k according to a first mathematical function and generating a second signature component by mathematically combining the first signature component with the private key d, the message m and the signature parameter k, and the signor verifying the signature by recovering a value k from the signature components without using the public key y and utilizing the recovered value k' in the first mathematical function to derive a value r' in order to verify the signature parameter k and k' are equivalent, thereby verifying the signature. This signature verification applies to all ElGamal-type signatures and works in any group and in particular elliptic curve groups. The signature verification method is of particular use in devices having limited computational power such as 'smart cards' or where a large number of verifications are to be performed by the signor.