Data encryption system and method

• US 8,670,564 B1
• Filed: 08/14/2007
• Issued: 03/11/2014
• Est. Priority Date: 08/14/2006
• Status: Active Grant

• Current Assignee: Key Holdings, LLC
• Original Assignee: Key Holdings, LLC
• Inventors: Clayton, Ray, Mendoza, Eliel J., Cochran, Ronn Warren
• Primary Examiner(s): Le, Vu
• Application Number:
  US11/838,652
• Time in Patent Office: 2,401 Days
• Field of Search: 380/46
• US Class Current: 380/46
• CPC Class Codes: H04L 2209/16 Obfuscation or hiding, e.g. involving white box
• CPC Class Codes: H04L 9/0816 Key establishment, i.e. cryptographic processes or cryptographic protocols whereby a shared secret becomes available to two or more parties, for subsequent use
• CPC Class Codes: H04L 9/0841 involving Diffie-Hellman or related key agreement protocols
• CPC Class Codes: H04L 9/3013 involving the discrete logarithm problem, e.g. ElGamal or Diffie-Hellman systems
• CPC Class Codes: H04L 9/3236 using cryptographic hash functions

Abstract

A sender apparatus encrypts data using a key. The apparatus then calculates various parameters based on the key and a shared secret between the sender apparatus and a recipient apparatus that is remote from the sender apparatus. The calculated parameters are transmitted to the recipient apparatus, which uses such parameters to calculate the key based on the shared secret. The recipient apparatus then decrypts the data using the calculated key, which does not need to be transmitted from the sender apparatus to the recipient apparatus.

Claims

1. A sender apparatus, comprising:

a processing element;

a transceiver; and

memory for storing data, a first prime number (P), a second prime number (G), a third prime number (C), a first private prime number (Ps), a first random number (M), a second random number (R),

wherein the first private prime number (Ps), the first prime number (P), and the second prime number (G) are used by the processing element to calculate a sender public number (PUB s) according to an equation PUB_s=G^Ps mod P,

wherein the sender public number (PUBs) is provided to a recipient apparatus having knowledge of the first prime number (P), the second prime number (G), and the third prime number (C),

wherein the processing element uses encryption logic and a randomly generated key to encrypt the data,

wherein the processing element deletes the randomly generated key after encryption of the data,

wherein the processing element uses the first prime number (P), the first private prime number (Ps), a recipient public number (PUBr), and the second random number (R) to calculate a common shared secret (S),

wherein the processing element uses a key equation based on the key and the first random number (M) to calculate a plurality of parameters using simultaneous equations,

wherein the third prime number (C) is used in the key equation to calculate a first one (Y1) of the plurality of parameters and the common shared secret (S) is used in the key equation to calculate a second one (Y2) of the plurality of parameters,

wherein the encrypted data, the second random number (R), and the plurality of parameters (Y1,Y2) is transmitted by the transceiver to the recipient apparatus, the recipient apparatus using the first prime number (P), a recipient private prime number (Pr), the sender public number (PUBs), and the second random number (R) to calculate the common shared secret in accordance with a second shared secret equation and to use the common shared secret, the third prime number (C), the plurality of parameters (Y1,Y2) and the simultaneous equations to calculate the key without the key being transmitted to the recipient apparatus.

2. The sender apparatus of claim 1, wherein the sender public number (PUBs) is equal to a dividend modulo a divisor, wherein the dividend is the second prime number (G) raised to the power of the first private prime number (Ps) and the divisor is the first prime number (P).

3. The sender apparatus of claim 1, wherein the first one of the plurality of parameters (Y1) is equal to the key plus the second random number (M) multiplied by the third prime number (C).

4. The sender apparatus of claim 1, wherein the second one of the plurality of parameters (Y2) is equal to the key plus the second random number (M) multiplied by the common shared secret (S).

5. The sender apparatus of claim 1, wherein the common shared secret (S) is calculated using a hashing function performed on a Diffie-Hellman number plus the second random number (R), wherein the Diffie-Hellman number is equal to a dividend modulo a divisor, wherein the dividend is the recipient public number (PUBr) to the power of the first private prime number (Ps) and the divisor is the first prime number (P).

6. The sender apparatus of claim 1, wherein the recipient apparatus comprises:

a recipient processing element;

a recipient transceiver; and

recipient memory for storing data, the first prime number (P), the second prime number (G), the third prime number (C), the recipient private prime number (Pr), wherein the recipient private prime number (Pr), the first prime number (P), and the second prime number (G) are used by the recipient processing element to calculate the recipient public number (PUBr) according to an equation PUB_r=G^Pr mod P.

7. The sender apparatus of claim 6, wherein the recipient public number (PUBr) is equal to a dividend modulo a divisor, wherein the dividend is the second prime number (G) raised to the power of the recipient private prime number (Pr) and the divisor is the first prime number (P).

8. The sender apparatus of claim 1, wherein the second prime number (G) is the smallest quadratic residue mod the first prime number (P).

9. A method for communicating data between a sender device and a receiver device, comprising:

sharing simultaneous equations and a first prime number (P), a second prime number (G) and a third prime number (C) between the sender device and the receiver device via a trusted relationship;

generating a first random number (M), a second random number (R) and a randomly generated key (K) at the sender device;

calculating a plurality of parameters (Y1, Y2) using the first random number (M), the second random number (R), the first prime number (P), the second prime number (G), the third prime number (C), the randomly generated key (K), a calculated shared secret (S), and the simultaneous equations at the sender device, the simultaneous equations defining corresponding relationships between the first random number (M), the second random number (R) and the randomly generated key (K);

encrypting data using the key (K) at the sender device;

deleting the key (K) at the sender device after encryption of the data;

transmitting the encrypted data, the plurality of parameters (Y1, Y2) and the second random number (R) to the receiver device without transmitting the key (K);

generating the key (K) at the receiver device using the plurality of received parameters (Y1, Y2), the calculated shared secret (S), the first random number (M), the received second random number (R), the first prime number (P), the second prime number (G), the third prime number (C) and the simultaneous equations;

decrypting the encrypted data at the receiver device using the generated key (K); and

deleting the generated key (K) at the receiver device after decryption of the data.

10. The method of claim 9 further comprising:

exchanging a sender public number (PUBs) and a recipient public number (PUBr) between the sender device and the receiver device, the sender public number (PUBs) calculated using the first prime number (P), the second prime number (G) and a sender private prime number (Ps) stored in the sender device and the recipient public number (PUBr) calculated using the first prime number (P), the second prime number (G) and a recipient private prime number (Pr) stored in the recipient device, the sender public number (PUBs) used at the recipient device to generate the calculated shared secret and the recipient public number (PUBr) used at the sender device to generate the calculated shared secret.

11. The method of claim 9, wherein the one or more equations are linear equations.

12. The method of claim 9, wherein the one or more prime numbers comprise Diffie-Hellman variables.

13. The method of claim 10, wherein the calculated shared secret (S) is generated at the sender device using a hashing function performed on a Diffie-Hellman number plus the second random number (R), wherein the Diffie-Hellman number is equal to a dividend modulo a divisor, wherein the dividend is the recipient public number (PUBr) to the power of the sender private prime number (Ps) and the divisor is the first prime number (P).

14. The method of claim 10, wherein the calculated shared secret (S) is generated at the receiver device using a hashing function performed on a Diffie-Hellman number plus the second random number (R), wherein the Diffie-Hellman number is equal to a dividend modulo a divisor, wherein the dividend is the sender public number (PUBs) to the power of the recipient private prime number (Pr) and the divisor is the first prime number (P).