In 2018, Castryck et al [4] came up with a new method named CSIDH, and was an efficient way to create public keys. The method thus allows a direct replacement for the commonly used ECDH key exchange method and can be plugged into zero-RTT methods (such as QUIC) [article].
CSIDH with Go |
Theory
Many of our existing public key methods, including elliptic curve and RSA will be broken within a post-quantum era. Thus we need to find more robust methods for our key exchange techniques. One of the most interesting, both in terms of key sizes and performance, is SIDH (Supersingular Isogeny Diffie-Hellman). With this we have two elliptic curves (E1 and E2), and we can create a function that maps point (P) on E1 to a point Q on E2. This function is known as an isogeny. If we can map this function, every point on E1 can then be mapped to E2. Our secret key is then the isogeny, and the public key is the elliptic curve that we are using. For key exchange, Bob and Alice mix their isogeny and the other side's curve to generate a secret curve.
As part of NIST's approval process, SIDH is one of the front runners for standardization. Along with this there is a great deal of activity with the research community to study isogenies. In 2018, Castryck et al came up with a new method named CSIDH and which had smaller key sizes. It also has an efficient way to create the public keys. The method thus allow a direct replacement for the commonly used ECDH key exchange method, and can be plugged into zero-RTT methods (such as QUIC).
As with ECDH, CSIDH allows for the exchange of public keys in a non-interactive way. Bob just creates a new private key (b), and Alice does the same (a). They create their public keys and exchange them, and finally end up with the same shared key.
With CSIDH, we initally define a large prime number (\(p\)) and an ellipitic curve (\(E_0\)):
\( y^2 = x^3 + x \pmod p\)
This is a finite field over \(p\) and over an integer (\(Z\)). The public key becomes the \(P\) coefficient of the elliptic curve:
\( y^2 = x^3 + Px^2 + x\)
Alice then creates a random set of integers between \(−Z\) and \(Z\) and creates a class of integers \([a]\). This is her private key. She then starts with \(y^2 = x^3 + x\) and acts on the curve using [a] and ends up with \(E_A\):
\( y^2 = x^3 + Ax^2 + x\)
The value of \(A\) is her public key. An example of Alice's private key shows the random number generation for \([a]\):
{{f150475eaab1bcc91ff68b90187817f2f434f228f665466ad00912adc7551af513d5e1661650ce335f5bd0322b3c32b2bf8bed2da8f2e2b5ad19039eadf9b391} [2c f -4b -42 5f 3e -25 -1b 1d 51 51 e 5f 41 44 -11 45 2c 21 -33 43 2e 20 52 -10 32 -35 53 4c -2e 2e 1e -4e 32 -33 -e 45]}
and the public key with:
{{8ab3d9327db91a65139050bd35b49d6a551d3053851cd04527c578f6c207dd1afae2797774ffe949b80326be4ce41c8a3c4c4fb3124c0dcbf1d54216cdcd3dd3} [d42da16e50e1329a 9cc4b2c756ee0569 da2450bc0c8fb0e8 789387159d5dc6ce fac9d03d6c2df4b1 be61ffd36d62580a 133a53a471100843 3bca3d90ad7ac0d6]}
This is 512-bit cSIDH and has a prime number with 511 bits. The private key has 37 bytes, and the public key has 64 bytes, and where the shared secret is also 64 bytes long (512 bits).
For Bob we start with \([b]\) and end up with \(E_B\):
\( y^2 = x^3 + Bx^2 + x\)
Alice sends \(([a],A)\) and Bob sends \(([b],B)\). When received, Bob and Alice check that the received curves are a supersingular. Alice applies her secret key \([a]\) to \(E_B\) to derive:
\( E_R = [a] E_B = [a][b] E_0\)
and Bob derives:
\( E_R = [b] E_A= [b][a] E_0\)
This should be the same curve of:
\( E_R: y^2 = x^3 + Rx^2 + x\)
This operation is commutative (\(a \times b = b \times a\)), and thus we can use it in a Diffie-Hellman type exchange.
Coding
The following is an outline (based on code [here]):
package main import ( "crypto/rand" "fmt" "github.com/cloudflare/circl/dh/csidh" ) var rng = rand.Reader func main() { var alice_secret, bob_secret [64]byte // 512 bit share var alice_priv, bob_priv csidh.PrivateKey var alice_pub, bob_pub csidh.PublicKey // Alice generates random secret, and then public key csidh.GeneratePrivateKey(&alice_priv, rng) csidh.GeneratePublicKey(&alice_pub, &alice_priv, rng) // Bob generates random secret, and then public key csidh.GeneratePrivateKey(&bob_priv, rng) csidh.GeneratePublicKey(&bob_pub, &bob_priv, rng) csidh.DeriveSecret(&bob_secret, &alice_pub, &bob_priv, rng) csidh.DeriveSecret(&alice_secret, &bob_pub, &alice_priv, rng) fmt.Printf("\n\nAlice private: %x\nAlice public: %x\n", alice_priv,alice_pub) fmt.Printf("\n\nBob private: %x\nBob public: %x\n", bob_priv,bob_pub) fmt.Printf("\n\nAlice shared: %x\nBob shared: %x\n", alice_secret,bob_secret) }
A sample run is:
Alice private: {{a3eea2f4b0d1431e0c1b9b3c4bb8249fcfdd7b5cc15b7ee8707cf94a984ebb52c24a17f39ddfcff827a2210d4a15d7e73b9e38705103eb818cfb7e26211dfce3} [3c -35 -3b 1b 23 -34 2 53 d -12 1e -2b -2b 1b -30 d -20 3c 20 -14 35 34 -3b 4b 2f 2b -4d -1f 20 -1 c -12 -23 4d -40 4 34]} Alice public: {{a8f75500dac49bdbead57e594cdfbea6e32d0e42d8099fbe2d5073f033042597e0510bce35e47f6de4027d49d36161a0e2aa8c5c9fcf5510d3b8f94bc6f8cd97} [2633bcc1810cd558 5d8b5106afb2e346 8516a122babc7759 63cd578f918c1bf8 a673a03411a0d1f0 6e0951c9291ac85d e6fb8a66f3e1b77a 5332648d1050fd7e]} Bob private: {{d251abbad826db66b60d3b3d91abd93bfa7a184a425858f507c69f109aae6ce8a4bc1c8c6f709f418e99e71cb9e7c0bfde77aa146e94526e575fee47d61c4aaa} [-c 5e e -4 -4d -1c 4e -20 -2c 4e 53 -41 1e -22 10 -10 2e -11 2b -42 5e -35 -1d 31 -35 3e -4d 11 e 5 2f 1c -4d 23 -4f -2d -42]} Bob public: {{9978e81f1fc2e27d2a158639d974b98c285e3ce3bc90bee29414b98373150ea59694edbbf78ec8ad7738baf19b362113d487e8f87ab4b4d8a28a6f6f4a2d7b40} [2633bcc1810cd558 5d8b5106afb2e346 8516a122babc7759 63cd578f918c1bf8 a673a03411a0d1f0 6e0951c9291ac85d e6fb8a66f3e1b77a 5332648d1050fd7e]} Alice shared: 58d50c81c1bc332646e3b2af06518b5d5977bcba22a11685f81b8c918f57cd63f0d1a01134a073a65dc81a29c951096e7ab7e1f3668afbe67efd50108d643253 Bob shared: 58d50c81c1bc332646e3b2af06518b5d5977bcba22a11685f81b8c918f57cd63f0d1a01134a073a65dc81a29c951096e7ab7e1f3668afbe67efd50108d643253
References
[1] https://www.academia.edu/32263564/Introduction_to_Supersingular_Isogeny_Diffie-Hellman
[2] De Feo, Luca, David Jao, and Jérôme Plût. "Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies." Journal of Mathematical Cryptology 8.3 (2014): 209–247.
[3] Costello, C., Longa, P., & Naehrig, M. (2016, August). Efficient algorithms for supersingular isogeny Diffie-Hellman. In Annual Cryptology Conference (pp. 572–601). Springer, Berlin, Heidelberg.
[4] Wouter Castryck, Tanja Lange, Chloe Martindale, Lorenz Panny, Joost Renes. "CSIDH: An Efficient Post-Quantum Commutative Group Action". Date: 2018.11.18. ASIACRYPT 2018, LNCS 11274, pages 395–427.
[5] Childs, A., Jao, D., & Soukharev, V. (2014). Constructing elliptic curve isogenies in quantum subexponential time. Journal of Mathematical Cryptology, 8(1), 1–29.