In methods such as NTRU (Nth degree TRUncated polynomial ring) public key method we use a lattice-based method which is quantum robust. With this we take polynomials and perform operations, such as multiply and inverse modulus. The method most often used to find the inverse mod is the Extended Euclidean method applied to polynomial values. In lattice methods we use polynomials, such as: \(f=-1+x^2+x^3 \pmod p\). To define a key, we often use trinary values of \(\{-1, 0, +1\}\) as our factors. Then we need to find \(f^{-1} \pmod p\) in order to provide the reverse operation. In this case we apply the Extended Euclidean method to determine in inverse mod of a polynomial.
Inverse Polynomial (mod p)TheoryIn public key encryption, such as RSA, we need to find \(d\) given this: \(d e \pmod \varphi=1\) and where \(\varphi\) is \((p-1)(q-1)\). For this we need to perform an inverse mod operation: \(d = e^{-1} \pmod \varphi\) After we do this, this will be true: \(d e \pmod \varphi\)=1 The method most often used to find the inverse mod is the Extended Euclidean method applied to polynomial values. In lattice methods we use polynomials, such as: \(f=-1+x^2+x^3 \pmod p\) To define a key, we often use trinary values of \(\{-1, 0,\) and \(+1\}\) as our factors. Then we need to find \(f^{-1} \pmod p\) in order to provide the reverse operation. Luckily we can do with the Extended Euclidean method applied to polynomials. So let's take an example, and prove it. If we have \(f=-1+x^2+x^3 \pmod p\), and want to find the inverse mod of this for \(\pmod {32}\), we can determine it as: \(f'=-19+7x+13x^2+26x^3 \pmod {32}\) Now let's provide that this is true. Let's do: \(r = f \times f' = (-1+x^2+x^3) \times (-19+7x+13x^2+26x^3) \pmod {32}\) \(r = f \times f' = (-19 -7x - 13x^2- 26x^3 + 19x^2+7x^3+13x^4+26x^5+19x^3+7x^4+13x^5+26x^6) \pmod {32}\) We then get the result of: \(r= -19 -7x+ 6x^2 + 20x^4 + 39x^5+26x^6\) With polynomial operations in cryptography we then limit the highest power of the polynomial by dividing by \(D=x^4-1\) and where 3 is the highest polynomial power we can have: \(r= (-19 -7x+ 6x^2 + 20x^4 + 39x^5+26x^6)/(x^4-1)\) and which gives a result of [1]. CodingHere is the coding: import fracModulo from fractions import Fraction as frac from operator import add from operator import neg def trim(seq): if len(seq) == 0: return seq else: for i in range(len(seq) - 1, -1, -1): if seq[i] != 0: break return seq[0:i+1] def resize(c1,c2): if(len(c1)>len(c2)): c2=c2+[0]*(len(c1)-len(c2)) if(len(c1)<len(c2)): c1=c1+[0]*(len(c2)-len(c1)) return [c1,c2] def subPoly(c1,c2): [c1,c2]=resize(c1,c2) c2=list(map(neg,c2)) out=list(map(add, c1, c2)) return trim(out) def modPoly(c,k): if(k==0): print("Error in modPoly(c,k). Integer k must be non-zero") else: return [fracModulo.fracMod(x,k) for x in c] def multPoly(c1,c2): order=(len(c1)-1+len(c2)-1) out=[0]*(order+1) for i in range(0,len(c1)): for j in range(0,len(c2)): out[j+i]=out[j+i]+c1[i]*c2[j] return trim(out) def reModulo(num,div,modby): [_,remain]=divPoly(num,div) return modPoly(remain,modby) def divPoly(N,D): N, D = list(map(frac,trim(N))), list(map(frac,trim(D))) degN, degD = len(N)-1, len(D)-1 if(degN>=degD): q=[0]*(degN-degD+1) while(degN>=degD and N!=[0]): d=list(D) [d.insert(0,frac(0,1)) for i in range(degN-degD)] q[degN-degD]=N[degN]/d[len(d)-1] d=[x*q[degN-degD] for x in d] N=subPoly(N,d) degN=len(N)-1 r=N else: q=[0] r=N return [trim(q),trim(r)] def extEuclidPoly(a,b): switch = False a=trim(a) b=trim(b) if len(a)<i=len(b): a1, b1 = a, b else: a1, b1 = b, a switch = True Q,R=[],[] while b1 != [0]: [q,r]=divPoly(a1,b1) Q.append(q) R.append(r) a1=b1 b1=r S=[0]*(len(Q)+2) T=[0]*(len(Q)+2) S[0],S[1],T[0],T[1] = [1],[0],[0],[1] for x in range(2, len(S)): S[x]=subPoly(S[x-2],multPoly(Q[x-2],S[x-1])) T[x]=subPoly(T[x-2],multPoly(Q[x-2],T[x-1])) gcdVal=R[len(R)-2] s_out=S[len(S)-2] t_out=T[len(T)-2] ### ADDITIONAL STEPS TO SCALE GCD SUCH THAT LEADING TERM AS COEF OF 1: scaleFactor=gcdVal[len(gcdVal)-1] gcdVal=[x/scaleFactor for x in gcdVal] s_out=[x/scaleFactor for x in s_out] t_out=[x/scaleFactor for x in t_out] if switch: return [gcdVal,t_out,s_out] else: return [gcdVal,s_out,t_out] f=[-1,1,1,0,-1,0,1,0,0,1,-1] f=[-1,0,1,1] q=32 N=len(f) D=[0]*(N+1) D[0]=-1 D[N]=1 print ("D: ",D) [gcd_f,s_f,t_f]=extEuclidPoly(f,D) s_f=modPoly(s_f,q) print ("f=",f) print ("\ns_f=",s_f) f_p=multPoly(f,s_f) print ("f x s_f=",f_p) h=reModulo(f_p,D,q) print ("Res: ",h) A sample run is: D: [-1, 0, 0, 0, 1] f= [-1, 0, 1, 1] s_f= [19, 7, 13, 26] f x s_f= [-19, -7, 6, 0, 20, 39, 26] Res: [1, 0, 0] |