# US 2010/0169658 A1 · Elliptic curve-based message authentication code

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

- Number: US 2010/0169658 A1
- Document ID: US20100169658A1
- Status: Published application
- Kind: A1
- Application number: 12/318,501
- Filed: 2008-12-30
- Published: 2010-07-01
- Earliest claimed: 2008-12-30
- Inventors: Lahouari Ghouti; Mohammad K. Ibrahim
- Web page: https://patentgrep.com/patent/US20100169658A1

## CPC

- H04L 9/3013: {involving the discrete logarithm problem, e.g. ElGamal or Diffie-Hellman systems}
- H04L 9/0643: {Hash functions, e.g. MD5, SHA, HMAC or f9 MAC}
- H04L 9/3066: {involving algebraic varieties, e.g. elliptic or hyper-elliptic curves}
- H04L 2209/08: Randomization, e.g. dummy operations or using noise
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

The elliptic curve-based message authentication code is a computational method for improving the security of existing message authentication code (MAC) generating methods through the use of elliptic curve cryptography. Particularly, the message authentication codes and elliptic curve cryptography are based on an elliptic curve discrete logarithm problem, which is well known in mathematics to be a computationally hard problem.

## Claims

### Claim 1

A computerized method of generating an elliptic-curve based message authentication code, comprising the steps of:
a) a sending correspondent and a receiving correspondent agreeing upon a set of coefficients a and b such that α,b ∈ F, wherein F represents a finite field wherein the elements of F can be represented using (N+1) bits, wherein N is a natural number, and further agreeing upon a base point (xB,yB) ∈ EC, wherein EC represents an elliptic curve defined over F which satisfies the equation y2=x3+αx+b, and a base point on its twist (xTB,√{square root over ( αyTB) ∈ TEC, wherein TEC represents the twist of the elliptic curve EC defined over F that satisfies the equation αy2=x3+αx+b, wherein α ∈ F(p) is a non-quadratic residue element of the finite field F; and further, the sending correspondent and the receiving correspondent agree on a random number k, the random number k being a shared secret key for communication;
the sending correspondent performs the following steps:
b) embedding a bit string of the shared secret key into an x-coordinate of a key elliptic point (xk,√{square root over (αk)} yk) using a non-iterative embedding method;
c) if (xk,√{square root over (αk)}yk) is on the elliptic curve, then computing a scalar multiplication (xTS0,√{square root over ( αyTS0)=k(xTB,√{square root over ( αyTB) and setting (xS0,yS0)=(xk,yk), and if αk= α, then computing a scalar multiplication (xS0,yS0)=k(xB,yB) and setting (xTS0,√{square root over ( αyTS0)=xk,√{square root over ( αyk);
d) embedding the message N-bit string of the 0-th block into the x-coordinate of an elliptic message point (xm0,√{square root over (αm0)}ym0) using the non-iterative embedding method;
e) if the message point of the 0-th block is on the elliptic curve, then a set of message authentication code points are computed using (xc0,yc0)=(xm0,ym0)+(xS0,yS0) and (xTc0, √{square root over ( αyTS0), otherwise they are computed using (xTc0,√{square root over ( αyTc0)=(xm0,√{square root over ( αym0)+(xTS0,√{square root over ( αyTS0) and (xc0,yc0)=(xS0,yS0);
establishing an integer i denoting the ith message data block and having an initial value of i=1, then the following steps f) through h) are repeated until all the message data blocks are processed, and incrementing i at each step:
f) embedding the message N-bit string of the i-th block into the x-coordinate of the elliptic message point (xmi,√{square root over (αmi)}ymi) using the non-iterative embedding method;
g) if the message point of the i-th block is on the elliptic curve, then the message authentication code points are computed using (xci,yci)=(xmi,ymi)+(xci−1,yci−1) and (xTci,√{square root over ( αyTci)=(xTci−1,√{square root over ( αyTci−1), otherwise they are computed using (xTci,√{square root over ( αyTci)=(xmi,√{square root over ( αymi)+(xTci−1,√{square root over ( αyTci−1) and (xci,yci)=(xci−1,yci−1);
h) appropriate bits of the x-coordinate xc and a sign bit of the y-coordinate yc of the message authentication code point (xcu,ycu), and the appropriate bits of the x-coordinate xTc and the sign bit of the y-coordinate yTc of the MAC point (xTcu,√{square root over ( αyTcu) are concatenated together to form the message authentication code, which is appended to the message to be sent;
at the receiving correspondent, the following steps are performed:
i) embedding the bit string of the secret key into the x-coordinate of the key elliptic point (xk,√{square root over (αk)}yk) using the non-iterative embedding method;
j) if (xk,⇄{square root over (αk)}yk) is on the elliptic curve, then computing the scalar multiplication (xTS0,√{square root over ( αyTS0)=k(xTB,√{square root over ( αyTB) and setting (xS0,yS0)=(xk,yk), otherwise if αk=α0, then computing the scalar multiplication (xS0,yS0)=k(xB,yB) and setting (xTS0,√{square root over ( αyTS0)=(xk,√{square root over ( αyk);
k) embedding the received message N-bit string of the 0-th block into the x-coordinate of the received message elliptic point (xrm0,√{square root over (αrm0)}yrm0) using the non-iterative embedding method;
l) if the message point of the 0-th block is on the elliptic curve, then the message authentication code points are computed using (xrc0,yrc0)=(xrm0,yrm0)+(xS0,yS0) and (xrTc0,√{square root over ( αyrTc0)=(xTS0,√{square root over ( αyTS0), otherwise they are computed using (xrTc0,√{square root over ( αyrTc0)=(xrm0,√{square root over ( αyrm0)+(xTS0,√{square root over ( αyTS0) and (xrc0,yrc0)=(xS0,yS0);
initializing i as i=1, then the following steps m) through o) are repeated until all the received message data blocks are processed, and incrementing i at each step:
m) embedding the message N-bit string of the i-th block into the x-coordinate of the elliptic message point (xrmi,√{square root over (αrmi)}yrmi) using the non-iterative embedding method;
n) if the message point of the i-th block is on the elliptic curve, then the message authentication code points are computed using (xrci,yrci)=(xrmi,yrmi)+(xSi,ySi) and (xrTci, √{square root over ( αyrTci)=(xrTc−1,√{square root over ( αyrTci−1), otherwise they are computed using (xrTci,√{square root over ( αyrTci)=(xrmi,√{square root over ( αyrmi)+(xrTci−1,√{square root over ( αyrTci−1) and (xrci,yrci)=(xrci−1,yrci−1);
o) appropriate bits of the x-coordinate xrc and the sign bit of the y-coordinate yrc of the MAC point (xrcu,yrcu) and the appropriate bits of the x-coordinates xrTc and the sign bit of the y-coordinate yrTc of the message authentication code point (xrTcu,√{square root over ( αyrTcu) are concatenated together to form the message authentication code of the received message; and
p) if the received message authentication code is equal to the message authentication code of the received message generated at the receiving correspondent, then the received message is authenticated.

### Claim 2 (depends on 1)

The computerized method of generating an elliptic-curve based message authentication code as recited in claim 1, wherein the non-iterative embedding method 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=x3+αxmi+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 ( αymi); and
establishing a message point (xmi,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 3

A computerized method of generating an elliptic curve-based message authentication code, comprising the steps of:
a) a sending correspondent and a receiving correspondent agreeing upon a set of coefficients a and b such that α,b ∈ F, wherein F represents a finite field wherein the elements of F can be represented using (N+1) bits, wherein N is a natural number, and further agreeing upon a base point (xB,yB) ∈ EC, wherein EC represents an elliptic curve defined over F which satisfies the equation y2=x3+αx+b, and a base point on its twist (xTB,√{square root over ( αyTB) ∈ TEC, wherein TEC represents the twist of the elliptic curve EC defined over F that satisfies the equation αy2=x3+αx+b, wherein α ∈ F(p) is a non-quadratic residue element of the finite field F, and further, the 12 sending correspondent and the receiving correspondent agree on a random number k, the random number k being a shared secret key for communication;
the sending correspondent then performs the following steps:
b) embedding a bit string of the shared secret key into an x-coordinate of a key elliptic point (xk,√{square root over (αk)}yk) using a non-iterative embedding method;
c) if (xk,√{square root over (αk)}yk) is on the elliptic curve, then computing the scalar multiplication (xTS0,√{square root over ( αyTS0)=k(xTB,√{square root over ( αyTB) and setting (xS0,yS0)=(xk,yk), and if αk= α, then computing the scalar multiplication (xS0,yS0)=k(xB,yB) and setting (xTS0,√{square root over ( αyTS0)=(xk,√{square root over ( αyk);
d) embedding the message N-bit string of the 0-th block into the x-coordinate of the elliptic message point (xm0,√{square root over (αm0)}ym0) using the non-iterative embedding method;
e) if the message point of the 0-th block is on the elliptic curve, then the message authentication code points are computed using (xc0yc0)=(xm0,ym0)+(xS0,yS0) and (xTc0, √{square root over ( αyTc))32 (xTS0,√{square root over ( αyTS0), otherwise they are computed using (xTc0,√{square root over ( αyTc0)=(xm0,√{square root over ( αym0)+(xTS0,√{square root over ( αyTS0) and (xc0,yc0)=(xS0,yS0);
establishing an integer i denoting the ith message data block and having an initial value of i=1, then the following steps f) through h) are repeated until all the message data blocks are processed, and incrementing i at each step:
f) embedding the message N-bit string of the i-th block into the x-coordinate of the elliptic message point (xmi,√{square root over (αmi)}ymi) using the non-iterative embedding method;
g) doubling the points (xSi,ySi) and (xTSi,yTSi) such that (xSi,ySi)=2(xSi−1,ySi−1) and (xTSi,yTSi)=2(xTS1,√{square root over ( αyTSi−1);
h) if the message point of the i-th block is on the elliptic curve, then the message authentication code points are computed using (xci,yci)=(xmi,ymi)+(xmi−1,ymi−1)+(xSi,ySi) and (xTci,√{square root over ( αyTci)=(xTci−1,√{square root over ( αyTci−1), otherwise they are computed using (xTci,√{square root over ( αyTci)=(xmi,√{square root over ( αymi)+(xmi−1,√{square root over ( αymi−1)+(xTSi,√{square root over ( αyTSi) and (xci,yci)=(xci−1,yci−1);
i) appropriate bits of the x-coordinate xc and a sign bit of the y-coordinate yc of the message authentication code point (xcu,ycu), and the appropriate bits of the x-coordinate xTc and the sign bit of the y-coordinate yTc of the MAC point (xTcu,√{square root over ( αyTcu) are concatenated together to form the message authentication code, which is appended to the message to be sent;
at the receiving correspondent, the following steps are performed:
j) embedding the bit string of the secret key into the x-coordinate of the key elliptic point (xk,√{square root over (αk)}yk) using the non-iterative embedding method;
k) if (xk,√{square root over (αk)}yk) is on the elliptic curve, then computing the scalar multiplication (xTS0,√{square root over ( αyTS0)=k(xTB,√{square root over ( αyTB) and setting (xS0,yS0)=(xkyk), otherwise if αk= α, then computing the scalar multiplication (xS0yS0)=k(xB,yB) and setting (xTS0,√{square root over ( λyTS0)=(xk,√{square root over ( αyk);
l) embedding the received message N-bit string of the 0-th block into the x-coordinate of the received message elliptic point (xrm0,√{square root over (αrm0)}yrm0) using the non-iterative embedding method;
m) if the message point of the 0-th block is on the elliptic curve, then the message authentication code points are computed using (xrc0,yrc0)=(xrm0yrm0)+(xS0,yS0) and (xrTc0,√{square root over ( αyrTc0)=(xTS0,√{square root over ( αyTS0), otherwise they are computed using (xrTc0,√{square root over ( αyrTc0)=(xrm0,√{square root over ( αyrm0)+(xTS0, √{square root over ( αyTS0) and (xrc0,yrc0)=(xS0,yS0);
initializing i as i=1, then the following steps n) through p) are repeated until all the received message data blocks are processed, and incrementing i at each step:
n) embedding the message N-bit string of the i-th block into the x-coordinate of the elliptic message point (xrmi,√{square root over (αrmi)}yrmi) using the non-iterative embedding method;
o) 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 ( αyTSi−1);
p) if the message point of the i-th block is on the elliptic curve, then the message authentication code points are computed using (xrci,yrci)=(xrmi,yrmi)+(xrmi−1,yrmi−1)+(xSi,ySi) and (xrTci,√{square root over ( αyrTci)=(xrTci−1,√{square root over ( αyrTci−1), otherwise they are computed using (xrTci,√{square root over ( αyrTci)=(xrmi√{square root over ( αyrmi)+(xrmi−1√{square root over ( αyrmi−1)+(xTSi,√{square root over ( αyTSi) and (xrci,yrci)=(xrci−1,yrci−1);
q) appropriate bits of the x-coordinate xrc and the sign bit of the y-coordinate yrc of the message authentication code point (xrcu,yrcu), and the appropriate bits of the x-coordinates xrTc and the sign bit of the y-coordinate yrTc of the message authentication code point (xrTcu,√{square root over ( αyrTcu) are concatenated together to form the message authentication code of the received message; and
r) if the received message authentication code is equal to the message authentication code of the received message generated at the receiving correspondent, then the received message is authenticated.

### Claim 4 (depends on 3)

The computerized method of generating a message authentication code using elliptic curve cryptography as recited in claim 3, wherein the non-iterative embedding method 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+αsmi+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 ( αymi); 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 computerized method of generating an elliptic curve-based message authentication code, comprising the steps of:
a) a sending correspondent and a receiving correspondent agreeing 4 upon a set of coefficients a and b such that α,b ∈ F, wherein F represents a finite field wherein the elements of F can be represented using (N+1) bits, wherein N is a natural number, and further agreeing upon a base point (xB,yB) ∈ EC, wherein EC represents an elliptic curve defined over F which satisfies the equation y2=x3+αx+b, and a base point on its twist (xTB,√{square root over ( αyTB) ∈ TEC, wherein TEC represents the twist of the elliptic curve EC defined over F that satisfies the equation αy2=x3+αx+b, wherein α ∈ F(p) is a non-quadratic residue element of the finite field F; and further, the sending correspondent and the receiving correspondent agree on a random number k, the random number k being a shared secret key for communication, and assigning a vector smito represent an N-bit string of an i-th message block;
the sending correspondent then performs the following steps:
b) embedding a bit string of the shared secret key into an x-coordinate of a key elliptic point (xk,√{square root over (αk)}yk) using a non-iterative embedding method;
c) if (xk,√{square root over (αk)}yk) is on the elliptic curve, then computing the scalar multiplication (xTS0,√{square root over ( αyTS0)=k(xTB,√{square root over ( αyTB) and setting (xS0,yS0)=(xk,yk), and if αk= α, then computing the scalar multiplication (xS0,yS0)=k(xB,yB) and setting (xTS0,√{square root over ( αyTS0)=(xk,√{square root over ( αyk);
d) computing the N-bit string Sm0′ as Sm0′ =Sm0 ⊕ Sm−1 and then embedding the message N-bit string Sm0′ of the 0-th block into the x-coordinate of the elliptic message point (xm0,√{square root over (αm0)}ym0) using the non-iterative embedding method;
e) if the message point of the 0-th block is on the elliptic curve, then the message authentication code points are computed using (xc0,yc0)=(xm0,ym0)+(xS0,yS0) and (xTc0,√{square root over ( αyTS0)=(xTS0,√{square root over ( αyTS0), otherwise they are computed using (xTc0,√{square root over ( αyTc0)=(xm0,√{square root over ( αym0)+(xTS0,√{square root over ( αyTS0) and (xc0,yc0)=(xS0,yS0);
establishing an integer i denoting the ith message data block and having an initial value of i=1, then the following steps f) through h) are repeated until all the message data blocks are processed, and incrementing i at each step:
f) computing the N-bit string Sm1′ as Smi′=Smi ⊕ Smi−1 and embedding the message N-bit string of the i-th block into the x-coordinate of the elliptic message point (xmi,√{square root over (αmi)}ymi) using the non-iterative embedding method;
g) doubling the points (xSi,ySi) and (xTSi,yTSi) as (xSi,ySi)=2(xSi−1,ySi−1) and (xTSi,yTSi)=2(xTSi−1,√{square root over ( αyTSi−1);
h) if the message point of the i-th block is on the elliptic curve, then the message authentication code points are computed using (xci,yci)=(xmi,ymi)+(xmi−1,ymi−1)+(xSi,ySi) and (xTci,√{square root over ( αyTci)=(xTci−1,√{square root over ( αyTci−1), otherwise they are computed using (xTci,√{square root over ( αyTci)=(xmi,√{square root over ( αymi)+(xmi−1,√{square root over ( αymi−1)+(xTSi,√{square root over ( αyTSi) and (xci,yci)=(xci−1,yci−1);
i) appropriate bits of the x-coordinate xc and a sign bit of the y-coordinate yc of the message authentication code point (xcu,ycu), and the appropriate bits of the x-coordinate xTc and the sign bit of the y-coordinate yTc of the message authentication code point (xTcu,√{square root over ( αyTcu) are concatenated together to form the message authentication code, which is appended to the message to be sent;
at the receiving correspondent, the following steps are performed:
j) embedding the bit string of the secret key into the x-coordinate of the key elliptic point (xk,√{square root over (αk)}yk) using the non-iterative embedding method;
k) if (xk,√{square root over (αk)}yk) is on the elliptic curve, then computing the scalar multiplication (xTS0,√{square root over ( αkyTS0)=k(xTB,√{square root over ( αyTB) and setting (xS0,yS0)=(xk,yk), otherwise if αk= α, then computing the scalar multiplication (xS0,yS0)=k(xB,yB) and setting (xTS0,√{square root over ( αyTS0)=(xk,√{square root over ( αyk);
l) computing the N-bit string Srm0′ as Srm0′=Srm0 ⊕Srm−1, and embedding the received message N-bit string of the 0-th block into the x-coordinate of the received message elliptic point (xrm0,√{square root over (αrm0)}yrm0) using the non-iterative embedding method;
m) if the message point of the 0-th block is on the elliptic curve, then the message authentication code points are computed using (xrc0,yrc0)=(xrm0,yrm0)+(xS0,yS0) and (xrTc0, √{square root over ( αyrTc0)=(xTS0,√{square root over ( αyTS0), otherwise they are computed using (xrTc0,√{square root over ( αyrTc0)=(xrm0,√{square root over ( αyrm0)+(xTS0,√{square root over ( αyTS0) and (xrc0, xrc0)=(xS0,yS0);
initializing i as i=1, then the following steps n) through p) are repeated until all the received message data blocks are processed, and incrementing i at each step:
n) computing the N-bit string Srmi′ as Srmi′=Srmi ⊕ Srmi−1 and embedding the message N-bit string of the i-th block into the x-coordinate of the elliptic message point (xrmi,√{square root over (αrmi)}yrmi) using the non-iterative embedding method;
o) doubling the points (xSi,ySi) and (xTSi,yTSi) as (xSi,ySi)=2 (xSi−1,ySi−1) and (xTSi,yTSi)=2(xTSi−1,√{square root over ( αyTSi−1);
p) if the message point of the i-th block is on the elliptic curve, then the message authentication code points are computed using (xrci,yrci)=(xrmi,yrmi)+(xrmi−1,yrmi−1)+(xSi,ySi) and (xrTci,√{square root over ( αyrTci)=(xrTci−1,√{square root over ( αyrTci−1), otherwise they are computed using (xrTci,√{square root over ( αyrTci)=(xrmi,√{square root over ( αyrmi)+(xrmi−1,√{square root over ( αyrmi−1)+(xTSi,√{square root over ( αyTSi) and (xrci,yrci)=(xrci−1,yrci−1);
q) appropriate bits of the x-coordinate xrc and the sign bit of the y-coordinate yrc of the message authentication code point (xrcu,yrcu), and the appropriate bits of the x-coordinates xrTc and the sign bit of the y-coordinate yrTc of the message authentication code point (xrTcu,yrTcu) are concatenated together to form the message authentication code of the received message; and
r) if the received message authentication code is equal to the message authentication code of the received message generated at the receiving go correspondent, then the received message is authenticated.

### Claim 6 (depends on 5)

The computerized method of generating an elliptic curve-based message authentication code as recited in claim 5, wherein the non-iterative embedding method 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+αxmi+b, wherein if tmi on 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 ( αymi); 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= α.
