# US 2010/0166175 A1 · Cryptographic hash functions using elliptic polynomial cryptography

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2010/0166175 A1
- Document ID: US20100166175A1
- Status: Published application
- Kind: A1
- Application number: 12/318,495
- Filed: 2008-12-30
- Published: 2010-07-01
- Earliest claimed: 2008-12-30
- Assignees: King Fahd University of Petroleum and Minerals
- Inventors: Lahouari Ghouti; Mohammad K. Ibrahim; Atef J. Al-Najjar
- Web page: https://patentgrep.com/patent/US20100166175A1

## CPC

- H04L 9/3066: {involving algebraic varieties, e.g. elliptic or hyper-elliptic curves}
- H04L 9/0643: {Hash functions, e.g. MD5, SHA, HMAC or f9 MAC}
- H04L 9/3093: {involving Lattices or polynomial equations, e.g. NTRU scheme}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

The cryptographic hash functions using of elliptic polynomial polynomials are based on the elliptic polynomial discrete logarithm problem, which is well known as a computationally hard problem. The hash functions are based on the elliptic polynomial equation in their generation, where different elliptic polynomials are used for different blocks of the same plain text. Particularly, the hash functions use an elliptic polynomial with more than one independent x-coordinate. More specifically, a set of elliptic polynomial points are used that satisfy an elliptic polynomial equation with more than one independent x-coordinate which is defined over a finite field F.

## Claims

### Claim 1

A method of generating cryptographic hash functions using elliptic polynomial cryptography in an electronic communications system, comprising the steps of:
a) generating a set of hash function parameters, including the steps of:
b) establishing a two-dimensional Cartesian coordinate system having orthogonal coordinates x and y, establishing natural numbers n and N, wherein a message string to be encrypted is divided into N bit strings, and establishing a finite field F, an elliptic polynomial EC and a twist of the elliptic polynomial TEC;
c) specifying values of nx and ny, and a set of coefficients a1k, a2kl, a3k, c1lki, c2kl, c3kli, b1l, b2lk, b3lk, b4k, bc∈F, along with a base point on an elliptic polynomial (x0,B, x1,B, . . . , xnx,B, y0,B, y1,B, . . . , yny,B)∈ECxn+ny+2 and a base point on the twist of the elliptic polynomial (x0,TB, x1,TB, . . . , xnx,TB, √{square root over ( αy0,B, y1,TB, . . . , yny,TB)∈TECxn+ny+2;
(d) disclosing the values of nx and ny, the set of coefficients, the base point on the elliptic polynomial and the base point on the twist as public information;
(e) selecting a pair of random number scalars k1, k2 which are kept secret for a specific hash function to be used;
(f) computing the multiplication of the scalar k1 with a point (x0,B, x1,B, . . . , xnx,B, y0,B, y1,B, . . . , yny,B) to obtain a scalar multiplication such that (x0,Pu, x1,Pu, . . . , xnx,Pu, y0,Pu, y1,Pu, . . . , yny,Pu)=k1(x0,B, x1,B, . . . , xnx,B, y0,B, y1,B, . . . , yny,B);
(g) computing the multiplication of the scalar k2 with a point (x0,TB, x1,TB, . . . , xnx,TB, √{square root over ( αy0,B, y1,TB, . . . , yny,TB) to obtain a scalar multiplication such that (x0,TPu, x1,TPu, . . . , xnx,TPu, √{square root over ( αy0,TPu, y1,TPu, . . . , yny,TPu)=k1(x0,TB, x1,TB, . . . , xnx,TB, √{square root over ( αy0,B, y1,TB, . . . , yny,TB);
(h) disclosing the scalar multiplication points (x0,Pu, x1,Pu, . . . , xnx,Pu, y0,Pu, y1,Pu, . . . , yny,Pu) and (x0,TPu, x1,TPu, . . . , xnx,TPu, √{square root over ( αy0,TPu, y1,TPu, . . . , yny,TPu) as public information;
(i) generating a hash bit string of the message bit string, including:
(j) pre-processing the message bit string to obtain a bit string which is a multiple of (nx+ny+1)N-bit;
(k) computing an initial hash point (x0,c1, x1,c1, . . . , xnx,c1, y0,c1, y1,c1, . . . , yny,c1) on the elliptic polynomial by multiplying a scalar integer value km0 of the (nx+ny+1)N-bit string of an initial block of the message bit string with a point (x0,Pu, x1,Pu, . . . , xnx,Pu, y0,Pu, y1,Pu, . . . , yny,Pu) such that (x0,c1, x1,c1, . . . , xnx,c1, y0,c1, y1,c1, . . . , yny,c1)=km0(x0,Pu, x1,Pu, . . . , xnx,Pu, y0,Pu, y1,Pu, . . . , yny,Pu);
(l) computing an initial hash point (x0,Tc1, x1,Tc1, . . . , xnx,Tc1, √{square root over ( αy0,Tc1, y1,Tc1, . . . , yny,Tc1) on the twist of the elliptic polynomial by multiplying a scalar integer value km1 of the (nx+ny+1)N-bit string of the next block of the message bit string with a point (x0,TPu, x1,TPu, . . . , xnx,TPu, √{square root over ( αy0,TPu, y1,TPu, . . . , yny,TPu) such that:
(x0,Tc1, x1,Tc1, . . . , xnx,Tc1, √{square root over ( αy0,Tc1, y1,Tc1, . . . , yny,Tc1)=km1(x0,TPu, x1,TPu, . . . , xnx,TPu, √{square root over ( αy0,TPu, y1,TPu, . . . , yny,TPu);
m) establishing integer values i and u with an initial value of i=2, and repeating the following steps n) and o) until i>u:
n) embedding a (nx+ny+1)N-bit string of the ith block of the message bit string into (nx+1) x-coordinates X0, x1, . . . , xnx and ny y-coordinates y1, . . . , yny of the elliptic message point (x0,mi, x1,mi, . . . , xnx,mi, √{square root over ( αmiy0,mi, y1,mi, . . . , yny,mi) using non-iterative embedding;
(o) if the message point of the ith block is on the elliptic polynomial then computing the hash points as:
(x0,ci, x1,ci, . . . , xnx,ci, y0,ci, y1,ci, . . . , yny,ci)=(x0,mi, x1,mi, . . . , xnx,mi, y0,mi, y1,mi, . . . , yny,mi)+(x0,ci-1, x1,ci-1, . . . , xnx,ci-1, y0,ci-1, y1,ci, . . . , xny,ci-1)
and (x0,Tci, x1,Tci, . . . , xnx,Tci, √{square root over ( αy0,Tci, y1,Tci, . . . , yny,Tci)=(x0,mi, x1,mi, . . . , xnx,mi, √{square root over ( αy0,mi, y1,mi, . . . , yny,mi)+ and (x0,Tci-1, x1,Tci-1, . . . , xnx,Tci-1, √{square root over ( αy0,Tci-1, y1,Tci-1, . . . , xny,Tci-1) (x0,ci, x1,ci, . . . , xnx,ci, y0,ci, y1,ci, . . . , yny,ci)=(x0,ci-1, x1,ci-1, . . . , xnx,ci-1, y0,ci-1, y1,ci, . . . , xny,ci-1); and
(p) concatenating the appropriate bits of the x-coordinates x0,c, x1,c, . . . , xnx,c, the y-coordinates y1,c, . . . , ynx,c and a sign bit of y0,c of the hash point (x0,cu, x1,cu, . . . , xnx,cu, y0,cu, y1,cu, . . . , yny,cu), and the appropriate bits of the x-coordinates x0,Tc, x1,Tc, . . . , xnx,Tc, the y-coordinates y1,Tc, . . . , yny,Tc and a sign bit of y0,Tc of the hash point (x0,Tcu, x1,Tcu, . . . , xnx,Tcu, √{square root over ( αy0,Tcu, y1,Tcu, . . . , yny,Tcu) to form the hash bit string.

### Claim 2 (depends on 1)

The method of generating cryptographic hash functions as recited in claim 1, wherein the maximum block size that can be embedded into the (nx+1) x-coordinates and the ny y-coordinates is (nx+ny+1)N bits.

### Claim 3 (depends on 2)

The method of generating cryptographic hash functions as recited in claim 2, wherein the number of (nx+ny+1)N bit blocks in the message bit string is (u+1).

### Claim 4 (depends on 3)

The method of generating cryptographic hash functions as recited in claim 3, wherein said step of embedding comprises the steps of:
a) establishing integers M and L, and dividing the message bit string into M-bit strings such that ((nx+ny+1)N−L)>M>(N−L);
b) dividing each M-bit string into (nx+ny+1) strings mx0, mx1, . . . , mxnx, my1, . . . , myny, wherein the length of the string mx0 is less than or equal to (N−L) bits, and the length of each of the remaining (nx+ny) strings mx1, . . . , mxnx, my1, . . . , myny are each less than or equal to N bits, wherein each one of the (nx+ny+1) bit strings has an equivalent value which is an element of the finite field F;
c) assigning the value of the bit strings of mx1, . . . , mxnx to x1, . . . , xnx;
d) assigning the value of the bit strings of my1, . . . , myny to y1, . . . , yny;
e) assigning the value of the bit string of mx0 to x0;
f) substituting the values of x0, x1, . . . , xnx and y1, . . . , yny in the selected elliptic polynomial equation with (nx+1) x-coordinates and (ny+1) y-coordinates to form a quadratic equation in y0 of the form y02+Ay0+B=0, wherein A and B are variables; and
g) if the quadratic equation in y0 has solutions y0,1, y0,2 where the solutions are elements of the finite field F, then assigning one of the solutions to y0, and the message point is given by (x0,m, x1,m, . . . , xnx,m, y0,m, y1,m, . . . , yny,m), otherwise, assigning one of the solutions √{square root over ( α y0,1 & √{square root over ( α y0,2 to y0, and the message point is given by (x0,m, x1,m, . . . , xnx,m, √{square root over ( αy0,m, y1,m, . . . , yny,m).

### Claim 5 (depends on 4)

The method of generating cryptographic hash functions as recited in claim 4, wherein the assignment of solutions in the method of embedding includes assignment of solutions using a predetermined public method.

### Claim 6 (depends on 5)

The method of generating cryptographic hash functions as recited in claim 5, wherein the step of embedding further includes the step of denoting the message point as (x0,m, x1,m, . . . , xnx,m, √{square root over (α)}y0,m, y1,m, . . . , yny,m), wherein the point is on the elliptic polynomial if αmi=1, and the point is on the twist if αmi= α.

### Claim 7

A method of generating cryptographic hash functions in an electronic communications system using elliptic polynomial cryptography, comprising the steps of:
a) generating a set of hash function parameters, including the steps of:
b) establishing an ((nx+1)+(ny+1))-dimensional Cartesian coordinates system having orthogonal coordinates x0, x1, . . . , xnx, y0, y1, . . . , yny defined over a finite field F, such that x0, x1, . . . , xnx, y0, y1, . . . , yny∈F, wherein nx and ny are integers establishing an integer number N, wherein the values of the elements of F can be represented in N-bits strings, an elliptic polynomial ECnx+ny+2 and a twist of the elliptic polynomial TECnx+ny+2;
c) specifying values of nx and ny, and a set of coefficients a1k, a2kl, a3k, c1lki, c2kl, c3kli, b1l, b2lk, b3lk, b4k, bc∈F, along with a base point on an elliptic polynomial (x0,B, x1,B, . . . , xnx,B, y0,B, y1,B, . . . , yny,B)∈ECxn+ny+2 and a base point on the twist of the elliptic polynomial (x0,TB, x1,TB, . . . , xnx,TB, √{square root over ( αy0,B, y1,TB, . . . , yny,TB)∈TECxn+ny+2;
(d) disclosing the values of nx and ny, the set of coefficients, the base point on the elliptic polynomial and the base point on the twist as public information;
(e) selecting a pair of random number scalars k1, k2 which are kept secret for a specific hash function to be used;
(f) computing the multiplication of the scalar k1 with a point (x0,B, x1,B, . . . , xnx,B, y0,B, y1,B, . . . , yny,B) to obtain a scalar multiplication such that (x0,Pu, x1,Pu, . . . , xnx,Pu, y0,Pu, y1,Pu, . . . , yny,Pu)=k1(x0,B, x1,B, . . . , xnx,B, y0,B, y1,B, . . . , yny,B);
(g) computing the multiplication of the scalar k2 with a point (x0,TB, x1,TB, . . . , xnx,TB, √{square root over ( αy0,B, y1,TB, . . . , yny,TB) to obtain a scalar multiplication such that (x0,TPu, x1,TPu, . . . , xnx,TPu, √{square root over ( αy0,TPu, y1,TPu, . . . , yny,TPu)=k1(x0,TB, x1,TB, . . . , xnx,TB, √{square root over ( αy0,B, y1,TB, . . . , yny,TB);
(h) disclosing the scalar multiplication points (x0,Pu, x1,Pu, . . . , xnx,Pu, y0,Pu, y1,Pu, . . . , yny,Pu) and (x0,TPu, x1,TPu, . . . , xnx,TPu, √{square root over ( αy0,TPu, y1,TPu, . . . , yny,TPu) as public information;
(i) generating a hash bit string of the message bit string, including:
(j) pre-processing the message bit string to obtain a bit string which is a multiple of (nx+ny+1)N-bit;
(k) computing an initial hash point (x0,S1, x1,S1, . . . , xnx,S1, y0,S1, y1,S1, . . . , xny,S1) on the elliptic polynomial by multiplying a scalar integer value km0 of the (nx+ny+1)N-bit string of an initial block of the message bit string with a point (x0,Pu, x1,Pu, . . . , xnx,Pu, y0,Pu, y1,Pu, . . . , yny,Pu) such that:
(x0,S1, x1,S1, . . . , xnx,S1, y0,S1, y1,S1, . . . , yny,S1)=km0(x0,Pu, x1,Pu, . . . , xnx,Pu, y0,Pu, y1,Pu, . . . , yny,Pu);
(l) computing an initial hash point (x0,TS1, x1,TS1, . . . , xnx,TS1, √{square root over ( αy0,TS1, y1,TS1, . . . , yny,TS1) on the twist of the elliptic polynomial by multiplying a scalar integer value km1 of the (nx+ny+1)N-bit string of the next block of the message bit string with a point (x0,TPu, x1,TPu, . . . , xnx,TPu, √{square root over ( αy0,TPu, y1,TPu, . . . , yny,TPu) such that:
(x0,TS1, x1,TS1, . . . , xnx,TS1, √{square root over ( αy0,TS1, y1,TS1, . . . , yny,TS1)=km1(x0,TPu, x1,TPu, . . . , xnx,TPu, √{square root over ( αy0,TPu, y1,TPu, . . . , yny,TPu);
m) initializing the hash points such that
(x0,c1, x1,c1, . . . , xnx,c1, y0,c1, y1,c1, . . . , yny,c1)=(x0,S1, x1,S1, . . . , xnx,S1, y0,S1, y1,S1, . . . , xny,S1),
and
(x0,Tc1, x1,Tc1, . . . , xnx,Tc1, √{square root over ( αy0,Tc1, y1,Tc1, . . . , yny,Tc1)=(x0,TSi, x1,TSi, . . . , xnx,TSi, √{square root over ( αy0,TSi, y1,TSi, . . . , xny,TSi)
n) establishing an integer value i with an initial value of i=2, and repeating the following steps o) through q) until all of the message data blocks are processed, and incrementing i at each step:
o) embedding a (nx+ny+1)N-bit string of the ith block of the message bit string into (nx+1) x-coordinates X0, x1, . . . , xnx and ny y-coordinates y1, . . . , yny of the elliptic message point (x0,mi, x1,mi, . . . , xnx,mi, √{square root over ( αmiy0,mi, y1,mi, . . . , yny,mi) using non-iterative embedding;
p) doubling the points (x0,Si, x1,Si, . . . , xnx,Si, y0,Si, y1,Si, . . . , xny,Si) and
(x0,TSi, x1,TSi, . . . , xnx,TSi, √{square root over ( αy0,TSi, y1,TSi, . . . , xny,TSi)=2(x0,TSi-1, x1,TSi-1, . . . , xnx,TSi-1, √{square root over ( αy0,TSi-1, y1,TSi-1, . . . , xny,TSi-1);
q) if the message point of the ith block is on the elliptic polynomial, then the hash points are computed using: (x0,ci, x1,ci, . . . , xnx,ci, y0,ci, y1,ci, . . . , yny,ci)=(x0,mi, x1,mi, . . . , xnx,mi, y0,mi, y1,mi, . . . , yny,mi)+(x0,Si, x1,Si, . . . , xnx,Si, y0,Si, y1,Si, . . . , xny,Si)+(x0,mi-1, x1,mi-1, . . . , xnx,mi-1, y0,mi-1, y1,mi-1, . . . , xny,mi-1)
and
(x0,Tci, x1,Tci, . . . , xnx,Tci, √{square root over ( αy0,Tci, y1,Tci, . . . , yny,Tci)=(x0,Tci-1, x1,Tci-1, . . . , xnx,Tci-1, √{square root over ( αy0,Tci-1, y1,Tci-1, . . . , xny,Tci-1),
otherwise, they are computed using:
(x0,Tci, x1,Tci, . . . , xnx,Tci, √{square root over ( αy0,Tci, y1,Tci, . . . , yny,Tci)=(x0,mi, x1,mi, . . . , xnx,mi, √{square root over ( αy0,mi, y1,mi, . . . , yny,mi)+(x0,TSi, x1,TSi, . . . , xnx,TSi, √{square root over ( αy0,TSi, y1,TSi, . . . , xny,TSi)+(x0,mi-1, x1,mi-1, . . . , xnx,mi-1, √{square root over ( αy0,mi-1, y1,mi-1, . . . , xny,mi-1)
and
(x0,ci, x1,ci, . . . , xnx,ci, y0,ci, y1,ci, . . . , yny,ci)=(x0,ci-1, x1,ci-1, . . . , xnx,ci-1, y0,ci-1, y1,ci, . . . , xny,ci-1)
and
r) concatenating the appropriate bits of the x-coordinates x0,c, x1,c, . . . , xnx,c, the y-coordinates y1,c, . . . , ynx,c and a sign bit of y0,c of the hash point (x0,cu, x1,cu, . . . , xnx,cu, y0,cu, y1,cu, . . . , yny,cu), and the appropriate bits of the x-coordinates x0,Tc, x1,Tc, . . . , xnx,Tc, the y-coordinates y1,Tc, . . . , yny,Tc and a sign bit of y0,Tc of the hash point (x0,Tcu, x1,Tcu, . . . , xnx,Tcu, √{square root over ( αy0,Tcu, y1,Tcu, . . . , yny,Tcu) to form the hash bit string.

### Claim 8 (depends on 7)

The method of generating cryptographic hash functions as recited in claim 7, wherein the maximum block size that can be embedded into the (nx+1) x-coordinates and the ny y-coordinates is (nx+ny+1)N bits.

### Claim 9 (depends on 8)

The method of generating cryptographic hash functions as recited in claim 8, wherein the number of (nx+ny+1)N bit blocks in the message bit string is (u+1).

### Claim 10 (depends on 9)

The method of generating cryptographic hash functions as recited in claim 9, wherein said step of embedding comprises the steps of:
a) establishing integers M and L, and dividing the message bit string into M-bit strings such that ((nx+ny+1)N−L)>M>(N−L);
b) dividing each M-bit string into (nx+ny+1) strings mx0, mx1, . . . , mxnx, my1, . . . , myny, wherein the length of the string mx0 is less than or equal to (N−L) bits, and the length of each of the remaining (nx+ny) strings mx1, . . . , mxnx, my1, . . . , myny are each less than or equal to N bits, wherein each one of the (nx+ny+1) bit strings has an equivalent value which is an element of the finite field F;
c) assigning the value of the bit strings of mx1, . . . , mxnx to x1, . . . , xnx;
d) assigning the value of the bit strings of my1, . . . , myny to y1, . . . , yny;
e) assigning the value of the bit string of mx0 to x0;
f) substituting the values of x0, x1, . . . , xnx and y1, . . . , yny in the selected elliptic polynomial equation with (nx+1) x-coordinates and (ny+1) y-coordinates to form a quadratic equation in y0 of the form y02+Ay0+B=0, wherein A and B are variables; and
g) if the quadratic equation in y0 has solutions y0,1, y0,2 where the solutions are elements of the finite field F, then assigning one of the solutions to y0, and the message point is given by (x0,m, x1,m, . . . , xnx,m, y0,m, y1,m, . . . , yny,m), otherwise, assigning one of the solutions √{square root over ( α y0,1 & √{square root over ( α y0,2 to y0, and the message point is given by (x0,m, x1,m, . . . , xnx,m, √{square root over ( αy0,m, y1,m, . . . , yny,m).

### Claim 11 (depends on 10)

The method of generating cryptographic hash functions as recited in claim 10, wherein the assignment of solutions in the method of embedding includes assignment of solutions using a predetermined public method.

### Claim 12 (depends on 11)

The method of generating cryptographic hash functions as recited in claim 11, wherein the step of embedding further includes the step of denoting the message point as (x0,m, x1,m, . . . , xnx,m, √{square root over (α)}y0,m, y1,m, . . . , yny,m), wherein the point is on the elliptic polynomial if αmi=1, and the point is on the twist if αmi= α.

### Claim 13

A method of generating cryptographic hash functions using elliptic polynomial cryptography in an electronic communication system, comprising the steps of:
a) generating a set of hash function parameters, comprising the steps of:
b) establishing an ((nx+1)+(ny+1))-dimensional Cartesian coordinates system having orthogonal coordinates x0, x1, . . . , xnx, y0, y1, . . . , yny defined over a finite field F, such that x0, x1, . . . , xnx, y0, y1, . . . , yny∈F, wherein nx and ny are integers establishing an integer number N, wherein the values of the elements of F can be represented in N-bits strings, an elliptic polynomial ECnx+ny+2 and a twist of the elliptic polynomial TECnx+ny+2;
c) specifying values of nx and ny, and a set of coefficients a1k, a2kl, a3k, c1lki, c2kl, c3kli, b1l, b2lk, b3lk, b4k, bc∈F, along with a base point on an elliptic polynomial (x0,B, x1,B, . . . , xnx,B, y0,B, y1,B, . . . , yny,B)∈ECxn+ny+2 and a base point on the twist of the elliptic polynomial (x0,TB, x1,TB, . . . , xnx,TB, √{square root over ( αy0,B, y1,TB, . . . , yny,TB)∈TECxn+ny+2;
(d) disclosing the values of nx and ny, the set of coefficients, the base point on the elliptic polynomial and the base point on the twist as public information;
(e) selecting a pair of random number scalars k1, k2 which are kept secret for a specific hash function to be used;
(f) computing the multiplication of the scalar k1 with a point (x0,B, x1,B, . . . , xnx,B, y0,B, y1,B, . . . , yny,B) to obtain a scalar multiplication such that:
(x0,Pu, x1,Pu, . . . , xnx,Pu, y0,Pu, y1,Pu, . . . , yny,Pu)=k1(x0,B, x1,B, . . . , xnx,B, y0,B, y1,B, . . . , yny,B);
(g) computing the multiplication of the scalar k2 with a point (x0,TB, x1,TB, . . . , xnx,TB, √{square root over ( αy0,B, y1,TB, . . . , yny,TB) to obtain a scalar multiplication such that (x0,TPu, x1,TPu, . . . , xnx,TPu, √{square root over ( αy0,TPu, y1,TPu, . . . , yny,TPu)=k1(x0,TB, x1,TB, . . . , xnx,TB, √{square root over ( αy0,B, y1,TB, . . . , yny,TB);
(h) disclosing the scalar multiplication points (x0,Pu, x1,Pu, . . . , xnx,Pu, y0,Pu, y1,Pu, . . . , yny,Pu) and (x0,TPu, x1,TPu, . . . , xnx,TPu, √{square root over ( αy0,TPu, y1,TPu, . . . , yny,TPu) as public information;
i) establishing an integer i and a parameter Smi to represent the (nx+ny+1)N-bit string of the ith message block, and selecting an initial vector SM1 to be made public;
j) generating a hash bit string of the message bit string, comprising the following steps:
k) pre-processing the message bit string to obtain a bit string which is a multiple of (nx+ny+1)N-bits;
l) computing a point (x0,S1, x1,S1, . . . , xnx,S1, y0,S1, y1,S1, . . . , xny,S1) on the elliptic polynomial by multiplying a scalar integer value km0 of the (nx+ny+1)N-bit string of an initial block of the message bit string with a point (x0,Pu, x1,Pu, . . . , xnx,Pu, y0,Pu, y1,Pu, . . . , yny,Pu) such that (x0,S 1, x1,S1, . . . , xnx,S1, y0,S1, y1,S1, . . . , yny,S1)=km0(x0,Pu, x1,Pu, . . . , xnx,Pu, y0,Pu, y1,Pu, . . . , yny,Pu);
m) computing a point an initial hash point (x0,TS1, x1,TS1, . . . , xnx,TS1, √{square root over ( αy0,TS1, y1,TS1, . . . , yny,TS1) on the twist of the elliptic polynomial by multiplying a scalar integer value km1 of the (nx+ny+1)N-bit string of the next block of the message with a point (x0,TPu, x1,TPu, . . . , xnx,TPu, √{square root over ( αy0,TPu, y1,TPu, . . . , yny,TPu) such that (x0,TS1, x1,TS1, . . . , xnx,TS1, √{square root over ( αy0,TS1, y1,TS1, . . . , yny,TS1)=km1(x0,TPu, x1,TPu, . . . , xnx,TPu, √{square root over ( αy0,TPu, y1,TPu, . . . , yny,TPu);
n) initializing the hash points as
(x0,c1, x1,c1, . . . , xnx,c1, y0,c1, y1,c1, . . . , yny,c1)=+(x0,S1, x1,S1, . . . , xnx,S1, y0,S1, y1,S1, . . . , xny,S1),
and
(x0,Tc1, x1,Tc1, . . . , xnx,Tc1, √{square root over ( αy0,Tc1, y1,Tc1, . . . , yny,Tc1)=(x0,TS1, x1,TS1, . . . , xnx,TS1, √{square root over ( αy0,TS1, y1,TS1, . . . , yny,TS1);
o) establishing an integer value i and initializing the integer i as i=2, and repeating the following steps p) through s) until all of the message data blocks are processed, and incrementing fat each step:
p) computing the (nx+ny+1)N-bit string Smi′ as Smi′=Smi⊕Smi-1;
q) embedding a (nx+ny+1)N-bit string Smi′ of the ith block of the message bit string into (nx+1) x-coordinates X0, x1, . . . , xnx and ny y-coordinates y1, . . . , yny of the elliptic message point (x0,mi, x1,mi, . . . , xnx,mi, √{square root over (αmi)}y0,mi, y1,mi, . . . , yny,mi) using non-iterative embedding;
r) doubling the points (x0,Si, x1,Si, . . . , xnx,Si, y0,Si, y1,Si, . . . , xny,Si) and (x0,TSi, x1,TSi, . . . , xnx,TSi, √{square root over ( αy0,TSi, y1,TSi, . . . , xny,TSi), such that:
(x0,Si, x1,Si, . . . , xnx,Si, y0,Si, y1,Si, . . . , xny,Si)=2(x0,Si-1, x1,Si-1, . . . , xnx,Si-1, y0,Si-1, y1,Si-1, . . . , xny,Si-1)
and
(x0,TSi, x1,TSi, . . . , xnx,TSi, √{square root over ( αy0,TSi, y1,TSi, . . . , xny,TSi)=2(x0,TSi-1, x1,TSi-1, . . . , xnx,TSi-1, √{square root over ( αy0,TSi-1, y1,TSi-1, . . . , xny,TSi-1);
s) if the message point of the ith block is on the elliptic polynomial, then the hash points are computed using:
(x0,ci, x1,ci, . . . , xnx,ci, y0,ci, y1,ci, . . . , yny,ci)=(x0,mi, x1,mi, . . . , xnx,mi, y0,mi, y1,mi, . . . , yny,mi)+(x0,Si, x1,Si, . . . , xnx,Si, y0,Si, y1,Si, . . . , xny,Si)+(x0,mi-1, x1,mi-1, . . . , xnx,mi-1, y0,mi-1, y1,mi-1, . . . , xny,mi-1)
and
(x0,Tci, x1,Tci, . . . , xnx,Tci, √{square root over ( αy0,Tci, y1,Tci, . . . , yny,Tci)=(x0,Tci-1, x1,Tci-1, . . . , xnx,Tci-1, √{square root over ( αy0,Tci-1, y1,Tci-1, . . . , xny,Tci-1), otherwise, they are computed using:
(x0,Tci, x1,Tci, . . . , xnx,Tci, √{square root over ( αy0,Tci, y1,Tci, . . . , yny,Tci)=(x0,mi, x1,mi, . . . , xnx,mi, √{square root over ( αy0,mi, y1,mi, . . . , yny,mi)+(x0,TSi, x1,TSi, . . . , xnx,TSi, √{square root over ( αy0,TSi, y1,TSi, . . . , xny,TSi)+(x0,mi-1, x1,mi-1, . . . , xnx,mi-1, √{square root over ( αy0,mi-1, y1,mi-1, . . . , √yny,mi-1)
and
(x0,ci, x1,ci, . . . , xnx,ci, y0,ci, y1,ci, . . . , yny,ci)=(x0,ci-1, x1,ci-1, . . . , xnx,ci-1, y0,ci-1, y1,ci, . . . , xny,ci-1);
and
t) concatenating the appropriate bits of the x-coordinates x0,c, x1,c, . . . , xnx,c, the y-coordinates y1,c, . . . , ynx,c and a sign bit of y0,c of the hash point (x0,cu, x1,cu, . . . , xnx,cu, y0,cu, y1,cu, . . . , yny,cu), and the appropriate bits of the x-coordinates x0,Tc, x1,Tc, . . . , xnx,Tc, the y-coordinates y1,Tc, . . . , yny,Tc and a sign bit of y0,Tc of the hash point (x0,Tcu, x1,Tcu, . . . , xnx,Tcu, √{square root over ( αy0,Tcu, y1,Tcu, . . . , yny,Tcu) to form the hash bit string.

### Claim 14 (depends on 13)

The method of generating cryptographic hash functions as recited in claim 13, wherein the maximum block size that can be embedded into the (nx+1) x-coordinates and the ny y-coordinates is (nx+ny+1)N bits.

### Claim 15 (depends on 14)

The method of generating cryptographic hash functions as recited in claim 14, wherein the number of (nx+ny+1)N bit blocks in the message bit string is (u+1).

### Claim 16 (depends on 15)

The method of generating cryptographic hash functions as recited in claim 15, wherein said step of embedding comprises the steps of:
a) establishing integers M and L, and dividing the message bit string into M-bit strings such that ((nx+ny+1)N−L)>M>(N−L);
b) dividing each M-bit string into (nx+ny+1) strings mx0, mx1, . . . , mxnx, my1, . . . , myny, wherein the length of the string mx0 is less than or equal to (N−L) bits, and the length of each of the remaining (nx+ny) strings mx1, . . . , mxnx, my1, . . . , myny are each less than or equal to N bits, wherein each one of the (nx+ny+1) bit strings has an equivalent value which is an element of the finite field F;
c) assigning the value of the bit strings of mx1, . . . , mxnx to x1, . . . , xnx;
d) assigning the value of the bit strings of my1, . . . , myny to y1, . . . , yny;
e) assigning the value of the bit string of mx0 to x0;
f) substituting the values of x0, x1, . . . , xnx and y1, . . . , yny in the selected elliptic polynomial equation with (nx+1) x-coordinates and (ny+1) y-coordinates to form a quadratic equation in y0 of the form y02+Ay0+B=0, wherein A and B are variables; and
g) if the quadratic equation in y0 has solutions y0,1, y0,2 where the solutions are elements of the finite field F, then assigning one of the solutions to y0, and the message point is given by (x0,m, x1,m, . . . , xnx,m, y0,m, y1,m, . . . , yny,m), otherwise, assigning one of the solutions √{square root over ( α y0,1 & √{square root over ( α y0,2 to y0, and the message point is given by (x0,m, x1,m, . . . , xnx,m, √{square root over ( αy0,m, y1,m, . . . , yny,m).

### Claim 17 (depends on 16)

The method of generating cryptographic hash functions as recited in claim 16, wherein the assignment of solutions in the method of embedding includes assignment of solutions at random.

### Claim 18 (depends on 17)

The method of generating cryptographic hash functions as recited in claim 17, wherein the step of embedding further includes the step of denoting the message point as (x0,m, x1,m, . . . , xnx,m, √{square root over (α)}y0,m, y1,m, . . . , yny,m), wherein the point is on the elliptic polynomial if αmi=1, and the point is on the twist if αmi= α.