Patent ID: 8189771

Claim:
A method of generating hash functions for elliptic polynomial cryptography with elliptic polynomial hopping, comprising the steps of: establishing: a) a form of an elliptic polynomial equation by deciding on an underlying finite field F, a number of x-coordinates, and a set of monomials used, wherein this information is made public; b) a random number k 0 , which is kept as a secret key for a hash function to be used; c) selection of a random number generator, which is made public; d) a random number kp 0 which is made public; e) generation from kp 0 and using a publicly known method at least a portion of the coefficients b 1l (0) ,b 2lk (0) ε F to be used in the chosen elliptic polynomial form in generating the hash of the 0-th block; f) an initial base point (x 0,B (0) ,x 1,B (0) , . . . ,x nx,B (0) ,y B (0) ,α B ) for the selected polynomial, which is made public; and g) a computed scalar multiplication of the 0-th block shared key k 0 with a base point (x 0,B (0) ,x 1,B (0) , . . . ,x nx,B (0) ,y B (0) ,α B ) to obtain (x 0,kB (0) ,x 1,kB (0) , . . . ,x nx,kB (0) ,y kB (0) ,1)=k(x 0,B (0) ,x 1,B (0) , . . . ,x nx,B (0) ,y B (0) ,α B ), which is made public;) h) embedding the 0-th block into an elliptic polynomial message point) (x 0,m (0) ,x 1,m (0) , . . . ,x nx,m (0) ,y m (0) ,α m (0) ); i) the hash point of the 0-th data block (x 0,c (0) ,x 1,c (0) , . . . ,x nx,c (0) ,y c (0) ,α c (0) ) is computed using (x 0,c (0) ,x 1,c (0) , . . . ,x nx,c (0) ,y c (0) ,α c (0) )=(x 0,m (0) ,x 1,m (0) , . . . ,x nx,m (0) ,y m (0) ,α m (0) )+(x 0,kB (0) ,x 1,kB (0) , . . . ,x nx,kB (0) ,y kB (0) ,1), where α c (0) =α m (0) , and for j=1, repeating the following steps j) through n), and incrementing j at each step until all of the message data blocks are processed; j) using kp j-1 and the random number generator to generate a new random number kp j ; k) generating at least some of the coefficients b 1l (j) ,b 2lk (j) ε F of a j-th elliptic polynomial from the random number kp j ; l) embedding a j-th block of the message bit string into a j-th elliptic polynomial message point (x 0,m (j) ,x 1,m (j) , . . . ,x nx,m (j) ,y m (j) ,α m (j) ); m) hopping the hash point (x 0,c (j-1) ,x 1,c (j-1) , . . . ,x nx,c (j-1) ,y c (j-1) ,α c (j-1) ) to an equivalent hash point (x′ 0,c (j) ,x′ 1,c (j) , . . . ,x′ nx,c (j) ,y c (j) ,α′ c (j) ) that satisfies the j-th elliptic polynomial selected in step l); n) computing the hash point of the j-th data block (x 0,c (j) ,x 1,c (j) , . . . ,x nx,c (j) ,y c (j) ,α c (j) ) using (x 0,c (j) ,x 1,c (j) , . . . ,x nx,c (j) ,y c (j) ,α c (j) )=(x 0,m (j) ,x 1,m (j) , . . . ,x nx,m (j) ,y m (j) ,α m (j) )+(x′ 0,c (j) ,x′ 1,c (j) , . . . ,x′ nx,c (j) ,y′ c (j) ,α′ c (j) ), where α c (j) =Exclusive−OR(α m (j) , α′ c (j) ); and and o) the appropriate bits of the x-coordinates, and a bit indicating the value of α c (u) of the cipher point (x 0,c (u) ,x 1,c (u) , . . . ,x nx,c (u) ,y c (u) ,α c (j) ) are concatenated together to form the hash bit string.