NTRUEncrypt 在復雜代數上失敗
我遵循維基百科上描述的 NTRUEncrypt 密碼系統。我已經在Sage Math引擎中實現了它（一路上有一些小問題，但最終成功解決了）並且系統按預期工作。
我注意到關於將 NTRU 擴展到高階代數的有趣出版物。這是關於四元數的，但在下面的範例中，我將首先嘗試複數，一步一步。
所以，我已經實現了程式碼來定義密碼系統的參數，加密和解密，但最後我無法恢復初始多項式。我不知道這只是一個錯誤還是我的步驟中存在概念錯誤；需要一些幫助來解決這個問題。
定義參數和各自的多項式環：
N = 11 p = 3 q = 37 R.<x> = PolynomialRing(ZZ) RR = R.quotient(x^N - 1) P.<x> = PolynomialRing(Zmod(p)) PP = P.quotient(x^N - 1) Q.<x> = PolynomialRing(Zmod(q)) QQ = Q.quotient(x^N - 1)選擇多項式F $ f $ 和G $ g $
f_1 = RR([-1, 1, 1, 0, -1, 0, 1, 0, 0, 1, -1]) f_2 = RR([-1, 1, 1, 0, -1, 0, 1, 0, 0, 1, -1]) g_1 = RR([-1, 0, 1, 1, 0, 1, 0, 0, -1, 0, -1]) g_2 = RR([-1, 0, 1, 1, 0, 1, 0, 0, -1, 0, -1]) f = (f_1, f_2) g = (g_1, g_2)計算F $ f $ 在相應環PP $ PP $ 和問問 $ QQ $ 上的乘法逆。
記住：F−1個XX=[1個||F||2個]XX×ˉF $ f^{-1}{XX} = [\frac{1}{||f||^2}]{XX}\times \bar{f} $
還有：||F||2個=F2個0+F2個1個 $ ||f||^2 = f_0^2 + f_1^2 $ 和ˉF=(F0,−F1個) $ \bar{f} = (f_0, -f_1) $
f_ = (f[0], -f[1]) f_norm = f[0]^2 + f[1]^2 f_norm_inv_p = PP(f_norm) ^ -1 fp = ( PP(f_[0] * f_norm_inv_p), PP(f_[1] * f_norm_inv_p), ) f_norm_inv_q = QQ(f_norm) ^ -1 fq = ( QQ(f_[0] * f_norm_inv_q), QQ(f_[1] * f_norm_inv_q), )檢查復數乘法一個×b=(一個C−bd,一個d+bC) $ a \times b = (ac-bd, ad+bc) $
assert PP(f[0] * fp[0]) - PP(fp[1] * f[1]) == 1 assert PP(f[0] * fp[1]) + PP(f[1] * fp[0]) == 0 assert QQ(f[0] * fq[0]) - QQ(fq[1] * f[1]) == 1 assert QQ(f[0] * fq[1]) + QQ(f[1] * fq[0]) == 0生成公鑰H=pFq×G $ h = pf_q \times g $
pfq = (p * fq[0], p * fq[1]) h = ( QQ(pfq[0] * g[0]) - QQ(g[1] * pfq[1]), QQ(pfq[0] * g[1]) + QQ(pfq[1] * g[0]), )加密電子=r×H+米 $ e = r \times h + m $
m = ( PP([0, 0, 0, 0, 0, 1, 1, 0, -1, 1, 1]), PP([0, 0, 0, 0, 0, 1, 1, 0, -1, 1, 1]), ) r = ( RR([0, 1, 1, 1, 1, 1, 1, 0, -1, 1, 1]), RR([0, 1, 1, 1, 1, 1, 1, 0, -1, 1, 1]), ) rh = ( r[0] * h[0] - h[1] * r[1], r[0] * h[1] + r[1] * h[0], ) e = ( QQ(rh[0] + m[0]), QQ(rh[1] + m[1]), )解密：
一個=F×電子 $ a = f \times e $ （記得把係數居中提升）
b=PP[一個] $ b = PP[a] $
C=Fp×b $ c = f_p \times b $
a = ( QQ(f[0]) * e[0] - e[1] * QQ(f[1]), QQ(f[0]) * e[1] + QQ(f[1]) * e[0], ) a = ( ZZ['x']([coeff.lift_centered() for coeff in a[0].lift()]), ZZ['x']([coeff.lift_centered() for coeff in a[1].lift()]), ) b = (PP(a[0]), PP(a[1])) c = ( fp[0] * b[0] - b[1] * fp[1], fp[0] * b[1] + fp[1] * b[0], )最後C≠米 $ c \neq m $ … 我有點煩惱，why(?)
PS 要快速檢查Sage程式碼，您可以使用此站點：https ://sagecell.sagemath.org/
同樣，程式碼沒有任何問題：在這種情況下，舍入過程更加嘈雜，並且再次導致減少被正確提升。
本質上，我們在這裡使用 NTRU 和高斯整數作為基環Z[一世][X] $ \mathbb Z[i][x] $ 而不是更常見的Z[X] $ \mathbb Z[x] $ 。然而，我們仍然處於一個很好的歐幾里德環境中，所以這不應該讓我們擔心。有一個小問題，即 37 不會生成超過高斯分佈的素理想，因為例如37=(6個+一世)(6個−一世) $ 37=(6+i)(6-i) $ 。這可能會導致G(X) $ g(x) $ 的更多選擇不適合沒有逆，但在實踐中不太可能影響。另請注意，如果您不希望，您不必設置F1個=F2個 $ f_1=f_2 $ 或其他多項式。通過選擇此限制，當您可以使用 9 個殘基選擇時，您可以限制殘基選擇0,1個+一世,−1個−一世(模組p) $ 0,1+i,-1-i\pmod p $ p=3個 $ p=3 $ 。
無論如何，回想一下解密過程的目標是恢復（高斯）整數多項式 一個(X)=r(X)G(X)p+F(X)米(X)$$ a(x)=r(x)g(x)p+f(x)m(x) $$ 我們可以計算為
sage: inta = ( p*(r[0]*g[0]-r[1]*g[1]) + f[0]*m[0]-f[1]*m[1] , p*(r[0]*g[1]+r[1]*g[0])+f[0]*m[1]+f[1]*m[0]) sage: inta (0, -10*xbar^10 - 8*xbar^9 + 16*xbar^8 + 20*xbar^7 + 10*xbar^6 + 4*xbar^5 + 8*xbar^4 - 2*xbar^3 - 20*xbar^2 - 6*xbar)請注意，作為整數，一個(X) $ a(x) $ 的實部和虛部的係數是四對乘積的總和，而不是非高斯 NTRU 中的兩對乘積之和。這導致更大的係數增長和更大的錯誤機會。如果我們現在將我們希望恢復的一個(X) $ a(x) $ 與其在解密過程中獲得的縮減模q $ q $
sage: aq = ( QQ(f[0]) * e[0] - e[1] * QQ(f[1]), QQ(f[0]) * e[1] + QQ(f[1]) * e[0]) sage: aq (0, 27*xbar^10 + 29*xbar^9 + 16*xbar^8 + 20*xbar^7 + 10*xbar^6 + 4*xbar^5 + 8*xbar^4 + 35*xbar^3 + 17*xbar^2 + 31*xbar)並且所有係數都符合我們希望的 mod q $ q $ 然而，當我們嘗試提升時，我們看到一個(X) $ a(X) $ 的係數位於區間(−q/2個,q/2個) $ (-q/2,q/2) $ X7 $ x^7 $ 和X2個 $ x^2 $ 係數的虛部. 因此，當我們提升時，我們恢復了一個不正確的整數多項式：
sage: a = ( ZZ['x']([coeff.lift_centered() for coeff in aq[0].lift()]), ZZ['x']([coeff.lift_centered() for coeff in aq[1].lift()])) sage: a (0, -10*x^10 - 8*x^9 + 16*x^8 - 17*x^7 + 10*x^6 + 4*x^5 + 8*x^4 - 2*x^3 + 17*x^2 - 6*x)這導致無法恢復明文。如果您選擇了一個20<q/2的素數q $ q $ ，例如q=43，那麼該過程將執行良好。20<q/2個 $ 20<q/2 $ q=43 $ q=43 $