METHOD AND APPARATUS FOR IMPLEMENTING A NOVEL ONE-WAY HASH FUNCTION ON HIGHLY CONSTRAINED DEVICES SUCH AS RFID TAGS
First Claim
Patent Images
1. A method for implementing a one-way hash function on a highly constrained device that comprises the step of providing computing capability to the highly constrained device, computing a one way hash function with provable security properties which accepts a k-bit message m as input, and computes as output a numeric approximation A to some small subset of t<
- <
k out of the k bits in a Rabin ciphertext defined by c=m2 (mod n) where n is a k-bit composite modulus, and outputting the number approximation A.
1 Assignment
0 Petitions
Accused Products
Abstract
A method and apparatus for implementing a novel one-way hash function with provable security properties for authentication and non-authentication applications on highly constrained devices, with particular application to RFID tags.
-
Citations
20 Claims
-
1. A method for implementing a one-way hash function on a highly constrained device that comprises the step of providing computing capability to the highly constrained device, computing a one way hash function with provable security properties which accepts a k-bit message m as input, and computes as output a numeric approximation A to some small subset of t<
- <
k out of the k bits in a Rabin ciphertext defined by c=m2 (mod n) where n is a k-bit composite modulus, and outputting the number approximation A. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19)
- <
-
20. Apparatus for authenticating a device D to a reader E which share some secret information S by an interactive challenge-response protocol comprising:
-
a. means for receiving by D of a random challenge R sent from E; b. means for combining by D of the secret S and the challenge R by a MIX function which produces a k-bit value m=MIX(S,R); c. means for calculating a number approximation A of m by computing a one way hash function with provable security properties which accepts a k-bit message m as input, and computes as output a numeric approximation A to some small subset of t<
<
k out of the k bits in a Rabin ciphertext defined by c=m2 (mod n) where n is a k-bit composite modulus, and outputting the number approximation A that is sent from D to E;whereby E can verify the number approximation A of m by recomputing the same value, and can accept the proof of authenticity only if the computed and received values are the same.
-
Specification