Patent Document ID: 8699701
Application ID: 12958300
Patent Flag: 1

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 performing public key XZ-elliptic curve cryptography for use with network security protocols, the instructions comprising: (a) a first set of instructions which, when loaded into main memory and executed by the processor, causes the processor to calculate a shared key as a scalar multiplication between a sending private key k SPr , a receiving private key k RPr and a base point (X B ,Y B ,Z B ) as k SPr (k RPr (X B ,Y B ,Z B )), wherein a sending correspondent and a receiving correspondent select and agree upon an elliptic curve set EC 3 , and the sending correspondent establishes the sending private key k SPr and the receiving correspondent establishes the receiving private key k RPr , the sending correspondent and the receiving correspondent further agreeing upon the base point (X B ,Y B ,Z B )εEC 3 , and the receiving correspondent establishing a receiving public key k RPr (X B ,Y B ,Z B ) and the sending correspondent establishing a sending public key k SPr (X B ,Y B ,Z B ); (b) a second set of instructions which, when loaded into main memory and executed by the processor, causes the processor to embed a secret message bit string into an elliptic curve message point (X m ,Y m ,Z m ), wherein the embedding is performed as: (i) defining the respective message bit string as an M-bit string, wherein M is an integer such that (3N−L)>M>(2N−L), where L is an integer, N represents a number of bits used to represent F(p) elements, F(p) representing a finite field containing the elliptic curve set EC 3 , wherein D represents a set of points on EC 3 , (ii) dividing the respective message bit string into three strings m 1 , m 2 and m 3 , wherein the length of string m 1 is less than or equal to (N−L) bits, the length of string m 2 is less than or equal to (N−1) bits, and the length of string m 3 is less than or equal to N bits; (iii) assigning the value of the bit string m 3 to E m ; (iv) assigning the value of the bit string m 2 to Z m by first assigning the value of the bit string m 2 to R m , then using a Legendre test to determine if R m has a square root, and then, if R m has a square root, setting Z m =R m and if R m does not have a square root, then setting Z m =gR m , wherein g is non-quadratic residue in F(p); (v) computing aZ m 2 and bZ m 2 , wherein a and b are selected scalars; (vi) assigning the value of the bit string m 1 to X m ; (vii) computing a value T as T=X m 3 +(aZ m 2 )X m +(bZ m 3 ) and using a Legendre test to determine if T has a square root; and (viii) assigning the square root of T to Y m if T has a square root, and incrementally increasing X m and returning to step (vii) if T does not have a square root; (c) a third set of instructions which, when loaded into main memory and executed by the processor, causes the processor to compute a cipher point (X c ,Y c ,Z c ) as (X c ,Y c ,Z c )=(X m ,Y m ,Z m )+k SPr (k RPr (X B ,Y B ,Z B )); (d) a fourth set of instructions which, when loaded into main memory and executed by the processor, causes the processor to record a set of appropriate bits of X c and Z c as an encoded bit string and sending the set of appropriate bits of X c and Z c forming the encoded bit string to the receiving correspondent; (e) a fifth set of instructions which, when loaded into main memory and executed by the processor, causes the processor to calculate the shared key as k RPr (k SPr (X B ,Y B ,Z B )); (f) a sixth set of instructions which, when loaded into main memory and executed by the processor, causes the Processor to compute the elliptic curve message point (X m ,Y m ,Z m ) as (X m ,Y m ,Z m )=(X c ,Y c ,Z c )−k RPr (k SPr (X B ,Y B ,Z B )); (g) a seventh set of instructions which, when loaded into main memory and executed by the processor, causes the processor to retrieve the first secret message bit string from X m and Z m ; (h) an eighth set of instructions which, when loaded into main memory and executed by the processor, causes the processor to select a random integer k, wherein the random integer k is modulo p, wherein p is a selected integer 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 compute a scalar multiplication for a first signature point (X 1 ,Y 1 ,Z 1 ) as (X 1 ,Y 1 ,Z 1 )=k (X B ,Y B ,Z B ) at the sending correspondent; (j) a tenth set of instructions which, when loaded into main memory and executed by the processor, causes the processor to concatenate bit strings of X 1 and Z 1 together to form a single bit string [X 1 :Z 1 ] at the sending correspondent; (k) an eleventh set of instructions which, when loaded into main memory and executed by the processor, causes the processor to convert the single bit string [X 1 :Z 1 ] into an integer r mod p at the sending correspondent; (l) a twelfth set of instructions which, when loaded into main memory and executed by the processor, causes the processor to compute a message digest digest(M), wherein digest(M) is a bit string dependent upon secret message M, and converting the bit string into an integer e at the sending correspondent; (m) a thirteenth set of instructions which, when loaded into main memory and executed by the processor, causes the processor to compute a signature value s as s=k −1 (e+k Pr r)mod p at the sending correspondent: (n) a fourteenth set of instructions which, when loaded into main memory and executed by the processor, causes the processor to generate a digital signature of the message M as (r,s) at the sending correspondent; (o) a fifteenth set of instructions which, when loaded into main memory and executed by the processor, causes the processor to compute the message digest digest(M) and converting the bit string into an integer e 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 compute a pair of intermediate values u 1 and u 2 as u 1 =es −1 mod p and u 2 =rs −1 mod p, respectively, at the receiving correspondent; (q) a seventeenth set of instructions which, when loaded into main memory and executed by the processor, causes the processor to compute a scalar multiplication for a second signature point (X 2 ,Y 2 ,Z 2 ) as (X 2 ,Y 2 ,Z 2 )=u 1 (X B ,Y B ,Z B )+u 2 (X Pu ,Y Pu ,Z Pu ) at the receiving correspondent; (r) an eighteenth set of instructions which, when loaded into main memory and executed by the processor, causes the processor to concatenate bit strings of X 2 a Z 2 together to form a single bit string [X 2 :Z 2 ] at th receiving correspondent; (s) a nineteenth set of instructions which, when loaded into main memory and executed by the processor, causes the processor to convert the single bit string [X 2 :Z 2 ] into an integer v mod p at the receiving correspondent; and (t) a twentieth set of instructions which, when loaded into main memory and executed by the processor, causes the processor to accept the digital signature if v=r at the receiving correspondent.