Coppersmith攻击

First Post:

Last Update:

Coppersmith攻击

coppersmith是一种针对于模多项式找所有小整数根的攻击方式，有单变量，二元变量和多元变量三种形式，它运用LLL算法来实现
我的理解的是我们可以根据已知的公钥，密文和部分明文来构造一个多项式,然后用LLL算法将多项式转化为格的形式，通过寻找短向量来解出多项式的根，根的值就可能是私钥d或者明文。
具体可以参考ctf-wiki(https://ctf-wiki.org/crypto/asymmetric/rsa/rsa_coppersmith_attack/)

SUCTF:ez_RSA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from Crypto.Util.number import *
from hashlib import sha256
flag = open("flag.txt").read()
p = getPrime(512)
q = getPrime(512)
e = getPrime(256)
n = p*q
d = inverse(e,(p-1)*(q-1))
d_m = ((d >> 512) << 512)
print("d_m = ",d_m)
print("n = ",n)
print("e = ",e)

assert flag[6:-1] == sha256(str(p).encode()).hexdigest()[:32]
# d_m =  54846367460362174332079522877510670032871200032162046677317492493462931044216323394426650814743565762481796045534803612751698364585822047676578654787832771646295054609274740117061370718708622855577527177104905114099420613343527343145928755498638387667064228376160623881856439218281811203793522182599504560128
# n =  102371500687797342407596664857291734254917985018214775746292433509077140372871717687125679767929573899320192533126974567980143105445007878861163511159294802350697707435107548927953839625147773016776671583898492755338444338394630801056367836711191009369960379855825277626760709076218114602209903833128735441623
# e =  112238903025225752449505695131644979150784442753977451850362059850426421356123

这里给的是d的高位
由n=pq和φn=(p-1)(q-1)得到φn=n-p-q+1
代入de=kφn+1
这边是一个近似推导dme约等于k*(n-p-q+1)+1,由于n-p-q+1中n是1024位的素数，p和q的和对n的影响有限，可以简化为n
所以可得下面关系
$$
k=(ed_m-1)//n + 1
$$
由标准关系得到
$$
k(n-p-q+1)+1==e*d\
(p+q) =(n+1+k^{-1})\mod e
$$
那么可以通过coppersmith方法来构造多项式寻找根，从而解出p和q

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
from sage.all import *

def small_roots(f, X, beta=1.0, m=None):
    N = f.parent().characteristic()
    delta = f.degree()
    if m is None:
        epsilon = RR(beta**2 / f.degree() - log(2 * X, N))
        m = max(beta**2 / (delta * epsilon), 7 * beta / delta).ceil()
    t = int((delta * m * (1 / beta - 1)).floor())
    f = f.monic().change_ring(ZZ) #单项式化
    P, (x,) = f.parent().objgens()
    g = [x**j * N**(m - i) * f**i for i in range(m) for j in range(delta)]
    g.extend([x**i * f**m for i in range(t)])

    # 直接使用 Sage 的方法来处理矩阵 B
    B = Matrix(ZZ, len(g), delta * m + max(delta, t))
    for i in range(B.nrows()):
        for j in range(g[i].degree() + 1):
            B[i, j] = g[i][j] * X**j

    # 计算 B 的行简化形式
    B = B.echelon_form()  # 替代 flatter
    f = sum([ZZ(B[0, i] // X**i) * x**i for i in range(B.ncols())])
    
    roots = set([f.base_ring()(r) for r, m in f.roots() if abs(r) <= X])
    return [root for root in roots if N.gcd(ZZ(f(root))) >= N**beta]

d_m =  54846367460362174332079522877510670032871200032162046677317492493462931044216323394426650814743565762481796045534803612751698364585822047676578654787832771646295054609274740117061370718708622855577527177104905114099420613343527343145928755498638387667064228376160623881856439218281811203793522182599504560128
n =  102371500687797342407596664857291734254917985018214775746292433509077140372871717687125679767929573899320192533126974567980143105445007878861163511159294802350697707435107548927953839625147773016776671583898492755338444338394630801056367836711191009369960379855825277626760709076218114602209903833128735441623
e =  112238903025225752449505695131644979150784442753977451850362059850426421356123

# 计算 k 和 s
k = (e * d_m - 1) // n + 1
s = (n + 1 + inverse_mod(k, e)) % e

# 构造多项式
PR.<x> = PolynomialRing(Zmod(e))
f = x^2 - s * x + n
p0 = int(f.roots()[0][0])

# 查找小根
PR.<x0> = PolynomialRing(Zmod(n))
for i in range(0, 2**6):
    f = e * (x0 + 2**250 * i) + p0
    root = small_roots(f, X=2**250, beta=0.48, m=25)
    print("Roots found:", root)


x0 = 769306974883685623850311905036778346829296744303179040979107875413852719182
p = e * (x0 + 2**250 * 44) + p0
q = n // p

print("p:", p)
print("q:", q)

QQ20250121-231926.png

≡