Method and apparatus to provide public key authentication with low complexity devices

• US 8,112,626 B1
• Filed: 01/20/2006
• Issued: 02/07/2012
• Est. Priority Date: 01/20/2006
• Status: Active Grant

• Current Assignee: Gen Digital Inc.
• Original Assignee: Symantec Corporation (NortonLifeLock Inc.)
• Inventors: Adler, Joseph A., M'Raihi, David
• Primary Examiner(s): Srivastava, Vivek
• Assistant Examiner(s): Woldemariam, Nega
• Application Number:
  US11/336,255
• Time in Patent Office: 2,209 Days
• Field of Search: 713/153, 713/163, 713/183, 713/193, 713/340, 713/164, 713/150, 713/224, 713/201, 713/212, 713/213, 713/220, 713/223, 714/38, 714/49, 714/48, 714/35, 714/37, 709/203, 709/217, 709/223, 709/237, 709/225, 709/229, 709/227, 709/201, 709/220, 726/22, 726/14, 726/13, 726/11, 726/34, 726/25, 726/26, 726/27, 726/9, 726/28, 726/29, 380/42, 380/55, 380/58, 380/46, 345/581, 345/55
• US Class Current: 713/168
• CPC Class Codes: H04L 2209/805 Lightweight hardware, e.g. radio-frequency identification [RFID] or sensor
• CPC Class Codes: H04L 9/3066 involving algebraic varieties, e.g. elliptic or hyper-elliptic curves
• CPC Class Codes: H04L 9/3093 involving Lattices or polynomial equations, e.g. NTRU scheme
• CPC Class Codes: H04L 9/3271 using challenge-response

Abstract

A method and apparatus to authenticate limited processing-power systems (LPPS) using elliptic cryptography within a well known elliptic curve E, over a well known finite field F((E(F)). The apparatus comprises a random number generator to choose a random value b, of a similar order of magnitude to the order of E(F). The apparatus further comprises a challenge calculator to calculate a value C=bP and send the challenge to the LPPS, where P is a point on the elliptic curve E(F) which was used as a basis for generating a private key, a, for the LPPS. The apparatus further comprising an RFID reader to receive a challenge response, R=aC=abP from the LPPS, and a crypto calculator to calculate bQ, based on a public key, Q, of the LPPS. The apparatus further comprising a comparison logic to authenticate the LPPS if bQ=aC=abP.

Claims

1. An apparatus to authenticate limited processing-power systems (LPPS) using elliptic cryptography within a well known elliptic curve E, over a well known finite field F(E(F)), the apparatus comprising:

a random number generator to choose a random value b, of a similar order of magnitude to the order of E(F);

a challenge calculator to calculate a value C=bP, a challenge, and send the challenge to a limited power processing system (LPPS), where P is a point on the elliptic curve E(F) which was used as a basis for generating a private key, a, for the LPPS;

an RFID reader to receive a challenge response, R=aC=abP from the LPPS;

a crypto calculator to calculate bQ, based on a public key, Q=aP, of the LPPS; and

a comparison logic to;

determine that aC=abP=baP=bQ; and

authenticate the LPPS based on the determination.

2. The apparatus of claim 1, wherein the random number generator is a cryptographically strong random number generator, which produces non-predictable values of b.

3. The apparatus of claim 1, further comprising:

a look-up logic to look up a public key of the LPPS in a public key database.

4. The apparatus of claim 3, wherein the public key database is available through one or more of the following:

a local database accessible through a local computer system, a non-volatile memory which is coupled to the apparatus, and a remote database accessible through a network.

5. The apparatus of claim 4, wherein the network is selected from among the following:

a wireless network, a wireline network, and a cellular telephone network.

6. The apparatus of claim 1, wherein a private key based on random number a is stored in the LPPS, and not available outside the LPPS.

7. The apparatus of claim 6, wherein the random number a is stored in tamper resistant memory in the LPPS.

8. The apparatus of claim 6, wherein the private key comprises (F, E, P, a), and the public key comprises (F, E, P, Q), where E is the elliptic curve, F is the finite field, P is a point Pε

E(F) that is the “

base”

for a subgroup of E, and a is a random value.

9. The apparatus of claim 1, wherein the LPPS generates a random number, a, as a private key, wherein the random number a is of the same length as the order of E(F).

10. The apparatus of claim 1, wherein the well known finite field is a binary field.

11. The apparatus of claim 1, wherein the well known finite field is a ternary field.

12. An RFID system for enabling cryptographic verification of an identity of an RFID tag, the RFID system comprising:

a challenge calculator to calculate a challenge, C=bP, where b is a random number, and P is a point on an elliptic curve E(F) which was used as a basis for generating a private key, a, for a limited processing-power system (LPPS);

an RFID reader to receive a challenge response, R, and a tag identifier from the RFID tag;

a look-up logic to look up a public key, Q, associated with the tag identifier;

a crypto calculator to calculate a value of bQ on an elliptic curve over a finite field; and

a comparison logic to;

compare the bQ to the challenge response, R=aC=abP, received from the RFID tag to determine if bQ=R=aC=abP, and

authenticate the RFID tag if it is determined that bQ=R=aC=abP.

13. The RFID system of claim 12, further comprising:

a public key database for storing a public key of the RFID tag.

14. The RFID system of claim 13, wherein the public key database is selected from among the following:

a local database, a non-volatile memory coupled to the RFID reader, and a remote database accessible through a network.

15. The RFID system of claim 14, further comprising:

a network connection comprising one or more of the following;

a wireless network, a wireline network, and a cellular telephone network.

16. The RFID system of claim 12, wherein the finite field is a binary field.

17. The RFID system of claim 12, wherein the finite field is a ternary field.

18. A method of using public key cryptography for authentication of a limited processing-power system (LPPS) using elliptic cryptography within a well known elliptic curve E, over a well known finite field F (E(F)), the method comprising:

generating a private key, a, for the LPPS;

requesting the LPPS to generate a public key, Q, by multiplying an originating point P with the LPPS'"'"'s private key, a;

requesting a digital certificate for the public key;

generating a random number, b, and requesting the LPPS to calculate abP, in response to challenge bP;

calculating a value of bQ;

comparing abP to bQ, to determine whether bQ=abP; and

authenticating the LPPS if it is determined that bQ=abP.

19. The method of claim 18, wherein the LPPS generates the private key, a.

20. The method of claim 18, further comprising looking up the public key of the LPPS in a public key database.

21. The method of claim 20, wherein the public key database is selected from among the following:

a local database, a non-volatile memory coupled to the RFID reader, and a remote database accessible through a network.

22. The method of claim 18, wherein the well known finite field is a binary field.

23. The method of claim 18, wherein the well known finite field is a ternary field.