我们如何理解Coppersmith算法

博客很久没有更新了

我们先来讨论一个，在我萌新时代，困扰我很久的问题：RSA低位泄露

比如说RSA的p，原本是512位，但我们已经知晓了它的低400位，我们该如何复原p？

当时我只检索到这个要用到coppersmith算法求小根，但是对当时初入数论模运算都搞不明白的我来说，它过于超纲，拼尽全力无法战胜。

题目

这里随便找了一个题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import gmpy2
from gmpy2 import *
from Crypto.Util.number import *
from random import randint
from gmpy2 import invert
from scret import flag

def myfunction(num):  #立方
    output = 0
    output=num**3
    return output

if __name__ == '__main__':
    flag_len = len(flag)
    p, q = getPrime(512), getPrime(512)

    while True:
        r = getPrime(512)
        R = bytes_to_long(str(r).encode())
        if isPrime(R):
            break

    n = p * q * r
    hint1 = R * r
    mod = myfunction(n)
    hint2 = pow(3*n+1, p % (2 ** 400), mod)
    m = bytes_to_long(flag)
    c = pow(m, 65537, n)

    print('All data:')
    print(f'n = {n}')
    print(f'c = {c}')
    print(f'hint1 = {hint1}')
    print(f'hint2 = {hint2}')

Coppersmith

问题转化

前面的二项式展开我们都不提，就说我们已经求出了p的低400位,记为plowp_{low}

那么我们的p就可以表示为关于x (即phighp_{high})的一个方程，f(x)=x∗2400+plowf(x) = x*2^{400} + p_{low}

显然 f(x)≡0mod  pf(x) \equiv 0 \mod p

我们就把RSA低位泄露问题转化成了一个寻找多项式 f(x)=x∗2400+plowf(x) = x*2^{400} + p_{low} 在模 p 下的根 x₀ 的问题

这样的方程不好求解。

但是我们可以试着找到一个新的多项式 g(x)，它必须满足两个关键条件：

  • 条件A (共享根): g(x) 必须也以 x₀ 为根，即 g(x₀) ≡ 0 (mod p)。
  • 条件B (系数小): g(x) 作为整数多项式（暂时忽略模 p），它的系数必须非常小。

这里我们还发现，因为 x0x_0 相对 pp 来说非常小，我们可以认为它是一个小根。

魔法发生

因为 x0x_0 本身很小（这是前提），并且 g(x) 的系数也很小（条件B），那么当我们计算 g(x₀) 的整数值时，这个结果 |g(x₀)| 也将是一个非常小的整数。

同时，我们又知道 g(x₀) 是 p 的倍数（条件A）。

现在想象一下：一个数，它既是 p 的倍数（p 是一个非常大的数），又是另一个非常小的数。唯一的可能性是什么？

这个数只能是 0！

所以，我们得出结论： g(x0)=0g(x_0) = 0 在整数域上成立！

所以我们只需要求 g(x0)=0g(x_0) = 0 的根就好，问题变得尤为简单！

那么问题来了，说了一大堆，这个 g(x)g(x) 从哪来

LLL

这时候需要请我们LLL算法出场

我们先来简单回顾一下什么叫格，LLL算法在做什么。

格（Lattice）

想象一下，我们在平面上画出一个平面直角坐标系，然后取两个向量 u1=(0,1)u_1 = (0,1) 和 u2=(1,0)u_2 = (1,0) （把它们称为基向量）.这时候，由这两个向量线性组合，可以得到一个网格。网格上存在十字交叉点（即k1u1+k2u2k_1u_1 + k_2u_2），格就是所有这些点组成的集合

同理，我们可以用不同数量的不同向量作为基向量，并想象任由它们做线性组合，最终能够产生一张有很多点的复杂大网。

我们用的基向量如果长度太长且“非常不正交”，那它表示这张大网的某个点，应该会很不简洁，很不舒服。

我们这里说用来表示这个格的基向量是“坏向量”。

而LLL算法的作用就是

我们嫌弃一个格的基向量太坏了，就把这些基向量喂给LLL，LLL算法会返回给我们，比较短且近乎正交的新的基向量。

我们用它给的基向量就能很舒服的表达格上的每个点，它是“好向量”

所以LLL就是把一个格的“坏向量”转化成“好向量”。

LLL的作用

那么我们回归问题

我们希望构建一个由根是 x0x_0 的多项式们组成的格

这样的话，需要基也是根为 x0x_0 的多项式。

这样把基向量喂给LLL，他就会返回一组更好的基，这些基应当足够短。

我们就取其中的第一个向量 v∗v^* ,它就代表一个系数很小的、根是 x0x_0 的多项式

我们只要通过 v∗v^* 就能反解出 x0x_0 了

这个想法很顺，但是我们需要考虑喂给LLL一组什么样的基。

构造基

显然只要我们喂的基两两非线性，LLL算法就能跑的动。但是跑的动不代表跑的好。

  • 考虑维度

我们必须清楚，LLL算法找到的短向量 v* 的长度与格的维度 ww 和行列式密切相关。一个粗略的公式是：
$ ||v^*|| ≤ 2^{((w-1)/4)} * det(B)^{(1/w)}$

我们在构造基向量的时候，维度越高越容易找到短向量。

  • 考虑让g(x_0)小于模数

正如"魔法发生"那里提到的，g(x0)g(x_0) 应当小于模数

因此我们可能需要将模数放大

综合这两个要求，我们可以采用这样的聪明的构造方法：
取正整数m(在实际应用中我们常让m从小到大不断尝试)

构造 gi(x)=N(m−i)∗f(x)ig_i(x) = N^{(m-i)} * f(x)^i

我们不难发现, gi(x)g_i(x) 应当是 pmp^m 的倍数

于是我们就可以放心把模数放大为 pmp^m

同时也通过这种方式构建了m个方程，也是增大了维度。

所以我们只要把这样构建出来的一组基，喂给LLL，得到一个短向量，求解x0x_0 ，什么问题都解决了！

总结

你说这玩意咋寻思出来的呢（嚼嚼嚼嚼嚼）