Secure hash-and-sign signatures

• US 6,578,144 B1
• Filed: 03/23/1999
• Issued: 06/10/2003
• Est. Priority Date: 03/23/1999
• Status: Expired due to Term

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Rabin, Tal, Halevi, Shai, Gennaro, Rosario
• Primary Examiner(s): Darrow, Justin T.
• Application Number:
  US09/274,525
• Time in Patent Office: 1,540 Days
• Field of Search: 713/170, 713/176, 713/177, 713/181, 705/64, 705/69, 705/68, 380/30, 708/136, 708/605, 708/606
• US Class Current: 713/176
• CPC Class Codes: H04L 2209/56 Financial cryptography, e.g. electronic payment or e-cash
• CPC Class Codes: H04L 9/302 involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes
• CPC Class Codes: H04L 9/3236 using cryptographic hash functions
• CPC Class Codes: H04L 9/3249 using RSA or related signature schemes, e.g. Rabin scheme

Abstract

This invention is a method and apparatus which provide a solution to the problem of constructing efficient and secure digital signature schemes. It presents a signature scheme that can be proven to be existentially unforgeable under a chosen message attack, assuming a variant of the RSA conjecture. This scheme is not based on “signature trees”, but instead it uses a “hash-and-sign” paradigm, while maintaining provable security. The security proof is based on well-defined and reasonable assumptions made on the cryptographic hash function in use. In particular, it does not model this function as a random oracle. The signature scheme which is described in this invention is efficient. Further, it is “stateless”, in the sense that the signer does not need to keep any state, other than the secret key, for the purpose of generating signatures.

Claims

1. A method for generating a digital signature for a message, the method comprising:

generating a pair of keys which includes a secret key and a public key;

producing a first hashed value by hashing the message, utilizing a division intractable hash function; and

forming a signature using the first hashed value together with the secret key.

2. A method as recited in claim 1, including using components of an RSA signature scheme.

3. A method as recited in claim 1, wherein the step of generating includes choosing an RSA modulus n=pq, and a random element, s, in Z_n*, wherein p,q, are chosen as large prime integers and kept secret.

4. A method as in claim 3, wherein p,q are chosen such that (p−

1)/2 and (q−

1)/2 are also primes.

5. A method as in claim 3, wherein p,q are chosen such that (p−

1)/2 and (q−

1)/2 are prime powers.

6. A method as recited in claim 1, wherein the step of producing is randomized using random values.

7. A method as recited in claim 6, wherein the step of producing uses a cryptographic hash function.

8. A method as recited in claim 7, wherein the step of producing includes

computing a first temporary value T₁, as T₁=SHA1(M), where M is the message to be signed;

choosing four random strings (R₁, R₂, R₃, and R₄), each having 256 bits;

computing a second temporary value T₂, where

9. A method as recited in claim 6, wherein the signature includes the random values used in the producing step.

10. A method as recited in claim 3, wherein the step of forming a signature includes extracting the e^th root of s modulo n, σ

=e{square root over (s)} mod n, where e is the first hashed value, and when the signature thus formed includes the root σ

.

11. A method as in claim 10, wherein the step of extracting the e^th root includes employing inversion and exponentiation.

12. A method as in claim 10, wherein the step of extracting the e^th root includes:

finding a multiplicative inverse of e modulo φ

(n), d=e<sup>−

1</sup> mod φ

(n), and

computing σ

=s^d mod n.

13. A method as recited in claim 1, further comprising verifying the signature.

14. A method as recited in claim 13, wherein the step of verifying includes:

reproducing a second hashed value by hashing the message, utilizing the division intractable hash function; and

checking validity of the signature using the second hashed value and the public key.

15. A method as recited in claim 9, further comprising verifying the signature, wherein the step of verifying includes:

reproducing a second hashed value by hashing the message, utilizing the division intractable hash function, using the random values that are included in the signature; and

checking a validity of the signature using the second hashed value and the public key.

16. A method as recited in claim 10, further comprising verifying the signature, wherein the step of verifying includes:

reproducing a second hashed value by hashing the message, utilizing the division intractable hash function; and

checking a validity of the signature using the second hashed value and the public key.

17. A method as recited in claim 16, wherein the step of checking includes exponentiation and comparing.

18. A method as recited in claim 16, wherein the step of checking includes:

computing a value s′

=σ

^e′

mod n, where e′

is the second hashed value;

comparing s′

to s; and

declaring the signature to be valid if s′

is equal to s.

19. A method as recited in claim 13, further comprising employing the signature for authentication of the message to be signed.

20. A method as recited in claim 13, further comprising employing the signature for non-repudiation of the message to be signed.

21. A method as recited in claim 13, further comprising:

authenticating a financial transaction using the signature, and

providing non-repudiation of components of the financial transaction.

22. A method for authenticating a message, comprising:

a signer;

generating a pair of keys which includes a public key and a private key;

communicating the public key to an intended receiver of the message;

forming a signature for the message by;

producing a hashed value by hashing the message, utilizing a division intractable hash function, and

using the hashed value together with the private key to form the signature; and

sending the message and signature to the receiver.

23. A method as recited in claim 22, further comprising the receiver checking a validity of the signature using the public key and the message.

24. A method for constructing a digital signature, the method comprising:

generating a public key PK and a secret key SK;

employing a division intractable hash function H to hash a message M to be signed, thereby obtaining a hashed value e=H(M); and

signing the value e with respect to the public key PK using the secret key SK.

25. A method for constructing a digital signature, the method comprising:

generating a public key having an RSA modulus of n=pq, and a random element, s, in Z_n*, wherein p,q, are chosen as large prime integers and kept secret;

a signer applying a division intractable hash function to compute a first hashed value e=H(M), where M is representative of a message; and

the signer using the first hashed value e as an exponent, by finding the e^th root of s modulo n, such as to form the signature on M being an integer, σ

, such that σ

^e=s mod n.

26. A method as recited in claim 25, wherein p,q are chosen as safe primes.

27. A method as recited in claim 25, wherein p,q are chosen as quasi safe primes.

28. A method as recited in claim 25, wherein the signer does not have to keep any state information other than the secret key.

29. A method for verifying if a message M and a signature σ

are authentic with respect to a public key (n,s), the method comprising;

a receiver of the message applying a division intractable hash function to compute a hashed value e′

=H(M); and

the receiver declaring the message to be verified if σ

^e′

=s mod n.

30. An article of manufacture comprising a computer usable medium having computer readable program code means embodied therein for causing generation of a digital signature for a message, the computer readable program code means in said article of manufacture comprising computer readable program code means for causing a computer to effect:

generating a pair of keys which includes a secret key and a public key;

producing a first hashed value by hashing the message, utilizing a division intractable hash function; and

forming a signature using the first hashed value together with the secret key.

31. An article of manufacture as recited in claim 30, the computer readable program code means in said article of manufacture further comprising computer readable program code means for causing a computer to effect using components of an RSA signature scheme.

32. An article of manufacture as recited in claim 30, wherein the step of generating includes choosing an RSA modulus n=pq, and a random element, s, in Z_n*, wherein p,q, are chosen as large prime integers and kept secret.

33. An article of manufacture as recited in claim 30, wherein the step of producing is randomized using random values.

34. An article of manufacture as recited in claim 33, wherein the step of producing uses a cryptographic hash function.

35. An article of manufacture as recited in claim 34, wherein the step of producing includes

computing a first temporary value T₁, as T₁=SHA1(M), where M is the message to be signed;

choosing four random strings (R₁, R₂, R₃, and R₄), each having 256 bits;

computing a second temporary value T₂, where

36. An article of manufacture as recited in claim 34, wherein the signature includes the random values used in the step of producing.

37. An article of manufacture as recited in claim 33, the computer readable program code means in said article of manufacture further comprising computer readable program code means for causing a computer to effect verifying the signature, wherein the step of verifying includes:

reproducing a second hashed value by hashing the message, utilizing the division intractable hash function, using the random values that are includes in the signature; and

checking a validity of the signature using the second hashed value and the public key.

38. An article of manufacture as recited in claim 32, wherein the step of forming a signature includes extracting the e^th root of s modulo n, σ

=e{square root over (s)} mod n, where e is the first hashed value, and when the signature thus formed includes the root σ

.

39. An article of manufacture as recited in claim 38, wherein the step of extracting the e^th root includes employing inversion and exponentiation.

40. An article of manufacture as recited in claim 38, wherein the step of extracting the e^th root includes:

finding a multiplicative inverse of e modulo φ

(n), d=e<sup>−

1</sup> mod φ

(n), and

computing σ

=s^d mod n.

41. An article of manufacture as recited in claim 30, the computer readable program code means in said article of manufacture further comprising computer readable program code means for causing a computer to effect verifying the signature.

42. An article of manufacture as recited in claim 41, wherein the step of verifying includes:

reproducing a second hashed value by hashing the message, utilizing the division intractable hash function; and

checking a validity of the signature using the second hashed value and the public key.

43. A computer program product comprising a computer usable medium having computer readable program code means embodied therein for causing generation of a digital signature for a message, the computer readable program code means in said computer program product comprising computer readable program code means for causing a computer to effect:

generating a pair of keys which includes a secret key and a public key;

producing a first hashed value by hashing the message, utilizing a division intractable hash function; and

forming a signature using the first hashed value together with the secret key.

44. An article of manufacture comprising a computer usable medium having computer readable program code means embodied therein for causing authentication of a message, the computer readable program code means in said article of manufacture comprising computer readable program code means for causing a computer to effect:

a signer;

generating a pair of keys which include a public key and a private key;

communicating the public key to an intended receiver of the message;

forming a signature for the message by;

producing a hashed value by hashing the message, utilizing a division intractable hash function, and

using the hashed value together with the private key to form the signature; and

sending the message and signature to the receiver.

45. An article of manufacture as recited in claim 44, the computer readable program code means in said article of manufacture further comprising computer readable program code means for causing a computer to effect the receiver checking a validity of the signature using the public key and the message.

46. A computer program product comprising a computer usable medium having computer readable program code means embodied therein for causing generation of a digital signature for a message, the computer readable program code means in said computer program product comprising computer readable program code means for causing a computer to effect:

generating a public key PK and a secret key SK;

employing a division intractable hash function H to hash a message M to be signed, thereby obtaining a hashed value e=H(M); and

signing the value e with respect to the public key PK using the secret key PK.

47. A computer program product comprising a computer usable medium having computer readable program code means embodied therein for causing construction of a digital signature for a message, the computer readable program code means in said computer program product comprising computer readable program code means for causing a computer to effect:

generating a public key having an RSA modulus of n=pq, and a random element, s, in Z_n*, wherein p,q, are chosen as large prime integers and kept secret;

a signer applying a division intractable hash function to computer a first hashed value e=H(M), where M is representative of a message; and

the signer using the first hashed value e as an exponent, by finding the e^th root of s modulo n, such as to form the signature on M being an integer, σ

, such that σ

^e=s mod n.

48. A computer program product as recited in claim 47, wherein the signer does not have to keep any state information other than the secret key.

49. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for verifying if a message M and a signature σ

are authentic with respect to a public key (n,s), said method steps comprising;

a receiver of the message applying a division intractable hash function to compute a hashed value e′

=H(M); and

the receiver declaring the message to be verified if σ

^e′

=s mod n.

50. An apparatus for generating a digital signature for a message, the apparatus comprising:

a generator module to generate a pair of keys which includes a secret key and a public key;

a hashing module to produce a first hashed value by hashing the message, utilizing a division intractable hash function; and

a signature module to form a signature using the first hashed value together with the secret key.

51. An apparatus as recited in claim 50, wherein at least one module uses components of an RSA signature scheme.

52. An apparatus as recited in claim 50, wherein the step of generating includes choosing an RSA modulus n=pq, and a random element s, in Z_n*, wherein p,q, are chosen as large prime integers and kept secret.

53. An apparatus as recited in claim 50, wherein the hashing module uses random values.

54. An apparatus as recited in claim 53, wherein the hashing module includes components to:

compute a first temporary value T₁, as T₁=SHA1(M), where M is the message to be signed;

choose four random strings (R₁, R₂, R₃, and R₄), each having 256 bits;

compute a second temporary value T₂, where

55. An apparatus as recited in claim 52, wherein the signature module forms a signature by extracting the e^th root of s modulo n, σ

=e{square root over (s)} mod n, where e is the first hashed value, such that the signature includes the root σ

.

56. An apparatus as in claim 55, wherein the signature module performs extracting the e^th root by:

finding a multiplicative inverse of e modulo φ

(n), d=e<sup>−

1</sup> mod φ

(n), and

computing σ

=s^d mod n.

57. An apparatus as recited in claim 50, further comprising a verifier module to verify the signature.

58. An apparatus as recited in claim 56, wherein the verifier module verify the signature by:

reproducing a second hashed value by hashing the message, utilizing the division intractable hash function; and

checking a validity of the signature using the second hashed value and the public key.

59. An apparatus as recited in claim 55, wherein the verifier module verifies the signature by:

reproducing a second hashed value by hashing the message, utilizing the division intractable hash function; and

checking a validity of the signature using the second hashed value and the public key.

60. An apparatus as recited in claim 59, wherein the verifier module performs checking by:

computing a value s′

=σ

^e′

mod n, where e′

is the second hashed value;

comparing s′

to s; and

declaring the signature to be valid if s′

is equal to s.