如何自讨苦吃：暴力破解NTRU

介绍

格密码学是一种密码方案，它依赖于与格相关的某些计算问题的难度，格是由空间中点的重复模式形成的几何结构。基于格的密码学被认为是后量子密码学的一个有希望的候选者，因为它被认为是能够抵抗量子计算机的攻击的。

NTRU（N 阶截断多项式环单元）密码系统是一种基于格的公钥密码系统，于 1996 年被提出。它基于一种特定类型的格（称为理想格）的性质，理想格是一种由多项式环的理想构造的特殊类型。NTRU 密码系统使用具有小系数的多项式来生成公钥和私钥，然后将其用于加密和解密。更多详情，请参阅我们之前的帖子。在这篇文章中，我们将解释找到私钥等同于在格上找到短向量，并给出暴力攻击的界限。

NTRU 中的公钥和私钥

在我们之前的帖子中，我们讨论了 NTRU 加密方案。我们现在开始展示它的密钥如何与特定的格相关；加密和解密过程与此无关；因此可以将其放在一边。

从我们之前的帖子中回忆起环 $R = \mathbb{Z}[X]$ 和环 $R_q = \mathbb{Z}_q[X]$。NTRU 中的私钥由两个多项式 $f, g \in R$ 组成，它们的系数在某种程度上是小的：它们只允许等于 0、1 或 -1。 这些被称为三元多项式。

多项式 $f$ 必须有一个逆元 $F \in R_q$。例如，令 $N = 5, q = 37$，且

$f = 1 + x - x^2 + x^4$。令 $F \in R$ 为由

$F = 29x^4 + 35x^3 + 22x^2 + 12x + 32$ 给出的多项式，让我们证明 $F$ 是 $f$ 在 $R_q$ 中的逆元。

回想一下，我们在之前的帖子中解释了 $R_q$ 中的乘积：我们像往常一样相乘，替换掉 $x^N$ 的出现。那么在我们的示例中，我们有

$fF = 29x^8 + 35x^7 + 30x^6 + 6x^5 + 8x^3 + 2x^2 + 7x + 32 = (29 + 8)x^3 + (35 + 2)x^2 + (30 + 7)x + (6 + 32) = 1$。这个例子表明，$f$ 的逆可能有任意大的系数，即使 $f$ 很小。

公钥是由 $h = Fg$ 给出的多项式 $h \in R_q$。在我们的例子中，如果我们令

$g = x - x^3 - x^4$，我们有

$h = 28x^4 + 35x^3 + 22x^2 + 12x + 32$。我们看到，虽然 $h$ 是由三元多项式构造的，但它远非三元。

重访Rollup环

通过将每个 $x^N$ 的出现替换为 1，我们可以将每个多项式 $h \in R$ 写为 $h = h0 + \cdots + h{N-1}x^{N-1}$。此外，我们将把多项式 $h$ 识别为向量 $h = (h0, \dots, h{N-1})$。

就这些术语而言，$R$ 中的乘法可以用矩阵形式表示。更准确地说，令 $M_h \in \mathbb{Z}^{N \times N}$ 为以下矩阵。

$M_h = egin{pmatrix} h_0 & h1 & \cdots & h{N-1} \ h_{N-1} & h0 & \cdots & h{N-2} \ \vdots & \vdots & \ddots & \vdots \ h_1 & h_2 & \cdots & h_0 \end{pmatrix}$。

那么，给定一个多项式 $f \in R$ 并令 $g = fh$，不难看出我们有向量的等式

$g = f \cdot M_h$。关于上面的例子，读者可以验证模 37，我们有

(0, 1, 0, -1, -1) = (1, 1, -1, 0, 1) \cdot 
 egin{pmatrix}
32 & 12 & 22 & 35 & 28 \
28 & 32 & 12 & 22 & 35 \
35 & 28 & 32 & 12 & 22 \
22 & 35 & 28 & 32 & 12 \
12 & 22 & 35 & 28 & 32
\end{pmatrix}.

NTRU 格

自然攻击涉及寻找三元多项式 $f, g \in R$ 使得 $fh = g \in R_q$。等价地，存在 $k \in R$ 使得

$fh = g + qk \in R$。

为了使用上面的矩阵公式，我们引入由

$M_{h,q} = egin{pmatrix} I_N & M_h \ 0 & qIN \end{pmatrix}$ 给出的分块矩阵 $M{h,q}$。请注意，它具有非零行列式。这意味着它的行构成了 $\mathbb{R}^{2N}$ 的一个基。特别地，它们张成了一个（公开的）格，我们将其表示为 $L_{h,q}$。

考虑到分块乘法，我们看到上面的等式被重写为

$(f, -k) \cdot M_{h,q} = (f, g)$。从这里开始，我们可以把多项式放在一边。

请注意，左侧的向量是通过用 $(f, -k)$ 的系数（它们是整数）线性组合 $M{h,q}$ 的行获得的。换句话说，这是一个在格 $L{h,q}$ 中的向量。

右侧的向量，因为 $f$ 和 $g$ 是三元的，是一个小的（或短的）向量。因此，破解 NTRU 等同于在由公钥给出的格 $L_{h,q}$ 中找到短向量。

找到短向量的粗略方法

格：回顾基础知识

回想一下，给定 $\mathbb{R}^n$ 的一个基 $v_1, \dots, v_n$，由这个基定义的格 $L$ 是

$L = { \sum_{i=1}^n k_i v_i : k_i \in \mathbb{Z} }$。

很容易看出，如果我们对给定的基应用一个由具有积分系数且行列式为 1 或 -1 的矩阵（一个单模矩阵）给出的基变换，我们就得到了 $L$ 的一个不同的基。此外，$L$ 的每个其他基都是以这种方式获得的。

例如，由规范基 $e_1 = (1, 0), e_2 = (0, 1)$ 定义的平面中的格也可以由基

$v = (-7226, 23423), w = (379835, -1231231)$ 定义。事实上，$-1231231v - 379835w = e_1, -23432v - 7226w = e_2$，这表明 $e_1$ 和 $e_2$（以及因此它们的每个积分组合）可以写成 $v$ 和 $w$ 的积分组合。

正如我们所见，同一个格可以具有或多或少复杂的基。

体积

格 $L$ 最重要的不变量是它的体积，它是 $L$ 的基 $B$ 生成的平行六面体 $F$ 的大小。

它可以计算为 $vol(L) = |\det(C)|$，其中 $C$ 是以 $B$ 中的向量作为列的矩阵（有兴趣了解为什么这会计算体积的读者应该考虑 $n = 2$ 的情况）。这个数字与所选的基无关（即，$L$ 的一个不变量），因为更改 $B$ 会导致将 $C$ 乘以一个单模矩阵。

体积对于我们的密码学兴趣至关重要，因为它给出了最短向量大小的界限。

短向量：暴力破解

每个格 $L$ 都包含零向量，在讨论短向量时自然会将其丢弃。更准确地说，$L$ 中的最短向量是一个非零向量 $v \in L$，使得 $|v|$ 最小。这样的向量存在，尽管它不是唯一的：例如，因为 $|v| = |-v|$。

根据埃尔米特（Hermite）在 19 世纪的一个结果，我们知道

格 $L$ 包含一个最短向量 $v$，使得对于每个 $1 \le i \le n$ 都有 $|v_i| \le vol(L)^{1/n}$。

这给了我们一个框 $B$，我们可以在其中通过暴力破解来搜索最短向量。

这将花费多少？粗略地说，$L \cap B$ 应该是 $F$ 放入 $B$ 中的次数。因此，根据埃尔米特的结果，我们得到

$L \cap B \sim vol(B) / vol(L) = (2 vol(L)^{1/n})^n / vol(L) = 2^n$，这表明对于大的 $n$，暴力破解是不切实际的，与 $L$ 无关。这对于可用于埃尔米特结果的细微改进仍然成立。

总结

在这篇文章中，我们描述了如何将 NTRU 中涉及多项式的密钥查找问题转换为矩阵问题。我们解释了 NTRU 公钥背后的格，以及如何将查找私钥简化为在该格中查找短向量。我们还提供了一些关于通常使用暴力攻击查找短向量有多难的界限，表明对于足够大的 $n$ 值（即，非常大次数的多项式），这是不切实际的。在接下来的文章中，我们将介绍其他格方案（例如 CRYSTALS Kyber）以及与全同态加密相关的方案的基础知识，以及更有效的格缩减技术。

• 原文链接： blog.lambdaclass.com/how...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～