CRYSTALS (Cryptographic Suite for Algebraic Lattices) supports two quantum robust mechanisms: Kyber for key-encapsulation mechanism (KEM) and key exchange; and Dilithium for a digital signature algorithm. CRYSTALS-Kyber uses LWE (Learning with Errors) with lattice methods. A new lattice attack was discovered within the period of the assessment [1], but it is hoped that an updated version of Kyber can be produced for the final assessment. NIST have some worried about its side-channel robustness, but is a strong contender for KEM. Overall a KEM allows a symmetric key to be passed using public key methods. In this case, Alice will generate her key pair of a public key (pk) and a private key (sk). She then passes her public key to Bob, and then Bob creates a cipher text (ct) with Alice's public key. He passes the ciphertext to Alice, and who decrypts with her private key. This will reveal the key that Bob wants Alice to use. Kyber512 has a security level of AES-128, Kyber738 maps to AES-192, and Keyber1024 to AES-256.
Classic Mceliece using Bouncy Castle and C# |
Basics
Matrices
Some basic rules of matrices are:
\({(\textbf{A}^T)}^T=\textbf{A}\)
\(\textbf{(AB)}^T=\textbf{A}^T \textbf{B}^T\)
\({(c\textbf{A})}^T=c\textbf{A}^T\)
and where \(T\) is a transpose of the matrix.
Polynomials
In polynomial representation, we can take a data value of 1101 and represent it in polynomial powers:
\(x^3+1.x^2+0x+1 = x^3+x^2+1\)
We can then multiply, divide, add and subtract polynomial values. If you remember from school, for \((2x^2+1)\) times \((x+1)\) we get:
\((2x^2+1).(x+1) = 2x^3+2x^2+x+1\)
The (mod p) operation
Obviously, if we are multiplying polynomials, the coefficients of the powers could become large, so we perform a \(\pmod q\) operation on them. Let’s take a \(q\) value of 17 and let’s say we have:
\(a=2x^4+3x^3+10x+3\)
\(b=3x^5+14x^3+10x+4\)
Then, to add \(\pmod {17}\), we get:
\((2x^4+3x^3+10x+3)+(3x^5+14x^3+10x+4) = 3x^5+2x^4+17x^3+20x+7 = 3x^5+2x^4+3x+7 \pmod{17})\)
To subtract \(\pmod{17}\), we get:
\((2x^4+3x^3+10x+3)-(3x^5+14x^3+10x+4) = -3x^5+2x^4-11x^3-1 = 14x^5+2x^4+6x^3+16 \pmod {17}\)
To multiply \(\pmod{17}\), we get:
\((2x^4+3x^3+10x+3)*(3x^5+14x^3+10x+4) =\) [… working left to reader … ] \(= 6x^7+9x^6+7x^5+3x^4+8x^3+x^2+2x+12 \pmod{17}\)
For division, we will get a quotient and a remainder. With integers 19 divided by 5 gives a quotient of 3 and a remainder of 4. In cryptography, we are typically only interested in the remainder value. So we get:
\((2x^4+3x^3+10x+3)/(3x^5+14x^3+10x+4)\) Remainder: […working left to reader … ] \(= 2x^3+3x^2+10x+3 \pmod{17}\)
We can use Python to check this:
import numpy as np import sys import numpy q=17 a= [2,3,10,3] // 2x^4+3x^3+10x+3 b= [3,0,14,10,4] // 3x^5+14x^3+10x+4 print (np.poly1d(a)) print (np.poly1d(b)) r1 = np.floor( np.polyadd(a,b)) % q // Polynomial add r2 = np.floor( np.polymul(a,b)) % q // Polynomial multiply r3 = np.floor( np.polysub(a,b)) % q // // Polynomial subtract r4 = np.floor( np.polydiv(a,b)[1]) % q // // Polynomial divide with remainder print (np.poly1d(r1)) print (np.poly1d(r2)) print (np.poly1d(r3)) print (np.poly1d(r4))
And then the results are:
3 2 2 x + 3 x + 10 x + 3 4 2 3 x + 14 x + 10 x + 4 4 3 3 x + 2 x + 3 x + 7 7 6 5 4 3 2 6 x + 9 x + 7 x + 3 x + 8 x + 1 x + 2 x + 12 4 3 2 14 x + 2 x + 6 x + 16 3 2 2 x + 3 x + 10 x + 3
The code is:
Overall, \(q\) is the modulus for the numbers. For Kyber512, this value is 3,329.
The irreducible polynomial
The next key concept relates to the maximum power of the coefficients of the powers. If we do not constrain, the values of powers will become large. And, so, for each operation, we can divide by an irreducible polynomial (a polynomial that cannot be factored), and take the remainder of the operation. This is similar to our \(\pmod p\) operation in public key encryption (and where we divide by p each time, and take the remainder of the operation). If you want some examples: [here].
An irreducible polynomial of \(x^4+1\), will reduce our maximum coefficient power of \(x^3\). This variable (n) is defined as the maximum degree of the used polynomials. For Kyber512, this value is 256.
In Python, we basically perform a polynomial divide. As this will create two results (the division and the remainder), we take the second returned value (using [1] to identify the second argument returned):
A1 = np.floor( np.polydiv(A1,xN_1)[1]) % q
Key Generation
In Kyber we modify the normal LWE (Learning With Errors) approach and use MLWE (Module Learning With Errrors). With MLWE we use vectors of polynomials.
The private key (\(s\))
First, we start with the private key, and which is an array of polynomial values. In our case we will use:
\(s=(x^3−x^2+x,x^3+x)\)
Next, we create a matrix of polynomials for the public key (\(A\)) with:
\(A=\begin{pmatrix} 6x^3+16x^2+6x+1 & 5x^2+10 \\ 3x^3+8x^2+5x+4 & 9x^3+8x^2+2x+4 \end{pmatrix}\)
Finally, we will introduce an error polynomial:
\(e=(x^2+1,x-1)\)
Now, we compute:
\(t=A.s+e\)
The public key is then \((A,t)\). Using \(q=17\) and an irreducible polynomial of \(x^4+1\), we get:
\(t= ( 9x^3+13x +5, 2x^3+ 8x^2 ++ 13x+5)\)
I have used this program to work this out:
# Based on https://github.com/jack4818/kyber-py from polynomials import * from modules import * R = PolynomialRing(17, 4) M = Module(R) s0 = R([0,1,-1,1]) s1 = R([0,1,0,1]) s = M([s0,s1]).transpose() A00 = R([11,16,16,6]) A01 = R([3,6,4,9]) A10 = R([1,10,3,5]) A11 = R([15,9,1,6]) A = M([[A00, A01],[A10, A11]]) A00 = R([1,6,16,6]) A01 = R([10,0,5,0]) A10 = R([4,5,8,3]) A11 = R([4,2,8,9]) A = M([[A00, A01],[A10, A11]]) e0 = R([1,0,1,0]) e1 = R([-1,1,0,0]) e = M([e0,e1]).transpose() t = A @ s + e print("A->",A) print("t->",t)
and the test run is:
A-> [1 + 6*x + 16*x^2 + 6*x^3, 10 + 5*x^2] [ 4 + 5*x + 8*x^2 + 3*x^3, 4 + 2*x + 8*x^2 + 9*x^3] t-> [5 + 13*x + 9*x^3] [5 + 13*x + 8*x^2 + 2*x^3]
Key sizes
The Key sizes for Kyber and other PQC methdods are:
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 Learning with errors (Lattice) Kyber738 1,184 2,400 1,088 Learning with errors (Lattice) Kyber1024 1,568 3,168 1,568 Learning with errors (Lattice) Bike128 1,541 3,114 1,573 Code-based Bike192 3,083 6,198 3,115 Code-based Bike256 5,122 10,276 5,154 Code-based HQC128 2,249 2,289 4,497 Code-based HQC192 4,522 4,562 9,042 Code-based HQC256 7,245 7,285 14,485 Code-based McEliece348864 261,120 6,492 196 Code based McEliece460896 524,160 13,608 156 Code based McEliece6688128 1,044,992 13,932 208 Code based McEliece6960119 1,047,319 13,948 194 Code based McEliece8192128 1,357,824 14,120 208 Code based NTRUhps2048509 699 935 699 Lattice NTRUhps2048677 930 1,234 930 Lattice NTRUhps4096821 1,230 1,590 1,230 Lattice SIKEp434 330 44 346 Isogeny SIKEp503 378 56 402 Isogeny SIKEp751 564 80 596 Isogeny SIDH 564 48 596 Isogeny LightSABER 672 1,568 736 Learning with rounding (Lattice) SABER 992 2,304 1,088 Learning with rounding (Lattice) FireSABER 1,312 3,040 1,472 Learning with rounding (Lattice)
Code
We can create a Dotnet console project for .NET 8.0 with:
dotnet new console
First we install the Bouncy Castle library:
dotnet add package BouncyCastle.Cryptography
Next some code:
namespace Cmce { using Org.BouncyCastle.Pqc.Crypto.Cmce; using Org.BouncyCastle.Security; class Program { static void Main(string[] args) { try { var size="mceliece348864"; if (args.Length >0) size=args[0]; var random = new SecureRandom(); var keyGenParameters = new CmceKeyGenerationParameters(random, CmceParameters.mceliece348864r3); if (size=="mceliece460896") keyGenParameters = new CmceKeyGenerationParameters(random, CmceParameters.mceliece460896r3); else if (size=="mceliece6688128") keyGenParameters = new CmceKeyGenerationParameters(random, CmceParameters.mceliece6688128r3); else if (size=="mceliece6960119") keyGenParameters = new CmceKeyGenerationParameters(random, CmceParameters.mceliece6960119r3); else if (size=="mceliece6960119") keyGenParameters = new CmceKeyGenerationParameters(random, CmceParameters.mceliece6960119r3); else if (size=="mceliece8192128") keyGenParameters = new CmceKeyGenerationParameters(random, CmceParameters.mceliece8192128r3); var CmceKeyPairGenerator = new CmceKeyPairGenerator(); CmceKeyPairGenerator.Init(keyGenParameters); var aKeyPair = CmceKeyPairGenerator.GenerateKeyPair(); var aPublic = (CmcePublicKeyParameters)aKeyPair.Public; var aPrivate = (CmcePrivateKeyParameters)aKeyPair.Private; var pubEncoded =aPublic.GetEncoded(); var privateEncoded = aPrivate.GetEncoded(); var bobCmceKemGenerator = new CmceKemGenerator(random); var encapsulatedSecret = bobCmceKemGenerator.GenerateEncapsulated(aPublic); var bobSecret = encapsulatedSecret.GetSecret(); var cipherText = encapsulatedSecret.GetEncapsulation(); var aliceKemExtractor = new CmceKemExtractor(aPrivate); var aliceSecret = aliceKemExtractor.ExtractSecret(cipherText); Console.WriteLine("Cmce-{0}",size); 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); } } } }
A sample run showing the cipher text, and the public and private key is:
Cmce-mceliece8192128 Private key length: 14120 bytes Public key length: 1357824 bytes Ciphertext length: 208 bytes Alice private (first 50 bytes): 10FCB7ACD5F28BA1371728D4F8A4468E40C88306CF5505B841E984A86F6AF725FFFFFFFF00000000A405F8015B05380E6718 Alice public (first 50 bytes): 81E5EEDA642A34955CF33D5C4FBD9A400862BF4593DF255F5BBBEC9B6EC805861A9946A8B90D2635C812A7DE7B993D9A034E Cipher (first 50 bytes): 5C911606AFDB30BA16F914364DF2B1949C19A827FF70BC8B64B03AD0F2C9AE53FD1C3A4161EE01632358EF851D00047F334A Bob secret: FCBAE584DA20AD5A17827D1BA233331169E9BA11B4369F91F43CBCADD91B128E Alice secret: FCBAE584DA20AD5A17827D1BA233331169E9BA11B4369F91F43CBCADD91B128E