Copperstudy

---

最近遇到一个很不错的题【强网杯2019 Copperstudy】，里面包含大多数Coppersmith攻击，故以此题来分析其中出现的不同情况的攻击方式。

---

Coppersmith 可以用于求多项式的小根，经常用于 RSA 攻击中“已知某些二进制位，求剩余位”这一类问题。

---

d0:hash爆破

def d0(hashstr,str):
    for a in range(256):
        for b in range(256):
            for c in range(256):
                s = str+a.to_bytes(1,'big')+b.to_bytes(1,'big')+c.to_bytes(1,'big')
                if hashlib.sha256(s).hexdigest() == hashstr:
                    return binascii.hexlify(s)

sh = remote("node4.buuoj.cn",29418)
sh.recvline()
sh.recvuntil(b'=')
hashstr = sh.recvline()[:-1].decode()
sh.recvuntil(b'=')
str = binascii.unhexlify(sh.recvline()[:-1])
sh.recvline()
sh.sendline(d0(hashstr,str))
print(sh.recvline())

d1:已知p高位求低位

e = 
n = 
phigh = 
R.<x> = PolynomialRing(Zmod(n))
p = phigh + x
x0 = p.small_roots(X = 2^388,beta = 0.4)[0]
print(x0)

d2:已知m高位求低位

$$
highm = 2^{72}*m_{h72}\quad 和\quad
c≡(highm+x)^e\ mod\ n
$$

转换成sage方程：
$$
f = (highm+x)^e - c = 0
$$

n = 
e = 
c = 
highm = 

R.<x> = PolynomialRing(Zmod(n), implementation='NTL')

f = (highm+x)^e - c
x0 = f.small_roots()[0]
print(x0)

m = highm+x0
print(m)

d3:已知d低位求高位

d的低512bits
$$
e*d ≡ 1\ mod \ φ(n)\
=>e*d = 1+k*(p-1)*(q-1)
$$
两边对$2^{512}$取模，得：
$$
e*d_{low} ≡ 1 + k*(n-p-q+1)\ mod\ 2^{512}
$$
为了让上式成为单变量等式（假定k已知），两边同乘p（或q），得：
$$
e*d_{low}*p ≡ 1 + k*(n*p-p^2-n-p)\ mod\ 2^{512}
$$
解此方程可得到p的低512bits，再通过类似d2的方法求其高位，从而得到p,q。

需要注意的是k是未知的，需要枚举其值。参考他人博客，应该枚举前几个就行了。

import gmpy2
def getp(n,p_list):
    
    R.<x> = PolynomialRing(Zmod(n), implementation='NTL')
    for each in p_list:
        f = x*2^512 + each
        x0 = f.monic().small_roots(X = 2^128, beta = 0.4)
        if x0:
            return f(x0[0])
    return None


def d3(d_low,n,c,e):
    
    p_list = []
    for k in range(1,4):
        p = var('p')
        f = solve_mod([3*p*d_low == p+k*(n*p-p^2-n+p)],2^512)
        p_list += [int(x[0]) for x in f]
    #print(p_list)    
    p = int(getp(n,p_list))
    q = n//p
    d = inverse_mod(e,(p-1)*(q-1))
    m = pow(c,d,n)
    print(hex(m)[2:])
    
n = 
c = 
d_low = 
e = 3

d3(d_low,n,c,e)

d4:广播攻击

利用中国剩余定理求解。

import gmpy2
e=3
n1=78642188663937191491235684351005990853149481644703243255021321296087539054265733392095095639539412823093600710316645130404423641473150336492175402885270861906530337207734106926328737198871118125840680572148601743121884788919989184318198417654263598170932154428514561079675550090698019678767738203477097731989
c1=23419685303892339080979695469481275906709035609088426118328601771163101123641599051556995351678670765521269546319724616458499631461037359417701720430452076029312714313804716888119910334476982840024696320503747736428099717113471541651211596481005191146454458591558743268791485623924245960696651150688621664860
n2=98174485544103863705821086588292917749386955237408645745685476234349659452606822650329076955303471252833860010724515777826660887118742978051231030080666542833950748806944312437614585352818344599399156268450521239843157288915059003487783576003027303399985723834248634230998110618288843582573006048070816520647
c2=72080679612442543693944655041130370753964497034378634203383617624269927191363529233872659451561571441107920350406295389613006330637565645758727103723546610079332161151567096389071050158035757745766399510575237344950873632114050632573903701015749830874081198250578516967517980592506626547273178363503100507676

M = CRT([c1,c2],[n1,n2])
m = gmpy2.iroot(M,3)[0]
print(hex(m)[2:])

d5:ranklin-Reiter 相关消息攻击

$$
\begin{cases}
c_1 ≡ m^e\ mod\ n
\\
c_2 ≡ (m+1)^e\ mod\ n
\end{cases}
==>
\begin{cases}
m^e-c_1=0
\\
(m+1)^e-c_2=0
\end{cases}
$$

既然已知$m$是上述两方程的根，说明其公约式含$(x-m)$。

(因为方程可以化成$(x-x_1)*(x-x_2)*…*(x-x_e)$)

于是乎，对两个方程求公约式即可（sagemath是真的强大，这都能求，代码类似求两个数的公约数）

def gcd(a,b):
    if b == 0:
        return a.monic()
    else: 
        return gcd(b,a%b)

n = 
c1 = 
c2 = 
e = 

R.<x> = PolynomialRing(Zmod(n))
f1 = x^e - c1
f2 = (x+1)^e - c2

g = gcd(f1,f2)
#print(g)
#print(g.coefficients())#求各项的系数，按次数从低到高排列
m = n - g.coefficients()[0]
print(hex(m)[2:])

d6:Boneh Durfee 攻击

[+]n= 
[+]d=random.getrandbits(1024*0.270)
[+]e=invmod(d,phin)
[+]hex(e)=
[+]m=random.getrandbits(512)
[+]c=pow(m,e,n)=

已知$e，d≤n^{0.27}$。使用

Boneh Durfee 攻击

---

参考：

Coppersmith 攻击 (ruanx.net)