Patent Document ID: 20120237030
Application ID: 13482902
Patent Flag: 0

Claim One:
1. A computer software product that includes a non-transitory storage medium readable by a processor, the non-transitory storage medium having stored thereon a set of instructions for generating an elliptic-curve based message authentication code, the instructions comprising: (a) a first set of instructions which, when loaded into main memory and executed by the processor, causes the processor to embed a bit string of a shared secret key into an x-coordinate of a key elliptic point (x k ,√{square root over (α k )}y k ) using a non-iterative embedding method at a sending correspondent, wherein the sending correspondent and a receiving correspondent agree upon a set of coefficients a and b such that a,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 (x B ,y B )εEC, wherein EC represents an elliptic curve defined over F which satisfies the equation y 2 =x 3 +ax+b, and a base point on its twist ( x TB , α _ y TB ) ∈ TEC , wherein TEC represents the twist of the elliptic curve EC defined over F that satisfies the equation α y 2 =x 3 +ax+b, wherein α εF 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 the shared secret key for communication; (b) a second set of instructions which, when loaded into main memory and executed by the processor, causes the processor to compute a scalar multiplication ( x TS 0 , α _ y TS 0 ) = k ( x TB , α _ y TB ) and set (x S 0 ,y S 0 )=(x k ,y k ) if (x k ,y k ) if (x k ,√{square root over (α k )}y k ) is on the elliptic curve, and if α k = α , then performing a scalar multiplication (x S 0 ,y S 0 )=k(x B ,y B ) and setting ( x TS 0 , α _ y TS 0 ) = ( x k , α _ y k ) , wherein (x S 0 ,y S 0 ) is a 0-th value of shared secret point (x S 0 ,y S 0 ) and (x TS 0 ,y TS 0 ) is a 0-th value of a twist of the shared secret point (x TS ,y TS ) at the sending correspondent; (c) a third set of instructions which, when loaded into main memory and executed by the processor, causes the processor to embed the message N-bit string of the 0-th block into the x-coordinate of an elliptic message point (x m 0 ,√{square root over (α m 0 )}y m 0 ) using the non-iterative embedding method; (d) a fourth set of instructions which, when loaded into main memory and executed by the processor, causes the processor to compute a set of message authentication code points (x c 0 ,y c 0 ) and their corresponding twists (x Tc 0 ,y Tc 0 ) if the message point of the 0-th block is on the elliptic curve using (x c 0 ,y c 0 )=(x m 0 ,y m 0 )+(x S 0 ,y S 0 ) and ( x Tc 0 , α _ y Tc 0 ) = ( x TS 0 , α _ y TS 0 ) , otherwise they are computed using ( x Tc 0 , α _ y Tc 0 ) = ( x m 0 , α _ y m 0 ) + ( x TS 0 , α _ y TS 0 ) and (x c 0 ,y c 0 )=(x S 0 ,y S 0 ) at the sending correspondent; (e) a fifth set of instructions which, when loaded into main memory and executed by the processor, causes the processor to establish an integer i denoting the i th message data block and having an initial value of i=1, then the following sixth through eighth sets of instructions are repeated until all the message data blocks are processed, and incrementing i at each step: (f) a sixth set of instructions which, when loaded into main memory and executed by the processor, causes the processor to embed the message N-bit string of the i-th block into the x-coordinate of the elliptic message point (x m i ,√{square root over (α m i )}y m i ) using the non-iterative embedding method at the sending correspondent; (g) a seventh set of instructions which, when loaded into main memory and executed by the processor, causes the processor to compute the i-th block message authentication code points as (x c i ,y c i )=(x m i ,y m i )+(x c i-1 ,y c i-1 ) and ( x Tc i , α _ y Tc i ) = ( x Tc i - 1 , α _ y Tc i - 1 ) if the message point of the i-th block is on the elliptic curve, otherwise they are computed using ( x Tc i , α _ y Tc i ) = ( x m i , α _ y m i ) + ( x Tc i - 1 , α _ y Tc i - 1 ) and (x c i ,y c i )=(x c i-1 ,y c i-1 ) at the sending correspondent; (h) an eighth set of instructions which, when loaded into main memory and executed by the processor, causes the processor to concatenate together appropriate bits of the x-coordinate x, and a sign bit of the y-coordinate y c i of the message authentication code point (x c u ,y c u ), and the appropriate bits of the x-coordinate x Tc i and the sign bit of the y-coordinate y Tc i of the MAC point ( x Tc u , α _ y Tc u ) to form the message authentication code, which is appended to the message to be sent at the sending correspondent; (i) a ninth set of instructions which, when loaded into main memory and executed by the processor, causes the processor to embed the bit string of the secret key into the x-coordinate of the key elliptic point (x k ,√{square root over (α k )}y k ) using the non-iterative embedding method at the receiving correspondent; (j) a tenth set of instructions which, when loaded into main memory and executed by the processor, causes the processor to perform the scalar multiplication ( x TS 0 , α _ y TS 0 ) = k ( x TB , α _ y TB ) and set (x S 0 ,y S 0 )=(x k ,y k ) if (x k ,√{square root over (α k )}y k ) is on the elliptic curve, otherwise if α k =α 0 , then performing the scalar multiplication (x S 0 ,y S 0 )=k(x B ,y B ) and setting ( x TS 0 , α _ y TS 0 ) = ( x k , α _ y k ) at the receiving correspondent; (k) an eleventh set of instructions which, when loaded into main memory and executed by the processor, causes the processor to embed the received message N-bit string of the 0-th block into the x-coordinate of the received message elliptic point (x rm 0 ,√{square root over (α rm 0 )}y rm 0 ) using the non-iterative embedding method; (l) a twelfth set of instructions which, when loaded into main memory and executed by the processor, causes the processor to compute the received message authentication code points (x rc 0 ,y rd 0 ) and their corresponding twists (x rTc 0 ,y rTc 0 ) if the message point of the 0-th block is on the elliptic curve using (x rc 0 ,y rc 0 )=(x rm 0 ,y rm 0 )+(x S 0 ,y S 0 ) and ( x rTc 0 , α _ y rTc 0 ) = ( x TS 0 , α _ y TS 0 ) , otherwise they are computed using ( x rTc 0 , α _ y rTc 0 ) = ( x rm 0 , α _ y rm 0 ) + ( x TS 0 , α _ y TS 0 ) and (x rc 0 ,y rc 0 )=(x S 0 ,y S 0 ) at the receiving correspondent; (m) a thirteenth set of instructions which, when loaded into main memory and executed by the processor, causes the processor to initialize i as i=1, then the following fourteenth through sixteenth sets of instructions are repeated until all the received message data blocks are processed, and incrementing i at each step: (n) a fourteenth set of instructions which, when loaded into main memory and executed by the processor, causes the processor to embed the message N-bit string of the i-th block into the x-coordinate of the received elliptic message point (x rm i ,√{square root over (α rm i )}y rm i ) using the non-iterative embedding method at the receiving correspondent; (o) a fifteenth set of instructions which, when loaded into main memory and executed by the processor, causes the processor to compute the i-th block received message authentication code points if the message point of the i-th block is on the elliptic curve using (x rc i ,y rc i )=(x rm i ,y rm i )+(x S i ,y S i ) and ( x rTc i , α _ y rTc i ) = ( x rTc i - 1 , α _ y rTc i - 1 ) , otherwise they are computed using ( x rTc i , α _ y rTc i ) = ( x rm i , α _ y rm i ) + ( x rTc i - 1 , α _ y rTc i - 1 ) and (x rc i ,y rc i )=(x rc i-1 ,y rc i-1 ) at the receiving correspondent; (p) a sixteenth set of instructions which, when loaded into main memory and executed by the processor, causes the processor to concatenate together appropriate bits of the received x-coordinate x rd i and the sign bit of the y-coordinate y rc i of the MAC point (x rc u ,y rc u ), and the appropriate bits of the received x-coordinates x rTc i and the sign bit of the received y-coordinate y rTc i of the message authentication code point ( x rTc u , α _ y rTc u ) to form the message authentication code of the received message at the receiving correspondent; and (q) a seventeenth set of instructions which, when loaded into main memory and executed by the processor, causes the processor to authenticate the received message if the received message authentication code is equal to the message authentication code of the received message generated at the receiving correspondent.