Coppersmith定理

原理

用到格基规约和LLL算法。。。

啊？你问那是什么？去搜吧，反正我没看懂。

实现

有一个 e 阶的多项式 f, 那么可以：

• 在模 n 意义下，快速求出 以内的根
• 给定 β，快速求出模某个 b 意义下较小的根，其中
  b≥​​​，是 n 的因数。

一般采用sage下的small_roots(X=2^kbits,beta=β)。

应用

coppersmith定理应用最多的是高位攻击一类，通过该定理求得剩余二进制位。

限制性：coppersmith定理能求得的位数有限。

一般来说，n=p*q，设p，q均是1024位的大素数，则n的大小为2047bits或2048bits，而就是大概1024bits的数，与p，q接近，但是不一定满足
p，q≥，所以β一般取0.4，根据大佬们的证明得出，在上述条件下，只要未知二进制位数小于492均可应用coppersmith定理求解。

满足上述要求的情况下，所需要的small_roots()函数中的参数X代表所需求解根的上限，即假设未知的位数是kbits，参数X导入的值就是2^kbits。

例题 [BaseCTF 2024]铜匠

附件

from Crypto.Util.number import getPrime, bytes_to_long
#from secret import flag
flag=b'XXXX'

p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 65537
hint1 = p >> 721
hint2 = q % (2 ** 266)
ct = pow(bytes_to_long(flag), e, n)
print(hint1)
print(hint2)
print(n)
print(ct)
'''
hint1 = 14439249591349619691972392177790365247490839237199085979433418493254022567815148979672690178
hint2 = 90063199151369157959005663017593053931871580139169245885113098598755909124764417
n = 18347545778876678838092757800261556931131930866012101566000425608407193858675622059415995283684230959320874387944052648148677918542763633503231962873204645415818139345588988936580526094727943067102768943117592654029397879665312089518191052154267343886226820785206334238961064175118262578895847281575656290248049404047727756356910896332939145136942219317065063060070725033146788186604738271846183709127655298440696824683099637827282095133642324657860714680107691622056420045091586609974536644773286992447027164350612852922016376888380895187804771279035652496676089183636450028327097084911908336202253562671798012457461
ct = 15659576879410368237140555530527974801613150473447768911067611094143466009251385693099110691602954207905029692682380253595062935017486879899242785756448973466690818942065250284891341066578689696180061755610538867770441139827574063212967027249650509215685566103350688284041405586915563454117672061141919712416360596137520514412607512596079964611672166435592936417138352662031529414118312166411150736015788925026636845744110093161894267707446937939130745326244186579516665160036229715964182962542836836457885170975474737620430886449029488829662146456489724775166105816909257516908496172172266375617868819982791477888289
'''

​思路

给了p的高位和q的低位，用逆元算出p的低位，得出p一共已知的位数，中间未知的455位考虑用coppersmith解，如果直接解解不出来，可以尝试抬高位数进行爆破，最后找到flag。幸运的是，这道题可以直接解出来。

exp​​

#sage
hint1 = 14439249591349619691972392177790365247490839237199085979433418493254022567815148979672690178
hint2 = 90063199151369157959005663017593053931871580139169245885113098598755909124764417
n = 18347545778876678838092757800261556931131930866012101566000425608407193858675622059415995283684230959320874387944052648148677918542763633503231962873204645415818139345588988936580526094727943067102768943117592654029397879665312089518191052154267343886226820785206334238961064175118262578895847281575656290248049404047727756356910896332939145136942219317065063060070725033146788186604738271846183709127655298440696824683099637827282095133642324657860714680107691622056420045091586609974536644773286992447027164350612852922016376888380895187804771279035652496676089183636450028327097084911908336202253562671798012457461
ct = 15659576879410368237140555530527974801613150473447768911067611094143466009251385693099110691602954207905029692682380253595062935017486879899242785756448973466690818942065250284891341066578689696180061755610538867770441139827574063212967027249650509215685566103350688284041405586915563454117672061141919712416360596137520514412607512596079964611672166435592936417138352662031529414118312166411150736015788925026636845744110093161894267707446937939130745326244186579516665160036229715964182962542836836457885170975474737620430886449029488829662146456489724775166105816909257516908496172172266375617868819982791477888289
e = 65537
 
p_high = hint1<<721
q_low = hint2
mod = 1<<266
p_low = n*inverse_mod(q_low,mod) % mod
PR.<x> = PolynomialRing(Zmod(n))
 
f = p_high + x*mod + p_low
pp = f.monic().small_roots(X=2^455,beta=0.4)
if pp:
    p=(pp[0]*mod)+p_high+p_low
    
 
from Crypto.Util.number import *
from gmpy2 import *
 
 
q = n//p
phi = (p-1)*(q-1)
d = inverse(e, phi)
m = long_to_bytes(pow(ct, d, n))
print(m)

​

​

​

​