Digital signature algorithm

• US 5,231,668 A
• Filed: 07/26/1991
• Issued: 07/27/1993
• Est. Priority Date: 07/26/1991
• Status: Expired due to Term

• Current Assignee: United States Secretary of Commerce
• Original Assignee: THE GOVERNMENT OF THE UNITED STATES OF AMERICA, AS REPRESENTED BY THE SECRETARY OF COMMERCE
• Inventors: Kravitz, David W.
• Primary Examiner(s): CANGIALOSI, SALVATORE A
• Application Number:
  US07/736,451
• Time in Patent Office: 732 Days
• Field of Search: 380/28, 380/30
• US Class Current: 380/28
• CPC Class Codes: H04L 9/3013 involving the discrete logarithm problem, e.g. ElGamal or Diffie-Hellman systems
• CPC Class Codes: H04L 9/3247 involving digital signatures

Abstract

A method is provided for generating and verifying a digital signature of a message m. This method requires a pair of corresponding public and secret keys (y and x) for each signer, as well as a pair of public and secret values (r and k) generated for each message by the signer. The public value r is calculated according to the rule r=(g^k mod p) mod q. A value s is then selected according to the rule s=k^-1 (H(m)+xr) mod q where H is a known conventional hashing function. The message m, along with the signature (r,s) is then transmitted. When the transmitted signal is received a verification process is provided. The received values of r and s are tested to determine whether they are congruent to 0 mod g. Additionally, r is tested to determine whether it is equal to v mod q, where v is computed from r, s, m and y. For legitimately executed signatures, v=g^k mod p.

Claims

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

(a) providing a secret value k unique to said message m;

(b) providing a public value g;

(c) calculating said value r proceeding from a prime modulus p and a value g selected to be a prime divisor of p-1 according to the rule

r=(g^k mod p) mod g;

(d) applying a hashing transform H only to said message m to generate a transformed message H(m);

(e) calculating said value s according to the rule s=f(H(m)) where said value s is a function of m only by way of said transformed message H(m); and

,

(f) generating a signal representative of said digital signature (r,s) in accordance with said value r and said value s and transmitting said generated signal.

2. The method for generating a digital signature (r,s) of claim 1, wherein step (a) comprises the step of randomly selecting said secret value k.

3. The method for generating a digital signature (r,s) of claim 1, wherein step (b) comprises the step of calculating said value g proceeding from a value h which may be any non-zero integer such that h.sup.(p-1)/q is not congruent to 1 mod p according to the rule

4. The method for generating a digital signature (r,s) of claim 1, wherein step (d) comprises the step of transforming said message m by applying a one-way transform H to said message M.

5. The method for generating a digital signature (r,s) of claim 1, wherein step (e) further comprises the step of calculating said value s according to the rule

6. The method for generating a digital signature (r,s) of claim 1, wherein steps (a)-(c) are performed prior to knowledge of said message m.

7. The method for generating a digital signature (r,s) of claim 1, comprising the further step of transmitting a signed message formed of said message m and said digital signature (r,s).

8. The method for generating a digital signature (r,s) of claim 7, comprising the further steps

(g) receiving said transmitted signed message including a received digital signature (r,s) with a received value r and a received value s;

and,

(h) verifying said received digital signature (r,s).

9. The method for generating a digital signature (r,s) of claim 8, wherein step (h) comprises the step of reconstructing said g^k mod p of step (c) to provide a recovered g^k mod p.

10. The method for generating a digital signature (r,s) of claim 9, comprising the step of determining a value v proceeding from a value u₁ =(H(m))(s)^-1 mod g and a value u₂ =(r)(s)^-1 mod g according to the rule

11. The method for generating a digital signature (r,s) of claim 10, comprising the step of determining whether said determined value v after reduction mod q is the same as said received value r.

12. The method for generating a digital signature (r,s) of claim 11, comprising the further step of determining that said received digital signature (r,s) is verified in response to determining that said determined value v after reduction mod q is the same as said received value r.

13. The method for generating a digital signature (r,s) of claim 8, wherein step (h) further comprises the step of determining whether said received value r is congruent to 0 mod g.

14. The method for generating a digital signature (r,s) of claim 8, wherein step (h) further comprises the step of determining whether said received value s is congruent to 0 mod g.

42. The method for generating and verifying a digital signature (r,s) of claim 5, wherein k^-1 is determined prior to knowledge of said message m.

15. 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

space="preserve" listing-type="equation">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.

16. The system for generating a digital signature (r,s) of claim 15, wherein said secret value k is randomly selected.

17. The system for generating a digital signature (r,s) of claim 15, wherein said public value g is calculated proceeding from a value h which may be any non-zero integer such that h.sup.(p-1)/q is not congruent to 1 mod p according to the rule

18. The system for generating a digital signature (r,s) of claim 15, wherein said transform means comprises one-way transform means for transforming said message m by applying a one-way hashing transform H to said message m.

19. The system for generating a digital signature (r,s) of claim 15, wherein a value x is a secret value and said value s is calculated according to the rule

20. The system for generating a digital signature (r,s) of claim 15, wherein said values k, g, and r are determined independently of said message m.

21. The system for generating a digital signature (r,s) of claim 15, further comprising:

means for receiving said transmitted signed message; and

,

verifying means for verifying said digital signature (r,s).

22. The system for generating a digital signature (r,s) of claim 21, wherein said verifying means further comprises means for reconstructing said g^k mod p to provide a recovered g^k mod p within said verifying means.

23. The system for generating a digital signature (r,s) of claim 22, further comprising means for determining a value v proceeding from a value u₁ =(H(m))(s)^-1 mod q and a value u₂ =(r)(s)^-1 mod q according to the rule

24. The system for generating a digital signature (r,s) of claim 23, further comprising means for determining whether said determined value of v after reduction mod q is the same as said received value r.

25. The system for generating a digital signature (r,s) of claim 24, further comprising means for determining that said signature (r,s) is verified in response to determining that said value v after reduction mod q is the same as said received value r.

26. The system for generating a digital signature (r,s) of claim 21, wherein said verifying means comprises means for determining whether said value r is congruent to 0 mod q.

27. The system for generating a digital signature (r,s) of claim 21, wherein said verifying means comprises means for determining whether said value s is congruent to 0 mod q.

43. The system for generating and verifying a digital signature (r,s) of claim 19, wherein k^-1 is determined prior to knowledge of said message m.

28. 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^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^k mod p in accordance with said message m;

(f) determining whether said isolated g^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.

29. The method for generating and verifying a digital signature (r,s) of claim 28, wherein step (b) comprises calculating said value g proceeding from a value h which may be any non-zero integer such that h.sup.(p-1)/q is not congruent to 1 mod p according to the rule

30. The method for generating and verifying a digital signature (r,s) of claim 28, wherein step (a) comprises randomly selecting said secret value k.

31. The method for generating and verifying a digital signature (r,s) of claim 29, wherein said reduction function F comprises reduction mod q.

32. The method for generating and verifying a digital signature (r,s) of claim 29, further comprising the step of determining a value v proceeding from a value u₁ =(H(m)) (s)^-1 mod q and a value u₂ =(r)(s)^'"'"'1 mod q, according to the rule

33. The method for generating and verifying a digital signature (r,s) of claim 29, further comprising the step of calculating said value r proceeding from a prime modulus p, according to the rule

34. The method for generating and verifying a digital signature (r,s) of claim 28, further comprising the step of calculating said value s according to the rule s=f(H(m)) where H is a hashing transform for producing a transformed message H(m) and said value s is a function of m only by way of said transformed message H(m).

35. The method for generating and verifying a digital signature (r,s) of claim 34, comprising the step of transforming said message m by applying a one-way transform H to said message m.

36. The method for generating and verifying a digital signature (r,s) of claim 29, further comprising the step of calculating said value s according to the rule

37. The method for generating and verifying a digital signature (r,s) of claim 36, comprising the step of determining k^-1 prior to knowledge of message m.

38. The method for generating and verifying a digital signature (r,s) of claim 28, wherein steps (a)-(c) are formed prior to knowledge of said message m.

39. The method for generating and verifying a digital signature of claim 36, comprising the further step of transmitting a signed message formed of said message m and said digital signature (r,s) proceeding from said calculated value of s.

40. The method for generating and verifying a digital signature (r,s) of claim 29, wherein step (g) further comprises the step of determining verification in accordance with a determination whether said received value r is congruent to 0 mod q.

41. The method for generating and verifying a digital signature (r,s) of claim 29, wherein step (g) further comprises the step of determining verification in accordance with a determination whether said received value s is congruent to 0 mod q.

44. 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^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^k mod p in accordance with said message m;

comparison means for determining whether said isolated g^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.