如何在 NTRU 上將消息編碼和解碼為多項式形式

此問題基於先前提出的問題。如何將消息變成 NTRU 加密的多項式？

我的任務是使用玩具參數實現 NTRU，例如 $ N=7 $ 或者 $ N=11 $ 我有一些問題。

1. 消息長度是否必須小於或等於參數 $ N $ ? 我可以對大於參數的消息進行加密嗎 $ N $ 還是我必須把它們分開？
2. 提到的一種方法是將消息轉換為 ASCII，然後轉換為三進制形式，然後將它們加起來作為輸入，如下所示：

h 01101000 X^3+X^5+X^6
e 01100101 1+X^2+X^5+X^6
l 01101100 X^2+X^3+X^5+X^6
l 01101100 X^2+X^3+X^5+X^6
o 01101111 1+X+X^2+X^3+X^5+X^6
w 01110111 1+X+X^2+X^4+X^5+X^6
o 01101111 1+X+X^2+X^3+X^5+X^6
r 01110010 X+X^4+X^5+X^6
l 01101100 X^2+X^3+X^5+X^6
d 01100100 X^2+X^5+X^6

但是，在這種情況下，鑑於解密的消息將是所有多項式的相加，我該如何解密消息？還是我必須分別加密和解密每個字母？

NTRU 在環上執行 $ R = \mathbb Z[x]/(X^N -1) $ . 因此所有參數都必須位於這個多項式環中。

1.消息長度是否必須小於或等於參數N？我可以對大於參數 N 的消息進行加密還是必須將它們分解？

這實際上取決於編碼。連結範例建議使用二進制編碼。在這種情況下，如果使用 ASCII，那麼您可以使用 7 次多項式對其進行編碼。因此，如果您的 $ N =7 $ 那麼您不能加密多個 ASCII 字元。假設您對消息使用 ASCII 字元，您必須逐個字元地劃分消息進行加密。

其他編碼是可能的，如三元 $ {-1,0,1} $ , 但是，為簡單起見，將二進製文件保留在開頭。

2. 但是，在這種情況下，鑑於解密的消息將是所有多項式的相加，我該如何解密消息？還是我必須分別加密和解密每個字母？

您必須分別加密它們中的每一個。請注意，該範例不是三進制編碼，而是二進制編碼。像這樣檢查它們；

$$ \texttt{h 01101000} = \color{red}{1}\cdot X^6 + \color{red}{1}\cdot X^5 + \color{blue}{0}\cdot x^4 + \color{red}{1}\cdot X^3 + \color{blue}{0}\cdot x^2 + \color{blue}{0}\cdot x^1 + \color{blue}{0}\cdot x^0 $$

實際上，在三元中，人們希望看到一些 $ -1x^i $ 至少在某些編碼中，如果不故意選擇所有編碼，則不包括 $ -1 $ .

---

以下是將字元編碼為多項式的範例 SageMath 程式碼。使用 NTRU 加密/解密執行的完整程式碼位於GitHub。

Zx.<x> = ZZ[]

def encodeASCIIToPolynomial(c):
  
   C = ord(c)
   M = 0
   i = 0
   while(C > 0):
       M = M + x^i*(C %2)
       C = C//2
       i += 1
   return M
   
def decodePolynomialToASCII(D):

   x =0
   for t in D:
       x = x + t
       x = x *2
   return x

message = 'Z'
print("Message to Encrypt            ", message)
m = encodeASCIIToPolynomial(message)
print("Message encoded to Polynomial ", m)
print("Decoding back to character     ",chr(decodePolynomialToASCII(m)))

引用自：https://crypto.stackexchange.com/questions/88561