Coppersmith 攻击

N1Key2023/4/19大约 22 分钟p高位攻击p低位攻击明文m高低位攻击明文m低位攻击dq的低位攻击已知p的部分高低位

关于Coppersmith

定理：设 N是一个未知因子分解的整数， $p \geq N^{β}$ 是 N 的一个因子，设 $f_{p} (x)$ 是一个单变量的次数为 $δ$ 的多项式，设 $c_{n}$ 是一个以 $l o g N$ 为上界的量。那么我们可以在 $(l o g N, δ)$ 的多项式时间内找到方程 $f_{p} (x) \equiv 0 m o d p$ 的满足条件： $| x_{0} | \leq \frac{1}{2} N^{\frac{β^{2}}{δ} - ε}$ 的解。

（这里的 $ε$ 是一个任意小的正数）

Coppersmith 方法的基本思路是将模多项式方程转化为整数上的多项式方程，利用 $f (x)$ 构造 $g (x)$ ， $g (x)$ 包含 $f (x)$ 的所有小整数模根，即： $f (x_{0}) \equiv 0 (m o d p) \Rightarrow g (x_{0}) = 0$

利用上面的定理容易证明：若 $N = p * q$ ，其中 p，q 是比特位相同的素数，那么已知 p 的 $\frac{1}{4} l o g_{2} N$ 高位（或低位）比特就可以在多项式时间内得到 N 的因子分解。

学习Coppersmith需要安装sagemath软件，推荐在ubantu中安装更加便捷。接下来开始介绍利用 Coppersmith 定理解决RSA加密相关的问题。

对 sagemath 中用到的函数补充说明:
PolynomialRing ：构造多项式环
Zmod(n) ：模运算
implementation='NTL' ：执行 NTL
small_roots(self, X=None , beta=1.0 , epsilon=None)：计算多项式的小整数根
其中的参数：X —— 根的绝对边界， beta( $β$ ) —— compute a root mod p where p is a factor of N and $p \geq N^{β}$
(程序默认值是 1.0 ，此时 p=N)，epsilon （默认： $β / 8$ )
monic()：用于将多项式的首项系数归一化为1。它接受一个多项式作为参数，然后返回一个新的多项式，其中首项系数已经被归一化为1。这个过程可以简化多项式的表达式，使其更易于计算和分析。

参考 sagemath 文档介绍：后续在接下来的题目应用，讲解具体的用法。

sage文档链接：

https://doc.sagemath.org/html/en/reference/polynomial_rings/sage/rings/polynomial/polynomial_modn_dense_ntl.html#sage.rings.polynomial.polynomial_modn_dense_ntl.small_roots

已知素数p的高位攻击

在RSA加密算法中，如果私钥中的素因子泄露了部分信息，那么攻击者从这部分泄漏的数据中很可能会恢复出完整的私钥数据。设素因子 p 的二进制位表示为： $p_{n} . . . p_{t + 1} p_{t} . . . p_{1}$ ，其高位比特数据 $p_{n} . . . p_{t + 1}$ 被泄露。令 $Δ p = p_{n} . . . p_{t + 1} 0. . .0$ 为高位已知量，设 $X = p_{t} . . . p_{1}$ 为低位未知量，由 $N = p * q$ 得：

$X$ 为模多项式 $f (x) = (Δ p + X) m o d N$ 的小整数解。

这里Coppersmith算法利用条件：知道 p 的高位为素因子p 的位数约 $\frac{1}{2}$ 比特位时即可。

例题：

from flag import flag
from Crypto.Util.number import *

p = getPrime(1024)
q = getPrime(1024)
e = 65537
n = p*q

m = bytes_to_long(flag)

print n
print pow(m, e, n)
print p>>256<<256

# output
# 26406507468595611843852094067483173843988114465094045314324958205247973393878612589146897816881236818219902539975703710689353618174826904300589643161784341674436810639999244652231756242284615955258973430337702733454791782484002773967293198343866259490519754466626455660967042613249021854707331393440280088268816341057924652807723419166490363777181753297185283416885627445213950857480287818564281651822264024891956284486733856518809532470029519647769749231421957169481281821885757924521580543834665554242403238567286205389138437021157096962185096308108489101554724344868500500476691994206988217768341711716527866730487
# 22371088752722216457725632164373582195669473128756299754645443284929524768654545905154985577175225182544638209286885657892360668965805613727315024761409924679131145149936406239774150607378706790494820180586939668429812955766507811860718575149988809217701964019618239260041070894375952033566803105327100696642244951676616707205397327491933042019560545721027871057909242509336729865025061616686254481161431063503607378134616485979961926628954536592552923269161255759846497309277397441639921544384778106116567555705005440627393593876072210594939647990615797269482726733444406876986888296295032722008287447468255108089357
# 159945952275533485818121954231313618960321976049710904254772419907677971914439101482974923293074598678164025819370654132149566696084245679106109087142916286461708005676333840438629476722637189134626565206159794947442549588155962485884562239895738265024295739578695834796427810095412842888401159276765814718464

这里我们已知素因子 p 的高位为 1024-256 = 768 bits ，未知的低位数据为 256 bits，根据上面的理论介绍我们可以使用 coppersmith 算法恢复 p的准确数据。

关键函数在于 small_roots 设置根的界限X 和 beta 的值，beat一般设置为 0.4 ，后面会详细介绍这样设置的目的。

x0 = p.small_roots(X=2^256,beta=0.4)

sagemath实现 exp :

#sage
from Crypto.Util.number import *
from gmpy2 import *

e = 65537
n = 26406507468595611843852094067483173843988114465094045314324958205247973393878612589146897816881236818219902539975703710689353618174826904300589643161784341674436810639999244652231756242284615955258973430337702733454791782484002773967293198343866259490519754466626455660967042613249021854707331393440280088268816341057924652807723419166490363777181753297185283416885627445213950857480287818564281651822264024891956284486733856518809532470029519647769749231421957169481281821885757924521580543834665554242403238567286205389138437021157096962185096308108489101554724344868500500476691994206988217768341711716527866730487
c = 22371088752722216457725632164373582195669473128756299754645443284929524768654545905154985577175225182544638209286885657892360668965805613727315024761409924679131145149936406239774150607378706790494820180586939668429812955766507811860718575149988809217701964019618239260041070894375952033566803105327100696642244951676616707205397327491933042019560545721027871057909242509336729865025061616686254481161431063503607378134616485979961926628954536592552923269161255759846497309277397441639921544384778106116567555705005440627393593876072210594939647990615797269482726733444406876986888296295032722008287447468255108089357

# print p>>256<<256
p_high = 159945952275533485818121954231313618960321976049710904254772419907677971914439101482974923293074598678164025819370654132149566696084245679106109087142916286461708005676333840438629476722637189134626565206159794947442549588155962485884562239895738265024295739578695834796427810095412842888401159276765814718464

PR.<x> = PolynomialRing(Zmod(n),implementation='NTL')
f = p_high + x
x0 = f.small_roots(X=2^256,beta=0.4)
print('x0 =',x0)

p = p_high + int(x0[0])
q = n//p
assert p*q==n

d = invert(e,(q-1)*(p-1))
m = pow(c,d,n)
print(long_to_bytes(int(m)))

sage中运算结果：得到模多项式的小整数根 $x_{0}$

x0 = [34617643142235695556586808773805798019055870312898061509976159971261415964273]
b'flag{f4f41143a6fc8f8f7365c6ccb5e3cb78}'

$x_{0}$ 也就是p的未知低比特位的值，将其与已知高比特位值相加即可：p = p_high + x0

注意这里的 p_high 缺失的低位填充成了 0 ，后面的 RSA 相关攻击算法也是一样的，如下图：

p 高位不够的攻击

这里讲解两道题，都涉及到了当 p,q 同二进制位数时，已知 p 的高位攻击但高位不够的情况，在这里情况下，我们需要先爆破部分低位，使得未知低位满足条件：p_unknown_bits $\div$ p_bits $\leq 0.44$ （这里指beta = 0.44）

第一种情况

大家可以自己去生成一组 256 bits 或者更大数据量的素数 p,q 进行测试实验，如下是我已经测试过的结果：

这样的数据直接拿去高位攻击是不行的，必须要已知 144 位才能高位攻击，

此时计算比值为： (256 - 144) / 256 = 0.4375

我们要爆破 136 到 144 中的8位二进制数，即2位十六进制然后再进行已知高位攻击

先将 leak_p 转化为16进制：

题目 task.py

from Crypto.Util.number import *
from gmpy2 import *
from secret import flag

m = bytes_to_long(flag)
e = 65537
p= getPrime(256)
leak_p = p >> 120
print("leak_p =",leak_p)
q = getPrime(256)
n = p*q
c= pow(m,e,n)
print("n =",n)
print("c =",c)
# leak_p = 57303545022436031674172379509633863887077
# n = 6290400850108673527783456723558868077251853788073859360516042680251422818079380463161520548743184302018140978345372703177688378631564416901363981788817257
# c = 3018879496435827891565409624549580574355607699876796814908055868300197064252462047054251836059387617618529706009316747223510404878163964048672091931778452

sagemath实现 exp :

from sage.all import *
from Crypto.Util.number import *
from gmpy2 import *


n = 6290400850108673527783456723558868077251853788073859360516042680251422818079380463161520548743184302018140978345372703177688378631564416901363981788817257
c = 3018879496435827891565409624549580574355607699876796814908055868300197064252462047054251836059387617618529706009316747223510404878163964048672091931778452
e = 65537
pbits = 256

# leak_p = 57303545022436031674172379509633863887077
# print(hex(leak_p<<8))
# leak_p = 0xa8666553ec59acad3ed8208f060abba8e500

for i in range(1, 127):
    leak_p = 0xa8666553ec59acad3ed8208f060abba8e500
    leak_p = leak_p + int(hex(i),16)
#     print(leak_p)

    kbits = pbits - leak_p.nbits()  # 设置界的 bit上限
#     print(kbits)
    
    p_high = leak_p << kbits
    PR.<x> = PolynomialRing(Zmod(n))
    f = p_high + x
    roots = f.small_roots(X=2^kbits, beta=0.4)  #计算模多项式的小整数根
    
    if(roots):
		print('roots =',roots)
        p = p_high + int(roots[0])
        q = n//int(p)
        assert p*q == n
        
        phi = (p-1)*(q-1)
        d = invert(e,phi)
        flag = int(pow(c,d,n))
        print(long_to_bytes(flag))

这里采用的是循环爆破的方式，爆破出部分未知低比特位，然后再使用 coppersmith 算法计算模多项式的小整数根。

运算结果：

roots = [2302780466607342296780200504205035]
b'flag{b1695180-0205-461e-8f91-5474c719f5c6}'

第二种情况

第二种情况是不仅已知高位的位数不够，而且直接采用爆破部分低位再用coppersmith算法进行计算，也是行不通的，如直接采用这种写法： f.small_roots(X=2^253, beta=0.4)

这里用 [2023HGAME] CTF 的一道例题来讲解这种情况。

题目 task.py

def create_keypair(nbits):
    p = getPrime(nbits // 2)
    q = getPrime(nbits // 2)
    N = p*q
    phi = (p-1)*(q-1)
    e = 65537
    d = inverse(e, phi)
    leak = p >> 253
    return N, e, d, leak

#N = 115093328038628808000295235261362405802946414639474481950854274471056071400567939760489029514405676751158500439316121705879898379961723340037451609143927918592230719040332243486155308305995684632393529193889098207326916292333323740045854874108499021528070619818564785319040208958162851719315919939795936617311
#e = 65537
#leak = 724556813270353646000965587597160596427818318026275239319104891346445173041116

已知量为 N、e、leak，这里的 leak 为p泄露的高位值，未知低比特数为 253。

我们可以知道 N的大小为 1024 bits，p泄露的高位为 259 bits，未知的低位为 253 bits；按照公式前面理论部分的条件：p_unknown_bits $\div$ p_bits $\leq 0.44$ （这里指beta = 0.44），我们需要将 p 未知低位的数据量通过爆破降低到 225 bits 才可能通过 coppersmith算法计算出模多项式的小整数根。但爆破的数据量为 2^28 ，这用我们的计算机基本无法实现，也不是一个很好的方法。

改进我们的方法：

先爆破 p 的低 10 位有效值，降低 未知低位bit/p_bits 的比值，然后利用 coppersmith 调节 $X$ 的边界，增大格的维度就能爆破出来了。边界的大小主要是通过调节small_roots 的参数 epsilon 的值，值越小，beta比值越接近或小于 0.44，同时随着调节的值越小计算速度会越慢。sage官方默认给的 epsilon = $β / 8$ ，我们可以设置在0.01以上大一点。关于爆破范围，这里取 2的9次方上下。也可能在 2的10次方附近。也就3、4分钟就出了，自己调节一下。这里我们设置为 f.small_roots(X=2 ^ kbits, beta=0.4,epsilon=0.015)

关于 sage.rings.polynomial.polynomial_modn_dense_ntl.small_roots(self , X=None , beta=1.0 , epsilon=None) 函数中参数更详细的介绍：

该函数是一个用于在整数模下搜索多项式小根的函数。该函数使用NTL库中的算法进行实现，并提供了一些参数来控制搜索的精度和效率。其中，

1、参数epsilon是一个可选参数，用于控制搜索多项式小根的精度。具体来说，epsilon用于控制NTL算法中使用的插值多项式的次数。插值多项式是一种多项式函数，可以通过一些已知的点来近似地计算一个函数在其他点上的值。在搜索多项式小根时，插值多项式用于确定多项式的根的近似位置。

当epsilon的值较小时，NTL算法使用的插值多项式次数也会比较小，这可以降低计算量，但可能会导致算法无法找到所有小根。相反，当epsilon的值较大时，NTL算法使用的插值多项式次数也会比较大，这可以增加算法找到所有小根的可能性，但计算量也会相应地增加。

需要注意的是，如果不指定epsilon参数，则NTL算法将使用默认值。默认情况下，epsilon的值为 $β / 8$ 。在实践中，这个值通常是比较合适的，但也可能需要根据具体情况进行调整。因此，在使用small_roots函数时，我们需要根据具体情况选择合适的epsilon值，以获得更准确的结果。

2、X：用于指定搜索多项式小根的范围。默认情况下，X的值为None，表示搜索整个整数域。如果需要限制搜索的范围，可以将X设置为一个正整数，表示搜索区间为 $[- X, X]$ 。对于非常大的搜索范围，可以将X设置为一个RR对象，表示使用实数范围进行搜索。

3、beta：用于控制NTL算法中的松弛因子。松弛因子是一种通过调整插值多项式的精度来控制搜索速度和精度的方法。beta的默认值为1.0，表示使用默认的松弛因子。可以通过调整beta的值来改变算法的搜索速度和精度。较小的beta值会加快搜索速度，但可能会降低搜索精度，而较大的beta值则会增加搜索精度，但可能会降低搜索速度。

sagemath实现 exp :

from sage.all import *
from Crypto.Util.number import *
from gmpy2 import *
from tqdm import tqdm

e = 65537
n = 115093328038628808000295235261362405802946414639474481950854274471056071400567939760489029514405676751158500439316121705879898379961723340037451609143927918592230719040332243486155308305995684632393529193889098207326916292333323740045854874108499021528070619818564785319040208958162851719315919939795936617311
c = 0x8a887d3c9ee7f6ad81517ffbba417f5cac350abd3314b34d9f58845e15f68ef00fafb69ec0b60cdc90975c4db3f0fc1334f3fc9ed84c69e95fbb584a5f3158603523294ec3e79aea20080dd40513a6bd4532d8a64c1d46aae28fab19ea5b9d7aadea315c380ac9a2a92856af99204e79c6ea11b754e02db3f7c94efdb535cfe8
        
pbits = 512

# leak_p = 724556813270353646000965587597160596427818318026275239319104891346445173041116
# leak_p = leak_p<<10
# print(hex(leak_p))
# leak_p = 0x1907927e6c31e6d08b2d680921f7669fb4e9a15568cd3ed54a71d0861ff5629f7000

for i in tqdm(range(800, 1, -1)):
    leak_p = 0x1907927e6c31e6d08b2d680921f7669fb4e9a15568cd3ed54a71d0861ff5629f7000
    leak_p = leak_p + int(hex(i), 16)
#     print(leak_p)

    kbits = pbits - leak_p.nbits()  # 用于设置根X的界限
#     print(kbits)

    p_high = leak_p << kbits
    
    PR.<x> = PolynomialRing(Zmod(n))
    f = p_high + x
    roots = f.small_roots(X=2 ^ kbits, beta=0.4, epsilon=0.015)  # 计算模多项式的小整数根

    if (roots):
        print("p_root =", roots[0])
        p = p_high + int(roots[0])
        q = n // p
        if p * q == n:
            print("p =", p)
            d = invert(e, (q - 1) * (p - 1))
            m = pow(c, int(d), n)
            print(long_to_bytes(int(m)))

运算结果：

调节后可以看到计算出 flag 的速度还是很快的。

p的低位攻击

我们设素因子 p 的二进制位表示为： $p_{n} . . . p_{t + 1} p_{t} . . . p_{1}$ ，其低位比特数据 $p_{t} . . . p_{1}$ 被泄露。令 $Δ p = p_{t} . . . p_{1}$ 为低位已知量，设 $X = p_{n} . . . p_{t + 1}$ 为高位未知量，由 $N = p * q$ 得**： $X$ 为模多项式 $f (x) = (2^{t} * X + Δ p) m o d N$ 的小整数解。**(其中的 t 就是 p 已知低位的比特数量)

例题 task.py：

from Crypto.Util.number import *
from secret import flag
p = getPrime(1024)
q = getPrime(1024)
n = p*q
m = bytes_to_long(flag)
e = 65537
c = pow(m, e, n)

print("n =", n)
print("c =", c)
print("p =", p&((1<<560) - 1))

'''
n = 21595945409392994055049935446570173194131443801801845658035469673666023560594683551197545038999238700810747167248724184844583697034436158042499504967916978621608536213230969406811902366916932032050583747070735750876593573387957847683066895725722366706359818941065483471589153682177234707645138490589285500875222568286916243861325846262164331536570517513524474322519145470883352586121892275861245291051589531534179640139953079522307426687782419075644619898733819937782418589025945603603989100805716550707637938272890461563518245458692411433603442554397633470070254229240718705126327921819662662201896576503865953330533
c = 1500765718465847687738186396037558689777598727005427859690647229619648539776087318379834790898189767401195002186003548094137654979353798325221367220839665289140547664641612525534203652911807047718681392766077895625388064095459224402032253429115181543725938853591119977152518616563668740574496233135226296439754690903570240135657268737729815911404733486976376064060345507410815912670147466261149162470191619474107592103882894806322239740349433710606063058160148571050855845964674224651003832579701204330216602742005466066589981707592861990283864753628591214636813639371477417319679603330973431803849304579330791040664
p = 1426723861968216959675536598409491243380171101180592446441649834738166786277745723654950385796320682900434611832789544257790278878742420696344225394624591657752431494779
'''

分析题目：

p = getPrime(1024)
print("p =", p&((1<<560) - 1))

从这两段代码可以得知：p = 1024bits，且 560 bits 低位数据是已知的，通过上面的理论知识我们可以构造相关的模多项式，然后利用 Coppersmith 算法计算出多项式的小整数根，即可恢复出完整的私钥 p。

用到的参数：monic()：用于将多项式的首项系数归一化为1。

sagemath实现 exp :

#sage
from gmpy2 import *
from Crypto.Util.number import *

n = 21595945409392994055049935446570173194131443801801845658035469673666023560594683551197545038999238700810747167248724184844583697034436158042499504967916978621608536213230969406811902366916932032050583747070735750876593573387957847683066895725722366706359818941065483471589153682177234707645138490589285500875222568286916243861325846262164331536570517513524474322519145470883352586121892275861245291051589531534179640139953079522307426687782419075644619898733819937782418589025945603603989100805716550707637938272890461563518245458692411433603442554397633470070254229240718705126327921819662662201896576503865953330533
c = 1500765718465847687738186396037558689777598727005427859690647229619648539776087318379834790898189767401195002186003548094137654979353798325221367220839665289140547664641612525534203652911807047718681392766077895625388064095459224402032253429115181543725938853591119977152518616563668740574496233135226296439754690903570240135657268737729815911404733486976376064060345507410815912670147466261149162470191619474107592103882894806322239740349433710606063058160148571050855845964674224651003832579701204330216602742005466066589981707592861990283864753628591214636813639371477417319679603330973431803849304579330791040664
pbar = 1426723861968216959675536598409491243380171101180592446441649834738166786277745723654950385796320682900434611832789544257790278878742420696344225394624591657752431494779

PR.<x> = PolynomialRing(Zmod(n))
f = x*2^560 + pbar
f=f.monic()

kbit=1024-560  # 用于设置根X的界限
root = f.small_roots(X=2^kbit, beta=0.4,epsilon=0.015)  # 计算模多项式的小整数根

p = int(2^560*root[0] + pbar)
q = n // p
assert p*q == n

e=65537
d=invert(e,(p-1)*(q-1))
m=pow(c,int(d),n)
print(long_to_bytes(int(m)))

明文m的高位攻击

在RSA加密算法中，如果泄露了部分明文信息，那么攻击者从这部分泄漏的数据中很可能会恢复出完整的明文。设明文 m 的二进制位表示为： $m_{n} . . . m_{k + 1} m_{k} . . . m_{1}$ ，其低位比特数据 $m_{n} . . . m_{k + 1}$ 被泄露。令 $Δ m = m_{n} . . . m_{k + 1} 0. . .0$ 为已知量，设 $X = m_{t} . . . m_{1}$ 为未知量；由 $c \equiv m^{e} (m o d n)$ 可以构造模多项式：

$X$ 为模多项式 $f (x) = ((Δ m + X)^{e} - c) m o d N$ 的小整数解。

**例题：**这里由于没找到啥题目样例，索性自己随便出了一道，不考虑非预期解。

c = 49448440304854831648796534024125601382006282873198989997965557974794200333763817072355620545318651927253247674282578472637671741164408087215327482745901235293974786619481946963756529643023816474028709984009212852065178750039594108019217271743973042473197736068985706708503716012186147977316095727799381598075488417125
n = 28847074924932453349543409136399812128594610949367020026474778343570858319481313455200890189364023790182887175049408105958843453263073050626086662142940263874460213271683958427975341123423883215407111909499389249677340455477004237510991188529190235171007660645641687224704887400900068278836154730644879715422040757103147552875954913961588149167053461868101745063648215554184664115626793497487765708744642552805937987823454039925728887745567746569963466846339068171354494330823482202581747310450407677264654959638952096601645772638052521701110952634257302519671771900589919411338060623904602870338988690057676936333193
e = 3
m_high = ((m >> 88) << 88)
m_high = 0x666c61677b343833323734383733383438777975727975737238796538727938323372000000000000000000

题目分析，这里我们由代码 m_high = ((m >> 88) << 88) 可知，m的未知低位有 88 bits，根据上面的原理构造模多项式用 Coppersmith求解多项式的根即可恢复出明文 m。

sagemath实现 exp :

#sage
from gmpy2 import *
from Crypto.Util.number import *

c = 49448440304854831648796534024125601382006282873198989997965557974794200333763817072355620545318651927253247674282578472637671741164408087215327482745901235293974786619481946963756529643023816474028709984009212852065178750039594108019217271743973042473197736068985706708503716012186147977316095727799381598075488417125
n = 28847074924932453349543409136399812128594610949367020026474778343570858319481313455200890189364023790182887175049408105958843453263073050626086662142940263874460213271683958427975341123423883215407111909499389249677340455477004237510991188529190235171007660645641687224704887400900068278836154730644879715422040757103147552875954913961588149167053461868101745063648215554184664115626793497487765708744642552805937987823454039925728887745567746569963466846339068171354494330823482202581747310450407677264654959638952096601645772638052521701110952634257302519671771900589919411338060623904602870338988690057676936333193
e = 3
m_high = 0x666c61677b343833323734383733383438777975727975737238796538727938320000000000000000000000


kbits = 22*4
PR.<x> = PolynomialRing(Zmod(n))

f = (m_high + x)**e - c   # 构造的模多项式
f = f.monic()
root = f.small_roots(X=2^kbits, beta=0.5)  # 计算模多项式的小整数根
print(root)

m  = (m_high + root[0])
print(long_to_bytes(int(m)))

enc = pow(m,3,n)
assert enc == c
print("ok")

运行结果：

[62194515593725596442703997]
b'flag{483274873848wyuryusr8ye8ry823r3r8327r8}'
ok

明文m的低位攻击

设明文 m 的二进制位表示为： $m_{n} . . . m_{k + 1} m_{k} . . . p_{1}$ $(n >> k)$ ，其低位比特数据 $m_{k} . . . m_{1}$ 被泄露。令 $Δ m = m_{k} . . . m_{1}$ 为低位已知量，设 $X = m_{n} . . . m_{k + 1}$ 为高位未知量；由 $c \equiv m^{e} (m o d n)$ 可以构造模多项式：

$X$ 为模多项式 $f (x) = ((2^{k} * X + Δ m)^{e} - c) m o d N$ 的小整数解。(其中的 k 是 m 已知低位的比特数量)

例题 [2022天山固网杯]：

from Crypto.Util.number import *
from secret import flag
p = getPrime(512)
q = getPrime(512)
assert GCD(3, (p-1)*(q-1)) != 1
assert len(flag) == 40
assert flag.startswith(b'DASCTF{')
assert flag.endswith(b'}')
n = p*q
m = bytes_to_long(flag[7:-1]+b'12345678900987654321')
e = 3
c = pow(m, e, n)

print("n =", n)
print("m =", m&((1<<350)-1))
print("c =", c)

'''
n = 78143938921360185614860462235112355256968995028076215097413461371745388165946555700961349927305255136527151965763804585057604387898421720879593387223895933656350645970498558271551701970896688207206809537892771605339961799334047604053282371439410751334173463317244016213693285842193635136764938802757014669091
m = 1906077032611187208365446696459387107800629785754941498024021333398862239730761050657886407994645536780849
c = 50130000135496687335562420162077023127865865388254124043997590968769445787929013990729805222613912997653046528125102370938788632651827553831996692788561639714991297669155839231144254658035090111092408296896778962224040765239997700906745359526477039359317216610131441370663885646599680838617778727787254679678
'''

分析题目代码

assert len(flag) == 40
m = bytes_to_long(flag[7:-1]+b'12345678900987654321')
print("m =", m&((1<<350)-1))

从这三行代码可以知道：m 为 52 字节长度，1 byte = 8bit，所以 m 的值大约为 52*8 = 416 bits，现在 350 bits的低位数据已知，那么未知的高位数据大约为：416 - 350 = 66 bits，所以我们在使用 Coppersmith 算法计算 X 时，设置根的界限也应该为 X=2^66

sagemath实现 exp :

#sage
from gmpy2 import *
from Crypto.Util.number import *

n = 78143938921360185614860462235112355256968995028076215097413461371745388165946555700961349927305255136527151965763804585057604387898421720879593387223895933656350645970498558271551701970896688207206809537892771605339961799334047604053282371439410751334173463317244016213693285842193635136764938802757014669091
m_low = 1906077032611187208365446696459387107800629785754941498024021333398862239730761050657886407994645536780849
c = 50130000135496687335562420162077023127865865388254124043997590968769445787929013990729805222613912997653046528125102370938788632651827553831996692788561639714991297669155839231144254658035090111092408296896778962224040765239997700906745359526477039359317216610131441370663885646599680838617778727787254679678

e = 3

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

f = (x*2^350 + m_low)**e - c  # 构造的模多项式
f = f.monic()
root = f.small_roots(X=2^66,beta=0.5)[0]   # 计算模多项式的小整数根
print('root =',root)

m=root*2^350+m_low
print(long_to_bytes(int(m)))

这里我们设置 beta 参数使用默认值也是可以，因为根值数据量相对较小。

运行结果：

root = 15910343942542255508
b'739a9a9e50c9a8a5ba83ae2a8e75947012345678900987654321'

dq的低位攻击

这题属于结合了 dq泄露和依据题目信息构造一元多项式，然后用 Coppersmith 算法进行求解。也是一道很好的题目，供大家学习 Coppersmith 攻击利用。

例题：蓝帽杯2022 corrupted_key

注：只截取了和 coppersmith 相关的内容，不是完整的题目。目标是求解出私钥 p、q来。

n = 0xd7152506aa9cec05e5335d6b46f5491407c3199fd51091f1f6030d3762b9e03f49c9dcdc075054e0cc148b974b41854bd93b4ee16a2a876ee62005e80ef806b7aa3b64b1bf9b1fa773e353d0cdb9ff9783ddd5f5e67499ad10f361e938d00b82a6a4c42a0535c5e76721798e86b45cd4b8d03b0d7e75c2be8766a1e843bdc641
e = 0x10001
dq_low = 0xc90bcecf1cbab3358585e8a041d1b1
qinvp = 0xe3016cb3609c1d643c167439c3b938b881f4237f24860d3b1cb85a626d5ccd4726964e0f8270d6c4df9ebfebcc538e4ee5e1a7b7368ede51ec6ae917f78eb598

分析题目：

先梳理已知条件和未知条件，已知条件： n，e，dq_low，qinvp
未知条件：d，p，q，dq
我们需要先求出 dq，然后通过 dq泄露的原理求出 q，然后用 qinvp 的公式构造一元多项式，结合 coppersmith算法求多项式的根
（其中：dq = d % (q-1)，qinvp = q^(-1) % p ，qinvp为模数p下q的逆元素）

构造一元多项式的过程如下：

和 dq 泄露的原理一样，由：

$e d \equiv 1 m o d (q - 1) * (p - 1) \Rightarrow e d = 1 + k_{1} * (q - 1) (p - 1)$

$d q \equiv d m o d (q - 1) \Rightarrow e * d q \equiv e * d m o d (q - 1)$

将上面两式相结合得到：

$e * d q = (1 + k_{1} * (q - 1) (p - 1)) m o d (q - 1) \Rightarrow e * d q = 1 m o d (q - 1)$

$e * d q = 1 + k_{1} * (q - 1) \Rightarrow (e * d q - 1) / k_{1} + 1 = q$

又由 $q i n v p \equiv q^{- 1} m o d p \Rightarrow q i n v p * q \equiv 1 m o d p \Rightarrow q i n v p * q = 1 + k_{2} * p \Rightarrow q i n v p * q^{2} - q = k_{2} * n \Rightarrow q i n v p * q^{2} - q \equiv 0 m o d n$

将上面的关于q 的等式带入，得到：

$q i n v p * ((e * d q - 1) / k_{1} + 1)^{2} - ((e * d q - 1) / k_{1} + 1) \equiv 0 m o d n$

**等式1：**令 qinvp 为 t，化简得到： $t * (e * d q - 1)^{2} + k_{1} * (2 * t - 1) * (e * d q - 1) + k_{1}^{2} * (t - 1) \equiv 0 m o d n$

**等式2：**因为已知 dq 的低比特位数据量为120bits，我们令： $d q = (2^{120} * x + d q l o w)$

关于变量 k1 ，由 $e * d q = 1 + k_{1} * (q - 1)$ 可知：dq < q - 1 ，所以 $0 < k_{1} < e$ ，确定 k1 的范围可以爆破 k1 找到符合解的值。

其他变量都已知，将等式1、2相结合，构造成模多项式然后用 coppersmith求解小整数根 x 即可恢复出 dq，然后再用上面推导的公式 $(e * d q - 1) / k_{1} + 1 = q$ 得到 q 的值。

sagemath实现 exp :

#sage
from gmpy2 import *
from tqdm import tqdm
from sage.all import *

n = 0xd7152506aa9cec05e5335d6b46f5491407c3199fd51091f1f6030d3762b9e03f49c9dcdc075054e0cc148b974b41854bd93b4ee16a2a876ee62005e80ef806b7aa3b64b1bf9b1fa773e353d0cdb9ff9783ddd5f5e67499ad10f361e938d00b82a6a4c42a0535c5e76721798e86b45cd4b8d03b0d7e75c2be8766a1e843bdc641
e = 0x10001
dq_low = 0xc90bcecf1cbab3358585e8a041d1b1
qinvp = 0xe3016cb3609c1d643c167439c3b938b881f4237f24860d3b1cb85a626d5ccd4726964e0f8270d6c4df9ebfebcc538e4ee5e1a7b7368ede51ec6ae917f78eb598

t = qinvp

PR.<x> = PolynomialRing(Zmod(n))
dq = (2^120*x + dq_low)
kbit = 512 - 120  # 用于设置根X的界限

for k in tqdm(range(e,1,-1)):
    f = t*pow(e*dq - 1,2) + k*(2*t-1)*(e*dq - 1) + pow(k,2)*(t-1)  # 构造的模多项式
    f = f.monic()
    root = f.small_roots(X=2^kbit,beta=0.5)   # 计算模多项式的小整数根
    if root:
        dq = 2^120*root[0] + dq_low
        print('k =',k)
        q = int((e*dq - 1)//k + 1)
        p = n//q
        if p*q == n:
            print('dq =',dq)
            print('p =',p)
            print('q =',q)
            break

运算结果：

已知 p 部分高、低位，恢复 p

考点：题目给了私钥 p 的部分高位和部分低位，但是中间存在未知比特数据，我们需要构造多项式然后用coppersimth定理来恢复完整的私钥 p

题目：[鹤城杯 2021]BabyRSA

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)

hint1 = 1514296530850131082973956029074258536069144071110652176122006763622293335057110441067910479
hint2 = 40812438243894343296354573724131194431453023461572200856406939246297219541329623
n = 21815431662065695412834116602474344081782093119269423403335882867255834302242945742413692949886248581138784199165404321893594820375775454774521554409598568793217997859258282700084148322905405227238617443766062207618899209593375881728671746850745598576485323702483634599597393910908142659231071532803602701147251570567032402848145462183405098097523810358199597631612616833723150146418889589492395974359466777040500971885443881359700735149623177757865032984744576285054725506299888069904106805731600019058631951255795316571242969336763938805465676269140733371287244624066632153110685509892188900004952700111937292221969
ct = 19073695285772829730103928222962723784199491145730661021332365516942301513989932980896145664842527253998170902799883262567366661277268801440634319694884564820420852947935710798269700777126717746701065483129644585829522353341718916661536894041337878440111845645200627940640539279744348235772441988748977191513786620459922039153862250137904894008551515928486867493608757307981955335488977402307933930592035163126858060189156114410872337004784951228340994743202032248681976932591575016798640429231399974090325134545852080425047146251781339862753527319093938929691759486362536986249207187765947926921267520150073408188188

由代码行：

hint1 = p >> 724
hint2 = q % (2 ** 265)

我们可以知道 p 的高 300 bit数据，和 q 的低 265 bit数据，

令 $q_{l} = q m o d 2^{265}$ , $q = q_{l} + 2^{265} * k$

$n = p * q = p * q_{l} + 2^{265} * k * p$

等式两边乘以 $q_{l}$ 的逆元：

$n * q_{l}^{- 1} = p + 2^{265} * k * p * q_{l}^{- 1}$

等式两边进行模 $2^{265}$ 运算，得到 p 的低 265 bit数据：

$p_{l} = n * q_{l}^{- 1} m o d 2^{265}$

EXP：

from Crypto.Util.number import *
from gmpy2 import *

p_high = 1514296530850131082973956029074258536069144071110652176122006763622293335057110441067910479
q_low = 40812438243894343296354573724131194431453023461572200856406939246297219541329623
n = 21815431662065695412834116602474344081782093119269423403335882867255834302242945742413692949886248581138784199165404321893594820375775454774521554409598568793217997859258282700084148322905405227238617443766062207618899209593375881728671746850745598576485323702483634599597393910908142659231071532803602701147251570567032402848145462183405098097523810358199597631612616833723150146418889589492395974359466777040500971885443881359700735149623177757865032984744576285054725506299888069904106805731600019058631951255795316571242969336763938805465676269140733371287244624066632153110685509892188900004952700111937292221969
c = 19073695285772829730103928222962723784199491145730661021332365516942301513989932980896145664842527253998170902799883262567366661277268801440634319694884564820420852947935710798269700777126717746701065483129644585829522353341718916661536894041337878440111845645200627940640539279744348235772441988748977191513786620459922039153862250137904894008551515928486867493608757307981955335488977402307933930592035163126858060189156114410872337004784951228340994743202032248681976932591575016798640429231399974090325134545852080425047146251781339862753527319093938929691759486362536986249207187765947926921267520150073408188188
e = 0x10001

p_low = n * invert(q_low, pow(2, 265)) % pow(2, 265)
p_part = (p_high << 724) + p_low

mod = pow(2, 265)

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

# 利用 mod*i 爆破中间的未知 bit
for i in range(1, 100):
    f = p_part + x * mod * i
    f = f.monic()
    
    kbits = 1024 - 565 - bit_length(i) # 中间未知 bit 的大小,用于设置多项式的最小根范围
    
    root = f.small_roots(X=2 ^ 454, beta=0.4)
    if (root):
        p = p_part + root[0] * mod * i
        q = n // int(p)
        if p * q == n:
            print(root)
            print(i)
            print('p =', p)
            print('q =', q)
            d = invert(e,(int(q)-1)*(int(p)-1))
            m = pow(c,d,n)
            print(long_to_bytes(int(m)))
            break

对于这段程序：

for i in range(1, 100):
    f = p_part + x * mod * i
    f = f.monic()

实现的就是对中间未知代码的爆破，因为已知的p高低比特位还是不足以利用coppersmith算法计算出根来，所以中间的未知比特也需要爆破出几位后，在进行coppersimth攻击利用

pow(2, 265) * i ，随着 i 的增大相当于在前面一个个添加二进制数据：

比如初始数据为0 ，当i=1时为 1 ，当i=2时为 10 ，当i=3时为 11 ，当i=4时为 100,

从而实现了对中间未知比特的爆破

攻击条件

当 Alice 使用 (N , e) 作为公钥，M1 和 M2 是两个不同的明文消息，且满足线性关系： $M_{1} \equiv f (M_{2}) m o d N$ ，

其中 $f$ 为一个线性多项式： $f = a x + b, (b \neq 0)$ ；

如果给定 $< N, e, C 1, C 2, f >$ ,攻击者就能在时间复杂度 $O (e (l o g N)^{2})$ 内恢复明文 M1，M2。

证明：

因为 $C_{1} = M^{e} m o d N$ ，我们知道 $M_{2}$ 是多项式 $g_{1} (x) = f (x)^{e} - C_{1}$ 的根。类似的， $M_{2}$ 也是多项式 $g_{2} (x) = x^{e} - C_{2}$ 的根。因此，线性因子 $x - M_{2}$ 能够将两个多项式相除。所以攻击者利用欧几里得算法计算出 $g_{1}, g_{2}$ 的最大公因数 $g c d (g_{1}, g_{2})$ ，如果这个 gcd 的结果是线性的，那么我们就得到了 $M_{2}$ 。

实现算法：

from gmpy2 import *
from Crypto.Util.number import*
from sage.all import *

C1 = 
C2 = 
N =
e = 

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a.monic()

def attack(C1,C2,N,e):
    PR.<x> = PolynomialRing(Zmod(n))
    g1 = (ax+b)^e - C1
    g2 = (ax+b)^e - C2
    return -gcd(g1,g2)[0] # 获取多项式的最大公因式的常数项

m1 = attack(C1,C2,N,e)
print(m1)

[HackTM CTF Quals 2023] d-phi-enc

task.py

from Crypto.Util.number import bytes_to_long, getStrongPrime
from secret import flag

assert len(flag) == 255
e = 3
p = getStrongPrime(1024, e=e)
q = getStrongPrime(1024, e=e)
n = p * q
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
enc_d = pow(d, e, n)
enc_phi = pow(phi, e, n)
enc_flag = pow(bytes_to_long(flag), e, n)
print(f"{n = }")
print(f"{enc_d = }")
print(f"{enc_phi = }")
print(f"{enc_flag = }")

# n = 24476383567792760737445809443492789639532562013922247811020136923589010741644222420227206374197451638950771413340924096340837752043249937740661704552394497914758536695641625358888570907798672682231978378863166006326676708689766394246962358644899609302315269836924417613853084331305979037961661767481870702409724154783024602585993523452019004639755830872907936352210725695418551084182173371461071253191795891364697373409661909944972555863676405650352874457152520233049140800885827642997470620526948414532553390007363221770832301261733085022095468538192372251696747049088035108525038449982810535032819511871880097702167
# enc_d = 23851971033205169724442925873736356542293022048328010529601922038597156073052741135967263406916098353904000351147783737673489182435902916159670398843992581022424040234578709904403027939686144718982884200573860698818686908312301218022582288691503272265090891919878763225922888973146019154932207221041956907361037238034826284737842344007626825211682868274941550017877866773242511532247005459314727939294024278155232050689062951137001487973659259356715242237299506824804517181218221923331473121877871094364766799442907255801213557820110837044140390668415470724167526835848871056818034641517677763554906855446709546993374
# enc_phi = 3988439673093122433640268099760031932750589560901017694612294237734994528445711289776522094320029720250901589476622749396945875113134575148954745649956408698129211447217738399970996146231987508863215840103938468351716403487636203224224211948248426979344488189039912815110421219060901595845157989550626732212856972549465190609710288441075239289727079931558808667820980978069512061297536414547224423337930529183537834934423347408747058506318052591007082711258005394876388007279867425728777595263973387697391413008399180495885227570437439156801767814674612719688588210328293559385199717899996385433488332567823928840559
# enc_flag = 24033688910716813631334059349597835978066437874275978149197947048266360284414281504254842680128144566593025304122689062491362078754654845221441355173479792783568043865858117683452266200159044180325485093879621270026569149364489793568633147270150444227384468763682612472279672856584861388549164193349969030657929104643396225271183660397476206979899360949458826408961911095994102002214251057409490674577323972717947269749817048145947578717519514253771112820567828846282185208033831611286468127988373756949337813132960947907670681901742312384117809682232325292812758263309998505244566881893895088185810009313758025764867

题目分析：

已知条件如下

e = 3
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
enc_d = pow(d, e, n)
enc_phi = pow(phi, e, n)
enc_flag = pow(bytes_to_long(flag), e, n)

$d_{e n c} = d^{e} m o d n$ ， ........ 式1

$p h i_{e n c} = p h i^{e} m o d n$ ， ........ 式2

$f l a g_{e n c} = f l a g^{e} m o d n$

我们需要求出 d 的值来，才能解密出 flag ，观察式1、式2，采用了相同的指数和模数n进行的加密，并且 $d = e^{- 1} m o d p h i$ ，两者存在线性关系，很明显这是 Franklin-Reiter 相关消息攻击 。

由 $e d \equiv 1 m o d p h i$ ， $e = 3 ， d < p h i ， e d = 1 + k * p h i$ ，所以 k < e ，即 k < 3。

构造多项式 $g_{1} = p h i^{e} - p h i_{e n c} ， g_{2} = (e d)^{e} - e^{e} d_{e n c} = (1 + k * p h i)^{e} - e^{e} d_{e n c}$

计算多项式的最大公因数，即可得到 phi 的值。

EXP：

from gmpy2 import *
from Crypto.Util.number import*
from sage.all import *

e = 3
n = 24476383567792760737445809443492789639532562013922247811020136923589010741644222420227206374197451638950771413340924096340837752043249937740661704552394497914758536695641625358888570907798672682231978378863166006326676708689766394246962358644899609302315269836924417613853084331305979037961661767481870702409724154783024602585993523452019004639755830872907936352210725695418551084182173371461071253191795891364697373409661909944972555863676405650352874457152520233049140800885827642997470620526948414532553390007363221770832301261733085022095468538192372251696747049088035108525038449982810535032819511871880097702167
enc_d = 23851971033205169724442925873736356542293022048328010529601922038597156073052741135967263406916098353904000351147783737673489182435902916159670398843992581022424040234578709904403027939686144718982884200573860698818686908312301218022582288691503272265090891919878763225922888973146019154932207221041956907361037238034826284737842344007626825211682868274941550017877866773242511532247005459314727939294024278155232050689062951137001487973659259356715242237299506824804517181218221923331473121877871094364766799442907255801213557820110837044140390668415470724167526835848871056818034641517677763554906855446709546993374
enc_phi = 3988439673093122433640268099760031932750589560901017694612294237734994528445711289776522094320029720250901589476622749396945875113134575148954745649956408698129211447217738399970996146231987508863215840103938468351716403487636203224224211948248426979344488189039912815110421219060901595845157989550626732212856972549465190609710288441075239289727079931558808667820980978069512061297536414547224423337930529183537834934423347408747058506318052591007082711258005394876388007279867425728777595263973387697391413008399180495885227570437439156801767814674612719688588210328293559385199717899996385433488332567823928840559
enc_flag = 24033688910716813631334059349597835978066437874275978149197947048266360284414281504254842680128144566593025304122689062491362078754654845221441355173479792783568043865858117683452266200159044180325485093879621270026569149364489793568633147270150444227384468763682612472279672856584861388549164193349969030657929104643396225271183660397476206979899360949458826408961911095994102002214251057409490674577323972717947269749817048145947578717519514253771112820567828846282185208033831611286468127988373756949337813132960947907670681901742312384117809682232325292812758263309998505244566881893895088185810009313758025764867

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a.monic()

def attack(C1,C2,N,e):
    k = 2
    PR.<x> = PolynomialRing(Zmod(n))
    # 替换 a，b 的值
    g1 = x^e - C1
    g2 = (k*x+1)^e - C2
    return -gcd(g1,g2)[0] # 获取多项式的最大公因式的常数项

phi = attack(enc_phi,e^e*enc_d,n,e)
print(phi)

d = pow(e, -1, phi)
m = pow(enc_flag, int(d), n)
print(long_to_bytes(int(m)))

Hastad’s broadcast attack（相关消息攻击变种类型）

[PlaidCTF 2017] Multicast

task.py

from random import randint
from gmpy2 import *
from Crypto.Util.number import *

nbits = 1024
e = 5
flag = b'PCTF{L1ne4r_P4dd1ng_w0nt_s4ve_Y0u_fr0m_H4s7ad!}'
assert len(flag) <= 64
m = bytes_to_long(flag)
out = open("data.txt","w")

for i in range(e):
    while True:
        p = getPrime(512)
        q = getPrime(512)
        ni = p * q
        phi = (p - 1) * (q - 1)
        if gcd(phi, e) == 1:
            break

    while True:
        ai = randint(1, ni - 1)
        if gcd(ai, ni) == 1:
            break

    bi = randint(1, ni - 1)
    mi = ai * m + bi
    ci = pow(mi, e, ni)
    out.write(str(ai) + '\n')
    out.write(str(bi) + '\n')
    out.write(str(ci) + '\n')
    out.write(str(ni) + '\n')

data.txt

69083553146183344839772978505267712546348345951915552104934666999364893606414967631473531356169090286677897220956536147203986323670778671853966574104550916190831974039291113434428713226539656233005536401237618731903013444912424490954403050283261443145833828774338405850464149745370010921929208582803372719662
1847353606880715823527099792264841437499256859046112182901817731898583109812226034453486290034759426343181112477498401843027934563915568068662901070357638240406212287869791959600724393823543974271939728800168160170264361943043888105413027223078955278440961637038127459036967868261370295558665462738851664674
13924397671629169794872532654354896735104301636897981275021597449713744312702850679542667853889775700566291452624971794825605462609659305736119167763171202028684488729179106128850062049316631850373987498751231054904292395688010798166991604433834113228237987911867991301264314792383410544657232986272138720776
107176667955056054888106289112863406099193890480114548290390156586316295797860714447523894766296345238663487884525751440074160698573876676529510120482633305843604033670838833224316621039974842663423971964367617383524243164757298543267528648455662196669719411550337416706436014652957797379123891565563380621721
27025595670607123748133955387986761928986723842407963667833744851457582823949409825451502999363014637018266381381800334740959357732693327871649715849440610655814448606276225985636706847320729571129651265791968308846145775455134446011658371731137714821594128627843120134392299295278193619998726010683820300906
76626521446699164152465241536023395842467420530412705255543098462161399927889232797875074266701010280661667851769988806969262190694662659916308198862288454347865777843483804317714263754964326435968683758707252482706186266157923587034286069745922345373717550980870551177895535541280767243258161167226140529179
74820001900443652318294067181707795319993357148314983190736617977547527951708569170206478241294503335669164830735894900549009883421968340647253048091278584463455833751347773269310148496440204410893225151858930449694234125324321395015257722229646579662704510552084383728048226410232141635889320648460673299335
116940935524323795130742526994657925027084667081524402264947741484054748546876541534619667289853985612350852220069194599338546449074832255593771931123087798582432365325897386813589970457955530817464044545954375253380129491859158211405510009895941963611340400391118219478974834168088677930751757315159110921841
3004029671513060545517047598385797934912754972599429487078366757715733246340760740484289209221138121568405251845847578856114711659946228365274190780159966913357682874178318970562635144717761245951754408952773122354583612422645258507146795630561366955268226048296864853067903656400207186949463324893914485565
39916349286626463801197107509708900778499859478703695888378041406302001988773262878930035955207487249221227735861868182215434820807844055889132141226547303138247159556705455695270756436706739886462479337109843197568024375533105139465029460850504284879314129902197486373473299170494478698741715992027042335920
14108999386222915459940913638433135402751523880380098398237968303803785854582535395117824943688282642164021530817702254201291805032640778641839809162886268856556652703619578965302291774447936003759868066323907388148146727752981125365333046242305065445858381847752308536916145502431706840471314490470498925933
100668102943542293762890526110731145470895119442621421158649868631915746146377966542031367735374167457406299434355768725246104804285632863373024153609404762902208230939718098090168262799174612923680636870557478441319366190063047687786785211877198536555745316733683533528849562416675658775836498023052914901749
42305211872257990504112591982462712826623117527580306258621876854892728665082535381823460722212076449810881809439537932537619270097066694079814712136330261508201872405339882571623217945205024525421229411985020496914748229102523658456972139082089291624782533401385935487411288676903751198610145921301518231107
37927948227203538741746385301195518552457676697015260677758470292294745311488915679784285945487731017142600921756814455642818173556814139042013977633776585763163271296255014647248684364947573160457459801483696377003575286309739820627536302900476424058673287304085337544422656511271366685116274814463373028939
29808378278310626950656040722768610557513777159495566134112105939237344988328390169388824486265334935284692186547128505302437631500267072936205473588904993250984366335171085215776781494184026623681600861765081754836053424849422843633084928107942855476866942904060229897408614881375916806167293356422910088562
80450031402201203587730534009338660865222026164984422981250298135548464160260574889923232542563882168618899594606271070764435488631855210441010916420059803623249294290301484880522559794167514055495411717729597100446344174893389277795663285345593590647340104666332031316803275436638414115193469755829893511487
35798442949372217448131245718267683892608947365147471016957781854054771928382329233065506241624702265207177594187978141208820788381204095301540789196845409818326829309725267401115274448449544207730582441399296587733377747658506089439891602945020732454221665678849354836056443444544603686977883511757122333808
15148604454321045616017299717211628700774278430049633748723698755621714384646643282913626328387905917563070000934175316190944226369346680779250458706206743862204417104832969982264440206554850551723416393459529398494316425018200651517022177685036277113534264161058597282135279496222169055121895473052233762246
90847039947327313643774540191254303763104502856236195148227169238729840332433440088244863054796973078431673232305152421572163200464861625035107176753552370732936207870756803675490237581973525804663863823181351604257906567409397759543713937699041851977124940235865938476195092603195522703292454934101412022811
93862849424043561789940054837392625966883465717813492561917969675964529083848723311514364070936115132154848096497003118110036719543385624344289211314373383330520240583297483284951457880437389550791045654411987778690675595035123064122359417085803319134114455113012761800931917960807358624095094896528184569953

EXP：

from gmpy2 import *
from Crypto.Util.number import *
from sage.all import PolynomialRing

with open('data.txt','r') as f:
    data = f.read().split()
data = [int(i) for i in data]
# print(data)

e = 5
a_i = []
b_i = []
c_i = []
n_i = []
for i in range(5):
    a_i.append(data[4*i+0])
    b_i.append(data[4*i+1])
    c_i.append(data[4*i+2])
    n_i.append(data[4*i+3])

T_i = [crt([int(i==j) for j in range(5)],n_i) for i in range(5)]
# print("T_i = ",T_i)

PR.<x> = PolynomialRing(Zmod(prod(n_i)))
g_i = []
for i in range(5):
    g_i.append(T_i[i] * ((a_i[i] * x + b_i[i]) ^ e - c_i[i]))
g = sum(g_i).monic()  # 计算和          
# print(g_i)
root = g.small_roots(X=2**400,beta=0.5)[0]
print(root)
print(long_to_bytes(int(root)))
# 48256277589562736290346738984160936248669152041168006480231762961805279486041361025591223549819869423406508417405
# b'PCTF{L1ne4r_P4dd1ng_w0nt_s4ve_Y0u_fr0m_H4s7ad!}'

[CakeCTF 2021] Party Ticket

task.py

from Crypto.Util.number import getPrime, isPrime
from hashlib import sha512
import random

def getSafePrime(bits):
    while True:
        p = getPrime(bits - 1)
        q = 2*p + 1
        if isPrime(q):
            return q

def make_inivitation():
    flag = b'scdscjbsjvcjdsbcjbasjcbdsjbcjkdsb'
    m = int.from_bytes(flag + sha512(flag).digest(), "big")

    p = getSafePrime(512)
    q = getSafePrime(512)

    n = p * q
    assert m < n

    b = random.randint(2, n-1)

    c = m*(m + b) % n

    return c, n, b

# print("Dear Moe:")
c1,n1,b1 = make_inivitation()
print("c1 = {}\nn1 = {}\nb1 = {}\n".format(c1,n1,b1))

# print("Dear Lulu:")
c2,n2,b2 = make_inivitation()
print("c2 = {}\nn2 = {}\nb2 = {}\n".format(c2,n2,b2))

# c1,n1,b1 = (39795129165179782072948669478321161038899681479625871173358302171683237835893840832234290438594216818679179705997157281783088604033668784734122669285858548434085304860234391595875496651283661871404229929931914526131264445207417648044425803563540967051469010787678249371332908670932659894542284165107881074924, 68660909070969737297724508988762852362244900989155650221801858809739761710736551570690881564899840391495223451995828852734931447471673160591368686788574452119089378643644806717315577499800198973149266893774763827678504269587808830214845193664196824803341291352363645741122863749136102317353277712778211746921, 67178092889486032966910239547294187275937064814538687370261392801988475286892301409412576388719256715674626198440678559254835210118951299316974691924547702661863023685159440234566417895869627139518545768653628797985530216197348765809818845561978683799881440977147882485209500531050870266487696442421879139684)
# c2,n2,b2 = (36129665029719417090875571200754697953719279663088594567085283528953872388969769307850818115587391335775050603174937738300553500364215284033587524409615295754037689856216651222399084259820740358670434163638881570227399889906282981752001884272665493024728725562843386437393437830876306729318240313971929190505, 126991469439266064182253640334143646787359600249751079940543800712902350262198976007776974846490305764455811952233960442940522062124810837879374503257253974693717431704743426838043079713490230725414862073192582640938262060331106418061373056529919988728695827648357260941906124164026078519494251443409651992021, 126361241889724771204194948532709880824648737216913346245821320121024754608436799993819209968301950594061546010811840952941646399799787914278677074393432618677546231281655894048478786406241444001324129430720968342426822797458373897535424257744221083876893507563751916046235091732419653547738101160488559383290)

分析：

由加密代码：c = m*(m + b) % n

得： $c 1 = m^{2} + m * b 1 m o d n 1$ ， $c 2 = m^{2} + m * b 2 m o d n 2$

根据 Hastad broadcast attack 算法，利用中国剩余定理 CRT ，构造多项式，参考上一题的做法：

解多项式小根的参数要逐步尝试，直到满足条件得到根值：small_roots(X=2^900,beta=0.5,epsilon=0.04)

EXP：

from gmpy2 import *
from Crypto.Util.number import *
from sage.all import PolynomialRing

c1,n1,b1 = (39795129165179782072948669478321161038899681479625871173358302171683237835893840832234290438594216818679179705997157281783088604033668784734122669285858548434085304860234391595875496651283661871404229929931914526131264445207417648044425803563540967051469010787678249371332908670932659894542284165107881074924, 68660909070969737297724508988762852362244900989155650221801858809739761710736551570690881564899840391495223451995828852734931447471673160591368686788574452119089378643644806717315577499800198973149266893774763827678504269587808830214845193664196824803341291352363645741122863749136102317353277712778211746921, 67178092889486032966910239547294187275937064814538687370261392801988475286892301409412576388719256715674626198440678559254835210118951299316974691924547702661863023685159440234566417895869627139518545768653628797985530216197348765809818845561978683799881440977147882485209500531050870266487696442421879139684)
c2,n2,b2 = (36129665029719417090875571200754697953719279663088594567085283528953872388969769307850818115587391335775050603174937738300553500364215284033587524409615295754037689856216651222399084259820740358670434163638881570227399889906282981752001884272665493024728725562843386437393437830876306729318240313971929190505, 126991469439266064182253640334143646787359600249751079940543800712902350262198976007776974846490305764455811952233960442940522062124810837879374503257253974693717431704743426838043079713490230725414862073192582640938262060331106418061373056529919988728695827648357260941906124164026078519494251443409651992021, 126361241889724771204194948532709880824648737216913346245821320121024754608436799993819209968301950594061546010811840952941646399799787914278677074393432618677546231281655894048478786406241444001324129430720968342426822797458373897535424257744221083876893507563751916046235091732419653547738101160488559383290)


n_i = [n1,n2]
c_i = [c1,c2]
b_i = [b1,b2]

T_i = [crt([int(i == j) for j in range(2)], n_i) for i in range(2)]
# print("T_i = ",T_i)

PR.<x> = PolynomialRing(Zmod(prod(n_i)))
g_i = []
for i in range(2):
    g_i.append(T_i[i] * (x^2 + x*b_i[i] - c_i[i]))
g = sum(g_i).monic()
print(g)
root = g.small_roots(X=2^900,beta=0.5,epsilon=0.04)[0]
print(root)
print(long_to_bytes(int(root)))