為什麼 NTRUEncrypt 在大模數的不同值上失敗？
我試圖嚴格遵循此處的算法（保持相同的變數名稱）並在Sage Math引擎中重建密碼系統。它似乎適用於參數
(N, p, q) = (11, 3, 31)，但在最後引發斷言錯誤(N, p, q) = (11, 3, 29)。請看下面的程式碼：N = 11 p = 3 q = 31 # fails for 29 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 = RR([-1, 1, 1, 0, -1, 0, 1, 0, 0, 1, -1]) g = RR([-1, 0, 1, 1, 0, 1, 0, 0, -1, 0, -1]) fp = PP(f) ^ -1 fq = QQ(f) ^ -1 assert fp * f == 1 assert fq * f == 1 h = QQ( (p * fq) * g ) m = PP([-1, 0, 0, 1, -1, 0, 0, 0, -1, 1, 1]) r = RR([-1, 0, 1, 1, 1, -1, 0, -1, 0, 0]) e = QQ(r * h + m) a = QQ(f) * e a = ZZ['x']([coeff.lift_centered() for coeff in a.lift()]) b = PP(a) c = fp * b assert c == m我在這裡做錯了什麼嗎？
PS 要快速檢查Sage程式碼，您可以使用此站點： https ://sagecell.sagemath.org/
沒有什麼不正確的，基於格的密碼術有解密失敗的機會，並且這種機會隨著度數和雜訊相對於模數的增加而增加。我認為查看此處的實際數字非常有啟發性，以便了解基於格的密碼學中固有的一些不確定性。如果我們擴展您的 sage 程式碼以並排生成兩個案例
N = 11 p = 3 q1 = 31 q2 = 29 R.<x> = PolynomialRing(ZZ) RR = R.quotient(x^N - 1) P.<x> = PolynomialRing(Zmod(p)) PP = P.quotient(x^N - 1) Q1.<x> = PolynomialRing(Zmod(q1)) QQ1 = Q1.quotient(x^N - 1) Q2.<x> = PolynomialRing(Zmod(q2)) QQ2 = Q2.quotient(x^N - 1) f = RR([-1, 1, 1, 0, -1, 0, 1, 0, 0, 1, -1]) g = RR([-1, 0, 1, 1, 0, 1, 0, 0, -1, 0, -1]) fp = PP(f) ^ -1 fq1 = QQ1(f) ^ -1 fq2 = QQ2(f) ^ -1 assert fp * f == 1 assert fq1 * f == 1 assert fq2 * f == 1 h1 = QQ1( (p * fq1) * g ) h2 = QQ2( (p * fq2) * g ) m = PP([-1, 0, 0, 1, -1, 0, 0, 0, -1, 1, 1]) r = RR([-1, 0, 1, 1, 1, -1, 0, -1, 0, 0]) e1 = QQ1(r * h1 + m) e2 = QQ2(r * h2 + m) a1 = QQ1(f) * e1 al1 = ZZ['x']([coeff.lift_centered() for coeff in a1.lift()]) a2 = QQ2(f) * e2 al2 = ZZ['x']([coeff.lift_centered() for coeff in a2.lift()]) b1 = PP(al1) b2 = PP(al2) c1 = fp * b1 c2 = fp * b2請注意，我還為一個(X)模組q $ a(x)\mod q $ 及其對Z[X] $ \mathbb Z[x] $ 的提升使用了單獨的變數。如果我們比較
a1，a2我們看到sage: a1 27*xbar^10 + 3*xbar^9 + 30*xbar^8 + 4*xbar^7 + 15*xbar^6 + 10*xbar^5 + 4*xbar^4 + 20*xbar^3 + 27*xbar^2 + 24*xbar sage: a2 25*xbar^10 + 3*xbar^9 + 28*xbar^8 + 4*xbar^7 + 15*xbar^6 + 10*xbar^5 + 4*xbar^4 + 18*xbar^3 + 25*xbar^2 + 22*xbar這些是相同多項式一個(X)=r(X)G(X)p+F(X)米(X)$$ a(x)=r(x)g(x)p+f(x)m(x) $$ =−4個X10+3個X9−X8個+4個X7+15X6個+10X5個+4個X4個−11X3個−4個X2個−7X$$ =-4x^{10}+3x^9-x^8+4x^7+15x^6+10x^5+4x^4-11x^3-4x^2-7x $$ 在整數上，為了解密，我們想將這個多項式的每一個約簡提升到原始整數版本。整數多項式的係數是小整數乘積之和，所以我們希望它們不要變大。特別是，如果所有係數都在(−q/2個,q/2個) $ (-q/2,q/2) $ 範圍內，則縮減可以解釋為該區間中的留數，並無誤地提升回原始多項式。但是，如果我們看X6個 $ x^6 $ t 的係數是 15，這雖然在區間(−31/2個,31/2個) $ (-31/2,31/2) $ 內，但不在區間內(−29/2個,29/2個) $ (-29/2,29/2) $ 所以我們的減少不是微不足道的，我們的電梯不起作用。具體來說，如果我們看一下
al1，al2我們有sage: al1 -4*x^10 + 3*x^9 - x^8 + 4*x^7 + 15*x^6 + 10*x^5 + 4*x^4 - 11*x^3 - 4*x^2 - 7*x sage: al2 -4*x^10 + 3*x^9 - x^8 + 4*x^7 - 14*x^6 + 10*x^5 + 4*x^4 - 11*x^3 - 4*x^2 - 7*x在第二種情況下，我們在整數上恢復了錯誤的多項式，導致後續步驟失敗。q $ q $ 越大，整數多項式的係數落在可恢復範圍之外的可能性越小，從而減少解密失敗。然而，增加q $ q $ 可以讓攻擊者的生活更輕鬆，並且必須達成權衡。
在解密失敗的情況下，可以通過掃描提升多項式中接近q/2個 $ q/2 $ 的係數來糾正此類錯誤，然後查看如果我們將這些可疑係數調整為±q $ \pm q $ 會發生什麼。然而，這會導致解密時間不穩定，並產生各種側通道、欺騙和故障注入漏洞。