2

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

4

2 回答 2

6

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

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

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

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

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

1这是转型的关键。一个五位数的三进制数正好对应于在处计算多项式。所以在多项式和三进制数之间存在明显的一一对应关系。a4a3a2a1a0a4 * x^4 + a3 * x^3 + a2 * x^2 +a1 * x + a0 * x^0x = 3{-1, 0, 1}

于 2009-10-13T20:06:04.410 回答
3

我为 NTRU 工作，所以我很高兴看到这种兴趣。

IEEE 标准 1363.1-2008 指定如何使用最新的参数集实现 NTRUEncrypt。它为二进制->三进制转换指定的方法是：

如下将每个三位量转换为两个三元系数，并将得到的三元量连接起来得到[输出]。

{0, 0, 0} -> {0, 0}
{0, 0, 1} -> {0, 1}
{0, 1, 0} -> {0, -1}
{0, 1, 1} -> {1, 0}
{1, 0, 0} -> {1, 1}
{1, 0, 1} -> {1, -1}
{1, 1, 0} -> {-1, 0}
{1, 1, 1} -> {-1, 1}

要转换回来：

将每组两个三元系数按如下方式转换为三个位，并将得到的位量串联得到[输出]：

{0, 0} -> {0, 0, 0}
{0, 1} -> {0, 0, 1}
{0, -1} -> {0, 1, 0}
{1, 0} -> {0, 1, 1}
{1, 1} -> {1, 0, 0}
{1, -1} -> {1, 0, 1}
{-1, 0} -> {1, 1, 0}
{-1, 1} -> {1, 1, 1}
{-1, -1} -> set "fail" to 1 and set bit string to {1, 1, 1}

请注意，要安全地加密消息，您不能简单地将消息转换为三进制并应用原始 NTRU 加密。消息需要在加密之前进行预处理，在加密之后进行后处理，以防止可能在传输过程中修改消息的主动攻击者。必要的处理在 IEEE Std 1363.1-2008 中指定，并在我们 2003 年的论文“NAEP：存在解密失败的可证明安全性”中进行了讨论（可从http://www.ntru.com/cryptolab/articles.htm#2003_3，但请注意，此描述针对的是二进制多项式而不是三进制）。

希望这可以帮助。

@Bert：我们在不同的时候都推荐过二元或三元多项式。三元多项式允许使用较短的密钥实现相同的安全性。然而，过去我们认为二进制多项式允许 q（大模）为 256。这对 8 位处理器很有吸引力。从那以后，我们已经确定采用 q = 256 会降低安全性，这是不可接受的（特别是，它使解密失败的可能性太大）。由于我们不再将小 q 作为目标，因此我们可以利用三元多项式总体上给出更小的键。

于 2010-03-08T20:43:09.920 回答