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

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.