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

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.