# US 2010/0166174 A1 · Hash functions using elliptic curve cryptography

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

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

## 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/50: {using hash chains, e.g. blockchains or hash trees}
- H04L 2209/30: Compression, e.g. Merkle-Damgard construction
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

The hash functions using elliptic curve cryptography are hash functions that are produced using both an elliptic curve and a twist of the elliptic curve. Hash points are assigned values that either correspond to points on the elliptic curve or to points on the twist, depending upon whether the scalar value of the corresponding message block produces a quadratic residue or a quadratic non-residue when substituted as the x-value into the elliptic curve equation. The corresponding hash point x-coordinates are concatenated to form the hash bit string. The hash points may be doubled, and the hash functions may be applied to multimedia data by applying a media compression method to the message data before computing the hash points.

## Claims

### Claim 1

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 Fare represented by (N+1) bits, and wherein N is a selected natural number;
(b) establishing an elliptic curve EC that satisfies y2=x3+ax+b, wherein x and y are Cartesian coordinates;
(c) establishing a twist TEC of the elliptic curve EC that satisfies αy2=x3+ax+b, wherein α is non-quadratic residue of the finite field F;
(d) specifying a base point on the elliptic curve (xB,yB)∈EC and a base point on the twist of the elliptic curve (xTB,√{square root over ( α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 k1,k2, 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 k1 with the base point (xB,yB) to produce the scalar multiplication (xPu,yPu)=k1(xB,yB);
(f) computing a multiplication of the random number k2 with the base point (xTB,√{square root over ( αTB) to produce the scalar multiplication (xTPu,√{square root over ( αTPu)=k2(xTB,√{square root over ( αTB);
(g) establishing (xPu,yPu) and (xTPu,√{square root over ( α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 (xc1,yc1) on the elliptic curve;
(j) computing an initial hash point (xTc1,√{square root over ( αTc1) on the twist of the elliptic curve;
(k) establishing an integer i representing an ith message data block and setting i=2;
(l) embedding a message N bit string of an ith block into the x-coordinate of the elliptic message point (xmi,√{square root over (αmi)}ymi) using non-iterative embedding;
(m) computing the set of hash points as (xci,yci)=(xmi,ymi)+(xci−1,yci−1) and (xTci,√{square root over ( αTci)=(xTci−1,√{square root over ( αTci−1) if αmi=1, and otherwise computing the set of hash points as (xTci,√{square root over ( αTci)=(xmi,√{square root over ( αmi)+(xTci−1,√{square root over ( αTci−1) and (xci,yci)=(xci−1,yci−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 xc, and the sign bit of the y-coordinate yc of a hash point (xcu,ycu), along with the bits of the x-coordinates xTc and the sign bit of the y-coordinate yTc of a hash point (xTcu,√{square root over ( αTcu) to form a hash bit string.

### Claim 2 (depends on 1)

The method of generating hash functions using elliptic curves for cryptography as recited in claim 1, wherein step (i) includes multiplication of a scalar integer value km0 of the N bit string of an initial block of a message with the point (xPu,yPu), such that (xc1, yc1)=km0(xPu,yPu).

### Claim 3 (depends on 2)

The method of generating hash functions using elliptic curves for cryptography as recited in claim 2, wherein step (j) includes multiplication of a scalar integer value km1 of the N bit string of the next block of the message with the point (xTPu,√{square root over ( αTPu) such that (xTc1,√{square root over ( αTc1)=km1(xTPu,√{square root over ( αTPu).

### Claim 4 (depends on 1)

The method of generating hash functions using elliptic curves for cryptography as recited in claim 1, wherein the step of non-iterative embedding comprises the steps of:
dividing the message bit string into N bit strings and establishing mi as the ith block;
assigning the value of the bit string of mi to xmi;
substituting the values of xmi and computing a value tmi as tmi=xmi3+axmi+b, wherein if tmi is quadratic residue such that ymi=√{square root over (tmi)} then a temporary message point (xmi,ymi) is established, and if tmi is non-quadratic residue such that
y
m
i
=
t
m
i
α
_
then the temporary message point is established as (xmi,√{square root over ( αmi); and
establishing a message point (xmi,√{square root over (αmi)}ymi), wherein the message point is on the elliptic curve if αmi=1, and the message point is on the twist of the elliptic curve if αmi= α.

### Claim 5

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 Fare represented by (N+1) bits, and wherein N is a selected natural number;
(b) establishing an elliptic curve EC that satisfies y2=x3+ax+b, wherein x and y are Cartesian coordinates;
(c) establishing a twist TEC of the elliptic curve EC that satisfies αy2=+x3+ax+b, wherein α is non-quadratic residue of the finite field F;
(d) specifying a base point on the elliptic curve (XB,yB)∈EC and a base point on the twist of the elliptic curve (xTB,√{square root over ( α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 k1,k2, 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 k1 with the base point (xB,yB) to produce the scalar multiplication (xPu,yPu)=k1(xB,yB);
(f) computing a multiplication of the random number k2 with the base point (xTB,√{square root over ( αTB) to produce the scalar multiplication (xTPu,√{square root over ( αTPu)=k2(xTB,√{square root over ( αTB);
(g) establishing (xPu,yPu) and (xTPu,√{square root over ( αTPu) as public information;
(h) processing a message bit string to produce a bit string that is a multiple of N bits, wherein N is a selected natural number;
(i) computing a temporary initial hash point (xS1,yS1) on the elliptic curve;
(j) computing a temporary initial hash point (xTS1,√{square root over ( αTS1) on the twist of the elliptic curve;
(k) initializing a set of initial hash points (xc1, yc1) and (xTc1,√{square root over ( αTc1) such that (xc1,yc1)=(xS1,yS1) and (xTc1,√{square root over ( αTc1)=(xTS1,√{square root over ( αTS1);
(l) establishing an integer i representing an ith message data block and setting i=2;
(m) embedding a message N bit string of an ith block into the x-coordinate of the elliptic message point (xmi,√{square root over (αmi)}ymi) using non-iterative embedding;
(n) doubling the points (xSi,ySi) and (xTSi,yTSi), such that (xSi,ySi)=2(xSi−1,ySi−1) and (xTsi,yTSi)=2(xTSi−1,√{square root over ( αTSi−1);
(o) computing the set of hash points as (xci,yci)=(xmi,ymi)+(xmi−1, ymi−1)+(xSi,ySi) and (xTci,√{square root over ( αTci)=(xTci−1,√{square root over ( αTci−1) if αmi=1, and otherwise computing the set of hash points as (xTci,√{square root over ( αTci)=(xmi,√{square root over ( αmi)+(xmi−1,√{square root over ( αmi−1)+(xTSi,√{square root over ( αTSi) and (xci,yci)=(xci−1,yci−1);
(p) repeating steps (m) through (o) until the message data blocks are processed and incrementing i at each said step; and
(q) concatenating bits of the x-coordinate xc and the sign bit of the y-coordinate yc of a hash point (xcu,ycu, along with the bits of the x-coordinates xTc and the sign bit of the y-coordinate yTc of a hash point (xTcu,√{square root over ( αTcu) to form a hash bit string.

### Claim 6 (depends on 5)

The method of generating hash functions using elliptic curves for cryptography as recited in claim 5, wherein step (i) includes multiplication of a scalar integer value km0 of the N bit string of an initial block of a message with the point (xPu,yPu), such that (xS1,yS1)=km0(xPu,yPu).

### Claim 7 (depends on 6)

The method of generating hash functions using elliptic curves for cryptography as recited in claim 6, wherein step (j) includes multiplication of a scalar integer value km1 of the N bit string of the next block of the message with the point (xTPu,√{square root over ( αTPu), such that (xTS1,√{square root over ( αTS1)=km1(xTPu,√{square root over ( αTPu).

### Claim 8 (depends on 5)

The method of generating hash functions using elliptic curves for cryptography as recited in claim 5, wherein the step of non-iterative embedding comprises the steps of:
dividing the message bit string into N bit strings and establishing mi as the ith block;
assigning the value of the bit string of mi to xmi;
substituting the values of xmi and computing a value tmi as tmi+xmi3+axmi+b, wherein if tmi is quadratic residue such that ymi=√{square root over (tmi)} then a temporary message point (xmi,ymi) is established, and if tmi is non-quadratic residue such that
y
m
i
=
t
m
i
α
_
then the temporary message point is established as (xmi,√{square root over ( αmi); and
establishing a message point (xmi,√{square root over (αmi)}ymi), wherein the message point is on the elliptic curve if αmi=1, and the message point is on the twist of the elliptic curve if αmi= α.

### Claim 9

A method of generating hash functions using elliptic curves for cryptography, comprising the steps of:
(a) specifying a set of coefficients a,b∈F and selecting an initial vector Sm1, 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 y2=x3+ax+b, wherein x and y are Cartesian coordinates;
(c) establishing a twist TEC of the elliptic curve EC that satisfies αy2=x3ax+b, wherein α is non-quadratic residue of the finite field F;
(d) specifying a base point on the elliptic curve (xB,yB)∈EC and a base point on the twist of the elliptic curve (xTB,√{square root over ( αTB)∈TEC;
(c) establishing the set of coefficients, the base point on the elliptic curve, the base point on the twist of the elliptic curve, and the initial vector Sm1 as public information;
(d) selecting a pair of random numbers k1,k2, 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 k1 with the base point (xB,yB) to produce the scalar multiplication (xPu,yPu)=k1(xB,yB);
(f) computing a multiplication of the random number k2 with the base point (xTB,√{square root over ( αTB) to produce the scalar multiplication (xTPu,√{square root over ( αTPu)=k2(xTB,√{square root over ( αTB);
(g) establishing (xPu,yPu) and (xTPu,√{square root over ( αTPu) as public information;
(h) processing a message bit string to produce a bit string that is a multiple of N bits, wherein N is a selected natural number;
(i) computing a temporary initial hash point (xS1,yS1) on the elliptic curve;
(j) computing a temporary initial hash point (xTS1,√{square root over ( αTS1) on the twist of the elliptic curve;
(k) initializing a set of initial hash points (xc1,yc1) and (xTc1,√{square root over ( αT1) such that (xc1,yc1)=(xS1,yS1) and (xTc1,√{square root over ( αTc1)=(xTS1,√{square root over ( αTS1);
(l) establishing an integer i representing an ith message data block and setting i=2;
(m) computing an N-bit string Smi such that Smi′=Smi⊕Smi−1, wherein Smi′ is the N-bit string of the ith block of the message, and embedding a message N bit string of an ith block into the x-coordinate of the elliptic message point (xmi,√{square root over (αmi)}ymi) using non-iterative embedding;
(n) doubling the points (xSi,ySi) and (xTSi,yTSi), such that (xSi,ySi)=2(xSi−1,ySi−1) and (xTSi,yTSi)=2(xTSi−1,√{square root over ( αTSi−1);
(o) computing the set of hash points as (xci,yci)=(xmi,ymi)+(xmi−1,ymi−1)+(xSi,ySi) and (xTci,√{square root over ( αTci)=(xTci−1,√{square root over ( αTci−1) if αmi=1, and otherwise computing the set of hash points as (xTci,√{square root over ( αTci)=(xmi,√{square root over ( αmi)+(xmi−1,√{square root over ( αmi−1)+(xTSi,√{square root over ( αTSi) and (xci,yci)=(xci−1,yci−1);
(p) repeating steps (m) through (o) until the message data blocks are processed and incrementing i at each said step; and
(q) concatenating bits of the x-coordinate xc and the sign bit of the y-coordinate yc of a hash point (xcu,xcu) along with the bits of the x-coordinates xTc and the sign bit of the y-coordinate yTc of a hash point (xTcu,√{square root over ( αTcu) to form a hash bit string.

### Claim 10 (depends on 9)

The method of generating hash functions using elliptic curves for cryptography as recited in claim 9, wherein step (i) includes multiplication of a scalar integer value km0 of the N bit string of an initial block of a message with the point (xPu,yPu), such that (xS1,yS1)=km0(xPu,yPu).

### Claim 11 (depends on 10)

The method of generating hash functions using elliptic curves for cryptography as recited in claim 10, wherein step (j) includes multiplication of a scalar integer value km1 of the N bit string of the next block of the message with the point (xTPu,√{square root over ( αTPu), such that (xTS1,√{square root over ( αTS1)=km1(xTPu,√{square root over ( αTPu).

### Claim 12 (depends on 9)

The method of generating hash functions using elliptic curves for cryptography as recited in claim 9, wherein the step of non-iterative embedding comprises the steps of:
dividing the message bit string into N bit strings and establishing mi as the ith block;
assigning the value of the bit string of mi to xmi;
substituting the values of xmi and computing a value tmi as tmi=xm13+axm1+b, wherein if tmi is quadratic residue such that ymi=√{square root over (tmi)} then a temporary message point (xmi,ymi) is established, and if tmi is non-quadratic residue such that
y
m
i
=
t
m
i
α
_
then the temporary message point is established as (xmi,√{square root over ( αmi); and
establishing a message point (xmi,√{square root over (αmi)}ymi), wherein the message point is on the elliptic curve if αmi=1, and the message point is on the twist of the elliptic curve if αmi= α.