Supersingular Isogeny Key Encapsulation (SIKE) is a post-quantum cryptography key encapsulation method for key exchange, and is based on Supersingular Isogeny Diffie-Hellman (SIDH). It has a similar methodology to the Diffie-Hellman method, but is quantum robust. It was created by Luca de Feo, David Jao and Jerome Plut [2][paper] and enhanced by Craig Costello, Patrick Longa, and Michael Naehrig at Microsoft [3][paper], and has one of the smallest key sizes for quantum robust crypo methods (where the public keys is 751 bytes). In elliptic curve methods the public key is only 32 bytes. It also supports perfect forward secrecy (PFS) and which stops the long-term key from being compromised, on the cracking of a single key (neither NTRU [here] Ring-LWS [here] are setup for PFS). Optimised code has shown the key parameters can be generated with 200 milliseconds, and the code has even been ported to ARM processors. The method is still relatively slow compared with elliptic curve methods (and requires around 50 million cycles of a processor).
SIKE with Go |
Theory
If we have two elliptic curves (\(E_1\) and \(E_2\)), we can create a function that maps a point (P) on \(E_1\) to a point Q on \(E_2\). This function is known as an isogeny. If we can map this function, every point on \(E_1\) can be mapped to \(E_2\). Our secret key is then the isogeny, and the public key is the elliptic curve. For key exchange, Bob and Alice mix their isogeny and the other side's curve to generate a secret curve.
With isogeneous elliptic curves we thus do not deal with a single elliptic curve but a family of them [paper]. An isogeny is then a map \(\phi\) : \(E_1\) -> \(E_2\) and where points on the source curve \(E_1\) map to the target curve \(E_2\). It turns out that for every isogeny \(\phi\): \(E_1\) -> \(E_2\), there's a dual isogeny \(\phi\): \(E_2\) -> \(E_1\), so we can say that two curves are isogenous if they're linked by an isogeny.
Let's take an example of Bob and Alice generating the same shared key (as we do with the Diffie-Hellman methods). First Alice has a starting curve of \(E_0\), and four points on that curve: \(P_A\), \(Q_A\), \(P_B\), \(Q_B\).
Alice then select two random values \(m_a\) and \(n_A\) and keeps these secret. These will be scalar values.
She then determines a secret point \(R_a\) which is:
\(R_a = m_a \times P_a + n_a \times Q_a \)
This is her secret isogeny (\(\phi_a\)).
She then transforms \(P_b\) and \(P_q\) with this isogeny, and where Alice evaluates \(\phi_A\) at point \(P_b\), and at \(Q_b\).
She then sends \(E_a\) (her public key), and two transformed points (\(\phi_A(P_b)\) and \(\phi_A(Q_b)\)) to Bob.
Bob does the same, but swaps the a and b values \(P_a\) for \(P_b\), \(Q_a\) for \(Q_b\) and vice versa. He will generate his own random values \(m_b\) and \(n_b\). Bob calculates his secret: (\(\phi_B\)).
The following defines the exchange [1]:
Next, Alice uses \(E_a\), \(\phi_a(P_a)\), \(\phi_b(Q_a)\) to construct an isogeny \(\phi'_a\) using \(m_a \times \phi_a(P_a) + n_a \times \phi_b(q_a)\).
Bob uses \(E_a\), \(\phi_a(P_b)\), \(\phi_a(Q_b)\) to construct an isogeny \(\phi'_b\) using \(m_b \times \phi_a(P_b) + n_b \times \phi_a(Q_b)\).
Now \(\phi'a\) maps to a curve \(E_{ab}\), and \(\phi'_b\) maps to \(E_{ba}\), and we can define them is isomorphic. After this, we can calculate a value from the j-invariant, and where \(j(E_{ab})\) is equal to \(j(E_{ba})\), and this will be the same shared secret between Bob and Alice. For a curve of \(y^2 = x^3 + px + q\), the j-invariant is:
\(j = 1728 \frac{4p^3}{4p^3 + 27q^2}\)
At the end of this, Bob and Alice will have the same key, and they will know that a quantum computer will not be able to crack it, and that no previous keys can be cracked.
Coding
The following is an outline (based on code [here]):
package main import ( "bytes" "crypto/rand" "fmt" "github.com/cloudflare/circl/dh/sidh" ) func main() { prvA := sidh.NewPrivateKey(sidh.Fp503, sidh.KeyVariantSike) pubA := sidh.NewPublicKey(sidh.Fp503, sidh.KeyVariantSike) prvB := sidh.NewPrivateKey(sidh.Fp503, sidh.KeyVariantSike) pubB := sidh.NewPublicKey(sidh.Fp503, sidh.KeyVariantSike) prvA.Generate(rand.Reader) prvA.GeneratePublicKey(pubA) prvB.Generate(rand.Reader) prvB.GeneratePublicKey(pubB) fmt.Printf("Alice private: %x\nAlice public: %x\n", *prvA, *pubA) fmt.Printf("Bob private: %x\nBob public: %x\n", *prvB, *pubB) var kem = sidh.NewSike503(rand.Reader) ct := make([]byte, kem.CiphertextSize()) ssE := make([]byte, kem.SharedSecretSize()) ssD := make([]byte, kem.SharedSecretSize()) kem.Encapsulate(ct, ssE, pubB) kem.Decapsulate(ssD, prvB, pubB, ct) fmt.Printf("%t\n", bytes.Equal(ssE, ssD)) kem.Encapsulate(ct, ssE, pubA) kem.Decapsulate(ssD, prvA, pubA, ct) fmt.Printf("\nAlice shared: %x\nBob shared: %x \nEqual: %t\n", ssE,ssD,bytes.Equal(ssE, ssD)) }
A sample run is:
Alice private: {{c000049c00 6} 53a6702212c581353efe328ab5cd2d69a6e3d0ad9ee046c15c05e34844353608 3312d40ebe210cb860a9717564470e797dff2cce6cc6dc31} Alice public: {{c00004a300 6} [{[8cc865ea84d9aae5 71055570106ac84c 145fbde1f9fbf698 a88a8529dbb98651 91845915201a2dbd f2b4e77f2ae89a86 fe7918aa5bc6c63a 103b67e35290d3 0 0 0 0] [8b1a857ec7175352 112c362cde004a9 af0801fd57087895 f2a1749cdf5707e8 907d94076858ca2 ebac5de8aec5b586 fa72a50840bc676d 3a1b89a78702dd 0 0 0 0]} {[2e081904fc66cfd6 ee7e1943ddce7e15 96165b18fecb9e50 fae10b4b30f70981 b950a0b0c71a407d 672c48808dca0e61 ee5e4500eb00b206 1e15b86e098a14 0 0 0 0] [f849a4f3696041a3 f5d97d00c81b5f 53423d22f3f4e45d c97bd0aedbefc36f 28b2ed5e3dd4724 9ade8b4324bd0972 9b57f9ab5d4dba1b 801ee7d3f1085 0 0 0 0]} {[13eb4c512c169ac5 1ab19e06e806a51d 6ad6511ef7af9458 1e394919ad3c3c72 3ff374113ec1dc04 4f5cfc428217b63f 2a72b13b1c1a0dfa 6a635e07bd1893 0 0 0 0] [244889c2a5e41e87 b30aab90b84d71b9 9fb6b34e28682e9f a7c23517bee9651e f19e8b6c36b00d9c 926fe66306178910 b935b6ced0104651 3300b8e197c1e 0 0 0 0]}]} Bob private: {{c00004aa00 6} 57e9bcf2afd5445eaeb5323e59d8756ba3fc27fa0906251405a9c9ffaea9950b 504b3fddfc7ab738f1b4319677c8ac4912c9ef58d36f7cf8} Bob public: {{c00004b100 6} [{[1646c05125c0bf33 3f7db4efd65acfad 5f0debd38e3cdd63 ef0ff19a67928b1 a57773a5b0f0ec20 b6d110e87aae33a1 adcd04ea0278036 1789c8654a7099 0 0 0 0] [1f804ba79cc60ed2 e22a6a7b52c92317 511c50900dc1ef3 799472151889fa71 abe6967355136a5f fe2193d9d38582a7 4364b58c210b991e 12526ca2448b44 0 0 0 0]} {[9f8746301f179650 6c8e7f3eaef7f7a6 b9de44992695c0a6 a1af8780d47523fe 524ceb08b727c390 df4bed0f3429cd95 4f4290bdd5ff3c72 2fdf1abde72c3d 0 0 0 0] [4b7e93cd1442494f d04c5bd5f2bed1e0 f7988432f99339da a41d276f9e534d4 1fc9df17cb1629ad adc44bbc0dd74c4b 74dae0751d24fd2e c8028280c0aed 0 0 0 0]} {[ea7a90aff4e08e78 67a734ac35911575 4f90399f14bf18a2 8b97d438c0c7ff66 5140d04e6a0cb24d b3207394be08d536 4036a85a0df12f52 20aa19e6e5a561 0 0 0 0] [c9ab47ae5f97364 a6f998aaa5d8d4ad 21a6d43917fbdaf d456de25197138c5 15ba4f89afbd68f2 3c909566afe62ebd 3ffa57e0effa5c55 4e7295359d49 0 0 0 0]}]} true Alice shared: 0fc2623d6135990b25da16f8b0e8c520 Bob shared: 0fc2623d6135990b25da16f8b0e8c520 Equal: true