US 2010/0166174 A1Published application

Hash functions using elliptic curve cryptography

AssigneeKing Fahd University of Petroleum and Minerals

InventorsLahouari Ghouti, Mahammad K. Ibrahim, Atef J. Al-Najjar

Life of this patent

Estimating the term…

Loading patent…

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.

Claims12

Dependent claims

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.

15 more elements

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.

17 more elements

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.

17 more elements

Dependencies are inferred from the claim text.

Facts

Application: 12/318,406Filed 29 Dec 2008
Published: 1 Jul 2010
Term ends: Not estimatedThe source records don’t support an estimate.

Classification5 codes

H04L 9/3066
Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy: involving…
H04L 9/0643
The encryption apparatus using shift registers or memories for block-wise or stream coding, e.g. DES systems or RC4; Hash functions;…
H04L 9/50
Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols: using hash chains, e.g.…
H04L 2209/30
Additional information or applications relating to cryptographic mechanisms or cryptographic arrangements for secret or secure communication…

Family

US 8,184,803 B2Related patent
US 2010/0166174 A1This patent

From the US filing history. Foreign family members aren’t listed.

Timeline

Citations

Open elsewhere

Building an agent or pulling many patents? Use the API or MCP server instead of scraping pages. Get an API key