Method and apparatus to provide authentication and privacy with low complexity devices

• US 8,171,289 B2
• Filed: 06/11/2007
• Issued: 05/01/2012
• Est. Priority Date: 06/09/2006
• Status: Active Grant

• Current Assignee: Symantec Corporation (NortonLifeLock Inc.)
• Original Assignee: Symantec Corporation (NortonLifeLock Inc.)
• Inventors: Adler, Joseph A., M'Raihi, David
• Primary Examiner(s): Pyzocha, Michael
• Assistant Examiner(s): Branske, Hilary
• Application Number:
  US11/761,273
• Publication Number:
  US 20080170695A1
• Time in Patent Office: 1,786 Days
• Field of Search: 713/155, 713/159, 713/168, 713/171, 713/172, 713/174, 713/189, 713/193, 713/194, 726/30, 380/277, 380/28, 380/30
• US Class Current: 713/168
• CPC Class Codes: G06F 7/725 over elliptic curves
• CPC Class Codes: H04L 2209/805 Lightweight hardware, e.g. radio-frequency identification [RFID] or sensor
• CPC Class Codes: H04L 9/0841 involving Diffie-Hellman or related key agreement protocols
• CPC Class Codes: H04L 9/3066 involving algebraic varieties, e.g. elliptic or hyper-elliptic curves
• CPC Class Codes: H04L 9/3271 using challenge-response

Abstract

A method and apparatus to provide a cryptographic protocol for secure authentication, privacy, and anonymity. The protocol, in one embodiment, is designed to be implemented in a small number of logic gates, executed quickly on simple devices, and provide military grade security.

Claims

1. A method of utilizing a radio-frequency identification (RFID) tag comprising:

receiving a challenge at the RFID tag from a reader;

calculating S=f(s, O_E), U=f(u, O_O), B=E(n, k_E), G=f(A, k_O), where

A is a function of the challenge and a private key of the RFID tag;

s and u are random numbers generated by the RFID tag,

n is a tag ID,

k_E and k_O are functions of a first public key and a second public key of the reader respectively, and

O_E and O_O are originators, provided by the reader; and

returning S, U, B, and G from the RFID tag to the reader, the returned data including a challenge response and the tag ID, and being unique for each response even when responding to an identical challenge.

2. The method of claim 1, wherein the originators O_E and O_O are points on an elliptical curve.

3. The method of claim 1, wherein the originators O_Eand O_O are generators for large primes.

4. The method of claim 1, further comprising initializing the RFID tag, wherein the initialization comprises receiving from the reader:

the first public key of a first key pair for privacy;

the second public key of a second key pair for obfuscation; and

the tag ID.

5. The method of claim 4, wherein the initialization further comprises:

selecting a third key pair for authentication; and

sending a public key of the third key pair to the reader.

6. The method of claim 4, wherein initialization further comprises:

receiving from the reader a private key of a third key pair for authentication, the private key of the third key pair stored only by the RFID tag.

7. A low processing power system (LPPS) comprising:

a transceiver configured to transmit and receive data, the transceiver further configured to receive a challenge from a reader system;

a crypto logic configured to perform cryptographic calculations, the crypto logic configured for calculating S=f(s, O_E), U=f(u, O_O), B=E(n, k_E), G=f(A, k_O), where

A is a function of the challenge and a private key of the LPPS,

s and u are random numbers generated by the LPPS,

n is an identifier of the LPPS,

k_E and k_O are functions of a first public key and a second public key of the reader respectively, and

O_E and O_O are originators, provided by the reader;

the transceiver further configured to return S, U, B, and G to the reader system, the returned data including a challenge response and the identifier of the LPPS, and being unique for each response even when responding to an identical challenge.

8. The system of claim 7, further comprising a secured memory to store the private key of the LPPS and the identifier of the LPPS.

9. The system of claim 7, wherein the crypto logic is further configured for generating the random numbers s and u.

10. The system of claim 7, further comprising:

a memory to store initialization data, the initialization data including the public keys of the reader, and the identifier of the LPPS.

11. The system 7, wherein the originators O_E and O_O are points on an elliptical curve, and wherein originators O_E and O_O are the same point on the same elliptical curve.