Patent ID: 8291221

Claim:
A method for implementing a one-way hash function on an RFID device that comprises the step of providing computing capability to the RFID device, computing a one way hash function with security properties which accepts a k-bit message m where k is greater than 1200 bits as input, and computes as output a numeric approximation A to a small subset of t<<k, where t is from 16 bits to 64 bits, out of the k bits in a Rabin ciphertext defined by c=m 2 (mod n) where n is a k-bit composite modulus, and wherein the subset of bits in the Rabin ciphertext is a window of t consecutive bits, and wherein the numeric approximation to the t consecutive bits of c, denoted from LSB to MSB by c {i+1} , c {i+2} , . . . , c {i+t} , is defined by the steps of computing an extended window of t+u bits from c, denoted from LSB to MSB by c {i-u+1} , c {i-u+2} , . . . , c {i} , c {i+1} , . . . c {i+t} , and assuming that no carry was entering into the computation of the least significant bit c {i-u+1} from lower indexed bit computations which are not carried out, the numeric approximation A consisting of the last t bits in this extended window, and the first u bits in the extended window being discarded, and outputting the number approximation A.