如何在 NTRU-PKCS 中找到多項式的逆
我正在編寫 NTRU 公鑰密碼系統的基於 java 的實現。我可以很好地理解加密和解密過程中涉及的大多數算法，但是密鑰生成過程給我帶來了嚴重的麻煩。
對於不熟悉的人，我將簡要介紹密碼系統的一些基礎知識，否則，請跳到標題為The Problem的段落。
我們將使用具有度數的多項式 $ <n $ . 添加和減去這些多項式的功能正常，但是乘以這些多項式的工作方式不同¹²。給定兩個多項式 $ A $ 和 $ B $ 學位 $ <n $ , 他們的產品是 $$ A \cdot B = c_0,x^0 + c_1,x^1 + \ldots + c_{n-1},x^{n-1} = C $$ 其中每個係數 $ c_k $ 由³計算： $$ c_k=\sum_{0\le i<n}a_i,b_{(k-i\bmod n)} $$ 乘以每個係數 $ a $ 同樣來自 $ b $ 以相反的順序（如果 $ b_k $ 是第一個係數 $ b $ 然後 $ b_{k-1} $ 循環到最後一個係數 $ b $ 等等）確保得到的多項式的次數保持不變 $ <n $ .
鑰匙 $ F $ 是一個多項式，其係數為 $ {-1,0,1} $ . 一個例子（其中 $ n=7 $ ） 是： $$ 1,x^0 + 0,x^1 + 0,x^2 + 1,x^3 + -1,x^4 + -1,x^5 + 0,x^6 $$ 或更簡單地說： $$ 1 + x^3 - x^4 - x^5 $$
$ F $ 用作私鑰，但必須經過驗證才能具有逆多項式 $ F_q $ 和 $ F_p $ , 這是多項式 $ <n $ 具有整數係數 $ q_i $ 和 $ 0 \leq q_i < q $ ， 和 $ p_i $ 和 $ 0 \leq p_i < p $ ， 在哪裡 $ q $ 和 $ p $ 是預定義的整數 ( $ q $ 與素數互質 $ p $ ).
$ F $ 必須滿足 $ F_q $ 和 $ F_p $ 存在給定：
$$ F \cdot F_q \equiv 1 \pmod q \quad\text{and}\quad F \cdot F_p \equiv 1 \pmod p $$ 也就是說，如果我們定義 $ C=F \cdot F_q $ , 它的係數 $ c_k $ 必須驗證 $$ c_k\bmod q=\begin{cases}1&\text{if }k=0\0&\text{otherwise}\end{cases} $$ 和同樣的 $ F \cdot F_p \equiv 1 \pmod p $ .
說了這麼多……
問題
我仍在努力掌握用於計算私有多項式密鑰的多項式逆的算法 $ F $ , $ F_p $ ， 和 $ F_q $ 為了$$ F\cdot F_q \equiv 1 \pmod q $$並且對於 $ p $ 等等
或者甚至驗證是否 $ F $ 是可逆的。我已經看到解釋算法的不同虛擬碼，但我所看到的都沒有詳細說明。該算法的其他解釋相當於“您可以使用擴展的歐幾里得算法計算逆”，沒有範例，並且我自己看看 eea，我仍然不知道它是如何應用的。我非常感謝有關多項式的簡明解釋 $ F $ 整數 $ p/q $ 和多項式次數 $ n $ .
讓我知道是否有任何我遺漏的關鍵概念或我遺漏的關鍵變數。
編者註：
¹在這個修改後的多項式乘法中， $ x^n $ 假定為 $ 1 $ 度係數 $ \ge n $ .
²等價地，這是多項式乘法模 $ x^n-1 $ .
³ $ u \bmod n $ 被定義為整數 $ v $ 和 $ 0\le v<n $ 和 $ u−v $ 的倍數 $ n $ .
免責聲明：我不熟悉 NTRU，也不在我的舒適區。因此進行了許多編輯。
提出的問題可以概括為：給定 $ n $ , $ q $ 互質互質 $ p $ ，並且對於 $ 0\le i<n $ 係數 $ f_i\in{-1,0,1} $ 的 $ F=\displaystyle\sum_{0\le i<n}f_i $ ， 找出 $ n $ 係數 $ q_i $ 的 $ F_q $ 和 $ p_i $ 的 $ F_p $ 這樣，多項式乘法執行模 $ x^n-1 $ , $ F\cdot F_q\equiv1\pmod q $ 和 $ F\cdot F_p\equiv1\pmod p $ ，或確定這是不可能的。
我們可以將問題處理為 $ F_q $ . 同樣的方法將適用 $ F_p $ . 或者，由於 $ q $ 和 $ p $ 互質，我們可以找到 $ H $ 和 $ F\cdot H\equiv1\pmod{(p,q)} $ 如果它存在，則減少其係數模 $ q $ 和 $ p $ 找到 $ q_i $ 和 $ p_i $ （但如果沒有 $ H $ ，我們只能得出結論，至少有一個 $ F_q $ 或者 $ F_p $ 不存在）。
一種概念上簡單的方法是將問題視為一個系統 $ n $ 線性方程組 $ \Bbb Z_q $ ， 和 $ n $ 未知數 $ q_i $ , 通過使用問題對等價方程的定義獲得 $ F_q\cdot F\equiv1\pmod q $ : $$ \forall k\in[0,n-1),\quad \sum_{0\le i<n}q_i,f_{(k-i\bmod n)}\equiv\begin{cases}1&\text{if }k=0\0&\text{otherwise}\end{cases}\pmod q $$ 並使用高斯消元法。如果我們使用問題的 $ F=1+x^3-x^4-x^5 $ 為了 $ n=7 $ , 那個線性系統去$$ q_0-q_2-q_3+q_4\equiv1\pmod q\ q_1-q_3-q_4+q_5\equiv0\pmod q\ q_2-q_4-q_5+q_6\equiv0\pmod q\ q_3-q_5-q_6+q_0\equiv0\pmod q\ q_4-q_6-q_0+q_1\equiv0\pmod q\ q_5-q_0-q_1+q_2\equiv0\pmod q\ q_6-q_1-q_2+q_3\equiv0\pmod q $$ 也就是說，通過重新調整$$ \begin{matrix} +q_0& &-q_2&-q_3&+q_4& & &\equiv1\pmod q\ &+q_1& &-q_3&-q_4&+q_5& &\equiv0\pmod q\ & &+q_2& &-q_4&-q_5&+q_6&\equiv0\pmod q\ +q_0& & &+q_3& &-q_5&-q_6&\equiv0\pmod q\ -q_0&+q_1& & &+q_4& &-q_6&\equiv0\pmod q\ -q_0&-q_1&+q_2& & &+q_5& &\equiv0\pmod q\ &-q_1&-q_2&+q_3& & &+q_6&\equiv0\pmod q\end{matrix} $$ 係數矩陣是循環的，其最後一行的係數為 $ F $ 以相反的順序。
這個碰巧沒有解決方案，除了 $ q=1 $ : 如果我們總結所有得到的行 $ 0\equiv1\pmod q $ . 一般情況下，除了 $ q=1 $ , 時無法解決 $ 0=\sum f_i $ 就像在此樣品中。
雖然我們通常可以通過高斯消除和仔細應用算術來解決系統（或發現它沒有解決方案） $ \Bbb Z_q $ , 這有成本 $ \mathcal O(n^3,\log q,\log\log q) $ 和用途 $ \mathcal O(n^2,\log q) $ 記憶。雖然循環矩陣有更好的方法，但我不會進一步討論。
解決這個問題的更好方法來自擴展歐幾里得算法，它給出了 $ A $ 和 $ B $ 在主環中，發現 $ U $ 和 $ V $ 在那個戒指中 $ A\cdot U+B\cdot V=G $ ， 在哪裡 $ G $ 是的最大公約數 $ A $ 和 $ B $ . 作為提供模逆的副產品 $ U $ 的 $ A $ 模組 $ B\ne0 $ , 或告訴它不存在時 $ G\ne1 $ .
該算法特別在這些環中找到逆：
戒指 $ \Bbb Z_q $ （整數），其中非負數 $ a $ 和 $ b $ 它可以去：
如果 $ b=0 $ ，輸出*“ $ a $ 你沒有反模 $ b $ “*然後停下來。
$ c\gets a $ , $ d\gets b $ , $ u\gets0 $ 和 $ v\gets1 $ .
重複
- 如果 $ c=0 $ ，輸出*“ $ a $ 你沒有反模 $ b $ “*然後停下來。
- 如果 $ c=1 $ ，輸出*“的倒數 $ a $ 模組 $ b $ 是 $ v $ “*然後停下來。
- 執行歐幾里得除法 $ d $ 經過 $ c $ 產商 $ z $ 和剩餘的 $ r $ 和 $ 0\le r<c $ .
- $ d\gets r $ 和 $ u\gets u+z\cdot v $ .
- 如果 $ d=0 $ ，輸出*“ $ a $ 你沒有反模 $ b $ “*然後停下來。
- 如果 $ d=1 $ ，輸出*“的倒數 $ a $ 模組 $ b $ 是 $ b-v $ “*然後停下來。
- 執行歐幾里得除法 $ c $ 經過 $ d $ 產商 $ z $ 和剩餘的 $ r $ 和 $ 0\le r<d $ .
- $ c\gets r $ 和 $ v\gets v+z\cdot u $
具有域內係數的多項式環 $ \Bbb Q $ （有理數），它可以去哪裡：
如果 $ B=0 $ ，輸出*“ $ A $ 你沒有反模 $ B $ “*然後停下來。
$ C\gets A $ , $ D\gets B $ , $ U\gets0 $ 和 $ V\gets1 $ .
重複
- 如果 $ C=0 $ ，輸出*“ $ A $ 你沒有反模 $ B $ “*然後停下來。
- 如果 $ C $ 有學位 $ 0 $ （也就是說，只有術語 $ c_0 $ )，輸出*“的倒數 $ A $ 模組 $ B $ 是 $ (1/c_0),V $ “*然後停下來。
- 執行多項式除法 $ D $ 經過 $ C $ 產商 $ Z $ 和剩餘的 $ R $ 程度小於程度 $ C $ .
- $ D\gets R $ 和 $ U\gets U+Z\cdot V $ .
- 如果 $ D=0 $ ，輸出*“ $ A $ 你沒有反模 $ B $ “*然後停下來。
- 如果 $ D $ 有學位 $ 0 $ （也就是說，只有術語 $ d_0 $ )，輸出*“的倒數 $ A $ 模組 $ B $ 是 $ (-1/d_0),V $ “*然後停下來。
- 執行多項式除法 $ C $ 經過 $ D $ 產商 $ Z $ 和剩餘的 $ R $ 程度小於程度 $ D $ .
- $ C\gets R $ 和 $ V\gets V+Z\cdot U $ .
在有限域中具有係數的多項式環 $ \Bbb Z_p $ 為素數 $ p $ : 同上，除了當一個係數 $ \displaystyle\frac st $ 得到，我們將其替換為整數 $ 0 $ 什麼時候 $ s=0 $ ，或以其他方式使用整數 $ (t/\gcd(s,t))^{-1},(s/\gcd(s,t))\bmod q $ .
後者正是我們需要的 $ F_p $ : 我們餵 $ A=F $ 和 $ B=x^n-1 $ 到算法，它計算 $ F_p=A^{-1}\bmod B $ （或告訴它不存在）。
但是，對於復合 $ q $ , 可以出現 $ \displaystyle\frac st $ 不能帶回來 $ \Bbb Z_q $ 因為 $ \gcd(t,q)\ne1 $ .
我不確定：
- 如果我們可以得出結論，當我們遇到問題時，我們可以停下來得出結論： $ F $ 不可逆。
- 如果我們可以用域中的係數計算多項式環中的逆 $ \Bbb Q $ ，最後減少。我想我們可以找到 $ F $ 不可逆，但它確實是模可逆的 $ q $ .
什麼時候 $ q $ 是不同素數的乘積，我們可以通過找到每個素數除法的逆模數來解決這個問題 $ q $ , 並使用中國剩餘定理來計算逆模的係數 $ q $ . 我們不需要知道因式分解 $ q $ 提前：當我們遇到問題時，GCD 給了我們一個（可能是部分的）因式分解 $ q $ . 但是我不知道什麼時候該做什麼 $ q $ 能被素數的平方整除。
工作中：進一步理順，例如。
有關成熟、更快的方法，請參閱 Joseph H. Silverman，Almost Inverses 和 Fast NTRU Key Creation，NTRU Technical Report #014，1999。