WARNING: the SIKE algorithm is only for research purposes, insecure Supersingular Isogeny Key Encapsulation (SIKE) [4] 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 key is 378 bytes and the private key is 434 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 PQC KEM using Bouncy Castle and C# |
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.
Keysizes
For our existing ECC methods, the key sizes are:
Type Public key size (B) Secret key size (B) Ciphertext size (B) ------------------------------------------------------------------------ P256_HKDF_SHA256 65 32 65 P384_HKDF_SHA384 97 48 97 P521_HKDF_SHA512 133 66 133 X25519_HKDF_SHA256 32 32 32 X448_HKDF_SHA512 56 56 56
In this case, we see a 32-byte secret (private) key size for P256, and 64 bytes for the public key (as it has an x- and y-co-ordinate value) and then another byte added to identify the type of point. This gives a 65 byte public key. For X22519, we only require a single co-ordinate value, and thus only need 32 bytes for the public key (and which is the same size as the secret key). The following defines the key sizes for Kyber, SABER, NTRU and McEliece:
Type Public key size (B) Secret key size (B) Ciphertext size (B) ------------------------------------------------------------------------ Kyber512 800 1,632 768 Kyber738 1,184 2,400 1,088 Kyber1024 1,568 3,168 1,568 LightSABER 672 1,568 736 SABER 992 2,304 1,088 FireSABER 1,312 3,040 1,472 McEliece348864 261,120 6,452 128 McEliece460896 524,160 13,568 188 McEliece6688128 1,044,992 13,892 240 McEliece6960119 1,047,319 13,948 226 McEliece8192128 1,357,824 14,120 240 NTRUhps2048509 699 935 699 NTRUhps2048677 930 1,234 930 NTRUhps4096821 1,230 1,590 1,230 SIKEp434 330 44 346 SIKEp503 378 56 402 SIKEp751 564 80 596 Frodokem19888 9,616 19,888 9,720 Frodokem31296 15,632 31,296 15,744 Frodokem43088 21,520 43,088 21,632
Note: LightSABER has a security level of AES-128, SABER maps to AES-192, and FireSABER to AES-256. Kyber512 has a security level of AES-128, Kyber738 maps to AES-192, and Keyber1024 to AES-256. NTRUhps2048509 has a security level of AES-128, NTRUhps2048677 maps to AES-192, and NTRUhps4096821 to AES-256.
In terms of performance on an ARM Cortex-M4 (32-bit RISC processor), the following is the number of cycles taken for various operations for key generation, key encapulation and key decapsulation:
scheme (implementation) level key generation encapsulation decapsulation ---------------------------------------------------------------------------- frodokem640aes (m4) 1 48,348,105 47,130 922 46,594,383 kyber512 (m4) 1 463,343 566,744 525,141 kyber768 (m4) 3 763,979 923,856 862,176 lightsaber (m4f) 1 361,687 513,581 498,590 saber (m4f) 3 654,407 862,856 835,122 ntruhps2048509 (m4f) 1 79,658,656 564,411 537,473 ntruhps2048677 (m4f) 3 143,734,184 821,524 815,516 sikep434 (m4) 1 48,264,129 78,911,465 84,276,911 sikep610 (m4) 3 119,480,622 219,632,058 221,029,700 mceliece348864f 1 1,430,811,294 582,199 2,706,681 mceliece348864 1 2,146,932,033 582,199 2,706,681
Coding
Next some code:
namespace Sike { using Org.BouncyCastle.Pqc.Crypto.Sike; using Org.BouncyCastle.Security; class Program { static void Main(string[] args) { try { var method="sikep434_compressed"; if (args.Length >0) method=args[0]; var random = new SecureRandom(); var keyGenParameters = new SikeKeyGenerationParameters (random, SikeParameters.sikep434); if (method=="sikep434_compressed") keyGenParameters = new SikeKeyGenerationParameters(random, SikeParameters.sikep434_compressed); else if (method=="sikep503") keyGenParameters = new SikeKeyGenerationParameters(random, SikeParameters.sikep503); else if (method=="sikep503_compressed") keyGenParameters = new SikeKeyGenerationParameters(random, SikeParameters.sikep503_compressed); else if (method=="sikep610") keyGenParameters = new SikeKeyGenerationParameters(random, SikeParameters.sikep610); else if (method=="sikep610_compressed") keyGenParameters = new SikeKeyGenerationParameters(random, SikeParameters.sikep610_compressed); else if (method=="sikep751") keyGenParameters = new SikeKeyGenerationParameters(random, SikeParameters.sikep751); else if (method=="sikep751_compressed") keyGenParameters = new SikeKeyGenerationParameters(random, SikeParameters.sikep751_compressed); var SikeKeyPairGenerator = new SikeKeyPairGenerator(); SikeKeyPairGenerator.Init(keyGenParameters); var aKeyPair = SikeKeyPairGenerator.GenerateKeyPair(); var aPublic = (SikePublicKeyParameters)aKeyPair.Public; var aPrivate = (SikePrivateKeyParameters)aKeyPair.Private; var pubEncoded =aPublic.GetEncoded(); var privateEncoded = aPrivate.GetEncoded(); var bobSikeKemGenerator = new SikeKemGenerator(random); var encapsulatedSecret = bobSikeKemGenerator.GenerateEncapsulated(aPublic); var bobSecret = encapsulatedSecret.GetSecret(); var cipherText = encapsulatedSecret.GetEncapsulation(); var aliceSikeKemExtractor = new SikeKemExtractor(aPrivate); var aliceSecret = aliceSikeKemExtractor.ExtractSecret(cipherText); Console.WriteLine("Sike Engine:\t\t\t{0}",keyGenParameters.Parameters.Name); Console.WriteLine("Sike Key Size:\t\t\t{0}",keyGenParameters.Parameters.DefaultKeySize); Console.WriteLine("Private key length:\t\t{0} bytes",aPrivate.GetEncoded().Length); Console.WriteLine("Public key length:\t\t{0} bytes",aPublic.GetEncoded().Length); Console.WriteLine("Ciphertext length:\t\t{0} bytes",cipherText.Length); Console.WriteLine("\nAlice private (first 50 bytes):\t{0}",Convert.ToHexString(aPrivate.GetEncoded())[..100]); Console.WriteLine("Alice public (first 50 bytes):\t{0}",Convert.ToHexString(aPublic.GetEncoded())[..100]); Console.WriteLine("\nCipher (first 50 bytes):\t{0}",Convert.ToHexString(cipherText)[..100]); Console.WriteLine("\nBob secret:\t\t{0}",Convert.ToHexString(bobSecret)); Console.WriteLine("Alice secret:\t\t{0}",Convert.ToHexString(aliceSecret)); } catch (Exception e) { Console.WriteLine("Error: {0}",e.Message); } } } }
Sike P434 produces a 128-bit key size:
Sike Engine: sikep434 Sike Key Size: 128 Private key length: 374 bytes Public key length: 330 bytes Ciphertext length: 346 bytes Alice private (first 50 bytes): 3E4CB940F44A181D61615644140E30A78E308FF24B0AF36ADD86EEEE04D02BE9A95CA91C0757A6855FEC00007A8028AFB6C3 Alice public (first 50 bytes): 7A8028AFB6C3653AD5CFAC3AB78961B126D971E1D4C7EAFD586E4428E0325D3A3E3D6787F5AE9AAC85CEF1DF23F503745EFB Cipher (first 50 bytes): 404D1C040BED897B31EEF1FC3993F5B407571EE060AE85C6354F7EFFCC436FF56CBCF1AFD0A415E3DA3FD22EE3E951ACABFC Bob secret: 7E17D32E5C8DDFAB71FBFC26FEA4AE29 Alice secret: 7E17D32E5C8DDFAB71FBFC26FEA4AE29
and for Sike p503, we have a 192-bit key size:
Sike Engine: sikep503 Sike Key Size: 192 Private key length: 434 bytes Public key length: 378 bytes Ciphertext length: 402 bytes Alice private (first 50 bytes): E00271024A34DB496262D002FC838ABC263600730DCB22A77BC1A6B274FE85477A9CA3B73D316B19EA1BE0902C94DECCCB81 Alice public (first 50 bytes): 89D27879E6CB2A5A409FCA16E11C7A0B493DB9D4A312A5E3F328DD2D3B1493915B735EE6DCB3C65D23F25F445251E8492E13 Cipher (first 50 bytes): 413AADAA134A10001011BD22A751E0B042B7993CBB33DAC74C235C8267293ABEA24B1126C3BE0AB097D2542C5AB89A3FA053 Bob secret: BF3244AB69AC2C3C6DA78CCCB343C54B270B9968F8057352 Alice secret: BF3244AB69AC2C3C6DA78CCCB343C54B270B9968F8057352
and for Sike P751, we get a 256-bit key:
Sike Engine: sikep751 Sike Key Size: 256 Private key length: 644 bytes Public key length: 564 bytes Ciphertext length: 596 bytes Alice private (first 50 bytes): ED31E23CDC3C90679056842B863CB1C864837463388F083AF1D3DB4366193197644C490189D8EBBC5C2D847F368B6380EF24 Alice public (first 50 bytes): 007846E6DA04B6836DB811E96E5FB1E6E178E8E5B7589EF89DB5AD6B72375C63DBB19BF8CC448775C4B9E308D5D5E0F01FB5 Cipher (first 50 bytes): 4E26A3383C67BED6F69F5589F2BC5400A4FDE06AD5406C9457BE6A39B9815BB5867BDD5E969676FE7ECD26FAB3A34AF78F28 Bob secret: 615C19587497F12745000EEAC247963C9E299066A79C4BB6A7794F956DD69DFD Alice secret: 615C19587497F12745000EEAC247963C9E299066A79C4BB6A7794F956DD69DFD