Patent ID: 8225100

Claim:
A method for producing a message hash, comprising: segmenting a message into a sequence of blocks; accessing an integer g, wherein p is a first prime number, q is a second prime number not equal to 2 that divides p−1, and g is a generator of a subgroup, with order q, of the group of integers less than p; initializing a first intermediate hash value based on a first block of the sequence; for each remaining block in the sequence, initializing a respective intermediate hash value, selecting a number of integers from the subgroup generated by g, adding each of the number of integers to the respective intermediate hash value to yield a sum, and reducing the sum modulo a value related to p, wherein the number of integers selected for each remaining block depends on the respective intermediate hash value of a prior block, and wherein selecting the number of integers is based at least on a current block of the message; and returning, via a processor, a hash value of the message derived from a selection of bits based at least on a last-produced intermediate hash.