Elliptic curve-based message authentication code

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.

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.