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

• US 8,751,806 B1
• Filed: 01/11/2012
• Issued: 06/10/2014
• 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): Hoffman, Brandon
• Assistant Examiner(s): Woldemariam, Nega
• Application Number:
  US13/348,176
• Time in Patent Office: 881 Days
• Field of Search: None
• 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. A radio-frequency identification (RFID) tag, comprising:

a memory for storing a tag identifier and a random number table; and

a processing device, responsive to energy from a RFID tag reader, configured to;

receive an initialization message instructing the RFID tag to initialize, the message comprising an identifier;

store the identifier in the memory;

select a random number as a private key;

generate an acknowledgement response to the message;

receive a request to compute a public key using elliptic cryptography, wherein the request comprises a value representing a point on an elliptical curve E over a finite field F;

compute the public key using the private key and the point on the elliptical curve E over the finite field F;

generate a response to the request, the response comprising the computed public key and facilitating certification of the RFID tag and the computed public key associated with the RFID tag; and

in response to challenges issued by the RFID tag reader and generated using the value and another random number, send challenge responses to the RFID tag reader, the challenge responses generated using the private key and the challenge, wherein the computed public key facilitating authentication of the challenge responses.

2. The RFID tag of claim 1, wherein the public key is stored as a digital certificate in the memory.

3. The RFID tag of claim 1, wherein the initialization message includes a definition of the field F and the elliptic curve E.

4. The RFID tag of claim 1, wherein the private key is sent with the tag identifier.

5. The RFID tag of claim 1, wherein the private key is sent to the tag by an external source.

6. The RFID tag of claim 1 wherein the acknowledgement responses comprises an acknowledgement that the tag identifier has been received and the private key has been generated.

7. The RFID tag of claim 1 wherein the memory is disabled by a tamper logic circuit based on a determination that the low power processing device is subject to tampering.

8. The RFID tag of claim 1 wherein the public key is stored as a digital certificate on the processing device.

9. The RFID tag of claim 1, wherein the field F is a binary field.

10. The RFID tag of claim 1, wherein the field F is a ternary field.

11. A method, comprising:

receiving an initialization message at a processing device, the message comprising a tag identifier and instructions to initialize the processing device;

storing the identifier in a memory;

selecting a random number as a private key;

generating an acknowledgement response to the message;

receiving a request to compute a public key using elliptic cryptography, wherein the request comprises a value representing a point on an elliptical curve E over a finite field F;

computing the public key using the private key and the point on the elliptical curve E over the finite field F;

generating a response to the request, the response comprising the computed public key and facilitating certification of the processing device and the computed public key associated with the processing device; and

in response to challenges issued by a reader of the processing device and generated using the value and another random number, sending challenge responses to the reader, the challenge responses generated using the private key and the challenge, wherein the computed public key facilitating authentication of the challenge responses.

12. The method of claim 11, wherein the low power processing device selects a key value sent to the processing device by an external source as the private key.

13. The method of claim 11, wherein the private key is sent with the identifier.

14. The method of claim 11, wherein the acknowledgement response comprises an acknowledgement that the tag identifier has been received and the private key has been generated.

15. The method of claim 11, wherein the memory is disabled by a tamper logic circuit based on a determination that the low power processing device is subject to tampering.

16. The method of claim 11, wherein the public key is stored as a digital certificate on the processing device.

17. The method of claim 11, wherein the field F is a binary field.

18. The method of claim 11, wherein the field F is a ternary field.

19. The method of claim 11, wherein the elliptical curve is a Kobliz curve.

20. The method of claim 11, wherein the elliptical curve is a NIST reduction polynomial.

21. The method of claim 11, wherein the processing device comprises a radio-frequency identification (RFID) tag and wherein the reader comprises an RFID tag reader.