Patent Document ID: 20110200188
Application ID: 12656906
Patent Flag: 0

Claim One:
1. A computerized method of performing cipher block chaining using elliptic polynomial 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 1k , a 2kl , a 3k , c 1lki , c 2kl , c 3kli , b 1l , b 2lk , b 3lk , b 4k , b c ∈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 polynomial (x 0,B , x 1,B ,. .. , x nx,B , y 0,B , y 1,B ,. .. , y ny,B )∈EC nx+ny+2 and a base point on the twist of the elliptic polynomial (x 0,TB , x 1,TB ,. .. , x nx,TB , √{square root over ( α y 0,TB , y 1,TB ,. .. , y ny,TB )∈TEC nx+ny+2 ; the sending correspondent then performs the following steps: c) embedding a bit string of the secret key into the (nx+1) x-coordinates x 0 , x 1 ,. .. , x nx and the ny y-coordinates y 1 ,. .. , y ny , of a key elliptic point (x 0,k , x 1,k ,. .. , x nx,k , √{square root over (α k )}y 0,k , y 1,k ,. .. , y ny,k ); d) computing a scalar multiplication (x 0,TS 0 , x 1,TS 0 ,. .. , x nx,TS 0 , √{square root over ( α y 0,TS 0 , y 1,TS 0 ,. .. , y ny,TS 0 )= k(x 0,TB , x 1,TB ,. .. , x nx,TB , √{square root over ( α y 0,B , y 1,TB ,. .. , y ny,TB ) if x 0,k , x 1,k ,. .. , x nx,k , √{square root over (α k )}y 0,k , y 1,k ,. .. , y ny,k is on the elliptic polynomial, wherein α k =1, and setting (x 0,S 0 , x 1,S 0 ,. .. , x nx,S 0 , y 0,S 0 , y 1,S 0 ,. .. , x ny,S 0 )=(x 0,k , x 1,k ,. .. , x nx,k , y 0,k , y 1,k ,. .. , y ny,k ), wherein if α k =α o , then computing a scalar multiplication (x 0,S 0 , x 1,S 0 ,. .. , x nx,S 0 , y 0,S 0 , y 1,S 0 ,. .. , x ny,S 0 )= k(x 0,B , x 1,B ,. .. , x nx,B , y 0,B , y 1,B ,. .. , y ny,B ) and setting (x 0,TS 0 , x 1,TS 0 ,. .. , x nx,TS 0 , √{square root over ( α y 0,TS 0 , y 1,TS 0 ,. .. , x ny,TS 0 )=(x 0,k , x 1,k ,. .. , x nx,k , √{square root over ( α y 0,k , y 1,k ,. .. , y ny,k ); e) embedding the message (nx+ny+1) N-bit string of an initial block, which is referred to as the 0-th block, into the x-coordinate of an elliptic message point (x 0,m 0 , x 1,m 0 ,. .. , x nx,m 0 , √{square root over (α m 0 )}y 0,m 0 , y 1,m 0 ,. .. , y ny,m 0 ); f) computing a set of cipher points as (x 0,c 0 , x 1,c 0 ,. .. , x nx,c 0 , y 0,c 0 , y 1,c 0 ,. .. , y ny,c 0 )= (x 0,m 0 , x 1,m 0 ,. .. , x nx,m 0 , y 0,m 0 , y 1,m 0 ,. .. , y ny,m 0 ) +(x 0,S 0 , x 1,S 0 ,. .. , x nx,S 0 , y 0,S 0 , y 1,S 0 ,. .. , x ny,S 0 ) and (x 0,Tc 0 , x 1,Tc 0 ,. .. , x nx,Tc 0 , √{square root over ( α y 0,Tc 0 , y 1,Tc 0 ,. .. , y ny,Tc 0 )= (x 0,TS 0 , x 1,TS 0 ,. .. , x nx,TS 0 , √{square root over ( α y 0,TS 0 , y 1,TS 0 ,. .. , x ny,TS 0 ) if the message point of the 0-th block is on the elliptic polynomial, where α m 0 =1, wherein if otherwise, the set of cipher points are computed as (x 0,Tc 0 , x 1,Tc 0 ,. .. , x nx,Tc 0 , √{square root over ( α y 0,Tc 0 , y 1,Tc 0 ,. .. , y ny,Tc 0 )= (x 0,m 0 , x 1,m 0 ,. .. , x nx,m 0 , √{square root over ( α y 0,m 0 , y 1,m 0 ,. .. , y ny,m 0 ) +(x 0,TS 0 , x 1,TS 0 ,. .. , x nx,TS 0 , √{square root over ( α y 0,TS 0 , y 1,TS 0 ,. .. , x ny,TS 0 ) and (x 0,c 0 , x 1,c 0 ,. .. , x nx,c 0 , y 0,c 0 , y 1,c 0 ,. .. , y ny,c 0 )=(x 0,S 0 , x 1,S 0 ,. .. , x nx,S 0 , y 0,S 0 , y 1,S 0 ,. .. , x ny,S 0 ); g) sending appropriate bits of the x-coordinates x 0,c , x 1,c ,. .. , x nx,c and the y-coordinates y 1,c ,. .. , y ny,c of the cipher point (x 0,c 0 , x 1,c 0 ,. .. , x nx,c 0 , y 0,c 0 , y 1,c 0 ,. .. , y ny,c 0 ) to the receiving correspondent if the message point of the 0-th block is on the elliptic polynomial, wherein if the message point of the 0-th block is on the twist of the elliptic polynomial, the appropriate bits of the x-coordinates x 0,Tc , x 1,Tc ,. .. , x nx,Tc and y-coordinates y 1,Tc ,. .. , y ny,Tc (of the cipher point (x 0,Tc 0 , x 1,Tc 0 ,. .. , x nx,Tc 0 , √{square root over ( α y 0,Tc 0 , y 1,Tc 0 ,. .. , y ny,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 (nx+ny+1) N-bit string of an i-th block into the (nx+1) x-coordinates x 0 , x 1 ,. .. , x nx , and the ny y-coordinates y 1 ,. .. , y ny of the elliptic message point (x 0,m i , x 1,m i ,. .. , x nx,m i , √{square root over (α m i )}y 0,m i , y 1,m i ,. .. , y ny,m i ) j) computing the set of cipher points as (x 0,c i , x 1,c i ,. .. , x nx,c i , y 0,c i , y 1,c i ,. .. , y ny,c i )= (x 0,m i , x 1,m i ,. .. , x nx,m i , y 0,m i , y 1,m i ,. .. , y ny,m i ) +(x 0,c i-1 , x 1,c i-1 ,. .. , x nx,c i-1 , y 0,c i-1 , y 1,c i-1 ,. .. , x ny,c i-1 ) and (x 0,Tc i , x 1,Tc i ,. .. , x nx,Tc i , √{square root over ( α y 0,Tc i , y 1,Tc i ,. .. , y ny,Tc i )= (x 0,Tc i-1 , x 1,Tc i-1 ,. .. , x nx,Tc i-1 , √{square root over ( α y 0,Tc i-1 , y 1,Tc i-1 ,. .. , x ny,Tc i-1 ) if the message point of the i-th block is on the elliptic polynomial, where α m i =1, wherein if otherwise, the set of cipher points are computed as (x 0,Tc i , x 1,Tc i ,. .. , x nx,Tc i , √{square root over ( α y 0,Tc i , y 1,Tc i ,. .. , y ny,Tc i )= (x 0,m i , x 1,m i ,. .. , x nx,m i , √{square root over ( α y 0,m i , y 1,m i ,. .. , y ny,m i ) +(x 0,Tc i-1 , x 1,Tc i-1 ,. .. , x nx,Tc i-1 , √{square root over ( α y 0,Tc i-1 , y 1,Tc i-1 ,. .. , x ny,Tc i-1 ) and (x 0,c i , x 1,c i ,. .. , x nx,c i , y 0,c i , y 1,c i ,. .. , y ny,c i )=(x 0,c i-1 , x 1,c i-1 ,. .. , x nx,c i-1 , y 0,c i-1 , y 1,c i-1 ,. .. , x ny,c i-1 ) k) sending appropriate bits of the x-coordinates x 0,c , x 1,c ,. .. , x nx,c and the y-coordinates y 1,c ,. .. , y ny,c of the cipher point (x 0,c i , x 1,c i ,. .. , x nx,c i , y 0,c i , y 1,c i ,. .. , y ny,c i ) to the receiving correspondent if the message point of the i-th block is on the elliptic polynomial, wherein if the message point of the i-th block is on the twist of the elliptic polynomial, the appropriate bits of the x-coordinates x 0,Tc , x 1,Tc ,. .. , x nx,Tc ., and y-coordinates y 1,Tc ,. .. , y ny,Tc of the cipher point (x 0,Tc i , x 1,Tc i ,. .. , x nx,Tc i , √{square root over ( α y 0,Tc i , y 1,Tc i ,. .. , y ny,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 (nx+1) x-coordinates x 0 , x 1 ,. .. , x nx and the ny y-coordinates y 1 ,. .. , y ny of the key elliptic point (x 0,k , x 1,k ,. .. , x nx,k , √{square root over (α k )}y 0,k , y 1,k ,. .. , y ny,k ); m) computing a scalar multiplication (x 0,TS 0 , x 1,TS 0 ,. .. , x nx,TS 0 , √{square root over ( α y 0,TS 0 , y 1,TS 0 ,. .. , y ny,TS 0 )= k(x 0,TB , x 1,TB ,. .. , x nx,TB , √{square root over ( α y 0,B , y 1,TB ,. .. , y ny,TB ) if (x 0,k , x 1,k ,. .. , x nx,k , √{square root over (α k )}y 0,k , y 1,k ,. .. , y ny,k ) is on the elliptic polynomial, where α k =1, and setting (x 0,S 0 , x 1,S 0 ,. .. , x nx,S 0 , y 0,S 0 , y 1,S 0 ,. .. , x ny,S 0 )=(x 0,k , x 1,k ,. .. , x nx,k , y 0,k , y 1,k ,. .. , y ny,k ), wherein if α k = α , then computing a scalar multiplication (x 0,S 0 , x 1,S 0 ,. .. , x nx,S 0 , y 0,S 0 , y 1,S 0 ,. .. , x ny,S 0 )= k(x 0,B , x 1,B ,. .. , x nx,B , y 0,B , y 1,B ,. .. , y ny,B ) and setting (x 0,TS 0 , x 1,TS 0 ,. .. , x nx,TS 0 , √{square root over ( α y 0,TS 0 , y 1,TS 0 ,. .. , x ny,TS 0 )=(x 0,k , x 1,k ,. .. , x nx,k , √{square root over ( α y 0,k , y 1,k ,. .. , y ny,k ); n) computing a message point (x 0,m 0 , x 1,m 0 ,. .. , x nx,m 0 , y 0,m 0 , y 1,m 0 ,. .. , y ny,m 0 ) as (x 0,m 0 , x 1,m 0 ,. .. , x nx,m 0 , y 0,m 0 , y 1,m 0 ,. .. , y ny,m 0 )= (x 0,c 0 , x 1,c 0 ,. .. , x nx,c 0 , y 0,c 0 , y 1,c 0 ,. .. , y ny,c 0 ) −(x 0,S 0 , x 1,S 0 ,. .. , x nx,S 0 , y 0,S 0 , y 1,S 0 ,. .. , x ny,S 0 ) and setting (x 0,Tc 0 , x 1,Tc 0 ,. .. , x nx,Tc 0 , √{square root over ( α y 0,Tc 0 , y 1,Tc 0 ,. .. , y ny,Tc 0 )=x 0,TS 0 , x 1,TS 0 ,. .. , x nx,TS 0 , √{square root over ( α y 0,TS 0 , y 1,TS 0 ,. .. , x ny,TS 0 ) if the received cipher point of the 0-th block (x 0,c 0 , x 1,c 0 ,. .. , x nx,c 0 , y 0,c 0 , y 1,c 0 ,. .. , y ny,c 0 ) is on the elliptic polynomial, wherein if the received cipher point (x 0,Tc 0 , x 1,Tc 0 ,. .. , x nx,Tc 0 , √{square root over ( α y 0,Tc 0 , y 1,Tc 0 ,. .. , y ny,Tc 0 ) is on the twist of the elliptic polynomial, the message point (x 0,m 0 , x 1,m 0 ,. .. , x nx,m 0 , √{square root over ( α y 0,m 0 , y 1,m 0 ,. .. , y ny,m 0 ) is computed as (x 0,m 0 , x 1,m 0 ,. .. , x nx,m 0 , √{square root over ( α y 0,m 0 , y 1,m 0 ,. .. , y ny,m 0 )= (x 0,Tc 0 , x 1,Tc 0 ,. .. , x nx,Tc 0 , √{square root over ( α y 0,Tc 0 , y 1,Tc 0 ,. .. , y ny,Tc 0 ) −(x 0,TS 0 , x 1,TS 0 ,. .. , x nx,TS 0 , √{square root over ( α y 0,TS 0 , y 1,TS 0 ,. .. , x ny,TS 0 ) and (x 0,c 0 , x 1,c 0 ,. .. , x nx,c 0 , y 0,c 0 , y 1,c 0 ,. .. , y ny,c 0 )=(x 0,S 0 , x 1,S 0 ,. .. , x nx,S 0 , y 0,S 0 , y 1,S 0 ,. .. , y ny,S 0 ); o) recovering the secret message bit string of 0-th block from the (nx+1) x-coordinates and the ny y-coordinates of the point (x 0,m 0 , x 1,m 0 ,. .. , x nx,m 0 , y 0,m 0 , y 1,m 0 ,. .. , y ny,m 0 ) if the message point is on the elliptic polynomial, wherein the secret message bit string of the 0-th block is recovered from the (nx+1) x-coordinates and the ny y-coordinates of the point (x 0,m 0 , x 1,m 0 ,. .. , x nx,m 0 , √{square root over ( α y 0,m 0 , y 1,m 0 ,. .. , y ny,m 0 ) if the message point is on the twist of the elliptic polynomial; p) setting i=0 and iteratively repeating the following steps q) through r) until i>u: q) computing the message point (x 0,m i , x 1,m i ,. .. , x nx,m i , √{square root over ( α y 0,m i , y 1,m i ,. .. , y ny,m i ) as (x 0,m i , x 1,m i ,. .. , x nx,m i , y 0,m i , y 1,m i ,. .. , y ny,m i )= (x 0,c i , x 1,c i ,. .. , x nx,c i , y 0,c i , y 1,c i ,. .. , y ny,c i ) −(x 0,c i-1 , x 1,c i-1 ,. .. , x nx,c i-1 , y 0,c i-1 , y 1,c i-1 ,. .. , x ny,c i-1 ) and (x 0,Tc i , x 1,Tc i ,. .. , x nx,Tc i , √{square root over ( α y 0,Tc i , y 1,Tc i ,. .. , y ny,Tc i )=(x 0,Tc i-1 , x 1,Tc i-1 ,. .. , x nx,Tc i-1 , √{square root over ( α y 0,Tc i-1 , y 1,Tc i-1 ,. .. , x ny,Tc i-1 ); if the received cipher point of the i-th block (x 0,c i , x 1,c i ,. .. , x nx,c i , y 0,c i , y 1,c i ,. .. , y ny,c i ) is on the elliptic polynomial, wherein if the received cipher point (x 0,Tc i , x 1,Tc i ,. .. , x nx,Tc i , √{square root over ( α y 0,Tc i , y 1,Tc i ,. .. , y ny,Tc i ) is on the twist of the elliptic polynomial, the message point (x 0,m i , x 1,m i ,. .. , x nx,m i , √{square root over ( α y 0,m i , y 1,m i ,. .. , y ny,m i ) is computed as (x 0,m i , x 1,m i ,. .. , x nx,m i , √{square root over ( α y 0,m i , y 1,m i ,. .. , y ny,m i )= (x 0,Tc i , x 1,Tc i ,. .. , x nx,Tc i , √{square root over ( α y 0,Tc i , y 1,Tc i ,. .. , y ny,Tc i ) −(x 0,Tc i-1 , x 1,Tc i-1 ,. .. , x nx,Tc i-1 , √{square root over ( α y 0,Tc i-1 , y 1,Tc i-1 ,. .. , x ny,Tc i-1 ) and (x 0,c i , x 1,c i ,. .. , x nx,c i , y 0,c i , y 1,c i ,. .. , y ny,c i )=(x 0,c i-1 , x 1,c i-1 ,. .. , x nx,c i-1 , y 0,c i-1 , y 1,c i-1 ,. .. , x ny,c i-1 ); and r) recovering the secret message bit string of i-th block from the (nx+1) x-coordinates and the ny y-coordinates of the point (x 0,m i , x 1,m i ,. .. , x nx,m i , y 0,m i , y 1,m i ,. .. , y ny,m i ) if the message point is on the elliptic polynomial, wherein the secret message bit string of the i-th block is recovered from the (nx+1) x-coordinates and the ny y-coordinates of the point (x 0,m i , x 1,m i ,. .. , x nx,m i , √{square root over ( α y 0,m i , y 1,m i ,. .. , y ny,m i ) if the message point is on the twist of the elliptic polynomial.