Granted Patent B2

US 10,355,859 · App. 15/470,259 · Granted Jul 16, 2019

Abstract

Claims (39)

1. A method for a Diffie Hellman key exchange, the method comprising:

selecting a field size p in the form p=hq+1, where q is a prime number that is one plus a factorial number b, such that q=(b!+1), and h is a cofactor, such that p=hq+1 is prime;

selecting a generator integer g whose order modulo p is the prime q or is divisible by q;

choosing a private key x;

computing a public key gx mod p by raising said generator g to the power of said private key x, using arithmetic modulo said prime field size p;

sending said public key gx mod p to a correspondent;

receiving, from the correspondent, a second public key B comprising g raised to a second private key y selected by the correspondent, in the form gy;

creating a key Bx from the received second public key B, by raising said second public key B to the power of said private key x, using arithmetic modulo said prime field size p; and

using the key Bx for secure electronic communications with the correspondent.

2. The method of claim 1 , wherein b is chosen so the prime order exceeds a minimal threshold size.

3. The method of claim 2 , wherein the minimal threshold size is 3000 bits.

4. The method of claim 3 , wherein b is selected to be 427.

5. The method of claim 4 , Wherein h is selected to be a 630, resulting in p=630(427!+1)+1.

6. The method of claim 3 , wherein b is selected to be 872.

7. The method of claim 6 , wherein h is selected to be 1398, resulting in p=1398(872!+1)+1.

8. A computing device configured for a Diffie Hellman key exchange, the computing device comprising a processor configured to:

select a field size p in the form p=hq +1, where q is a prime number that is one plus a factorial number b, such that q=(b!+1), and h is a cofactor, such that p=hq +1 is prime;

select a generator integer g whose order modulo p is the prime q or is divisible by q;

choose a private key x;

compute a public key gx mod p by raising said generator g to the power of said private key x, using arithmetic modulo said prime field size p;

send said public key gx mod p to a correspondent;

receive, from the correspondent, a second public key B comprising g raised to a second private key y selected by the correspondent, in the form gy;

create a key Bx from the received second public key B, by raising said second public key B to the power of said private key x, using arithmetic modulo said prime field size p; and

using the key Bx for secure electronic communications with the correspondent.

9. The computing device of claim 8 , wherein b is chosen so the prime order exceeds a minimal threshold size.

10. The computing device of claim 9 , wherein the minimal threshold size is 3000 bits.

11. The computing device of claim 10 , wherein b is selected to be 427.

12. The computing device of claim 11 , wherein h is selected to be a 630, resulting in p=630(427!+1)+1.

13. The computing device of claim 10 , wherein b is selected to be 872.

14. The computing device of claim 13 , wherein h is selected to be 1398, resulting in p=1398(872!+1)+1.

15. A computer readable medium comprising program code, that when executed by a processor of a computing device is configured for a Diffie Hellman key exchange, the program code causing the computing device to:

select a field size p in the form p=hq+1, where q is a prime number that is one plus a factorial number b, such that q =(b!+1), and h is a cofactor, such that p=hq+1 is prime;

select a generator integer g Whose order modulo p is the prime q or is divisible by q;

choose a private key x;

compute a public key gx mod p by raising said generator g to the power of said private key x, using arithmetic modulo said prime field size p;

send said public key gx mod p to a correspondent;

receive, from the correspondent, a second public key B comprising g raised to a second private key y selected by the correspondent, in the form gy;

create a key Bx from the received second public key B, by raising said second public key B to the power of said private key x, using arithmetic modulo said prime field size p; and

using the key Bx for secure electronic communications with the correspondent.

Assignments (8)