Small Public-Key Based Digital Signatures for Authentication

• US 20090003597A1
• Filed: 02/24/2006
• Published: 01/01/2009
• Est. Priority Date: 02/25/2005
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Rose, Gregory Gordon, Gantman, Alexander, Hawkes, Philip Michael, Noerenberg, John W. II
• Granted Patent: US 8,437,473 B2
• Time in Patent Office: Days
• US Class Current: 380/44
• CPC Class Codes: H04L 2209/20 Manipulating the length of blocks of bits, e.g. padding or block truncation
• 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

Embodiments disclosed allow authentication between two entities having agreed on the use of a common modulus N. The authentication includes generating a pseudorandom string value; generating a public key value based on the modulus N and the pseudorandom string value; generating a private key value corresponding to the public key value; receiving a verifier'"'"'s public key value; generating a shared secret value based on the modulus N, the private key value and the verifier'"'"'s public key value; calculating an authentication signature value using the shared secret value; and transmitting the authentication signature value for authentication. When the authentication signature is received, the public key value and the shared value are generated to calculate an authentication signature value. Thereafter, the authentication signature values are compared and authenticated.

Claims

1. A method for use in authentication between two entities having agreed on the use of a common modulus N, the method comprising:

generating a pseudorandom string value from an input value;

generating a first public key value based on the modulus N and the pseudorandom string value;

generating a first private key value corresponding to the first public key value;

receiving a second public key value; and

generating a shared secret value based on the modulus N, the first private key value and the second public key value.

2. The method as in claim 1, further comprising:

calculating an authentication signature value using the shared secret value; and

transmitting the authentication signature value.

3. The method as in claim 2, further comprising:

truncating the authentication signature value; and

wherein transmitting the authentication signature value comprises transmitting a truncated authentication signature value.

4. The method as in claim 2 or claim 3 as dependent thereon, wherein calculating the authentication signature value comprises calculating the authentication signature value using the shared secret value and the input value.

5. The method as in claim 2 or any one of the claim 3-4 as dependent thereon, further comprising:

receiving a password value;

encrypting the password value using the first private key value; and

transmitting the encrypted password value.

6. The method as in claim 5, wherein calculating the authentication signature value comprises calculating the authentication signature value using the shared secret value and the encrypted password value.

7. The method as in any one of the preceding claims, wherein generating the first private key value comprises:

generating the first private key value by solving for the discrete logarithm problem modulo N.

8. The method as in any one of the preceding claims, further comprising:

receiving a user input data and wherein the input value is based on the user input data.

9. The method as in any one of the preceding claims, further comprising:

transmitting the input value.

10. The method as in any one of the preceding claims, further comprising:

generating a second private key corresponding to the second public key value by solving the discrete logarithm problem modulo N; and

using the second private key as a shared secret key.

11. A processor configured to control the performance of a method as in any one of the preceding claims.

12. A storage medium configured to store instructions to perform a method as in claim 1 or any one of the claims 2-10 dependent thereon.

13. Apparatus for use in authentication between two entities having agreed on the use of a common modulus N, the apparatus comprising:

means for generating a pseudorandom string value from an input value;

means for generating a first public key value based on the modulus N and the pseudorandom string value;

means for generating a first private key value corresponding to the first public key value;

means for receiving a second public key value; and

means for generating a shared secret value based on the modulus N, the first private key value and the second public key value.

14. The apparatus as in claim 13, further comprising:

means for calculating an authentication signature value using the shared secret value; and

means for transmitting the authentication signature value.

15. The apparatus as in claim 14, further comprising:

means for truncating the authentication signature value; and

wherein transmitting the authentication signature value comprises transmitting a truncated authentication signature value.

16. The apparatus as in claim 14 or claim 15 as dependent thereon, wherein the means for calculating the authentication signature value comprises means for calculating the authentication signature value using the shared secret value and/or the input value.

17. The apparatus as in claim 14 or any one of the claim 15-16 as dependent thereon, further comprising:

means for receiving a password value;

means for encrypting the password value using the first private key value; and

means for transmitting the encrypted password value.

18. The apparatus as in claim 17, wherein the means for calculating the authentication signature value comprises means for calculating the authentication signature value using the shared secret value and the encrypted password value.

19. The apparatus as in claim 13 or any one of the claims 14-18 as dependent thereon, wherein the means for generating the first private key value comprises:

means for generating the first private key value by solving for the discrete logarithm problem modulo N.

20. The apparatus of claim 13 or any one of the claims 14-19 as dependent thereon, further comprising:

means for generating a second private key corresponding to the second public key value by solving the discrete logarithm problem modulo N; and

means for using the second private key as a shared secret key.

21. Apparatus for use in authentication between two entities having agreed on the use of a common modulus N, the apparatus comprising:

a pseudo-random generator configured to generate a pseudorandom string value from an input value;

a key generating unit configured to generate a first public key value based on the modulus N and the pseudorandom string value, and to generate a first private key value corresponding to the first public key value;

a receiver unit configured to receive a second public key value; and

a secret value generating unit configured to generate a shared secret value based on the modulus N, the first private key value and the second public key value.

22. The apparatus as in claim 21, further comprising:

a message authentication code unit configured to calculate an authentication signature value using the shared secret value; and

a transmitter unit configured to transmit the authentication signature value.

23. The apparatus as in claim 22, wherein the transmitter unit transmits a truncated authentication signature.

24. A method for use in authentication between two entities having agreed on the use of a common modulus N, the method comprising:

receiving a first authentication signature value;

generating a pseudorandom string value from an input value;

generating a first public key value based on the modulus N and the pseudorandom string value;

generating a shared secret value based on the modulus N, a private key value and the first public key value;

calculating a second authentication signature value using the shared secret value; and

comparing the first authentication signature value with the second authentication signature value.

25. The method as in claim 24, wherein comparing the first and second authentication signature values comprises comparing the first authentication signature value with a truncated portion of the second authentication signature value.

26. The method as in claim 24 or claim 25 as dependent thereon, the method further comprising:

receiving the input value.

27. The method as in claim 24 or any one of the claims 25-26 as dependent thereon, wherein calculating the authentication signature value comprises calculating the authentication signature value using the shared secret value and the input value.

28. The method as in claim 24 or any one of the claims 25-27 as dependent thereon, further comprising:

receiving an encrypted password value;

decrypting the password value using the first public key value; and

validating the decrypted password value.

29. The method as in claim 28, wherein calculating the authentication signature value comprises calculating the authentication signature value using the shared secret value and the encrypted password value.

30. A processor configured to control the performance of a method as in claim 24 or any one of the claims 25-29 as dependent thereon.

31. A storage medium configured to store instructions to perform a method as in claim 24 or any one of the claims 25-29 as dependent thereon.

32. Apparatus for use in authentication between two entities having agreed on the use of a common modulus N, the apparatus comprising:

means for receiving a first authentication signature value;

means for generating a pseudorandom string value from an input value;

means for generating a first public key value based on the modulus N and the pseudorandom string value;

means for generating a shared secret value based on the modulus N, a private key value and the first public key value;

means for calculating a second authentication signature value using the shared secret value; and

means for comparing the first authentication signature value with the second authentication signature value.

33. The apparatus as in claim 32, wherein the means for comparing the first and second authentication signature values comprises comparing the first authentication signature value with a truncated portion of the second authentication signature value.

34. The apparatus as in claim 32 or claim 33 as dependent thereon, further comprising:

means for receiving the input value.

35. The apparatus as in claim 32 or any one of the claims 33-34 as dependent thereon, wherein the means for calculating the authentication signature value comprises means for calculating the authentication signature value using the shared secret value and the input value.

36. The apparatus as in claim 32 or any one of the claims 33-35 as dependent thereon, further comprising:

means for receiving an encrypted password value;

means for decrypting the password value using the first public key value; and

means for validating the decrypted password value.

37. The apparatus of claim 36, wherein the means for calculating the authentication signature value comprises means for calculating the authentication signature value using the shared secret value and the encrypted password value.

38. Apparatus for use in authentication between two entities having agreed on the use of a common modulus N, the apparatus comprising:

a receiver unit configured to receive a first authentication signature value;

a pseudo-random generator configured to generate a pseudorandom string value from an input value;

a key generating unit configured to generate a first public key value based on the modulus N and the pseudorandom string value;

a shared secret value generating unit configured to generate a shared secret value based on the modulus N, a private key value and the first public key value;

a message authentication code unit configured to calculate a second authentication signature value using the shared secret value; and

a comparing unit configured to compare the first authentication signature value with the second authentication signature value.

39. The apparatus of claim 38, wherein the comparing unit compares the first authentication signature value with a truncated portion of the second authentication signature value.

40. A method for use in authentication between two entities having agreed on the use of a common modulus N, the method comprising:

receiving a public key value generated based on the modulus N;

generating a private key corresponding to the public key value by solving the discrete logarithm problem modulo N; and

using the private key as a shared secret key.

41. The method as in claim 40, wherein generating the private key comprises:

calculating the private key using the Chinese remainder theorem.

42. Apparatus for use in authentication between two entities having agreed on the use of a common modulus N, the apparatus comprising:

means for receiving a public key value generated based on the modulus N;

means for generating a private key corresponding to the public key value by solving the discrete logarithm problem modulo N; and

means for using the private key as a shared secret key.