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 shows how we can create a modulu polynomial and then generate its inverse. In this case we will created a polnomial (\(\textbf{f}\)) and then find its modulo inverse (\(\textbf{f_p}\)), and which will result in \(\textbf{f} \cdot \textbf{f}_p = 1 \pmod p\). If we then take a message (\(m\)) and multiply by \(\textbf{f}\) and then by \(\textbf{f}_p\), we should be able to recover the message:
Multiplying by inverse of a modulo of polynomialTheoryLet's take an example, with \(N=11\) (the highest polynomial factor), \(p=31\) and where Bob picks polynomial factors (\(\textbf{f}\)) of: \(\textbf{f}= [-1, 1, 1, 0, -1, 0, 1, 0, 0, 1, -1]\) \(f(x) = -1 x^{10} + 1 x^9 + 1 x^6 - 1 x^4 + 1 x^2 + 1 x - 1 \pmod {31}\) We then determine the inverse of this with: \(\textbf{f_p}: [9, 5, 16, 3, 15, 15, 22, 19, 18, 29, 5]\) \(f_p(x) = 5 x^{10} + 29 x^9 + 18 x^8 + 19 x^7 + 22 x^6 + 15 x^5 + 15 x^4 + 3 x^3 + 16 x^2 + 5 x + 9 \pmod {31}\) \(\textbf{f} \cdot \textbf{f_p} = 1 \pmod p\) So, we can now take a message (\(m\) and multiply it by \(\textbf{f}\) to gain a ciphertext, and then multiply it with \(\textbf{f_p}\) to recover the message. In the following we will use a message of: \(m=[1, 0, 1, 0, 1, 1, 1, 1]\) \(\textbf{m}=1 x^7 + 1 x^6 + 1 x^5 + 1 x^4 + 1 x^2 + 1\) A test run is: Values used: N= 11 p= 31 ======== Bob picks a polynomials (f): f(x)= [-1, 1, 1, 0, -1, 0, 1, 0, 0, 1, -1] 10 9 6 4 2 -1 x + 1 x + 1 x - 1 x + 1 x + 1 x - 1 ====Now we determine F_p === F_p: [9, 5, 16, 3, 15, 15, 22, 19, 18, 29, 5] 10 9 8 7 6 5 4 3 2 5 x + 29 x + 18 x + 19 x + 22 x + 15 x + 15 x + 3 x + 16 x + 5 x + 9 ====Now we determine the message === Alice's Message: [1, 0, 1, 0, 1, 1, 1, 1] 7 6 5 4 2 1 x + 1 x + 1 x + 1 x + 1 x + 1 ====Encrypted message === Encrypted message: [0, 1, 2, 1, 30, 0, 0, 1, 2, 1, 30] 10 9 8 7 4 3 2 30 x + 1 x + 2 x + 1 x + 30 x + 1 x + 2 x + 1 x ====Decrypted message === Decrypted message: [1, 0, 1, 0, 1, 1, 1, 1] 7 6 5 4 2 1 x + 1 x + 1 x + 1 x + 1 x + 1 Here is another example with \(p=97\): Values used: N= 11 p= 97 ======== Bob picks a polynomials (f): f(x)= [-1, 1, 1, 0, -1, 0, 1, 0, 0, 1, -1] 10 9 6 4 2 -1 x + 1 x + 1 x - 1 x + 1 x + 1 x - 1 ====Now we determine F_p === F_p: [62, 95, 77, 7, 5, 61, 76, 84, 12, 65, 39] 10 9 8 7 6 5 4 3 2 39 x + 65 x + 12 x + 84 x + 76 x + 61 x + 5 x + 7 x + 77 x + 95 x + 62 ====Now we determine the message === Alice's Message: [1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1] 10 8 5 3 2 1 x + 1 x + 1 x + 1 x + 1 x + 1 ====Encrypted message === Encrypted message: [2, 1, 96, 1, 0, 1, 2, 96, 1, 1, 96] 10 9 8 7 6 5 3 2 96 x + 1 x + 1 x + 96 x + 2 x + 1 x + 1 x + 96 x + 1 x + 2 ====Decrypted message === Decrypted message: [1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1] 10 8 5 3 2 1 x + 1 x + 1 x + 1 x + 1 x + 1 CodeThe code is based on this code [here] from fracModulo import extEuclidPoly, modPoly, multPoly, reModulo import numpy import sys N=11 p=31 f=[-1,1,1,0,-1,0,1,0,0,1,-1] m=[1,0,1,0,1,1,1,1] if (len(sys.argv)>1): N=int(sys.argv[1]) if (len(sys.argv)>2): p=int(sys.argv[2]) if (len(sys.argv)>3): f=eval("["+sys.argv[3]+"]") if (len(sys.argv)>4): m=eval("["+sys.argv[4]+"]") print("Values used:") print(" N=",N) print(" p=",p) print("========") print("\nBob picks a polynomials (f):") print("f(x)= ",f) print ("\n",numpy.poly1d(f[::-1])) D=[0]*(N+1) D[0]=-1 D[N]=1 print("\n====Now we determine F_p ===") [gcd_f,s_f,t_f]=extEuclidPoly(f,D) f_p=modPoly(s_f,p) print("F_p:",f_p) print ("\n",numpy.poly1d(f_p[::-1])) x=multPoly(f,m) enc=reModulo(x,D,p) x=multPoly(enc,f_p) dec=reModulo(x,D,p)[:len(m)] print("\n====Now we determine F_p ===") print("Alice's Message:\t",m) print ("\n",numpy.poly1d(m[::-1])) print("\n====Encrypted message ===") print("Encrypted message:\t",enc) print ("\n",numpy.poly1d(enc[::-1])) print("\n====Decrypted message ===") print("Decrypted message:\t",dec) print ("\n",numpy.poly1d(dec[::-1])) |