如何将消息转换为多项式？

Question

我正在做一个我必须实现NTRUEncrypt公钥密码系统的项目.这是根据他们加密指南的第一步 - "爱丽丝,想要向Bob发送一个秘密消息,将她的消息以多项式m的形式放入系数{-1,0,1}".我想知道如何将我的信息变成多项式.谢谢.

Answer 1

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

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

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

然后三元表示形式转换为多项式上{-1, 0, 1}通过映射三元数字0到0,三元数字1到1和三元位2到-1并假定对应于3 ^ k中的数字是系数的x ^ķ ¹:

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}这很容易计算并具有容易计算的逆.

¹这是转型的关键.五位三进制数正好对应评估多项式的.因此,在多项式和三元数之间存在明显的一对一对应关系.a4a3a2a1a0a4 * x^4 + a3 * x^3 + a2 * x^2 +a1 * x + a0 * x^0x = 3{-1, 0, 1}