Small public-key based digital signatures for authentication

• US 8,799,664 B2
• Filed: 04/09/2013
• Issued: 08/05/2014
• Est. Priority Date: 02/25/2005
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Rose, Gregory Gordon, Noerenberg, John W. II, Hawkes, Philip Michael, Gantman, Alexander
• Primary Examiner(s): Perungavoor, Venkat
• Assistant Examiner(s): Mehrmanesh, Amir
• Application Number:
  US13/859,646
• Publication Number:
  US 20130227297A1
• Time in Patent Office: 483 Days
• Field of Search: 380/30, 380/44, 380/282, 713/156, 713/171, 713/176, 713/180
• US Class Current: 713/176
• 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:

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 private key value corresponding to the first public key value;

generating a shared secret value based on the modulus N, the 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.

2. The method as in claim 1, 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.

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

receiving the input value.

4. The method as in claim 1, 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 1, further comprising:

receiving an encrypted password value;

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

validating the decrypted 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. 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 private key value corresponding to the first public key value;

means for generating a shared secret value based on the modulus N, the 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.

8. The apparatus as in claim 7, 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.

9. The apparatus as in claim 7, further comprising:

means for receiving the input value.

10. The apparatus as in claim 7, 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.

11. The apparatus as in claim 7, 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.

12. The apparatus of claim 11, 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.

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

a storage medium storing instructions; and

a processor communicatively coupled to the storage medium and configured to execute the instructions to implement;

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, and a private key value corresponding to the first public key value;

a shared secret value generating unit configured to generate a shared secret value based on the modulus N, the 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.

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