# US 8,751,806 B1 · Method and apparatus to provide public key authentication with low complexity devices

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 8,751,806 B1
- Document ID: US8751806B1
- Status: Granted
- Kind: B1
- Application number: 13/348,176
- Filed: 2012-01-11
- Granted: 2014-06-10
- Earliest claimed: 2006-01-20
- Assignees: Symantec Corporation
- Applicants: Joseph A. Adler; David M'Raihi
- Inventors: Joseph A. Adler; David M'Raihi
- Web page: https://patentgrep.com/patent/US8751806B1

## CPC

- H04L 9/3066: {involving algebraic varieties, e.g. elliptic or hyper-elliptic curves}
- H04L 9/3093: {involving Lattices or polynomial equations, e.g. NTRU scheme}
- H04L 9/3271: {using challenge-response}
- H04L 2209/805: Lightweight hardware, e.g. radio-frequency identification [RFID] or sensor
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## 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

### Claim 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.

### Claim 2 (depends on 1)

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

### Claim 3 (depends on 1)

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

### Claim 4 (depends on 1)

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

### Claim 5 (depends on 1)

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

### Claim 6 (depends on 1)

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.

### Claim 7 (depends on 1)

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.

### Claim 8 (depends on 1)

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

### Claim 9 (depends on 1)

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

### Claim 10 (depends on 1)

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

### Claim 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.

### Claim 12 (depends on 11)

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.

### Claim 13 (depends on 11)

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

### Claim 14 (depends on 11)

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.

### Claim 15 (depends on 11)

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.

### Claim 16 (depends on 11)

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

### Claim 17 (depends on 11)

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

### Claim 18 (depends on 11)

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

### Claim 19 (depends on 11)

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

### Claim 20 (depends on 11)

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

### Claim 21 (depends on 11)

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.