Digital signature algorithm

A system for generating a digital signature (r,s) of a message m wherein information is transmitted and received by users of said system, comprising:

• a secret value k unique to said message m;
• a public value g;
• transform means for applying a hashing transform H only to said message m to generate a transformed message H(m);
• means for calculating said value r proceeding from a prime modulus p and a value q selected to be a prime divisor of p-1 according to the rule
• r=(g.sup.k mod p) mod q;
• means for calculating said value s according to the rule s=f(H(m)) where said value s is a function of said message m only by way of H(m);
• generating means for receiving said calculated values of r and s and generating a signal representative of a signed message formed of said message m and said digital signature (r,s);
• and,
• transmitting means for transmitting said generated signal.

A method for generating and verifying a digital signature (r,s) of a message m in a system, comprising the steps of:

• (a) providing a secret value k unique to said message m;
• (b) providing a public value g;
• (c) determining said value r proceeding from a prime modulus p according to the rule r=F(g.sup.k mod p) wherein F is a reduction function independent of said message m;
• (d) receiving a signed message formed of said message m and said digital signature (r,s);
• (e) recovering and isolating g.sup.k mod p in accordance with said message m;
• (f) determining whether said isolated g.sup.k mod p after reduction according to said reduction function F is the same as said received value r;
• (g) determining that said signature (r,s) is verified in accordance with the determination of step (f);
• and,
• (h) generating a verification signal in accordance with step (g) and transmitting said verification signal.

A system for generating and verifying a digital signature (r,s) of a message m wherein information is transmitted and received by user of said system, comprising:

• a secret value k unique to said message m;
• a public value g;
• means for determining said value r proceeding from a prime modulus p according to the rule r=F(g.sup.k mod p) wherein F is a reduction function independent of said message m;
• means for receiving a signed message formed of said message m and said digital signature (r,s);
• means for recovering and isolating g.sup.k mod p in accordance with said message m;
• comparison means for determining whether said isolated g.sup.k mod p after reduction according to said reduction function F is the same as said received value r;
• verification means for determining that said signature (r,s) is verified in accordance with the determination of said comparison means;
• means for generating a verification signal in accordance with the verification of said verification means;
• and,
• means for transmitting said verification signal.