The NTRU (Nth degree TRUncated polynomial ring) public key method is a lattice-based method which is quantum robust. It uses the shortest vector problem in a lattice, and has an underpinning related to the difficulty of factorizing certain polynomials. NTRUhps2048509 has a security level of AES-128, NTRUhps2048677 maps to AES-192, and NTRUhps4096821 to AES-256.
NTRU using Bouncy Castle and C# |
Outline
NTRU is a asymmetric encryption and has been benchmarked as twice as fast as RSA to encrypt, and three times faster to decrypt. It is the public key method which is not based on factorization (RSA) or discrete logs (Elliptic Curve).
The following is taken from Wikipedia and shows the test case [here]:
Bob and Alice agree to share \(N\) (the largest polynomial power), \(p\) and \(q\), and then Bob generates two short polynomials (\(\textbf{f}\) and \(\textbf{g}\)), and generates his key pair from this. These polynomials have the co-efficients of -1, 0 and 1. For example, with \(N=11\), \(p=3\) and \(q=32\). If Bob picks values of:
\(\textbf{f}= [-1, 1, 1, 0, -1, 0, 1, 0, 0, 1, -1]\)
Then as a polynomial representation:
\(\textbf{f}=-1 + x + x^2 - x^4 + x^6 + x^9 - x^{10}\)
And then picks \(\textbf{g}\):
\(\textbf{g} = -1 + x^2 + x^3 + x^5 - x^8 - x^{10}\)
We then should be able to calculate the inverse of \(\textbf{f}\) for \(\pmod p\) and \( \pmod q\). Thus:
\(\textbf{f} \cdot \textbf{f}_p \pmod p = 1\)
\(\textbf{f} \cdot \textbf{f}_q \pmod q = 1\)
Using an inverse function we get [here]:
\(\textbf{f}_p= [9, 5, 16, 3, 15, 15, 22, 19, 18, 29, 5]\)
\(\textbf{f}_p = 9x^{10} + 5x^9 + 16 x^8 +3 x^7 + 15 x^6 + 15 x^5 + 22 x^4 + 19 x^3 + 18 x^2 + 29x +5\)
The public key then becomes:
\(\textbf{h} = p \cdot \textbf{f}_q . \textbf{f} \pmod q\)
In this case we get:
\(\textbf{f}_q \cdot \textbf{g} = [-5, -9, -1, -2, 11, 12, 13, 3, 22, 15, 16, 29, 60, 19, -2, -7, -36, -40, -50, -18, -30]\)
In order to create a ring, we then divide by \(x^N -1\) and get:
H (Bob's Public Key): [24, 19, 18, 28, 4, 8, 5, 17, 4, 17, 16]
And the private key is \(\textbf{f}\) and \(\textbf{f}_q\).
To encrypt we take Bob's public key (\(h\)), a random polynomial (\(\textbf{r}\)) and a message (\(\textbf{M}\)), and then compute:
\(Enc = \textbf{r} \cdot \textbf{h} + \textbf{M}\)
To decrypt, first we multiply by Bob's private key \(\textbf{f}_q\) and take \(\pmod q\):
\(Dec= (\textbf{r} \cdot \textbf{h} + \textbf{M}) . \textbf{f} \pmod q\)
and which gives:
\(Dec= (p \cdot \textbf{r} \cdot \textbf{f}_q \cdot \textbf{g}+ \textbf{M}) . \textbf{f} \pmod q\)
and since \((\textbf{f}_q . \textbf{f}) \pmod q\) is 1, we get:
\(Dec= (p \cdot \textbf{r} \cdot \textbf{g}+ \textbf{M} \cdot \textbf{f}) \)
Finally we multiply by \(\textbf{f}_p \pmod p\):
\(Dec= (p \cdot \textbf{r} \cdot \textbf{g}+ \textbf{M} \cdot \textbf{f}) . \textbf{f}_p \pmod p\)
This will be:
\(Dec= p \cdot \textbf{r} \cdot \textbf{f} \cdot \textbf{f}_p+ \textbf{M} \cdot \textbf{f} \cdot \textbf{f}_p \pmod p\)
And since we have a multipler of \(p\), we will get a zero value for the first term as we have \(\pmod p\) operation:
\(Dec= 0+ \textbf{M} \cdot \textbf{f} \cdot \textbf{f}_p \pmod p\)
And since \(\textbf{f} \cdot \textbf{f}_p \pmod p\) will be 1, we get:
\(Dec= \textbf{M}\)
Example values of the parameters are:
- Minimal security: \(N=167, p=3, q=128\)
- Good security: \(N=251, p=3, q=128\)
- Strong security: \(N=347, p=3, q=128\)
- Excellent security: \(N=503, p=3, q=256\)
The following defines the key sizes for the NIST KEM finalists (Kyber, SABER, NTRU, and McEliece) and SIDH/SIKE (Isogeny-based):
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) 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) McEliece348864 261,120 6,452 128 Code based McEliece460896 524,160 13,568 188 Code based McEliece6688128 1,044,992 13,892 240 Code based McEliece6960119 1,047,319 13,948 226 Code based McEliece8192128 1,357,824 14,120 240 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
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 [1]:
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
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 NTRU { using Org.BouncyCastle.Pqc.Crypto.Ntru; using Org.BouncyCastle.Security; class Program { static void Main(string[] args) { try { var size="NtruHps2048509"; if (args.Length >0) size=args[0]; var random = new SecureRandom(); var keyGenParameters = new NtruKeyGenerationParameters(random, NtruParameters.NtruHps2048509); if (size=="NtruHps2048677") keyGenParameters = new NtruKeyGenerationParameters(random, NtruParameters.NtruHps2048677); else if (size=="NtruHps4096821") keyGenParameters = new NtruKeyGenerationParameters(random, NtruParameters.NtruHps4096821); else if (size=="NtruHrss701") keyGenParameters = new NtruKeyGenerationParameters(random, NtruParameters.NtruHrss701); var NtruKeyPairGenerator = new NtruKeyPairGenerator(); NtruKeyPairGenerator.Init(keyGenParameters); var aKeyPair = NtruKeyPairGenerator.GenerateKeyPair(); var aPublic = (NtruPublicKeyParameters)aKeyPair.Public; var aPrivate = (NtruPrivateKeyParameters)aKeyPair.Private; var pubEncoded =aPublic.GetEncoded(); var privateEncoded = aPrivate.GetEncoded(); var bobNtruKemGenerator = new NtruKemGenerator(random); var encapsulatedSecret = bobNtruKemGenerator.GenerateEncapsulated(aPublic); var bobSecret = encapsulatedSecret.GetSecret(); var cipherText = encapsulatedSecret.GetEncapsulation(); var aliceKemExtractor = new NtruKemExtractor(aPrivate); var aliceSecret = aliceKemExtractor.ExtractSecret(cipherText); Console.WriteLine("Ntru-{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:
Ntru-NtruHps2048509 Private key length: 935 bytes Public key length: 699 bytes Ciphertext length: 699 bytes Alice private (first 50 bytes): C8470E7018C2887C2895E57A53BBD60F279189520154DC4663C33698CD6A35A17EA1EE5B9BD8A7C59C0096974C5AEF0C7397 Alice public (first 50 bytes): A5D4267792C11AE56EB895213AEECDC8D96F9C051698CC240C74CCB0835DB2E3792D50F0797A043AE6E1011ED1DE373188B1 Cipher (first 50 bytes): 6C938AD793FF83AE06A03F9F9F084D1DCB04D39C2E9301D845787F42F6820859B61AA0DB91B17F1405FE1D5B906FE6BA68FB Bob secret: 6F12453C9159AE2D5FE5AB201295E418 Alice secret: 6F12453C9159AE2D5FE5AB201295E418