Patent Document ID: 8331558
Application ID: 12656897
Patent Flag: 1

Claim One:
1. A computerized method of cipher block chaining using elliptic curve cryptography, 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 a,bε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, wherein the random number k is a shared secret key for communication, the sending and receiving correspondents further agreeing on a base point on an elliptic curve (x B ,y B )εEC and a base point on the twist of the elliptic curve (x TB ,√{square root over ( α y TB )εTEC; the sending correspondent then performs the following steps: (c) embedding a bit string of the secret key into the x-coordinate of a key elliptic point (x k ,√{square root over (α k )}y k ); (d) computing a scalar multiplication (x TS 0 ,√{square root over ( α y TS 0 )=k(x TB ,√{square root over ( α y TB ) if (x k ,√{square root over (α k )}y k ) is on the elliptic curve, where α k =1, and setting (x S 0 ,y S 0 )=(x k ,y k ), wherein if α k =α o , then computing a scalar multiplication (x S 0 ,y S 0 )=k(x B ,y B ) and setting (x TS 0 ,√{square root over ( α y TS 0 )=(x k ,√{square root over ( α y k ); (e) embedding the message N-bit string of a 0-th block into the x-coordinate of an elliptic message point (x m 0 ,√{square root over (α m 0 )}y m 0 ); (f) computing a set of cipher points as (x c 0 ,y c 0 )=(x m 0 ,y m 0 )+(x S 0 ,y S 0 ) and (x Tc 0 ,√{square root over ( α y Tc 0 )=(x TS 0 ,√{square root over ( α y TS 0 ) if the message point of the 0-th block is on the elliptic curve, where α m 0 =1, wherein if otherwise, the set of cipher points are computed as (x Tc 0 ,√{square root over ( α y Tc 0 )=(x m 0 ,√{square root over ( α y m 0 )+(x TS 0 ,√{square root over ( α y TS 0 ) and (x c 0 ,y c 0 )=(x S 0 ,y S 0 ); (g) sending appropriate bits of the x-coordinate of the cipher point (x c 0 ,y c 0 ) to the receiving correspondent if the message point of the 0-th block is on the elliptic curve, wherein if the message point of the 0-th block is on the twist of the elliptic curve, the appropriate bits of the x-coordinate of the cipher point (x Tc 0 ,√{square root over ( α y Tc 0 ) are sent to the receiving correspondent; (h) establishing integers i and u and iteratively repeating the following steps i) through k) until i>u: (i) embedding the message N-bit string of an i-th block into the x-coordinate of the elliptic message point (x m i ,√{square root over (α m i )}y m i ); (j) computing the set of cipher points as (x c i ,y c i )=(x m i ,y m i )+(x i i ,y S 0 ) and (x Tc i ,√{square root over ( α y Tc i )=(x Tc i-1 ,√{square root over ( α y Tc i-1 ) if the message point of the i-th block is on the elliptic curve, where α m i =1, wherein if otherwise, the set of cipher points are computed as (x Tc i ,√{square root over ( α y Tc i )=(x m i ,√{square root over ( α y m i )+(x Tc i-1 ,√{square root over ( α y Tc i-1 ) and (x c i ,y c i )=(x c i ,y c i ); (k) sending appropriate bits of the x-coordinate of the cipher point (x c i ,y c i ) to the receiving correspondent if the message point of the i-th block is on the elliptic curve, wherein if the message point of the i-th block is on the twist of the elliptic curve, the appropriate bits of the x-coordinate of the cipher point (x Tc i ,√{square root over ( α y Tc i ) are sent to the receiving correspondent; the receiving correspondent then performs the following steps: (l) embedding the bit string of the secret key into the x-coordinate of the key elliptic point (x k ,√{square root over (α k )}y k ); (m) computing a scalar multiplication (x TS 0 ,√{square root over ( α y TS 0 )=k(x TB ,√{square root over ( α y TB ) if (x k ,√{square root over (α k )}y k ) is on the elliptic curve, where α k =1, and setting (x S 0 ,y S 0 )=(x k ,y k ), wherein if α k = α , then computing a scalar multiplication (x S 0 ,y S 0 )=k(x B ,y B ) and setting (x TS 0 ,√{square root over ( α y TS 0 )=(x k ,√{square root over ( α y k ); (n) computing a message point as (x m 0 ,y m 0 )=(x c 0 ,y c 0 )−(x S 0 ,y S 0 ) and setting (x Tc 0 ,√{square root over ( α y Tc 0 )=(x TS 0 ,√{square root over ( α y TS 0 ) if the received cipher point of the 0-th block (x c 0 ,y c 0 ) is on the elliptic curve, wherein if the received cipher point (x Tc 0 ,√{square root over ( α y Tc 0 ) is on the twist of the elliptic curve, the message point (x m 0 ,√{square root over ( α y m 0 ) is computed as (x m 0 ,√{square root over ( α y m 0 )=(x Tc 0 ,√{square root over ( α y Tc 0 )−(x TS 0 ,√{square root over ( α y TS 0 ) and (x c 0 ,y c 0 )=(x S 0 ,y S 0 ); (o) recovering the secret message bit string of 0-th block from the x-coordinate of the point (x m 0 ,y m 0 ) if the message point is on the elliptic curve, wherein the secret message bit string of the 0-th block is recovered from the x-coordinate of the point (x m 0 ,√{square root over ( α y m 0 ) if the message point is on the twist of the elliptic curve; (p) setting i=0 and iteratively repeating the following steps q) through r) until i>u: (q) computing the message point as (x m i ,y m i )=(x c i ,y c i )−(x c i-1 ,y c i-1 ) and (x Tc i ,√{square root over ( α y Tc i )=(x Tc i-1 ,√{square root over ( α y Tc i-1 ) if the received cipher point of the i-th block (x c i ,y c i ) is on the elliptic curve, wherein if the received cipher point (x Tc i ,√{square root over ( α y Tc i ) is on the twist of the elliptic curve, the message point (x m i ,√{square root over ( α y m i ) is computed as (x m i ,√{square root over ( α y m i )=(x Tc i ,√{square root over ( α y Tc i )−(x Tc i-1 ,√{square root over ( α y Tc i-1 ) and (x c i ,y c i )=(x c i-1 ,y c i-1 ); and (r) recovering the secret message bit string of i-th block from the x-coordinate of the point (x m i ,y m i ) if the message point is on the elliptic curve, wherein the secret message bit string of the i-th block is recovered from the x-coordinate of the point (x m i ,√{square root over ( α y m i ) if the message point is on the twist of the elliptic curve.