RSA-ANALOGOUS XZ-ELLIPTIC CURVE CRYPTOGRAPHY SYSTEM AND METHOD

• US 20120140921A1
• Filed: 12/01/2010
• Published: 06/07/2012
• Est. Priority Date: 12/01/2010
• Status: Abandoned Application

• Current Assignee: King Fahd University Of Petroleum And Minerals
• Original Assignee: King Fahd University Of Petroleum And Minerals
• Inventors: GHOUTI, LAHOUARI, IBRAHIM, MOHAMMAD K.
• Application Number:
  US12/958,337
• Publication Number:
  US 20120140921A1
• Time in Patent Office: Days
• US Class Current: 380/44
• CPC Class Codes: H04L 9/003 for power analysis, e.g. differential power analysis [DPA] or simple power analysis [SPA]
• CPC Class Codes: H04L 9/302 involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes
• CPC Class Codes: H04L 9/3073 involving pairings, e.g. identity based encryption [IBE], bilinear mappings or bilinear pairings, e.g. Weil or Tate pairing

Abstract

The RSA-analogous XZ-elliptic curve cryptography system and method provides a computerized system and method that allows for the encryption of messages through elliptic polynomial cryptography and, particularly, in a manner which is analogous to RSA cryptography but which does not require multiple private keys, as in the RSA scheme. The RSA-analogous XZ-elliptic curve cryptography method is based on the integer factorization problem. It is well known that the integer factorization problem is a computationally “difficult” or “hard” problem.

Claims

1. A computerized method of performing RSA-analogous XZ-elliptic curve cryptography, comprising the steps of:

(a) selecting a pair of substantially large prime numbers p and q, and selecting a pair of values g_u and g_v, wherein g_u is non-residue of p and g_v is non-residue of q;

(b) selecting a pair of scalars a and b such that gcd(4a³+27b²,pq)=1;

(c) calculating an order N_p of an elliptic curve Y²=X³+aXZ²+bZ³ over a finite field F(p), wherein X, Y and Z are orthogonal Cartesian coordinates;

(d) calculating an order N_tp of a curve g_uY²=X³+aXZ²+bZ³ over the finite field F(p);

(e) calculating an order N_q of the elliptic curve Y²=X³+aXZ²+bZ³ over the finite field F(q);

(f) calculating an order N_tq of a curve g_vY²=X³+aXZ²+bZ³ over the finite field F(q);

(g) selecting a scalar e such that gcd(e,N_p)=gcd(e,N_q)=1;

(h) generating a secret key d as

2. The computerized method of performing RSA-analogous XZ-elliptic curve cryptography as recited in claim 1, wherein N_p=N_tp and N_q=N_tq.

3. The computerized method of performing RSA-analogous XZ-elliptic curve cryptography as recited in claim 2, wherein a receiving correspondent generates and publishes the public key in steps (a) through (i).

4. The computerized method of performing RSA-analogous XZ-elliptic curve cryptography as recited in claim 3, wherein a sending correspondent performs encryption of the message data string in steps (j) and (k).

5. The computerized method of performing RSA-analogous XZ-elliptic curve cryptography as recited in claim 4, wherein following step (k), the sending correspondent sends the X-coordinate and the Z-coordinate of the cipher point (X_c,Y_c,Z_c) to the receiving correspondent.

6. The computerized method of performing RSA-analogous XZ-elliptic curve cryptography as recited in claim 5, wherein the receiving correspondent performs decryption of the message data string in steps (l) and (m).

7. The computerized method of performing RSA-analogous XZ-elliptic curve cryptography as recited in claim 6, wherein the step of embedding includes the steps of:

(a) defining the message data string as an M-bit string, wherein M is an integer such that (2N−

L)>

M>

(2N−

L), where L is an integer, and N represents a number of bits used to represent the elements of F(p);

(b) dividing the message bit string into two strings m₁ and m₂, wherein the length of string m₁ is less than or equal to (N−

L) bits and the length of string m₂ is less than or equal to (N−

1) bits;

(c) assigning the value of the bit string m₂ to a variable R_m;

(d) using a Legendre test to determine if R_m has a square root, and if R_m has a square root, setting a variable Z_m equal to R_m, and if R_m does not have a square root, then setting Z_m=gR_m, where g is non-quadratic residue in F(p);

(e) computing aZ_m² and bZ_m³, where a and b are selected scalars;

(f) assigning the value of the bit string m₁ to X_m;

(g) computing a value T as T=X_m³+(aZ_m²)X_m+(bZ_m³) and using a Legendre test to determine if T has a square root; and

(h) assigning the square root of T to Y_m if T has a square root, and incrementally increasing X_m and returning to step (g) if T does not have a square root.

8. A system for performing RSA-analogous XZ-elliptic curve cryptography, comprising:

a processor;

computer readable memory coupled to the processor;

a user interface coupled to the processor;

a display coupled to the processor;

software stored in the memory and executable by the processor, the software having;

means for selecting a pair of substantially large prime numbers p and q, and selecting a pair of values g_u and g_v, wherein g_u is non-residue of p and g_v is non-residue of q;

means for selecting a pair of scalars a and b such that gcd(4a³+27b², pq)=1;

means for calculating an order N_p of an elliptic curve Y²=X³+aXZ²+bZ³ over a finite field F(p), wherein X, Y and Z are orthogonal Cartesian coordinates;

means for calculating an order N_tp of a curve g_uY²=X³+aXZ²+bZ³ over the finite field F(p);

means for calculating an order N_q of the elliptic curve Y²=X³+aXZ²+bZ³ over the finite field F(q);

means for calculating an order N_tq of a curve g_vY²=X³+aXZ²+bZ³ over the finite field F(q);

means for selecting a scalar e such that gcd(e,N_p)=gcd(e,N_q)=1;

means for generating a secret key d as

9. The system for performing RSA-analogous XZ-elliptic curve cryptography as recited in claim 8, wherein N_p=N_tp and N_q=N_tq.

10. A computer software product that includes a medium readable by a processor, the medium having stored thereon a set of instructions for performing RSA-analogous XZ-elliptic curve cryptography, the instructions comprising:

(a) a first sequence of instructions which, when executed by the processor, causes the processor to select a pair of substantially large prime numbers p and q, and selecting a pair of values g_u and g_v, wherein g_u is non-residue of p and g_v is non-residue of q;

(b) a second sequence of instructions which, when executed by the processor, causes the processor to select a pair of scalars a and b such that gcd(4a³+27b²,pq)=1;

(c) a third sequence of instructions which, when executed by the processor, causes the processor to calculate an order N_p of an elliptic curve Y²=X³+aXZ²+bZ³ over a finite field F(p), wherein X, Y and Z are orthogonal Cartesian coordinates;

(d) a fourth sequence of instructions which, when executed by the processor, causes the processor to calculate an order N_tp of a curve g_uY²=X³+aXZ²+bZ³ over the finite field F(p);

(e) a fifth sequence of instructions which, when executed by the processor, causes the processor to calculate an order N_q of the elliptic curve Y²=X³+aXZ²+bZ³ over the finite field F(q);

(f) a sixth sequence of instructions which, when executed by the processor, causes the processor to calculate an order N_tq of a curve g_vY²=X³+aXZ²+bZ³ over the finite field F(q);

(g) a seventh sequence of instructions which, when executed by the processor, causes the processor to select a scalar e such that gcd(e,N_p)=gcd(e,N_q)=1;

(h) an eighth sequence of instructions which, when executed by the processor, causes the processor to generate a secret key d as