Patent Document ID: 8385541
Application ID: 12656899
Patent Flag: 1

Claim One:
1. A computerized method of performing elliptic polynomial cryptography with elliptic polynomial hopping, 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 upon a random number k 0 , which is at least part of a shared secret key for communication, a random number generator, a random number kp 0 that is a portion of the shared secret key used for communication, and a set of (nx+1) numbers such that xb i ∈F, wherein i and nx are integers, wherein i=0,. .. , nx, the set being used to find an initial base point, the set being made public; the sending correspondent then performs the following steps: c) generating at least a portion of a set of coefficients b 1l (0) ,b 2lk (0) ∈F of a first elliptic polynomial to be used for a message authentication code of a 0-th message block from the shared secret key kp 0 ; d) embedding the set of (nx+1) numbers xb i ∈F into an elliptic polynomial point to obtain an initial base point (x 0,B (0) ,x 1,B (0) ,. .. , x nx,B (0) ,y B (0) ,α B ) using a data embedding method; e) embedding the 0-th block of the message bit string into an elliptic polynomial message point (x 0,m (0) ,x 1,m (0) ,. .. , x nx,m (0) ,y m (0) ,α m (0) ) using the data embedding method; f) computing a scalar multiplication of the 0-th block shared key k 0 with the base point (x 0,B (0) ,x 1,B (0) ,. .. , x nx,B (0) ,y B (0) ,α B ) as (x 0,kB (0) ,x 1,kB (0) ,. .. , x nx,kB (0) ,y kB (0) ,1)=k(x 0,B (0) ,x 1,B (0) ,. .. , x nx,B (0) ,y B (0) ,α B ); g) computing a cipher point of the 0-th data block (x 0,c (0) ,x 1,c (0) ,. .. , x nx,c (0) ,y c (0) ,α c (0) ) as: 
 ( x 0,c (0) ,x 1,c (0) ,. .. , x nx,c (0) ,y c (0) α c (0) )=( x 0,m (0) ,x 1,m (0) ,. .. , x nx,m (0) ,y m (0) ,α m (0) )+( x 0,kB (0) ,x 1,kB (0) ,. .. , x nx,kB (0) , y kB (0) ,1), wherein α c (0) =α m (0) , and sending a set of appropriate bits of the x-coordinates and a bit indicating the value of α c (0) of the cipher point (x 0,c (0) ,x 1,c (0) ,. .. , x nx,c (0) ,y c (0) ,α c (0) ) to the receiving correspondent; h) establishing integers j and u, such that j=1,. .. , u, and initializing the integer j as j=1 and repeating the following steps i) to m), and incrementing j at each step until all of the message data blocks are processed: i) generating a random number kp j with the random number generator based upon kp j-1 ; j) generating at least a portion of the coefficients b 1l (j) ,b 2lk (j) ∈F of the j-th elliptic polynomial from the random number kp j ; k) embedding the j-th block of the message bit string into a j-th elliptic polynomial message point (x 0,m (j) ,x 1,m (j) ,. .. , x nx,m (j) ,y m (j) ,α m (j) ) using the data embedding method; l) hopping the scalar multiplication point (x 0,kB (j-1) ,x 1,kB (j-1) ,. .. , x nx,kB (j-1) ,y kB (j-1) ,α kB (j-1) ) to an equivalent message authentication code point (x 0,kB (j) ,x 1,kB (j) ,. .. , x nx,kB (j) ,y kB (j) ,α kB (j) ) that satisfies the j-th elliptic polynomial of step j) using the data embedding method; m) computing the cipher point of the j-th data block (x 0,c (j) ,x 1,c (j) ,. .. , x nx,c (j) ,y c (j) ,α c (j) ) as: 
 ( x 0,c (j) ,x 1,c (j) ,. .. , x nx,c (j) ,y c (j) ,α c (j) )=( x 0,m (j) ,x 1,m (j) ,. .. , x nx,m (j) ,y m (j) ,α m (j) )+( x 0,kB (j) ,x 1,kB (j) ,. .. , x nx,kB (j) ,y kB (j) ,α kB (j) ); n) appropriate bits of the x-coordinates and a bit indicating the value of α c (j) of the cipher point (x 0,c (u) ,x 1,c (u) ,. .. , x nx,c (u) ,y c (u) ,α c (j) ) being sent to the receiving correspondent; the receiving correspondent then performs the following steps: o) generating at least a portion of the coefficients b 1l (0) ,b 2lk (0) ∈F of an initial elliptic polynomial to be used for the message authentication code of the 0-th message block from the shared secret key kp 0 ; p) embedding the set of (nx+1) numbers xb i ∈F into an elliptic polynomial point to obtain an initial base point (x 0,B (0) ,x 1,B (0) ,. .. , x nx,B (0) ,y B (0) ,α B ) using the data embedding method; q) computing the scalar multiplication of the 0-th block shared key k 0 with the base point (x 0,B (0) ,x 1,B (0) ,. .. , x nx,B (0) ,y B (0) ,α B ) as (x 0,kB (0) ,x 1,kB (0) ,. .. , x nx,kB (0) ,y kB (0) ,1)=k(x 0,B (0) ,x 1,B (0) ,. .. , x nx,B (0) ,y B (0) ,α B ); r) computing the message point of the 0-th data block (x 0,m (0) ,x 1,m (0) ,. .. , x nx,m (0) ,y m (0) ,α m (0) ) as: 
 ( x 0,m (0) ,x 1,m (0) ,. .. , x nx,m (0) ,y m (0) ,α m (0) )=( x 0,c (0) ,x 1,c (0) ,. .. , x nx,c (0) ,y c (0) ,α c (0) )−( x 0,kB (0) ,x 1,kB (0) ,. .. , x nx,kB (0) ,y kB (0) ,1), wherein α m (0) =α c (0) , and recovering the secret message bit string for the 0-th block from appropriate x-coordinates of the message point x 0,m (0) ,x 1,m (0) ,. .. , x nx,m (0) ,y m (0) ,α m (0) ) if α m (0) =1 and recovering the secret message bit string from a point (gx 0,m (0) ,gx 1,m (0) ,. .. , gx nx,m (0) ,√{square root over (g 3 )}y m (0) ,α m (0) ) if α m (j) =g; s) initializing the integer j as j=1 and repeating the following steps t) to (x), and incrementing j at each step until all of the message data blocks are processed: t) generating a random number kp j with the random number generator based upon kp j-1 ; u) generating at least a portion of the coefficients b 1l (j) ,b 2lk (j) ∈F of the j-th elliptic polynomial from the random number kp j ; v) hopping the scalar multiplication point (x 0,kB (j-1) ,x 1,kB (j-1) ,. .. , x nx,kB (j-1) ,y kB (j-1) ,α kB (j-1) ) to an equivalent message authentication point (x 0,kB (j) ,x 1,kB (j) ,. .. , x nx,kB (j) ,y kB (j) ,α kB (j) ) that satisfies the j-th elliptic polynomial selected in step u) using the data embedding method; w) computing the message point of the j-th received data block (x 0,m (j) ,x 1,m (j) ,. .. , x nx,m (j) ,y m (j) ,α m (j) ) is computed as: 
 ( x 0,m (j) ,x 1,m (j) ,. .. , x nx,m (j) ,y m (j) ,α m (j) )=( x 0,c (j) ,x 1,c (j) ,. .. , x nx,c (j) ,y c (j) ,α c (j) )−( x 0,kB (j) ,x 1,kB (j) ,. .. , x nx,kB (j) ,y kB (j) ,α kB (j) ), wherein α m (j) =α c (j) ; and x) recovering the secret message bit string for the j-th block from appropriate x-coordinates of the message point (x 0,m (j) ,x 1,m (j) ,. .. , x nx,m (j) ,y m (j) ,α m (j) ) if α m (j) =1, and recovering the secret message bit string from the point (gx 0,m (j) ,gx 1,m (j) ,. .. , gx nx,m (j) ,√{square root over (g 3 )}y m (j) ,α m (j) ) if α m (j) =g.