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

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.

Cryptographic hash functions using elliptic polynomial cryptography

Life of this patent

Cryptographic hash functions using elliptic polynomial cryptography

Life of this patent

Abstract

Claims18