Patent ID: 8184803

Claim:
A method of generating hash functions using elliptic curves for cryptography, comprising the steps of: (a) specifying a set of coefficients a,bεF, wherein F represents a finite field, wherein elements of F are represented by (N+1) bits, and wherein N is a selected natural number; (b) establishing an elliptic curve EC that satisfies y 2 =x 3 +ax+b, wherein x and y are Cartesian coordinates; (c) establishing a twist TEC of the elliptic curve EC that satisfies α y 2 =x 3 +ax+b, wherein α is non-quadratic residue of the finite field F; (d) specifying a base point on the elliptic curve (x B ,y B )εEC and a base point on the twist of the elliptic curve (x TB ,√{square root over ( α y TB )εTEC; (c) establishing the set of coefficients, the base point on the elliptic curve and the base point on the twist of the elliptic curve as public information; (d) selecting a pair of random numbers k 1 ,k 2 , wherein the pair of random numbers are established as private information and the pair of random numbers are scalars; (e) computing a multiplication of the random number k 1 with the base point (x B ,y B ) to produce the scalar multiplication (x Pu ,y Pu )=k 1 (x B ,y B ); (f) computing a multiplication of the random number k 2 with the base point (x TB ,√{square root over ( α y TB ) to produce the scalar multiplication (x TPu ,√{square root over ( α y TPu )=k 2 (x TB ,√{square root over ( α y TB ); (g) establishing (x Pu ,y Pu ) and (x TPu ,√{square root over ( α y TPu ) as public information; (h) processing a message bit string to produce a bit string that is a multiple of N bits; (i) computing an initial hash point (x c 1 ,y c 1 ) on the elliptic curve; (j) computing an initial hash point (x Tc 1 ,√{square root over ( α y Tc 1 ) on the twist of the elliptic curve; (k) establishing an integer i representing an i th message data block and setting i=2; (l) embedding a message N bit string of an i th block into the x-coordinate of the elliptic message point (x m i ,√{square root over (α m i )}y m i ) using non-iterative embedding; (m) computing the set of hash points as (x c i ,y c i )=(x m i ,y m i )+(x c i−1 ,y c i−1 ) and (x Tc i ,√{square root over ( α y Tc i )=(x Tc i−1 ,√{square root over ( α y Tc i−1 ) if α m i =1, and otherwise computing the set of hash points as (x Tc i ,√{square root over ( α y Tc i )=(x m i ,√{square root over ( α y m i )+(x Tc i−1 ,√{square root over ( α y Tc i−1 ) and (x c i ,y c i )=(x c i−1 ,y c i−1 ); (n) repeating steps (l) and (m) until the message data blocks are processed and incrementing i at each said step; and (o) concatenating bits of the x-coordinate x c , and the sign bit of the y-coordinate y c of a hash point (x c u ,y c u ), along with the bits of the x-coordinates x Tc and the sign bit of the y-coordinate y Tc of a hash point (x Tc u ,√{square root over ( α y Tc u ) to form a hash bit string.