# US 2010/0169644 A1 · Message authentication code with elliptic polynomial hopping

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

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

## CPC

- H04L 9/0662: {with particular pseudorandom sequence generator}
- H04L 9/0643: {Hash functions, e.g. MD5, SHA, HMAC or f9 MAC}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

The message authentication code with elliptic polynomial hopping provides methods for the generation of message authentication codes (MACs) utilizing elliptic curves, which are based on the elliptic curve discrete logarithm problem. The elliptic curve discrete logarithm problem is well known to be a computationally “difficult” or “hard” problem, thus providing enhanced security for the MACs. Different elliptic polynomials are used for different blocks of the same plaintext, each elliptic polynomial for each message block being selected at random using an initial secret key and a random number generator.

## Claims

### Claim 1

A computerized method of generating a message authentication code with elliptic polynomial hopping, comprising the steps of:
a sending correspondent and a receiving correspondent agreeing upon:
(a) a form of an elliptic polynomial equation by deciding on an underlying finite field F; a number of x-coordinates, and a set of monomials used;
(b) a random number k0, which is kept as a secret key for generating a message authentication code, and a method for generating the message authentication code given a random number;
(c) a random number generator;
d) a random number kp0 that is a portion of a shared secret key used for communication;
(e) a set of (nx+1) numbers such that xbi ∈ F, wherein i and nx are integers, wherein i=0, . . . , nx, the set being used to find an initial base point, the set being made public;
the sending correspondent then performing the following steps:
(f) generating at least a portion of a set of coefficients b1l(0), b2lk(0) ∈ F of a first elliptic polynomial to be used for a message authentication code of a first message block, from the shared secret key kp0;
(g) embedding the set of (nx+1) numbers xbi ∈ F into an elliptic polynomial point to obtain an initial base point (x0,B(0), x1,b(0), . . . , xnx,B(0), yB(0), αB) using a data embedding method;
(h) embedding the first block of the message bit string into an elliptic polynomial message point (x0,m(0), x1,m(0), . . . , xnx,m(0), ym(0), αm(0)) using the data embedding method;
(i) computing a scalar multiplication of the first block shared key k0 with the base point (x0,B(0), x1,B(0), . . . , xnx,B(0), yB(0), αB) as (x0,kB(0), x1,kB(0), . . . , xnx,kB(0), ykB(0), 1)=k(x0,B(0), x1,B(0), . . . , xnx,B(0), yB(0), αB);
(1) computing the message authentication point of the first data block (x0,c(0), x1,c(0), . . . , xnx,c(0), yc(0), αc(0)) as:
(x0,c(0), x1,c(0), . . . , xnx,c(0), yc(0)αc(0))=, wherein αc(0)=αm(0); (x0,m(0), x1,m(0), . . . , xnx,m(0), ym(0), αm(0))+(x0,kB(0), x1,kB(0), . . . , xnx,kB(0), ykB(0), 1)
initializing an integer j as j=1 and repeating the following steps (k) to (o), and incrementing j at each step until all of the message data blocks are processed:
(k) generating a random number kpj with the random number generator;
(l) generating at least a portion of the coefficients b1l(j), b2lk(j) ∈ F of the j-th elliptic polynomial from the random number kpj;
(m) embedding the j-th block of the message bit string into a j-th elliptic polynomial message point (x0,m(j), x1,m(j), . . . , xnx,m(j), ym(j), αm(j)) using the data embedding method;
(n) hopping the message authentication code point (x0,c(j-1), x1,c(j-1), . . . , xnx,c(j-1), yc(j-1), αc(j-1));to an equivalent message authentication code point (x′0,c(j), x′1,c(j), . . . , x′nx,c(j), y′c(j), α′c(j)) that satisfies the j-th elliptic polynomial of step (l) using the data embedding method;
(o) computing the message authentication code point of the j-th data block (x0,c(j), x1,c(j), . . . , xnx,c(j), yc(j), αc(j)) as:
(x0,c(j), x1,c(j), . . . , xnx,c(j), yc(j), αc(j))=(x0,m(j), x1,m(j), . . . , xnx,m(j), ym(j), αm(j))+; (x′0,c(j), x′1,c(j), . . . , xnx,c(j), yc(j), α′c(j))
(p) appropriate bits of the x-coordinates and a bit indicating the value of αc(u) of a cipher point (x0,c(u), x1,c(u), . . . , xnx,c(u), yc(u), αc(j)) are concatenated together to form the message authentication code bit string and are sent to the receiving correspondent;
the receiving correspondent performing the following steps:
(q) generating at least a portion of the coefficients b1l(0), b2lk(0) ∈ F of the first elliptic polynomial to be used for the message authentication code of the first message block from the shared secret key kp0;
(r) embedding the set of (nx+1) numbers xbi ∈ F into an elliptic polynomial point to obtain an initial base point (x0,B(0), x1,B(0), . . . , xnx,B(0), yB(0), αB) using the data embedding method;
(s) embedding the first block of the received message bit string into an elliptic polynomial message point (x0,rm(0), x1,rm(0), . . . , xnx,rm(0), yrm(0), αm(0)) using the data embedding method;
(t) computing the scalar multiplication of the first block shared key k0 with the base point (x0,B(0), x1,B(0), . . . , xnx,B(0), yB(0)) as (x0,kB(0), x1,kB(0), . . . , xnx,kB(0), ykB(0), 1)=k(x0,B(0), x1,B(0), . . . , xnx,B(0), yB(0), αB);
(u) computing the message authentication code point of the first received data block (x0,rc(0), x1,rc(0), . . . , xnx,rc(0), yrc(0)) as:
(x0,rc(0), x1,rc(0), . . . , xnx,rc(0), yrc(0)αrc(0))=(x0,rm(0), x1,rm(0), . . . , xnx,rm(0), yrm(0), αrm(0))+, wherein αrc(0)=αrm(0); (x0,kB(0), x1,kB(0), . . . , xnx,kB(0), ykB(0), 1)
initializing the integer j as j=1 and repeating the following steps (v) to (aa), and incrementing j at each step until all of the message data blocks are processed:
(v) generating a random number kpj with the random number generator based upon kpj-1;
(w) generating at least a portion of the coefficients b1l(j), b2lk(j) ∈ F of the j-th elliptic polynomial from the random number kpj;
(x) embedding the j-th block of the received message bit string into a j-th elliptic polynomial message point (x0,rm(j), x1,rm(j), . . . , xnx,rm(j), yrm(j), αrm(j)) using the data embedding method;
(y) hopping the message authentication point (x0,rc(j-1), x1,rc(j-1), . . . , xnx,rc(j-1), yrc(j-1), αrc(j-1) to an equivalent message authentication point (x′0,rc(j), x′1,rc(j), . . . , x′nx,rc(j), y′rc(j), α′rc(j)) that satisfies the j-th elliptic polynomial selected in step (l) using the data embedding method;
(z) computing the message authentication code point of the j-th received data block (x0,rc(j), x1,rc(j), . . . , xnx,rc(j), yrc(j), αrc(j)) is computed as:
(x0,rc(j), x1,rc(j), . . . , xnx,rc(j), yo(r), αrc(j))=(x0,rm(j), x1,rm(j), . . . , xnx,rm(j), yrm(j), αrm(j))+; (x′0,rc(j), x′1,rc(j), . . . , x′nx,rc(j), yrc(j), α′rc(j))
(aa) the appropriate bits of the x-coordinates, and a bit indicating the value of αc(u) of the message authentication point (x0,rc(u), x1,rc(u), . . . , xnx,rc(u), yrc(u), αrc(j)) are concatenated together to form the message authentication code bit string of the received message data; and
(bb) if the message authentication code bit string of the received message data is the same as the message authentication code bit string sent by the sending correspondent, then the message is authenticated.

### Claim 2 (depends on 1)

The computerized method of generating a message authentication code as recited in claim 1, wherein the form of the elliptic polynomial equation is selected to be
y
2
=
∑
l
∈
S
nx

b
1

l
(
s
)

x
l
3
+
∑
l
,
k
∈
S
nx
,
l
≠
k

b
2

lk
(
s
)

x
l
2

x
k
.

### Claim 3 (depends on 2)

The computerized method of generating a message authentication code as recited in claim 2, wherein the data embedding method includes the steps of:
(a) dividing the message bit string into (nx+ny+1) bit-strings mx,0, mx,1, . . . , mx,nx, my,1, . . . , mk,ny;
(b) assigning the value of the bit string of mx,0, mx,1, . . . , mx,nx to x0,m, x1,m, . . . , xnx,m;
(c) assigning the value of the bit string of my,1, . . . , mk,ny to y1,m, . . . , ymy,m;
(d) computing
T
(
s
-
1
)
=
∑
l
∈
S
nx

b
1

l

x
l
3
+
∑
l
,
k
∈
S
nx
,
l
≠
k

b
2

lk

x
l
2

x
k
;
and
(e) performing a Legendre test to determine if T has a square root, wherein if T has a square root, then assigning the square root to y0, and if T does not have a square root, then the x-coordinates and y-coordinates of the elliptic polynomial point with the embedded shared secret key bit string are selected as gxi,m and g3/2yi,m, respectively, where g is non-quadratic residue in F

### Claim 4 (depends on 3)

The computerized method of generating a message authentication code as recited in claim 3, wherein the step of generating a message authentication code includes the further step of:
a) setting the x-coordinates of a hopped point x0,o(r), x1,o(r), . . . , xnx,o(r) to the x-coordinates (x0,o(s), x1,o(s), . . . , xnx,o(s) of an original point xi,o(r)=xi,o(s) for i=0, . . . , nx;
b) substituting the value of the x-coordinates (x0,o(r), x1,o(r), . . . , xnx,o(r) into a new elliptic polynomial equation to obtain
T
(
r
)
=
∑
l
∈
S
nx

b
1

l
(
r
)

(
x
l
(
r
)
)
3
+
∑
l
,
k
∈
S
nx
,
l
≠
k

b
2

lk
(
r
)

(
x
l
(
r
)
)
2

x
k
(
r
)
,
wherein any value of (x0,o(r), x1,o(r), . . . , xnx,o(r) leads to a value of; and
c) if T(r) is quadratic reside, then setting yo(r)=√{square root over (T(r))} and the hopped point is given by (x0,o(r), x1,o(r), . . . , xnx,o(r), yo(r)) and if T is non-quadratic residue, then setting y0(r)=√{square root over (g3T(r))}, and the hopped point is given by (gx0,o(r), gx1,o(r), . . . , gxnx,o(r), yo(r)).

### Claim 5

A computerized method of generating a message authentication code with elliptic polynomial hopping, comprising the steps of:
a sending correspondent and a receiving correspondent agreeing upon:
(a) a form of an elliptic polynomial equation by deciding on an underlying finite field F; a number of x-coordinates, and a set of monomials used;
(b) a random number k0, which is kept as a secret key for generating a message authentication code;
(c) a random number generator;
d) a random number kp0 that is a portion of a shared secret key used for communication, and a method of generating the message authentication codes from a given random number;
(e) a set of (nx+1) numbers such that xbi ∈ F, wherein i and nx are integers, wherein i=0, . . . , nx, the set being used to find an initial base point, the set being made public;
the sending correspondent then performing the following steps:
(f) selecting an elliptic polynomial form from the agreed upon set of elliptic polynomial forms by generating its binary code using the shared secret key of a first block kp0, and the agreed-upon generation method;
(g) generating at least a portion of a set of coefficients b1l(0), b2lk(0) ∈ F of a first elliptic polynomial to be used for a message authentication code of a first message block, from the shared secret key kp0;
(h) embedding the set of (nx+1) numbers xbi ∈ F into an elliptic polynomial point to obtain an initial base point (x0,B(0), x1,B(0), . . . , xnx,B(0), yB(0), αB) using a data embedding method;
(i) embedding the first block of the message bit string into an elliptic polynomial message point (x0,m(0), x1,m(0), . . . , xnx,m(0), ym(0), αm(0)) using the data embedding method;
(j) computing a scalar multiplication of the first block shared key k0 with the base point (x0,B(0), x1,B(0), . . . , xnx,B(0), yB(0), αB) as (x0,kB(0), x1,kB(0), . . . , xnx,B(0), ykB(0), 1)=k(x0,B(0), x1,B(0), . . . , xnx,B(0), yB(0), αB);
(k) computing the message authentication point of the first data block (x0,c(0), x1,c(0), . . . , xnx,c(0), yc(0), αc(0)) as:
(x0,c(0), x1,c(0), . . . , xnx,c(0), yc(0)αc(0))=(x0,m(0), x1,m(0), . . . , xnx,m(0), ym(0), αm(0))+, wherein αc(0)=αm(0); (x0,kB(0), x1,kB(0), . . . , xnx,kB(0), ykB(0), 1)
initializing an integer j as j=1 and repeating the following steps (l) to (r), and incrementing j at each step until all of the message data blocks are processed:
(l) generating a random number kpj with the random number generator;
(m) selecting an elliptic polynomial form from the agreed upon set of elliptic polynomial forms by generating its binary code using the shared secret key of a j-th block kpj, and the agreed-upon generation method;
(n) generating at least a portion of the coefficients b1l(j), b2lk(j) ∈ F of the j-th elliptic polynomial from the random number kpj;
(o) embedding the j-th block of the message bit string into a j-th elliptic polynomial message point (x0,m(j), x1,m(j), . . . , xnx,m(j), ym(j),αm(j)) using the data embedding method;
(p) hopping the message authentication code point (x0,c(j-1), x1,c(j-1), . . . , xnx,c(j-1), yc(j-1), αc(j-1) to an equivalent message authentication code point (x′0,c(j), x′1,c(j), . . . , x′nx,c(j), y′c(j), α′c(j)) that satisfies the j-th elliptic polynomial of step (l) using the data embedding method;
(q) computing the message authentication code point of the j-th data block (x0,c(j), x1,c(j), . . . , xnx,c(j), yc(j), αc(j) ) as:
(x0,c(j), x1,c(j), . . . , xnx,c(j), yc(j), αc(j))=(x0,m(j), x1,m(j), . . . , xnx,m(j), ym(j), αm(j))+; (x′0,c(j), x′1,c(j), . . . , x′nx,c(j), y′c(j), α′c(j))
(r) appropriate bits of the x-coordinates and a bit indicating the value of αc(u) of a cipher point (x0,c(u), x1,c(u), . . . , xnx,c(u), yc(u), αc(u)) are concatenated together to form the message authentication code bit string and are sent to the receiving correspondent;
the receiving correspondent performing the following steps:
(s) selecting an elliptic polynomial form from the agreed upon set of elliptic polynomial forms by generating its binary code using the shared secret key of a-first block kp0, and the agreed-upon generation method;
(t) generating at least a portion of the coefficients b1l(0), b2lk(0) ∈ F of the first elliptic polynomial to be used for the message authentication code of the first message block from the shared secret key kp0;
(u) embedding the set of (nx+1) numbers xbi ∈ F into an elliptic polynomial point to obtain an initial base point (x0,B(0), x1,B(0), . . . , xnx,B(0), yB(0), αB) using the data embedding method;
(v) embedding the first block of the received message bit string into an elliptic polynomial message point (x0,rm(0), x1,rm(0), . . . , xnx,rm(0), yrm(0), αrm(0)) using the data embedding method;
(w) computing the scalar multiplication of the first block shared key k0 with the base point (x0,B(0), x1,B(0), . . . , xnx,B(0), yB(0), αB) as (x0,kB(0), x1,kB(0), . . . , xnx,kB(0), yB(0), αB)=k(x0,B(0), x1,B(0), . . . , xnx,B(0), yB(0), αB);
(x) computing the message authentication code point of the first received data block (x0,rc(0), x1,rc(0), . . . , xnx,rc(0), yrc(0), αrc(0)) as:
(x0,rc(0), x1,rc(0), . . . , xnx,rc(0), yrc(0), αrc(0))=(x0,rm(0), x1,rm(0), . . . , xnx,rm(0), yrm(0), αrm(0))+, wherein αrc(0)=αrm(0); (x0,kB(0), x1,kB(0), . . . , xnx,kB(0), ykB(0), 1)
initializing the integer j as j=1 and repeating the following steps (y) to (ee), and incrementing j at each step until all of the message data blocks are processed:
(y) generating a random number kpj with the random number generator based upon kpj-1;
(z) selecting an elliptic polynomial form from the agreed upon set of elliptic polynomial forms by generating its binary code using the shared secret key of the j-th block kpj, and the agreed-upon generation method;
(aa) generating at least a portion of the coefficients b1l(j), b1lk(j) ∈ F of the j-th elliptic polynomial from the random number kpj;
(bb) embedding the j-th block of the received message bit string into a j-th elliptic polynomial message point (x0,rm(j), x1,rm(j), . . . , xnx,rm(j), yrm(j), αrm(j))using the data embedding method;
(cc) hopping the message authentication point (x0,rc(j-1), x1,rc(j-1), . . . , xnx,rc(j-1), yrc(j-1), αrc(j-1)to an equivalent message authentication point (x′0,rc(j), x′1,rc(j), . . . , x′nx,rc(j), yrc(0), αrc(j-1))that satisfies the j-th elliptic polynomial selected in step 12) using the data embedding method;
(dd) computing the message authentication code point of the j-th received data block (x0,rc(j), x1,rc(j), . . . , xnx,rc(j), yrc(j), αrc(j))is computed as:
(x0,rc(j), x1,rc(j), . . . , xnx,rc(j), yrc(j), αrc(j))=(x0,rm(j), x1,rm(j), . . . , xnx,rm(j), yrm(j), αrm(j))+; (x′0,rc(j), x′1,rc(j), . . . , xnx,rc(j), yrc(0), α′rc(j))
(ee) the appropriate bits of the x-coordinates, and a bit indicating the value of ac(u) of the message authentication point (x0,rc(u), x1,rc(u), . . . , xnx,rc(u), yrc(u), αrc(j)) are concatenated together to form the message authentication code bit string of the received message data; and
(ff) if the message authentication code bit string of the received message data is the same as the message authentication code bit string sent by the sending correspondent, then the message is authenticated.

### Claim 6 (depends on 5)

The computerized method of generating a message authentication code as recited in claim 5, wherein the form of the elliptic polynomial equation is selected to be
y
2
=
∑
l
∈
S
nx

b
1

l
(
s
)

x
l
3
+
∑
l
,
k
∈
S
nx
,
l
≠
k

b
2

lk
(
s
)

x
l
2

x
k
.

### Claim 7 (depends on 6)

The computerized method of generating a message authentication code as recited in claim 6, wherein the data embedding method includes the steps of:
a) dividing the message bit string into (nx+ny+1) bit-strings mx,0, mx,1, . . . , mx,nx, my,1, . . . , mk,ny;
b) assigning the value of the bit string of mx,0, mx,1, . . . , mx,nx to x0,m, x1,m, . . . , xnx,m;
c) assigning the value of the bit string of my,1, . . . , mk,my to y1,m, . . . , yny,m;
d) computing
T
(
s
-
1
)
=
∑
l
∈
S
nx

b
1

l

x
l
3
+
∑
l
,
k
∈
S
nx
,
l
≠
k

b
2

lk

x
l
2

x
k
;
and
e) performing a Legendre test to determine if T has a square root, wherein if T has a square root, then assigning the square root to y0, and if T does not have a square root, then the x-coordinates and y-coordinates of the elliptic polynomial point with the embedded shared secret key bit string are selected as gxi,m and g3/2yi,m, respectively.

### Claim 8 (depends on 7)

The computerized method of generating a message authentication code as recited in claim 7, wherein the step of generating a message authentication code includes the further step of:
a) setting the x-coordinates of a hopped point (x0,o(r), x1,o(r), . . . , xnx,o(r) to the x-coordinates (x0,o(s), x1,o(s), . . . , xnx,o(s) of an original point xi,o(r)=xi,o(s) for i=0, . . . , nx,
b) substituting the value of the x-coordinates (x0,o(r), x1,o(r), . . . , xnx,o(r) into a new elliptic polynomial equation to obtain
T
(
r
)
=
∑
l
∈
S
nx

b
1

l
(
r
)

(
x
l
(
r
)
)
3
+
∑
l
,
k
∈
S
nx
,
l
≠
k

b
2

lk
(
r
)

(
x
l
(
r
)
)
2

x
k
(
r
)
,
wherein any value of (x0,o(r), x1,o(r), . . . , xnx,o(r) leads to a value of; and
c) if T(r) is quadratic reside, then setting yo(r)=√{square root over (T(r))} and the hopped point is given by (x0,o(r), x1,o(r), . . . , xnx,o(r), yo(r)), and if T is non-quadratic residue, then setting yo(r)=⇄{square root over (g3T(r))}, and the hopped point is given by (gx0,o(r), gx1,o(r), . . . , gnx,o(r), yo(r)). (x0,o(0), x1,o(0), . . . , xnx,o(0), yo(0))