Modular key exchange for key agreement and optional authentication

1. A method of generating a shared secret by a first device, wherein the shared secret is shared between the first device and a second device, comprising:

checking a certificate including the second device's public key Y;

randomly generating an ephemeral private key r;

computing an ephemeral public key R based upon the ephemeral private key r and a generator G, where the generator G is an element of a group ;

computing a semi-static shared secret R′ based upon the ephemeral private key r and the device's public key Y;

encrypting a certificate for the first device's public key X using a hash of the semi-static shared secret R′ as an encryption key;

transmitting to the second device the ephemeral public key R and the encrypted certificate for the first device's public key X;

receiving from the second device an ephemeral public key S;

checking that the ephemeral public key S is an element of the group ;

computing an ephemeral shared secret Z′ based upon the ephemeral private key r and the ephemeral public key S;

computing a semi-static shared secret S′ based upon a private key x of the first device, the ephemeral private key r, the ephemeral public key S, and the ephemeral shared secret Z′; and

computing the shared secret Z as the hash of the ephemeral shared secret Z′, the semi-static shared secret R′, the semi-static shared secret S′, the first device's public key X, and the second device's public key Y.

2. The method of claim 1 , wherein calculating a semi-static shared secret S′ further comprises calculating: S′=(x−r)·S+Z′.

3. The method of claim 1 , wherein the hash for computing the shared secret Z further includes a password w.

4. The method of claim 1 , wherein

the second device's certificate includes a second device extended public key Y′ where Y′=y·G′,

computing an ephemeral public key R further comprises calculating R=r·(G+π·G′), where π is the hash of a password and the generator G′ is an element of a group , and

computing a semi-static shared secret R′ further comprises calculating R′=r·(Y+π·Y′).

5. The method of claim 4 , wherein computing a semi-static shared secret S′ comprises calculating S′=(x−r+π)·S+Z′.

6. A method of generating a shared secret by a second device, wherein the shared secret is shared between a first device and the second device, comprising:

randomly generating an ephemeral private key S;

computing an ephemeral public key S based upon the ephemeral private key S and a generator G, where the generator G is an element of a group G;

receiving from the first device an ephemeral public key R and an encrypted certificate for the first device's public key X;

transmitting to the second device the ephemeral public key S;

checking that the ephemeral public key R is an element of the group G;

calculating an ephemeral shared secret Z′ based upon the ephemeral private key S and the ephemeral public key R;

calculating a semi-static shared secret R′ based upon a private key Y of the second user, the ephemeral private key S, the ephemeral public key R, and the ephemeral shared secret Z′;

decrypting the encrypted certificate for the first device's public key using a hash of the semi-static shared secret R′ as a decryption key;

checking the certificate for the first device's public key;

computing a semi-static shared secret S′ based upon the ephemeral private key S and the first device's public key X; and

computing the shared secret Z as the hash of the ephemeral shared secret Z′, the semi-static shared secret R′, the semi-static shared secret S′, the first device's public key X, and the second device's public key Y.

7. The method of claim 6 , wherein calculating a semi-static shared secret R′ further comprises calculating: R′=(y−s)·R+Z′.

8. The method of claim 6 , wherein the hash for computing the shared secret Z further includes a password w.

9. The method of claim 6 , wherein

computing an ephemeral public key S further comprises calculating S=s·(G+π·G′), where π is the hash of a password and the generator G′ is an element of a group ,

the first device's certificate includes a first device extended public key X′ where X′=x·G′,

and

computing a semi-static shared secret S′ further comprises calculating S′=s·(X+π·X′).

10. The method of claim 6 , wherein

computing an ephemeral public key S further comprises calculating S=s·G 90 , where G π =G+π·G′, π is the hash of a password, and the generator G′ is an element of a group , and

computing a semi-static shared secret S′ comprises calculating S′=s·{tilde over (X)} π , where {tilde over (X)} π =X+π·X′+π·G π and X′ is a first device extended public key where X′=x·G′.

11. A method of generating a shared secret by a first device, wherein the shared secret is shared between the first device and a second device comprising:

randomly generating an ephemeral private key r;

computing an ephemeral public key R based upon the ephemeral private key r and a generator G, where the generator G is an element of a group ;

transmitting to the second device the ephemeral public key R;

receiving from the second device an ephemeral public key S and an encrypted certificate including the second device's public key Y;

checking that the ephemeral public key S is an element of the group ;

computing an ephemeral shared secret Z′ based upon the ephemeral private key r and the ephemeral public key S;

decrypting the encrypted certificate for the second device's public key;

checking the certificate for the second device's public key Y;

computing a semi-static shared secret R′ based upon the ephemeral private key r and the second device's public key Y;

encrypting a certificate including the first device's public key X using a hash of the semi-static shared secret R′ as an encryption key;

transmitting to the second device the encrypted certificate for the first device's public key X;

computing a semi-static shared secret S′ based upon a private key x of the first user, the ephemeral private key r, the ephemeral public key S, and the ephemeral shared secret Z′; and

computing the shared secret Z as the hash of the ephemeral shared secret Z′, the semi-static shared secret R′, the semi-static shared secret S′, the first device's public key X, and the second device's public key Y.

12. The method of claim 11 , wherein calculating a semi-static shared secret S′ further comprises calculating: S′=(x−r)·S+Z′.

13. The method of claim 1 , wherein the hash for computing the shared secret Z further includes a password w.

14. The method of claim 11 , wherein

the second device's certificate for a second device extended public key Y′ where Y′=y·G′,

computing an ephemeral public key R further comprises calculating R=r·(G+π·G′), where π is the hash of a password and the generator G′ is an element of a group , and

computing a semi-static shared secret R′ further comprises calculating R′=r·(Y+π·Y′).

15. The method of claim 14 , wherein computing a semi-static shared secret S′ comprises calculating S′=(x−r+π)·S+Z′.

16. A method of generating a shared secret by a second device, wherein the shared secret is shared between a first party-device and the second device, comprising:

randomly generating an ephemeral private key S;

computing an ephemeral public key S based upon the ephemeral private key S and a generator G, where the generator G is an element of a group G;

receiving from the first device an ephemeral public key R;

checking to verify that the ephemeral public key R is an element of the group G;

calculating an ephemeral shared secret Z′ based upon the ephemeral private key S and the ephemeral public key R;

encrypting a certificate for the second device's public key Y using a hash of the ephemeral shared secret Z′ as an encryption key;

transmitting to the second device the ephemeral public key S and the encrypted certificate for the second device's public key Y;

calculating a semi-static shared secret R′ based upon a private key Y of the second user, the ephemeral private key S, the ephemeral public key R, and the ephemeral shared secret Z′;

receiving from the first device an encrypted certificate for the first device's public key X;

decrypting the encrypted certificate for the first device's public key using a hash of the semi-static shared secret R′ as a decryption key;

checking the certificate for the first device's public key;

computing a semi-static shared secret S′ based upon the ephemeral private keys and the first device's public key X; and

computing the shared secret Z as the hash of the ephemeral shared secret Z′, the semi-static shared secret R′, the semi-static shared secret S′, the first device's public key X, and the second device's public key Y.

17. The method of claim 16 , wherein calculating a semi-static shared secret R′ further comprises calculating: R′=(y−s)·R+Z′.

18. The method of claim 16 , wherein the hash for computing the shared secret Z further includes a password w.

19. The method of claim 16 , wherein

computing an ephemeral public key S further comprises calculating S=s·(G+π·G′), where π is the hash of a password and the generator G′ is an element of a group ,

the first device's certificate includes a first device extended public key X′ where X′=x·G′,

and

computing a semi-static shared secret S′ further comprises calculating S′=s·(X+π·X′).

20. The method of claim 16 , wherein

computing an ephemeral public key S further comprises calculating S=s·G π , where G π =G+π·G′, π is the hash of a password, and the generator G′ is an element of a group , and

computing a semi-static shared secret S′ comprises calculating S′=s·{tilde over (X)} π , where {tilde over (X)} π =X+π·X′+π·G π and X′ is a first device extended public key where X′=x·G′.