coppersmith攻击

标签（空格分隔）： RSA

本质

coppersmith实际上就是把“模 N 下的小根”问题，转化为“在某个格中找短向量”的问题；再用 LLL 找到短向量，从而把一个模等式提升成一个整数等式。
本质就是创造一个函数

$f(x)=x^{n}+a_1*x^{n-1}+...+a_{n-1}*x+c \quad mod \ N$

然后求解一个 $x$ 满足$f(x) \ mod \ N \ =0$

稍微仔细研究一下

###框定范围
要是硬解$x$肯定无法解答的，因为我们不知道这个$N^c$的$c$是多少。所以只能够先约定这个$c$的范围然后再解
$c$的值主要是取决于这几个值

1
2
3
4
多项式次数d
未知因子下界β
根上界X
模数N的位数n

$$
c = \left\lceil \frac{\beta^2}{\delta} \cdot \log_n X \right\rceil
$$

###开始构造格方便使用LLL
进而构造多项式族
对于$0 \le i \le c$ ，$0\le j < d$ ，定义
$$
g_{i,j}(x)=x^j*N^{max(0,m-i)}*f(x)^i
$$
且这些多项式满足
$$
g_{i,j}(x_0) ≡ 0 \ mod \ N
$$
此时构造一个格为$g_{i,j}(x)$的系数向量为行，组成一个格基$B$然后由于格中有个系数$x_0$满足
$h(x_0)$在$x_0$的时候是$N^c$的倍数这样就可以用LLL来求解x。

例题如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from Crypto.Util.number import getPrime, bytes_to_long
from secret import flag

p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 65537
hint1 = p >> 724
hint2 = q % (2 ** 265)
ct = pow(bytes_to_long(flag), e, n)
print(hint1)
print(hint2)
print(n)
print(ct)

这里我们可以看到只有$p$的高301位，以及$q$的低265位是清晰的
此时我们稍作化简

$$
N = p * q \
N = p * (k2^{265}+q_{low}) \
N = pk2^{265}+pq_{low}
$$

此时我们对N整体取低265位可以得到

$$
N_{low}=p_{low}*q_{low} \ mod \ 2^{265}
$$

根据这个我们可以得到p的低265位，但是p一共有1024位，我们还差1024-(1024-725)-265=459位不知道，到这里我们可以直接进行构造coppersmith攻击来解出剩下的459位，但是我们可以进行爆破几位来更快解出来，我们选择爆破6位

1
2
构造如下
f(x)=hint1*x^724+p_low+i*2^266+x*2^271

然后我们爆破6位的同时跑coppersmith攻击即可获取flag

Exp如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from Crypto.Util.number import long_to_bytes

h1 = 1514296530850131082973956029074258536069144071110652176122006763622293335057110441067910479
h2 = 40812438243894343296354573724131194431453023461572200856406939246297219541329623
n = 21815431662065695412834116602474344081782093119269423403335882867255834302242945742413692949886248581138784199165404321893594820375775454774521554409598568793217997859258282700084148322905405227238617443766062207618899209593375881728671746850745598576485323702483634599597393910908142659231071532803602701147251570567032402848145462183405098097523810358199597631612616833723150146418889589492395974359466777040500971885443881359700735149623177757865032984744576285054725506299888069904106805731600019058631951255795316571242969336763938805465676269140733371287244624066632153110685509892188900004952700111937292221969
c = 19073695285772829730103928222962723784199491145730661021332365516942301513989932980896145664842527253998170902799883262567366661277268801440634319694884564820420852947935710798269700777126717746701065483129644585829522353341718916661536894041337878440111845645200627940640539279744348235772441988748977191513786620459922039153862250137904894008551515928486867493608757307981955335488977402307933930592035163126858060189156114410872337004784951228340994743202032248681976932591575016798640429231399974090325134545852080425047146251781339862753527319093938929691759486362536986249207187765947926921267520150073408188188
e = 0x10001

mod = 1<<265
pl = n*inverse_mod(h2, mod) % mod
pbar = (h1 << 724) + pl

PR.<x> = PolynomialRing(Zmod(n))

for i in range(64):
    f = pbar + (x*mod*64) + (i<<265)
    f = f.monic()
    pp = f.small_roots(X=2^453, beta=0.4)
    if pp: break

p = int(pbar + (pp[0]<<271) + (i<<265))
q = n // p
d = inverse_mod(e, (p-1)*(q-1))
print(long_to_bytes(power_mod(c, d, n)))