格理论与曲柄函数

前段时间，我闲着无聊在 Twitter 上发了一篇帖子，讲的是如果你只知道一个整数的平方根的小数部分，如何找到这个整数。我的 Twitter 现在是私密的，而且也闲置不用了，但我还是时不时会收到关于这个主题的问题，所以我决定把它写成一篇博客文章放在这里。

你可能会问，为什么要关心从平方根的小数部分重构一个整数呢？事实证明，有个怪人声称这可以作为他出色的密码系统的基础，所以证明这种重构是可能的，就相当于一次密钥恢复攻击。

计算平方根

和一般的伪密码学一样，官方文档对算法的实际描述非常少，所以我们必须首先确定定义，然后才能真正攻击这个密码系统。

从文档中可以推断出，我们首先选择一个秘密的 $n$ 比特整数 $a$，它不是一个完全平方数（如果 $a$ 是一个完全平方数，攻击将不起作用，但算法只会产生零，所以很容易区分）。然后，我们通过查看 $\sqrt{a} - \lfloor\sqrt{a}\rfloor$ 的数字来生成一个“随机”比特流，也就是说，我们研究的原语是一个 DRBG。

在我们研究这个算法的安全性之前，我们先快速看一眼它在其他方面是如何作为一个 DRBG 工作的。计算平方根的最佳算法是使用牛顿法首先计算倒数平方根，然后通过与数字本身相乘来恢复平方根。换句话说，将牛顿法应用于函数 $f(x) = \frac{1}{x^2} - a$。这个函数显然在 $\frac{1}{\sqrt{a}}$ 处有一个零点，假设我们从一个还算体面的地方开始，牛顿法应该能以二次收敛的速度找到它。

对于牛顿法，我们需要首先计算我们函数的导数，也就是 $f'(x) = -2\frac{1}{x^3}$。

然后，牛顿迭代给了我们：

$x_{i+1} = x_i - \frac{f(x_i)}{f'(x_i)}=x_i-\frac{\frac{1}{x^2} - a}{-2\frac{1}{x_i^3}}=\frac{1}{2}x_i(3-ax_i^2)$

现在我们可以看到为什么我们更喜欢用迭代法计算逆平方根：这个公式恰好只除以 2，所以它比必须除以 $x_i$ 要便宜得多，否则如果事情没有这么顺利地抵消掉，我们就不得不这么做。

二次收敛意味着我们每次迭代步骤大约会使正确数字的数量翻倍，但是看看我们的迭代步骤，我们需要乘以几个 $n$ 比特精度的数字，所以这个算法的总时间复杂度应该是 $\mathcal{O}(n^\frac{3}{2}\log n)$，空间复杂度为 $\mathcal{O}(n)$ 比特。

这是非常糟糕的。一个 DRBG 应该具有线性时间复杂度和恒定空间复杂度，也就是说，产生额外的随机比特的成本不应该取决于之前创建了多少随机性。似乎即使我们的怪人也意识到了这一点，因为他使用这个生成器只是为了播种一个 Blum-Blum-Shub 生成器，虽然它是我们拥有的最慢的 DRBG 之一，但它具有线性时间复杂度和恒定空间复杂度。你也可以在其中添加一个后门，我想如果你喜欢的话，这也可以成为 DRBG 的一个属性。

格（Lattice）从左边进入舞台

撇开对这个 DRBG 表现有多糟糕的抱怨，我们来谈谈这篇文章的主要内容，如何破解它。我们将使用一个众所周知的技术来处理丢番图方程，并使用一些格数学。

为此，让我们得到一些我们的 $n$ 比特整数 $a$ 的 $m$ 比特流 $\alpha = \sqrt{a}-\lfloor\sqrt{a}\rfloor\in[0, 1]$。换句话说，$a = (k+\alpha)^2=k^2+2k\alpha+\alpha^2$，对于某个未知的整数 $k$。让我们设置 $l = a - k^2$。这样我们就有了 $2k\alpha - l = \alpha^2$，其中 $k$ 和 $l$ 都是未知的整数。这看起来不是很乐观，一个方程有两个未知变量，但后来你意识到 $\alpha$ 的精度足够高，包含了关于这两个整数的足够多的信息，如果我们能把它挖掘出来的话。这是一个线性方程（事实上，替换的目标之一就是使它线性化），如果你在我的前一篇文章中注意到了，当系数是整数时，线性方程正是格的用武之地。不过，在我们得到实际的格之前，我们还需要进一步处理它。首先，我们需要一个大数，比如 $p=2^{n+4}$。这里最重要的是不是 $p$ 本身的值，而是它对于接下来发生的事情来说足够大。接下来是一个格，由以下向量生成

$\begin{pmatrix}2p\alpha\1\0\end{pmatrix},\begin{pmatrix}-p\0\1\end{pmatrix}$

换句话说，我们的格的元素是 $\mathbb{R}^3$ 形式的向量 $\begin{pmatrix}p\cdot(2\alpha x-y)\x\y\end{pmatrix}$，其中 $x, y$ 是整数。特别是，根据我们之前的计算，向量 $\begin{pmatrix}p\alpha^2\k\l\end{pmatrix}$ 是我们格中的一个向量。由于 $p$ 如此之大，这个向量相当接近 $\begin{pmatrix}p\alpha^2\0\0\end{pmatrix}$，因为 $k$ 和 $l$ 都大约是 $\sqrt a$，也就是说，只有 $\frac{n}2$ 位的整数。但是，如果我们改变 $x$ 或 $y$，我们要么必须使它们非常大，否则我们将永远无法在第一个坐标中达到如此接近的程度，因为我们仔细地平衡了所有东西，以便我们的线性方程能够成立。

换句话说，如果我们找到最接近 $\begin{pmatrix}p\alpha^2\0\0\end{pmatrix}$ 的格向量，我们就找到了我们的整数 $k, l$ 以及它们对应的 $a$。

但是等等，我听到你说，这难道不是最近向量问题（Closest Vector Problem，CVP）吗，它以难以计算而闻名。没错，确实是。而且很难计算。对于更高维度的格来说。对于嵌入到三维空间中的秩为 2 的格来说，就不是了。你只需要减少上面的格基，用这个基表示 $\begin{pmatrix}p\alpha^2\0\0\end{pmatrix}$，将系数四舍五入为整数，然后，就像变魔术一样，这些系数就是未知的整数。我在这里实现了这个算法，这是一个示例输出：

二维格的格缩减非常快，导致算法的破解速度几乎与最初的计算速度一样快。该算法的作者建议了一种通过改变使用的偏移量来加强的技术，即丢弃一些密钥流。当然，这没有任何作用，因为攻击速度足够快，并且密钥流的计算速度足够慢，你可以简单地暴力破解所有可能的起点，根据需要将 $a$ 更改为 2 的幂，以解释丢弃的比特。

虽然这个算法显然不适用于密码学目的，但使用格来解决丢番图方程的一般技术是一种有用的工具，可以理解和研究，例如，在 Coppersmith 对具有小指数的 RSA 的攻击中使用了类似的技术，对于任何对离散数学感兴趣的人来说，理解这些技术都很有价值。

• 标签 密码学，格

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