encryption - 如何将消息变成多项式？

Question

我正在做一个项目，我必须在其中实现 NTRUEncrypt 公钥密码系统。根据他们的指南，这是加密的第一步 - “Alice 想要向 Bob 发送 secret 消息，将她的消息以系数为 {-1,0,1} 的多项式 m 的形式发送”。我想知道如何将我的消息变成多项式。谢谢。

Answer 1

你可以随心所欲地做。也许最直接的方法是将您的消息转换为三元表示

"Hello" -> 72, 101, 108, 108, 111 -> 02200, 10202, 11000, 11000, 11010

所以我将字符转换为它们的 ASCII 表示，然后将这些表示转换为它们的三进制表示(假设我仅限于 7 位 ASCII 空间，我只需要五个三进制数字)。

然后通过将三进制数字0映射到0，将三进制表示转换为{-1, 0, 1}上的多项式，三进制数 1 到 1 和三进制数 2 到 -1 并假设3对应的数字^k是x^k¹的系数:

02200 -> p1(x) = 0 +    0 * x + (-1) * x^2 + (-1) * x^3 + 0 * x^4
10202 -> p2(x) = (-1) + 0 * x + (-1) * x^2 +    0 * x^3 + 1 * x^4
11000 -> p3(x) = 0    + 0 * x +    0 * x^2 +    1 * x^3 + 1 * x^4
11000 -> p4(x) = 0    + 0 * x +    0 * x^2 +    1 * x^3 + 1 * x^4
11010 -> p5(x) = 0    + 1 * x +    0 * x^2 +    1 * x^3 + 1 * x^4

然后我的信息是

p1(x) + x^5 * p2(x) + (x^5)^2 * p3(x) + (x^5)^3 * p4(x) + (x^5)^4 * p5(x)

所以我的多项式的系数是

(0, 0, -1, -1, 0, -1, 0, -1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1).

无论您如何操作，关键是您可以根据自己的喜好将消息表示为多项式。最好是找到从消息空间到 {-1, 0, 1} 上的多项式空间的双射，该双射易于计算并且具有易于计算的逆。

¹ 这是转型的关键。五位数的三进制数 a4a3a2a1a0 正好对应于计算多项式 a4 * x^4 + a3 * x^3 + a2 * x^2 +a1 * x + a0 * x^0 在 x = 3。因此，{-1, 0, 1} 上的多项式与三元数之间存在明显的一一对应关系。