US 2010/0166176 A1 · Elliptical polynomial-based message authentication code

Abstract

The elliptic-polynomial based Message Authentication Code (MAC) provides MAC generation methods based on the elliptic polynomial discrete logarithm problem. It is well known that an elliptic polynomial discrete logarithm problem is a computationally “difficult” or “hard” problem. The methods use both an elliptic polynomial polynomial and its twist, even if the polynomial and its twist are not isomorphic. Since both the polynomial and its twist are used, multiple x- and y-coordinates can be used to embed bit strings into a point that satisfies the elliptic polynomial, and the embedding process is non-iterative, so that the time required to embed the bit string is independent of the bit string content.

A computerized method of generating an elliptic polynomial-based message authentication code, comprising the steps of:

a) defining a maximum block size that can be embedded into (nx+1) x-coordinates and ny y-coordinates, wherein n is an integer, and setting the maximum block size to be (nx+ny+1)N bits, wherein N is an integer;
b) a sending correspondent and a receiving correspondent agree upon the values of nx and ny, and further agree on a set of coefficients a1k, a2kl, a3k, c1lki, C2kl, c3kli, b1l, b2lk, b3lk, b4k & bcεF, wherein F represents a finite field where the field's elements can be represented in N-bits, the sending and receiving correspondents further agreeing on a random number k that represents a shared secret key for communication, the sending and receiving correspondents further agreeing on a base point on an elliptic polynomial (x0,B,x1,B, . . . , xnx,B,y0,B,y1,B, . . . , yny,B)εECxn+ny+2, wherein ECxn+ny+2 represents the 14 elliptic polynomial, and further agreeing on 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)εECxn+ny+2, wherein TECxn+ny+2 represents the twist of the elliptic polynomial ECxn+ny+2, and further, α is a non-quadratic residue element of F;
the sending correspondent then performs the following steps:
c) embedding the bit string of the secret key into the (nx+1) x-coordinates x0,x1, . . . , xnx, and the ny y-coordinates y1, . . . , yny, of a key elliptic point (x0,k,x1,k, . . . , xnx,k,√{square root over (αk)}y0,k,y1,, . . . , yny,k) using a non-iterative embedding method;
d) if (x0,k,x1,k, . . . , xnx,k,√{square root over (αk)}y0,k,y1,, . . . , yny,k) is on the elliptic polynomial, a scalar multiplication is computed as:
(x0,TS0,x1,TS0, . . . , xnx,TS0,√{square root over ( αy0,TS0,y1,TS0, . . . , xny,TS0)=(x0,TB,x1,, . . . , xnx,TB,√{square root over ( αy0,TB,y1,TB, . . . , yny,TB) and
(x0,S0,x1,S0, . . . , xnx,S0,y0,S0,y1,S0, . . . , xny,S0)=(x0,k,x1,k, . . . , xnx,k,y0,k,y1,k, . . . , yny,k),
otherwise, if αk= α, then the scalar multiplication is computed as:
(x0,S0,x1,S0, . . . , xnx,S0,y0,S0,y1,S0, . . . , xny,S0)=k(x0,B,x1,B, . . . , xnx,B,y0,B,y1,B, . . . , yny,B) and
(x0,TS0,x1,TS0, . . . , xnx,TS0,√{square root over ( αy0,TS0,y1,TS0, . . . , xny,TS0)=(x0,k,x1,k, . . . , xnx,k,√{square root over ( αy0,k,y1,k, . . . , yny,k);
e) dividing the message bit string into M-bit strings where ((nx+ny+1)N−L)>M>(N−L), where M and L are integers, and embedding the message bit string of the initial block of the message bit string into the (nx+1) x-coordinates and the ny y-coordinates of the elliptic message point (x0,m0,x1,m0, . . . , xnx,m0,√{square root over (αm0)}y0,m0,y1,m0, . . . , yny,m0) using the non-iterative embedding method;
f) if the message point of the 0-th block is on the elliptic polynomial, then the message authentication code points are computed as
(x0,c0,x1,c0, . . . , xnx,c0,√{square root over ( αy0,c0,y1,c0, . . . , yny,c0)=(x0,m0,x1,m0, . . . , xnx,m0,√{square root over ( αy0,m0,y1,m0, . . . , yny,m0)+(x0,S0,x1,S0, . . . , xnx,S0,√{square root over ( αy0,S0,y1,S0, . . . , xny,S0)
and (x0,Tc0,x1,Tc0, . . . , xnx,Tc0,√{square root over ( αy0,Tc0,y1,Tc0, . . . , yny,Tc0)=(x0,TS0,x1,TS0, . . . , xnx,TS0,√{square root over ( αy0,TS0,y1,TS0, . . . , xny,TS0), otherwise, they are computed as:
(x0,Tc0,x1,Tc0, . . . , xnx,Tc0,y0,Tc0,y1,Tc0, . . . , yny,Tc0)=(x0,m0,x1,m0, . . . , xnx,m0,y0,m0,y1,m0, . . . , yny,m0)+(x0,TS0,x1,TS0, . . . , xnx,TS0,y0,TS0,y1,TS0, . . . , xny,TS0)
(x0,c0,x1,c0, . . . , xnx,c0,y0,c0,y1,c0, . . . , yny,c0)=(x0,S0,x1,S0, . . . , xnx,S0,y0,S0,y1,S0, . . . , xny,S0);
g) initializing an integer i as i=1, and repeating the following steps h) and i) and incrementing i at each step until all of the message data blocks are processed:
h) embedding the message (nx+ny+1)N-bit string of an i-th block into the (nx+1) x-coordinates x0,x1, . . . , xnx and the 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 the non-iterative embedding method;
i) if the message point of the i-th block is on the elliptic polynomial, then the message authentication code points are computed 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,Tci-1,x1,Tci-1, . . . , xnx,Tci-1,√{square root over ( αy0,Tci-1,y1,Tci-1, . . . , xny,Tci-1), otherwise, they are computed as:
(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,Tci-1,x1,Tci-1, . . . , xnx,Tci-1,√{square root over ( αy0,Tci-1,y1,Tci-1, . . . , xny,Tci-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);
j) a set of appropriate bits of the x-coordinates x0,c,x1,c, . . . , xnx,c, y-coordinates y1,c, . . . , yny,c and a sign bit of y0,c of the message authentication code point (x0,cu,x1,cu, . . . , xnx,cu,y0,cu,y1,cu, . . . , yny,cu) and a set of appropriate bits of the x-coordinates x0,Tc,x1,Tc, . . . , xnx,Tc, y-coordinates y1,Tc, . . . , yny,Tc and the sign bit of y0,Tc of the message authentication code point (x0,Tcu,x1,Tcu, . . . , xnx,Tcu,√{square root over ( αy0,Tcu,y1,Tcu, . . . , yny,Tcu) are concatenated together to form the message authentication code, which is then appended to the message to be sent together with, if necessary, any additional information needed to help authenticate the message bit string at the receiving correspondent without compromising security and sent to the receiving correspondent;
the receiving correspondent then performs the following steps:
k) embedding the bit string of the secret key into the (nx+1) x-coordinates x0,x1, . . . , xnx, and the ny y-coordinates y1, . . . , yny, of the key elliptic point (x0,k,x1,k, . . . , xnx,k,√{square root over (αk)}y0,k,y1,k, . . . , yny,k) using the non-iterative embedding method;
l) if the point (x0,k,x1,k, . . . , xnx,k,√{square root over (αk)}y0,k,y1,k, . . . , yny,k) is on the elliptic polynomial, then a scalar multiplication is performed as (x0,TS0,x1,TS0, . . . , xnx,TS0,√{square root over ( αy0,TS0,y1,TS0, . . . , xny,TS0)=k(x0,TB,x1,TB, . . . , xnx,TB,√{square root over ( αy0,TB,y1,TB, . . . , yny,TB) and (x0,S0,x1,S0, . . . , xnx,S0,y0,S0,y1,S0, . . . , xny,S0)=(x0,k,x1,k, . . . , xnx,k,y0,k,y1,k, . . . , yny,k) otherwise i if αk=αo then the scalar multiplication is performed as (x0,S0,x1,S0, . . . , xnx,S0,y0,S0,y1,S0, . . . , xny,S0)=k(x0,B,x1,B, . . . , xnx,B,y0,B,y1,B, . . . , yny,B) and (x0,TS0,x1,TS0, . . . , xnx,TS0,√{square root over ( αy0,TS0,y1,TS0, . . . , xny,TS0)=(x0,k,x1,k, . . . , xnx,k,√{square root over (αk)}y0,k,y1,k, . . . , yny,k);
m) dividing the received message bit string into M-bit strings where ((nx+ny+1)N−L)>M>(N−L), where M and L are integers, and embedding the received message (nx+ny+1)N-bit string of the initial block of the received message bit string into the (nx+1) x-coordinates and the ny y-coordinates of the received message elliptic point (x0,rm0,x1,rm0, . . . , xnx,rm0,√{square root over (αrm0)}y0,rm0,y1,rm0, . . . , yny,rm0) using the non-iterative embedding method;
n) if the message point of the initial block is on the elliptic polynomial, then the message authentication points are computed as:
(x0,rc0,x1,rc0, . . . , xnx,rc0,y0,rc0,y1,rc0, . . . , yny,rc0)=(x0,rm0,x1,rm0, . . . , xnx,rm0,y0,rm0,y1,rm0, . . . , yny,rm0)+(x0,S0,x1,S0, . . . , xnx,S0,y0,S0,y1,S0, . . . , xny,S0) and
(x0,rTc0,x1,rTc0, . . . , xnx,rTc0,√{square root over ( αy0,rTc0,y1,rTc0, . . . , yny,rTc0)=(x0,TS0,x1,TS0, . . . , xnx,TS0,√{square root over ( αy0,TS0,y1,TS0, . . . , xny,TS0), otherwise, they are computed as:
(x0,rTc0,x1,rTc0, . . . , xnx,rTc0,√{square root over ( αy0,rTc0,y1,rTc0, . . . , yny,rTc0)=(x0,rm0,x1,rm0, . . . , xnx,rm0,√{square root over ( αy0,rm0,y1,rm0, . . . , yny,rm0)+(x0,rTS0,x1,rTS0, . . . , xnx,rTS0,√{square root over ( αy0,rTS0,y1,rTS0, . . . , xny,rTS0) and
(x0,rc0,x1,rc0, . . . , xnx,rc0,y0,rc0,y1,rc0, . . . , yny,rc0)=(x0,S0,x1,S0, . . . , xnx,S0,y0,S0,y1,S0, . . . , xny,S0);
o) initializing the integer i as i=0, and repeating the following steps p) and q) and incrementing i at each step until all of the message data blocks are processed:
p) embedding the received message (nx+ny+1)N-bit string of the i-th block the into the (nx+1) x-coordinates x0,x1, . . . , xnx, and the ny y-coordinates y1, . . . , yny) of the received message elliptic point (x0,rmi,x1,rmi, . . . , xnx,rmi,√{square root over (αrmi)}y0,rmi,y1,rmi, . . . , yny,rmi) using the non-iterative embedding method;
q) if the received message point of the i-th block is on the elliptic polynomial, then the message authentication points are computed as:
(x0,rci,x1,rci, . . . , xnx,rci,y0,rci,y1,rci, . . . , yny,rci)=(x0,rmi,x1,rmi, . . . , xnx,rmi,y0,rmi,y1,rmi, . . . , yny,rmi)+(x0,rci-1,x1,rci-1, . . . , xnx,rci-1,y0,rci-1,y1,rci-1, . . . , xny,rci-1)
and
(x0,rTci,x1,rTci, . . . , xnx,rTci,√{square root over ( αy0,rTci,y1,rTci, . . . , yny,rTci)=(x0,rTci-1,x1,rTci-1, . . . , xnx,rTci-1,√{square root over ( αy0,rTci-1,y1,rTci-1, . . . , xny,rTci-1), otherwise, they are
computed as:
(x0,rTci,x1,rTci, . . . , xnx,rTci,√{square root over ( αy0,rTci,y1,rTci, . . . , yny,rTci)=(x0,rmi,x1,rmi, . . . , xnx,rmi,√{square root over ( αy0,rmi,y1,rmi, . . . , yny,rmi)+(x0,rTci-1,x1,rTci-1, . . . , xnx,rTci-1,√{square root over ( αy0,rTci-1,y1,rTci, . . . , xny,rTci-1);
r) the appropriate bits of the x-coordinates x0,rc,x1,rc, . . . , xnx,rc, y-coordinates y1,rc, . . . , yny,rc and the sign bit of y0,rc of the message authentication code point (x0,rcu,x1,rcu, . . . , xnx,rcu,y0,rcu,y1,rcu, . . . , yny,rcu), and the appropriate bits of the x-coordinates x0,rTc,x1,rTc, . . . , xnx,rTc, y-coordinates y1,rTc, . . . , yny,rTc and the sign bit of y0,rTc of the message authentication point (x0,rTcu,x1,rTcu, . . . , xnx,rTcu,y0,rTcu,y1,rTcu, . . . , yny,rTcu) are concatenated together to form the message authentication code of the received message;
and
s) if the received message authentication code is equal to the message authentication code of the received message generated at the receiving correspondent, the received message is authenticated.

41 more elements

Elliptical polynomial-based message authentication code

Life of this patent

Elliptical polynomial-based message authentication code

Life of this patent

Abstract

Claims6