Patent ID: 6084965
Filing Date: 2000-07-04
Classification: H04L

Abstract:
A method for generating a digital signature giving message recovery and verifying the generated digital signature when system coefficients are g, q and p, wherein p and q are prime numbers different from each other, g is a natural number between 1 and p and a remainder obtained by dividing q.sup.th power of g by p is 1, the method comprising the steps of:for a signer, selecting a first random number r1, calculating a first remainder x.tbd.mg.sup.-r1 mod p, wherein m is a message, and applying the first remainder x and a signer's identification ID to a hash function to generate h(x, ID);for the signer, selecting second and third random numbers r2 and r3, calculating a second remainder r4.tbd.r1+ar2 mod q, wherein a is a first secret key, and calculating a third remainder r5.tbd.ar3+b mod q, wherein b is a second secret key;calculating a fourth remainder y1.tbd.r4+r5 h(x, ID) mod q and calculating a fifth remainder y2.tbd.r2+r3 h(x, ID) mod q, thus to generate a digital signature (x, y1, y2) for the message m;for a verifier, applying the first remainder x and the signer's identification ID to the hash function to generate h(x, ID); andrecovering the message m contained in the first remainder x by calculating a remainder .tbd.xg.sup.y1 v1.sup.y2 v2.sup.h(x, ID) mod p, wherein y1 is a first public key, v1.tbd.g.sup.-a mod p, v3 is a second public key and v2.tbd.g.sup.-b mod p, and verifying the validation of the digital signature (x, y1, y2) by confirming the contents of the recovered message.