一元Coppersmith

1
f.small_roots(x=x0,beta=beta0,epsilon=epsilon0)

这个函数是处理整数环/模数环上首一多项式的f(x)=0f(x)=0的问题，能返回满足条件的小根。

m泄露

1
2
3
4
5
6
R.<x> = PolynomialRing(Zmod(n))
f = (m_high + x)^e - c
m_low = f.small_roots(X=2^mbits,beta=1)[0]#mbits就是m泄露的位数
m = int(m_high + m_low)
print("m =",m)
print(long_to_bytes(m))

参考的方程就是me−c≡0(modn)m^e-c \equiv 0 \pmod{n}。如果是mm低位泄露等情况构造核心就是mhigh+x⋅2k+mlowm_{high}+x \cdot 2^{k}+m_{low}。

p泄露

1
2
3
4
5
6
7
P.<x> = PolynomialRing(Zmod(n))
f = p_high + x
x0 = f.small_roots(X=2^bits, beta=0.4)[0]
p =  p_high + int(x0)
q=n//p
d=inverse_mod(e,(p-1)*(q-1))
print(long_to_bytes(pow(c,d,n)))

利用small_roots()函数可以求出f≡0f\equiv 0在模小于nβn^{\beta}的某个因子下的根，这里的话也就是p。

d低位泄露

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
def recover_p(p0, n):
    PR = PolynomialRing(Zmod(n), 'x')
    x = PR.gen()
    nbits = 1024
    p0bits = p0.bit_length()
    f = 2^(p0bits - 2) * x + p0
    f = f.monic()
    roots = f.small_roots(X=2^(nbits // 2 - p0bits + 2), beta=0.49)
    if roots:
        x0 = roots[0]
        p = gcd(2^(p0bits - 2) * int(x0) + p0, n)
        print(f"Found p = {p}")
        return ZZ(p)
    return None
def find_p0(d0, e, n, bits):
    modulus = 1 << bits
    P.<x> = PolynomialRing(Zmod(modulus), 'x')
    for k in range(1, e + 1):
        # 构造多项式 k*X^2 + (e*d0 - (1+k*(n+1)))*X + k*n
        f = k * x^2 + (e * d0 - (1 + k * (n + 1))) * x + k * n
        roots = f.roots(multiplicities=False)
        for root in roots:
            p0 = ZZ(root)
            p = recover_p(p0, n)
            if p and p != 1:
                return p
    return None

这里nbits最好手动填一下

处理近似问题

举个例子来说就是，通过题目我们能获得pp的近似值，这个时候我们取pp的高位，因为这个高位一定是准确的，然后我们通过正常的pp泄露方法就能得到精确的pp。

d高位泄露

举个例子吧

1
2
3
4
5
6
7
8
9
10
11
from secret import m1
def task1():
    e = 149
    p = getPrime(512)
    q = getPrime(512)
    n = p * q
    d = inverse(e,(p-1)*(q-1))
    return (pow(m1, e, n), d >> 222 << 222, n)
c1, leak1, n1 = task1()
print(c1, leak1, n1)
# (89623543982221289730635223555830551523170205418976759060541832483843039074358160566735322009158596405712449020903311144480669706226166537602750967447480664875090686428406188847601970724994074417752345460791736191511081890913041143570455636020205647345764692062144226011846336769477026234106683791286490222089, 138474880017294332349992670187778287774153347391371789199005713563195654993662610111557185709277805165708109047494971468100563949333712521647405765501704478862377527360106399421209690341743821320754482338590671565510629203215009008479290995785318405211007685664887994061938667418220613430135743123498167435264, 146331610798417415036517077006943013321623040860385791423062775325646472298267580898028515394910588437521335092742913111680737790430660749825981979147191282007208147041227246620008377726207734522466015971515317594545750944838673018946440525615131606652748549901880641896940968837669894325535750125282351577689)

k(p−1)(q−1)+1=e⋅d≈e⋅dhighk(p-1)(q-1)+1=e \cdot d \approx e \cdot d_{high}

edhighp−k(p−1)(n−p)−p≈0ed_{high}p-k(p-1)(n-p)-p \approx 0

把pp看作主元就能近似得到pp。

例题

CheckIn

题目
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import os
from Crypto.Util.number import *
from secret import FLAG
p, q = getPrime(512), getPrime(512)
n = p * q
phi = (p - 1) * (q - 1)
e = 65537
r = bytes_to_long(b'n1junior2025')
gift = ((2025 * p + r * r) * p % phi) >> 750
msg = bytes_to_long(FLAG)
ct = pow(msg, e, n)
print(f"n = {n}")
print(f"e = {e}")
print(f"ct = {ct}")
print(f"gift = {gift}")
'''
n=127060392619341060272126983366487069092712215979664340339428955285201267724168574813227106020122399594060458777939446978632526348867806863618885370221957087197582864380885199290793062293120324984868138488667017882272415668310242448870352699380394381756621677031459335310964085476227148301120850021800822495119
e=65537
ct=18305235107479382231970252522433686185039231184629854177334609960907102735540326234277108553640185845164498239822263821349544015918443334769445559622730315115384134147808359107914969010678607157349844717217781801237935737980608575612421610972048739840839726108493286994232100086338529591086935374295281642738
gift=8312456126096895497368692810699639462746223116345115761188530231045483000989605820
'''
分析

破解的关键就是这里的giftgift。

gift<<750≈(2025p+r2)⋅p(modφ(n))gift<<750 \approx (2025p+r^2) \cdot p \pmod{\varphi(n)}

写成等式有

gift<<750+k⋅(p−1)(q−1)≈(2025p+r2)⋅pgift<<750+k\cdot (p-1)(q-1) \approx (2025p+r^2) \cdot p

为了删去qq我们可以左右同乘pp。

gift<<750⋅p+k⋅(p−1)(n−p)≈(2025p+r2)⋅p2gift<<750 \cdot p+k\cdot (p-1)(n-p) \approx (2025p+r^2) \cdot p^2

这里我们把pp看作主元就得到一个关于pp的方程。遍历可能的kk就能得到pp的近似解，再利用coppersmith还原即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from Crypto.Util.number import *
n=127060392619341060272126983366487069092712215979664340339428955285201267724168574813227106020122399594060458777939446978632526348867806863618885370221957087197582864380885199290793062293120324984868138488667017882272415668310242448870352699380394381756621677031459335310964085476227148301120850021800822495119
e=65537
ct=18305235107479382231970252522433686185039231184629854177334609960907102735540326234277108553640185845164498239822263821349544015918443334769445559622730315115384134147808359107914969010678607157349844717217781801237935737980608575612421610972048739840839726108493286994232100086338529591086935374295281642738
gift=8312456126096895497368692810699639462746223116345115761188530231045483000989605820
gift=gift<<750
r=bytes_to_long(b'n1junior2025')
PR.<x>=PolynomialRing(RealField(1000))
for k in range(2000,5000):
    f=(2025*x+r^2)*x^2-gift*x-k*(x-1)*(n-x)
    root=f.roots(multiplicities=False)
    for xx in root:
        p0=int(xx)
        P.<y>=PolynomialRing(Zmod(n))
        g=p0+y
        res=g.small_roots(X=2^226,beta=0.499,epsilon=0.04)
        for y0 in res:
            p=int(y0)+p0
            if 0<p<n and n%p==0:
                q=n//p
                d=inverse_mod(e,(p-1)*(q-1))
                print(long_to_bytes(pow(ct,d,n)))

多元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
35
def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()
    R = f.base_ring()
    N = R.cardinality()
    #f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)
    G = Sequence([], f.parent())
    for i in range(m + 1):
        base = N ** (m - i) * f ** i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base * prod(map(power, f.variables(), shifts))
            G.append(g)
    B, monomials = G.coefficients_monomials()
    monomials = vector(monomials)
    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)
    B = B.dense_matrix().LLL()
    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1 / factor)
    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B * monomials):
        H.append(h)
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots
    return []

这里的bound是指多元多项式各个未知量的上限

dp高位泄露

1
2
3
4
5
6
7
8
9
10
11
12
PR.<x,y> = PolynomialRing(Zmod(n))
f = e * (dp_high + x) + (y - 1)
res = small_roots(f,(2^bits,2^bits),m=1,d=3)
for root in res:
    dp_low = root[0]
    dp = dp_high + dp_low
    tmp = pow(2,e*dp,n) - 2
    p = GCD(tmp,n)
    q = n // p
    d = inverse(e,(p-1)*(q-1))
    m = pow(c,d,n)
    print(long_to_bytes(int(m)))

这里还有个技巧是tmptmp的构造

2e⋅dp≡2k⋅(p−1)+1≡2(modp)2^{e\cdot dp} \equiv 2^{k\cdot(p-1)+1} \equiv 2 \pmod{p}

这个构造可以避免常规做法下遍历[1,e][1,e]，因为当ee过大时遍历复杂度较高。