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

• US 8,908,866 B2
• Filed: 04/13/2012
• Issued: 12/09/2014
• 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): Shiferaw, Eleni
• Assistant Examiner(s): Branske, Hilary
• Application Number:
  US13/446,024
• Publication Number:
  US 20140301551A1
• Time in Patent Office: 970 Days
• Field of Search: 380/28, 380/30, 380/277, 726/30, 713193-194, 713/189, 713171-172, 713/174, 713/168, 713/159, 713/155
• US Class Current: 380/277
• 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 comprising:

receiving a challenge at a radio frequency identification (RFID) tag from an RFID tag reader;

initializing the RFID tag based upon a first public key of a first key pair, a second public key of a second key pair, and a tag ID n received from the RFID tag 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,

k_E and ko are functions of the first public key and the second public key, 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 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_E and Oo are generators for large primes.

4. The method of claim 1, further comprising:

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

5. A system comprising:

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

an initialization module configured to initialize a tag based upon a first public key of a first key pair, a second public key of a second key pair, and a tag ID n received from the reader system;

a cryptographic logic module configured to perform cryptographic calculations including 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 a low processing power system (LPPS),

s and u are random numbers;

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 being unique for each response even when responding to an identical challenge.

6. The system of claim 5, further comprising a secured memory to store the private key of the system and an identifier of the system.

7. The system of claim 5, wherein the cryptographic logic module is further configured to generate the random numbers s and u.

8. The system of claim 5, further comprising:

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

9. The system of claim 5, wherein the originators OE and 00 are points on an elliptical curve.