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. This page outlines the method used to generate the public key (h). With Lattice encryption, Bob and Alice agree to share N, p and q, and then Bob generates two short polynomials (f and g), and generates his key pair from this. Alice receives this, and she generates a random polynomial, and encrypts some data for Bob. Bob then decrypts the message with his private key. We generate the public and private key from N, p and q:
Lattice Encryption: NTRU Key GenerationTheoryNTRU 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:
A test run is: ==== Bob generates public key ===== Values used: N= 11 p= 3 q= 32 ======== Bob picks two polynomials (g and f): f(x)= [-1, 1, 1, 0, -1, 0, 1, 0, 0, 1, -1] g(x)= [-1, 0, 1, 1, 0, 1, 0, 0, -1, 0, -1] ====Now we determine F_p and F_q === F_p: [1, 2, 0, 2, 2, 1, 0, 2, 1, 2, 0] F_q: [5, 9, 6, 16, 4, 15, 16, 22, 20, 18, 30] ====And finally h==== f_q x g: [-5, -9, -1, -2, 11, 12, 13, 3, 22, 15, 16, 29, 60, 19, -2, -7, -36, -40, -50, -18, -30] H (Bob's Public Key): [24, 19, 18, 28, 4, 8, 5, 17, 4, 17, 16] ====Let's encrypt==== Alice's Message: [1, 0, 1, 0, 1, 1, 1] Random: [-1, -1, 1, 1] Encrypted message: [8, 2, 10, 23, 16, 7, 26, 2, 8, 3, 28] ====Let's decrypt==== Decrypted message: [1, 0, 1, 0, 1, 1, 1] This should match the run above. CodeThe code is based on this code [here] from fracModulo import extEuclidPoly,modPoly,multPoly,reModulo,addPoly,cenPoly, trim N=11 p=3 q=32 f=[-1,1,1,0,-1,0,1,0,0,1,-1] g=[-1,0,1,1,0,1,0,0,-1,0,-1] print("==== Bob generates public key =====") print("Values used:") print(" N=",N) print(" p=",p) print(" q=",q) print("========") print("\nBob picks two polynomials (g and f):") #f=[-1,0,1,1,-1,0,-1] #g=[0,-1,-1,0,1,0,1] d=2 print("f(x)= ",f) print("g(x)= ",g) D=[0]*(N+1) D[0]=-1 D[N]=1 print("\n====Now we determine F_p and F_q ===") [gcd_f,s_f,t_f]=extEuclidPoly(f,D) f_p=modPoly(s_f,p) f_q=modPoly(s_f,q) print("F_p:",f_p) print("F_q:",f_q) x=multPoly(f_q,g) h=reModulo(x,D,q) print("\n====And finally h====") print("f_q x g: ",x) print("H (Bob's Public Key): ",h) print("\n====Let's encrypt====") msg=[1,0,1,0,1,1,1] randPol=[-1,-1,1,1] print("Alice's Message:\t",msg) print("Random:\t\t\t",randPol) e_tilda=addPoly(multPoly(multPoly([p],randPol),h),msg) e=reModulo(e_tilda,D,q) print("Encrypted message:\t",e) print("\n====Let's decrypt====") tmp=reModulo(multPoly(f,e),D,q) centered=cenPoly(tmp,q) m1=multPoly(f_p,centered) tmp=reModulo(m1,D,p) print("Decrypted message:\t",trim(tmp)) |