由于最近碰到了太多cooper的题目，有一元的也有多元的，其中不乏很多让人头痛的难题，自己就想先整理一遍吧

Coppersmith 相关攻击与 Don Coppersmith 紧密相关，他提出了一种针对于模多项式（单变量，二元变量，甚至多元变量）找所有小整数根的多项式时间的方法

一般来说，Coopersmith在RSA中的应用是最多的，高位攻击一类的已知部分二进制位

那么在我们究竟要获取多少后才能打Copper呢？

我们这里先来看coopersmith定理的应用场景

现在给定了一个e阶的多项式f：

  • 给定β，快速求出模某个n的因数b意义下较小的根，其中b ≥ nβ ,(0 ≤ β ≤ 1)
  • 在模n的意义下，快速求出$n=\frac{β^{2}}{e}$ 以内的根

那么高位攻击明显是可以根据第二点来实现的

这里先对要用到的函数进行简单的介绍

1
2
3
4
5
6
7
8
9
10
11
12
PolynomialRing ：构造多项式环
Zmod(n) ：模运算

implementation='NTL' ：执行 NTL

small_roots(self, X=None , beta=1.0 , epsilon=None)：计算多项式的小整数根

其中的参数：X —— 根的绝对边界， beta($\beta$) —— compute a root mod p where p is a factor of N and $p \geq N^\beta$

(程序默认值是 1.0 ，此时 p=N)，epsilon （默认：$\beta/8$)

monic()：用于将多项式的首项系数归一化为1。它接受一个多项式作为参数，然后返回一个新的多项式，其中首项系数已经被归一化为1。这个过程可以简化多项式的表达式，使其更易于计算和分析。

这里打cooper，需要我们知道 的高位为素因子p 的位数约 $\frac{1}{2}$ 比特位时即可

基础

1.1、已知p高bit位

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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

对于上面的位操作来说相当与是先右移动256bit位，再向左移动256bit

看到这个例子

这就相当于是给了高位，或者说是低位的丢失

回到题目中来

我们知道p的高位=1024-256 = 768 bits，未知的低位数据为 256 bits，根据上面的理论这里明显是可以直接打cooper的

那么这里的关键函数是

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

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
25
26
27
28
29
30
31
32
33
from Crypto.Util.number import *

import gmpy2

e = 65537

p_high=159945952275533485818121954231313618960321976049710904254772419907677971914439101482974923293074598678164025819370654132149566696084245679106109087142916286461708005676333840438629476722637189134626565206159794947442549588155962485884562239895738265024295739578695834796427810095412842888401159276765814718464

c=22371088752722216457725632164373582195669473128756299754645443284929524768654545905154985577175225182544638209286885657892360668965805613727315024761409924679131145149936406239774150607378706790494820180586939668429812955766507811860718575149988809217701964019618239260041070894375952033566803105327100696642244951676616707205397327491933042019560545721027871057909242509336729865025061616686254481161431063503607378134616485979961926628954536592552923269161255759846497309277397441639921544384778106116567555705005440627393593876072210594939647990615797269482726733444406876986888296295032722008287447468255108089357

n=26406507468595611843852094067483173843988114465094045314324958205247973393878612589146897816881236818219902539975703710689353618174826904300589643161784341674436810639999244652231756242284615955258973430337702733454791782484002773967293198343866259490519754466626455660967042613249021854707331393440280088268816341057924652807723419166490363777181753297185283416885627445213950857480287818564281651822264024891956284486733856518809532470029519647769749231421957169481281821885757924521580543834665554242403238567286205389138437021157096962185096308108489101554724344868500500476691994206988217768341711716527866730487

PR.<x> = PolynomialRing(Zmod(n))  #构造多项式环

f = p_high+x            #

roots = f.small_roots(X=2^256,beta=0.4,epsilon=1)  #后面的两个参数都是默认的，

print(roots)

\#[34617643142235695556586808773805798019055870312898061509976159971261415964273]

p=p_high+int(roots[0])

q=n//p

phi=(p-1)*(q-1)

d=gmpy2.invert(e,phi)

m=pow(c,d,n)

print(long_to_bytes(m))

1.2 、已知p高bit位但泄露位数不够

上面也说过我们必须知道泄露位数的一半才能打cooper，那么这就不使用于下面这题

image-20250422160400020

这是我测试的数据，这种情况是不足以恢复p的，必须要知道144位才能恢复

但是136bit和144bit只差了8bit,也就是8个二进制数，那么爆破也就是最好的办法了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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

对于这道题目来说，p是256bit的数，也就是高位泄露了136位，

八位二进制数最大时255，那么我们直接开始爆破就好

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
36
37
38
39
40
41
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)
        

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

1.3、已知p的低位攻击

既然已知高位能恢复原先的p，那么如果我们知道p的低位呢

答案很明显也是可以的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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
'''

还是一样的

1
p&((1<<560) - 1)

我们可以知道p的低位

从代码中我们可以知道p是1024bit的，p泄露的低位是560位,那么从上面的理论中我们是可以恢复p的

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
from Crypto.Util.number import *

import gmpy2

n = 21595945409392994055049935446570173194131443801801845658035469673666023560594683551197545038999238700810747167248724184844583697034436158042499504967916978621608536213230969406811902366916932032050583747070735750876593573387957847683066895725722366706359818941065483471589153682177234707645138490589285500875222568286916243861325846262164331536570517513524474322519145470883352586121892275861245291051589531534179640139953079522307426687782419075644619898733819937782418589025945603603989100805716550707637938272890461563518245458692411433603442554397633470070254229240718705126327921819662662201896576503865953330533

c = 1500765718465847687738186396037558689777598727005427859690647229619648539776087318379834790898189767401195002186003548094137654979353798325221367220839665289140547664641612525534203652911807047718681392766077895625388064095459224402032253429115181543725938853591119977152518616563668740574496233135226296439754690903570240135657268737729815911404733486976376064060345507410815912670147466261149162470191619474107592103882894806322239740349433710606063058160148571050855845964674224651003832579701204330216602742005466066589981707592861990283864753628591214636813639371477417319679603330973431803849304579330791040664

p_low = 1426723861968216959675536598409491243380171101180592446441649834738166786277745723654950385796320682900434611832789544257790278878742420696344225394624591657752431494779

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

f = x*2^560+p_low

f = f.monic()

kbit=1024-560  # 用于设置根X的界限

roots=f.small_roots(X=2^kbit,beta=0.4,epsilon=0.015)

p = int(2^560*roots[0] + p_low)

q = n // p

assert p*q == n

e=65537

d=gmpy2.invert(e,(p-1)*(q-1))

m=pow(c,int(d),n)

print(long_to_bytes(int(m)))


还是一样的思路

2.1已知明文m的高位攻击

在RSA加密中，如果明文泄露了我们能直接恢复吗，答案明显是可以的

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

这里可以看到我们知道m高88位泄露，那么只要符合上面的条件我们就能恢复出m

基本过程一样，无非是构造多项式过程不一样

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
from Crypto.Util.number import *

c = 49448440304854831648796534024125601382006282873198989997965557974794200333763817072355620545318651927253247674282578472637671741164408087215327482745901235293974786619481946963756529643023816474028709984009212852065178750039594108019217271743973042473197736068985706708503716012186147977316095727799381598075488417125

n = 28847074924932453349543409136399812128594610949367020026474778343570858319481313455200890189364023790182887175049408105958843453263073050626086662142940263874460213271683958427975341123423883215407111909499389249677340455477004237510991188529190235171007660645641687224704887400900068278836154730644879715422040757103147552875954913961588149167053461868101745063648215554184664115626793497487765708744642552805937987823454039925728887745567746569963466846339068171354494330823482202581747310450407677264654959638952096601645772638052521701110952634257302519671771900589919411338060623904602870338988690057676936333193

e = 3

m_high = 0x666c61677b343833323734383733383438777975727975737238796538727938320000000000000000000000

kbits = 88

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

f = (m_high+x)**e-c

f = f.monic()

root = f.small_roots(X=2^88,beta=0.5)

print(root)

m=m_high+int(root[0])

print(long_to_bytes(m))

2.2已知明文m的低位攻击

那么m的低位也是一样的

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 *
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
'''

这里一样就不多说了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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=0.4时，在未知位数少于等于227bit时，可以恢复p

当beta=0.4,epsilon=0.01时，在未知位数少于等于248bit时，可以恢复p

拓展

1.1P泄露位数不够

TGCTF2025 EZRSA

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
from Crypto.Util.number import *

def genarate_emojiiiiii_prime(nbits, base=0):
    while True:
        p = getPrime(base // 32 * 32) if base >= 3 else 0
        for i in range(nbits // 8 // 4 - base // 32):
            p = (p << 32) + get_random_emojiiiiii() # 猜一猜
        if isPrime(p):
            return p

m = bytes_to_long(flag.encode()+ "".join([long_to_bytes(get_random_emojiiiiii()).decode() for _ in range(5)]).encode())
p = genarate_emojiiiiii_prime(512, 224)
q = genarate_emojiiiiii_prime(512)

n = p * q
e = "💯"
c = pow(m, bytes_to_long(e.encode()), n)

print("p0 =", long_to_bytes(p % 2 ** 256).decode())
print("n =", n)
print("c =", c)

p0 = '😘😾😂😋😶😾😳😷'
n = 156583691355552921614631145152732482393176197132995684056861057354110068341462353935267384379058316405283253737394317838367413343764593681931500132616527754658531492837010737718142600521325345568856010357221012237243808583944390972551218281979735678709596942275013178851539514928075449007568871314257800372579
c = 47047259652272336203165844654641527951135794808396961300275905227499051240355966018762052339199047708940870407974724853429554168419302817757183570945811400049095628907115694231183403596602759249583523605700220530849961163557032168735648835975899744556626132330921576826526953069435718888223260480397802737401

这里搞了点抽象看起来花里胡哨的，但是本质就是p的泄露

1
2
3
4
p = (p << 32) + get_random_emojiiiiii()
p = genarate_emojiiiiii_prime(512, 224)
p0 = '😘😾😂😋😶😾😳😷'
print("p0 =", long_to_bytes(p % 2 ** 256).decode())

我们从题目中可以知道的是p是512bit的，以及p0,想要打cooper就要知道这里的p0有多少位

1
p = genarate_emojiiiiii_prime(512, 224)

这里我们看出p的结构

这里一个emoji是四个字节，那么也就是说我们知道了其中的256位，但是p是512位的，那么也就打不了cooper，我们还差8bit，那么当泄露的字节来到了288bit，我们就可以打cooper了

之后e,phi不互素，直接有限域开方就好

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
from Crypto.Util.number import *

p0_ = 108837065531980906150333850570890620719343963272506332719822248235755953428663
n = 156583691355552921614631145152732482393176197132995684056861057354110068341462353935267384379058316405283253737394317838367413343764593681931500132616527754658531492837010737718142600521325345568856010357221012237243808583944390972551218281979735678709596942275013178851539514928075449007568871314257800372579
c = 47047259652272336203165844654641527951135794808396961300275905227499051240355966018762052339199047708940870407974724853429554168419302817757183570945811400049095628907115694231183403596602759249583523605700220530849961163557032168735648835975899744556626132330921576826526953069435718888223260480397802737401

a=4036991100

from tqdm import tqdm
for i in tqdm(range(100)):
    PR.<x> = PolynomialRing(Zmod(n))
    f = x * 2^288 + p0_ + (a+i)*2^256
    f = f.monic()
    roots = f.small_roots(X=2^225, beta=0.4,epsilon=0.04)

    if roots:
        x = roots[0]
        p_candidate = int(x * 2^288 + p0_ + (a+i)*2^256)
        if n % p_candidate == 0:
            print("Found p:", p_candidate)
            q_candidate = n // p_candidate
            break

from gmpy2 import *
from random import *
from libnum import *

p=int(p_candidate)
q=int(q_candidate)
e=int(4036989615)

print(p,q,n%p,n%q)

print(GCD(e,(p-1)*(q-1)))
print(GCD(e,(p-1)))
print(GCD(e,(q-1)))

d=inverse(e//GCD(e,(p-1)*(q-1)),(p-1)*(q-1))
c=pow(c,d,n)

R.<y>=Zmod(p)[]
f=y^15-c
f=f.monic()
m1=f.roots()

R.<z>=Zmod(q)[]
f=z^15-c
f=f.monic()
m2=f.roots()

for i in m1:
    for j in m2:
        m=solve_crt([int(i[0]),int(j[0])],[int(p),int(q)])
        print(long_to_bytes(int(m)))
        if b'TGCTF' in long_to_bytes(int(m)):
            print(long_to_bytes(int(m)).decode())


1.2p泄露位数不够且无法爆破

HGAME 2023

这里为什么说无法爆破呢，因为要爆破的数量级太大

1
2
3
4
5
6
7
8
9
10
11
12
13
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

这里是p的高位泄露

这里有253bit未知，根据定理只能有225bit未知，也就是说28bit要爆破也就是228,那么这就是相当大的数据了

那么有什么解决办法呢

位爆破+调节参数扩大格的范围

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
from tqdm import *

n = 68340867186438223292118569682710524595966327481168801678255800028919163918249557519447553078528255888326840419621716908729880235244230459900539486879943421761586611726942757775742624070088176246368128990077459966006579285028594729801017390816903003704541109757846868073362640037019813128220657114558520107057

pbits = 512

for i in trange(2**5):
	p4 = 531320819410375258952658395582915285878636410772332266245849790153420724865787<<(253-248)
	p4 = p4 + i
	kbits = pbits - p4.nbits()
	p4 = p4 << kbits
	PR.<x> = PolynomialRing(Zmod(n))
	f = x + p4
	roots = f.small_roots(X=2^kbits, beta=0.4, epsilon=0.01)
	if roots:        
		p = p4+int(roots[0]) 
		if n%p==0:
			print(i,p)
			break
            
q = n//p
e = 65537
c = 0x29d543c73f4175f22440eef5954184e9d740cd3785011d560431861ccf6c4ff380d46ad948f9888e8cac2f5e38ce5e994f023d7195b78439b90d53ad23a730cc99b1b75dae1aba416cb6e645c5d135de906be54f344daba47a10492183d03211bfbaa45c09be2bb1913b1453e0538db95c56140cb78dd9c43d21f8312245ef7d
f = (p-1)*(q-1)
d = inverse_mod(e,f)
m = pow(c,d,n)
print(bytes.fromhex(hex(m)[2:]))

# b'now_you_know_how_to_use_coppersmith'

0xGame2024

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
36
37
from Crypto.Util.number import bytes_to_long

from secret import flag

q = getPrime(512)

p = getPrime(512)

e = 65537

N = p * q

h = q >> 253

m = bytes_to_long(flag)

c = pow(m,e,N)

print(f'N = {N}')

print(f'e = {e}')

print(f'c = {c}')

print(f'h = {h}')

'''

N = 135500646574582511239845764710311769260801998982429500680171919823431178899526463566215834234383331374445093363969218810906991784569340270510936759183504496584225937614940086329775325893307453919055830270986601152002191368431527285285313669979358099782497422114870417519470053198217401297960844455029559146309

e = 65537

c = 41763956818640145556632229720626372656921875856507389014855753965024986594502113237270745517422792354256348958542864591249410500750410658988509136242435502259172258432676502846729088278202750721760451160668653746019965695721844819587671602925551448624324524027931677927410810126647175483982178300855471710099

h = 918578024558168836638919636090777586135497638818209533615420650282292168631485

'''

这里就是原题搬家了，这里就不再多说了

1.3P泄露的位数够但需要调整参数

Mini L-CTF Ezfactor

1
2
3
4
5
6
7
p.bit_length() == q.bit_length() == 768

gift = p>>360

gift = 484571358830397929370234740984952703033447536470079158146615136255872598113610957918395761289775053764210538009624146851126

n = 1612520630363003059353142253089981533043311564255746310310940263864745479492015266264329953981958844235674179099410756219312942121244956701500870363219075525408783798007163550423573845701695879459236385567459569561236623909034945892869546441146006017614916909993115637827270568507869830024659905586004136946481048074461682125996261736024637375095977789425181258537482384460658359276300923155102288360474915802803118320144780824862629986882661190674127696656788827

这里可以看到p是768bit，知道的高位是438bit，根据定理我们是可以直接打cooper的，可是实际测试我们发现无法恢复p

那么我们现在能做的就是调整参数了，问题随之而来，究竟如何调参呢？

当beta=0.4时，在未知位数少于等于227bit时，可以恢复p

当beta=0.4,epsilon=0.01时，在未知位数少于等于248bit时，可以恢复p

之前说过的，而我们现在未知的位数是330bit，那么beta肯定要往上调，不过具体的原理倒不是很清楚，以后再慢慢研究吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from Crypto.Util.number import*

n = 1612520630363003059353142253089981533043311564255746310310940263864745479492015266264329953981958844235674179099410756219312942121244956701500870363219075525408783798007163550423573845701695879459236385567459569561236623909034945892869546441146006017614916909993115637827270568507869830024659905586004136946481048074461682125996261736024637375095977789425181258537482384460658359276300923155102288360474915802803118320144780824862629986882661190674127696656788827

ph = 484571358830397929370234740984952703033447536470079158146615136255872598113610957918395761289775053764210538009624146851126

phh = ph*(2**360)

e = 107851261855564315073903829182423950546788346138259394246439657948476619948171

kbits = 360 

PR = PolynomialRing(Zmod(n),names = ('x'));(x,) = PR._first_ngens(1)

f = x + phh

p = f.small_roots(X = 2**360,beta = 0.45,epsilon = 0.02)[0] + phh

print(p)

1.4其他形式的泄露

2023LitCTF Babyxor

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from Crypto.Util.number import *
from secret import flag

m = bytes_to_long(flag)
assert len(flag)==32
p = getPrime(512)
q = getPrime(512)
n = p*q
e = 65537
c1 = p^m
c2 = pow(m,e,n)	
print(f'n = {n}')
print(f'c1 = {c1}')
print(f'c2 = {c2}')
"""
n = 139167681803392690594490403105432649693546256181767408269202101512534988406137879788255103631885736461742577594980136624933914700779445704490217419248411578290305101891222576080645870988658334799437317221565839991979543660824098367011942169305111105129234902517835649895908656770416774539906212596072334423407
c1 = 11201139662236758800406931253538295757259990870588609533820056210585752522925690049252488581929717556881067021381940083808024384402885422258545946243513996
c2 = 112016152270171196606652761990170033221036025260883289104273504703557624964071464062375228351458191745141525003775876044271210498526920529385038130932141551598616579917681815276713386113932345056134302042399379895915706991873687943357627747262597883603999621939794450743982662393955266685255577026078256473601
"""

这里并没有明确给出p的高位，但是我们仔细分析题目给出的条件

1
len(flag)=32

那么就是说flag是32字节也就是256bit，在看到p是512bit，那么p^m也就是p的低位丢失了，换句话说p的高位还是原来的高位，那不就是p的高位泄露

在看到cooper定理要求，这里显然是不满足的我们还需要爆破8位

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
import gmpy2
from tqdm import *
from Crypto.Util.number import *

n = 139167681803392690594490403105432649693546256181767408269202101512534988406137879788255103631885736461742577594980136624933914700779445704490217419248411578290305101891222576080645870988658334799437317221565839991979543660824098367011942169305111105129234902517835649895908656770416774539906212596072334423407
c1 = 11201139662236758800406931253538295757259990870588609533820056210585752522925690049252488581929717556881067021381940083808024384402885422258545946243513996
c2 = 112016152270171196606652761990170033221036025260883289104273504703557624964071464062375228351458191745141525003775876044271210498526920529385038130932141551598616579917681815276713386113932345056134302042399379895915706991873687943357627747262597883603999621939794450743982662393955266685255577026078256473601
e = 65537
pbits = 512

p_high = c1 >> 256
for i in trange(2**8):
    p4 = p_high << 8			#这里需要先爆破8位，使得知道264位以后再恢复p
    p4 = p4 + i
    kbits = pbits - p4.nbits()
    p4 = p4 << kbits
    R.<x> = PolynomialRing(Zmod(n))
    f = x + p4
    res = f.small_roots(X=2^kbits, beta=0.4, epsilon=0.01)
    if res != []:
        p = p4 + int(x[0])
        q = n // p
        d = gmpy2.invert(e,(p-1)*(q-1))
        m = pow(c2,d,n)
        print(long_to_bytes(int(m)))
        break

#LitCTF{oh!!!!coppersmith_is_fun}

1.5 明文的高位泄露

反方向的密码 相思

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
from Crypto.Util.number import *

import hashlib

from secrets import flag

def hash(x):

  return hashlib.sha256(x.encode()).digest()

def pad(message):

  return message + hash(str(len(message)))

m = bytes_to_long(pad(flag))

p = getStrongPrime(512)

q = getStrongPrime(512)

n = p * q

e = 3

print(pow(m, e, n))

print(n)

\# 120440199294949712392334113337541924034371176306546446428347114627162894108760435789068328282135879182130546564535108930827440004987170619301799710272329673259390065147556073101312748104743572369383346039000998822862286001416166288971531241789864076857299162050026949096919395896174243383291126202796610039053

\# 143413213355903851638663645270518081058249439863120739973910994223793329606595495141951165221740599158773181585002460087410975579141155680671886930801733174300593785562287068287654547100320094291092508723488470015821072834947151827362715749438612812148855627557719115676595686347541785037035334177162406305243

感觉是道比较有意思的高位泄露，与其它题目不同的是，这并没有直接给出m的高位

看到加密等式 C = (m||h(len(m)))3 mod  n 再观察题目给出的条件

1
hashlib.sha256(x.encode()).digest()

既然这里是用sha256加密，那么加密后的结果一定就是32字节的结果,通常来说flag长度在30-40位左右 C = (25632m + h)3 mod  n 那么我们来打cooper

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
from Crypto.Util.number import *

import hashlib

from tqdm import *

def hash(x):

  return hashlib.sha256(x.encode()).digest()

e = 3

c = 120440199294949712392334113337541924034371176306546446428347114627162894108760435789068328282135879182130546564535108930827440004987170619301799710272329673259390065147556073101312748104743572369383346039000998822862286001416166288971531241789864076857299162050026949096919395896174243383291126202796610039053

n = 143413213355903851638663645270518081058249439863120739973910994223793329606595495141951165221740599158773181585002460087410975579141155680671886930801733174300593785562287068287654547100320094291092508723488470015821072834947151827362715749438612812148855627557719115676595686347541785037035334177162406305243

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

for length in trange(20,50):

  suffix = bytes_to_long(hash(str(length)))

  f = (256^32*x + suffix)^3 - c

  f = f.monic()

  res = f.small_roots(X=256^length,beta=1,epsilon=0.05)

  if(res != []):

    print(long_to_bytes(int(res[0])))

    break

当然这里的flag头我们是知道所以还有另一种写法

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
36
37
38
39
from Crypto.Util.number import *

import hashlib

c = 120440199294949712392334113337541924034371176306546446428347114627162894108760435789068328282135879182130546564535108930827440004987170619301799710272329673259390065147556073101312748104743572369383346039000998822862286001416166288971531241789864076857299162050026949096919395896174243383291126202796610039053

n = 143413213355903851638663645270518081058249439863120739973910994223793329606595495141951165221740599158773181585002460087410975579141155680671886930801733174300593785562287068287654547100320094291092508723488470015821072834947151827362715749438612812148855627557719115676595686347541785037035334177162406305243

def hash(x):

  return hashlib.sha256(x.encode()).digest()

for i in range(10,40):                  #i代表{}中未知数的个数

  prefix = bytes_to_long(b"XYCTF{") * 256^(32 + 1 + i)

  

  pad = hash(str(i+7))

  low = bytes_to_long(b"}" + pad)

  

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

  

  f = (prefix + x*256^33 + low)^3 - c

  f = f.monic()

  res = f.small_roots(X=256^i)

  if res != []:

    m = prefix + int(res[0])*256^33 + low

    print(long_to_bytes(int(m)))

1.6已知dq的低位攻击

这个倒不是很常见

1
2
3
4
n = 0xd7152506aa9cec05e5335d6b46f5491407c3199fd51091f1f6030d3762b9e03f49c9dcdc075054e0cc148b974b41854bd93b4ee16a2a876ee62005e80ef806b7aa3b64b1bf9b1fa773e353d0cdb9ff9783ddd5f5e67499ad10f361e938d00b82a6a4c42a0535c5e76721798e86b45cd4b8d03b0d7e75c2be8766a1e843bdc641
e = 0x10001
dq_low = 0xc90bcecf1cbab3358585e8a041d1b1
qinvp = 0xe3016cb3609c1d643c167439c3b938b881f4237f24860d3b1cb85a626d5ccd4726964e0f8270d6c4df9ebfebcc538e4ee5e1a7b7368ede51ec6ae917f78eb598

分析条件，我们知道dq的低位，e，n

那么这里dq满足打cooper的条件，然后就是dq泄露的板子打

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
#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

二元cooper

那么在介绍完了coppersmith定理之后下面介绍二元cooper

这里对二元cooper的原理就不多说什么了，可以参考其他师傅们的blog，这里主要还是自己对题目的理解

放个二元coop而求小根的代码

m为移位（shifts），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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
import gmpy2
import itertools
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.coefficient_matrix()
    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 []

2.1 [CISCN 2021华南]small

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
36
37
38
39
40
41
42
43
44
45
import random, hashlib

from Crypto.Util.number import getPrime

from secret import x, y, flag

BITS = 70

assert(2**BITS < x < 2**(BITS+1))

assert(2**BITS < y < 2**(BITS+1))

m = str(x) + str(y)

h = hashlib.sha256()

h.update(m.encode())

assert(flag == "flag{" + h.hexdigest() + "}")

p = getPrime(512)

a = getPrime(510)

b = getPrime(510)

c = (1 + a * x * y ** 2 + b * x ** 2 * y) % p

print("p = " + str(p))

print("a = " + str(a))

print("b = " + str(b))

print("c = " + str(c))

'''

p = 8813834626918693034209829623386418111935369643440896703895290043343199520112218432639643684400534953548489779045914955504743423765099014797611981422650409

a = 2817275225516767613658440250260394873529274896419346861054126128919212362519165468003171950475070788320195398302803745633617864408366174315471102773073469

b = 1763620527779958060718182646420541623477856799630691559360944374374235694750950917040727594731391703184965719358552775151767735359739899063298735788999711

c = 2298790980294663527827702586525963981886518365072523836572440106026473419042192180086308154346777239817235315513418426401278994450805667292449334757693881

这里的加密很简单

1
c = (1 + a * x * y ** 2 + b * x ** 2 * y) % p

根据题目中的条件我们只有x,y是不知道的

一个方程两个未知数，那么直接打二元cooper

这里的构造思路和cooper是一样的

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
import gmpy2

import itertools

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.coefficient_matrix()

  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 []

p = 8813834626918693034209829623386418111935369643440896703895290043343199520112218432639643684400534953548489779045914955504743423765099014797611981422650409

a = 2817275225516767613658440250260394873529274896419346861054126128919212362519165468003171950475070788320195398302803745633617864408366174315471102773073469

b = 1763620527779958060718182646420541623477856799630691559360944374374235694750950917040727594731391703184965719358552775151767735359739899063298735788999711

c = 2298790980294663527827702586525963981886518365072523836572440106026473419042192180086308154346777239817235315513418426401278994450805667292449334757693881

R.<x,y> = PolynomialRing(Zmod(p))

f = (1 + a * x * y ** 2 + b * x ** 2 * y)-c

res = small_roots(f,(2^70,2^64),m=2,d=5)

print(res)

\#[(2109960504722998994279, 1693812585349439720973)]

这是比较简单的一题

2.2 SRCTF leak revenge

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from Crypto.Util.number import *
from secret import flag

m = bytes_to_long(flag)
p = getPrime(512)
q = getPrime(512)
n = p * q
e = getPrime(64)
dp = inverse(e, p - 1)
print(f"n = {n}")
print(f"e = {e}")
print(f"dph = {dp >> 115 <<115}")
print(f"c = {pow(m,e,n)}")

"""
n = 99808598778276923350368946118829564161543192771741967304113142692217693457972421525964898372688505220132024575461230316318177765543298394717753949509523080306599063058808987337840085569950414884529534449801215600413303898393849792345972321407524999652571659221193654323489992751031985715286873931985408130197
e = 9550490518460184889
dph = 4239371595915398923623854132330356869028911602649930928560125044718768467773415379438150660838271530302945945606708178367182566660953659123879375907323904
c = 18661814437233106799783882536249538287931377372915334052147813302071480339780465378376553936510407532657463793836895065758256947765504246845601788497861702555369338586376572381147331367628136147491699775987490116748428373153021965663362046971594255692960097313870139384700219810117047587229718472407783734575
"""

dp泄露最后我们是需要遍历e的，但是这里的e太大，无法遍历求解，所以打个二元cooper

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
from Crypto.Util.number import *
import gmpy2
import itertools

def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()
        print(d)
    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.coefficient_matrix()
    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 []

n = 99808598778276923350368946118829564161543192771741967304113142692217693457972421525964898372688505220132024575461230316318177765543298394717753949509523080306599063058808987337840085569950414884529534449801215600413303898393849792345972321407524999652571659221193654323489992751031985715286873931985408130197
e = 9550490518460184889
c = 18661814437233106799783882536249538287931377372915334052147813302071480339780465378376553936510407532657463793836895065758256947765504246845601788497861702555369338586376572381147331367628136147491699775987490116748428373153021965663362046971594255692960097313870139384700219810117047587229718472407783734575
leak = 4239371595915398923623854132330356869028911602649930928560125044718768467773415379438150660838271530302945945606708178367182566660953659123879375907323904

R.<x,y> = PolynomialRing(Zmod(n))
f = e * (leak + x) + (y - 1)
res = small_roots(f,(2^115,2^64),m=2,d=5)
print(res)
for root in res:
    dp_low = root[0]
    dp = leak + dp_low
    tmp = pow(2,e*dp,n) - 2
    p = gmpy2.gcd(tmp,n)
    q = n // p
    d = inverse(e,(p-1)*(q-1))
    m = pow(c,d,n)
    print(long_to_bytes(m))

    # SRCTF{00adb8189e3580577be8b97d1da8e205d0b64d4e65570547d7a67850fad1e4a2}

2.3Complex_signin

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
from Crypto.Util.number import *

from Crypto.Cipher import ChaCha20

import hashlib

from secret import flag

class Complex:

 def __init__(self, re, im):

  self.re = re

  self.im = im

 def __mul__(self, c):

  re_ = self.re * c.re - self.im * c.im

  im_ = self.re * c.im + self.im * c.re

  return Complex(re_, im_)

 def __eq__(self, c):

  return self.re == c.re and self.im == c.im

 def __rshift__(self, m):

  return Complex(self.re >> m, self.im >> m)

 def __lshift__(self, m):

  return Complex(self.re << m, self.im << m)

 def __str__(self):

  if self.im == 0:

   return str(self.re)

  elif self.re == 0:

   if abs(self.im) == 1:

    return f"{'-' if self.im < 0 else ''}i"

   else:

    return f"{self.im}i"

  else:

   return f"{self.re} {'+' if self.im > 0 else '-'} {abs(self.im)}i"

 def tolist(self):

  return [self.re, self.im]

def complex_pow(c, exp, n):

 result = Complex(1, 0)

 while exp > 0:

  if exp & 1:

   result = result * c

   result.re = result.re % n

   result.im = result.im % n

  c = c * c

  c.re = c.re % n

  c.im = c.im % n

  exp >>= 1

 return result

bits = 128

p = getPrime(1024)

q = getPrime(1024)

n = p * q

m = Complex(getRandomRange(1, n), getRandomRange(1, n))

e = 3

c = complex_pow(m, e, n)

print(f"n = {n}")

print(f"mh = {(m >> bits << bits).tolist()}")

print(f"C = {c.tolist()}")

print(f"enc = {ChaCha20.new(key=hashlib.sha256(str(m.re + m.im).encode()).digest(), nonce=b'Pr3d1ctmyxjj').encrypt(flag)}")

'''

n = 24240993137357567658677097076762157882987659874601064738608971893024559525024581362454897599976003248892339463673241756118600994494150721789525924054960470762499808771760690211841936903839232109208099640507210141111314563007924046946402216384360405445595854947145800754365717704762310092558089455516189533635318084532202438477871458797287721022389909953190113597425964395222426700352859740293834121123138183367554858896124509695602915312917886769066254219381427385100688110915129283949340133524365403188753735534290512113201932620106585043122707355381551006014647469884010069878477179147719913280272028376706421104753

mh = [3960604425233637243960750976884707892473356737965752732899783806146911898367312949419828751012380013933993271701949681295313483782313836179989146607655230162315784541236731368582965456428944524621026385297377746108440938677401125816586119588080150103855075450874206012903009942468340296995700270449643148025957527925452034647677446705198250167222150181312718642480834399766134519333316989347221448685711220842032010517045985044813674426104295710015607450682205211098779229647334749706043180512861889295899050427257721209370423421046811102682648967375219936664246584194224745761842962418864084904820764122207293014016, 15053801146135239412812153100772352976861411085516247673065559201085791622602365389885455357620354025972053252939439247746724492130435830816513505615952791448705492885525709421224584364037704802923497222819113629874137050874966691886390837364018702981146413066712287361010611405028353728676772998972695270707666289161746024725705731676511793934556785324668045957177856807914741189938780850108643929261692799397326838812262009873072175627051209104209229233754715491428364039564130435227582042666464866336424773552304555244949976525797616679252470574006820212465924134763386213550360175810288209936288398862565142167552]

C = [5300743174999795329371527870190100703154639960450575575101738225528814331152637733729613419201898994386548816504858409726318742419169717222702404409496156167283354163362729304279553214510160589336672463972767842604886866159600567533436626931810981418193227593758688610512556391129176234307448758534506432755113432411099690991453452199653214054901093242337700880661006486138424743085527911347931571730473582051987520447237586885119205422668971876488684708196255266536680083835972668749902212285032756286424244284136941767752754078598830317271949981378674176685159516777247305970365843616105513456452993199192823148760, 21112179095014976702043514329117175747825140730885731533311755299178008997398851800028751416090265195760178867626233456642594578588007570838933135396672730765007160135908314028300141127837769297682479678972455077606519053977383739500664851033908924293990399261838079993207621314584108891814038236135637105408310569002463379136544773406496600396931819980400197333039720344346032547489037834427091233045574086625061748398991041014394602237400713218611015436866842699640680804906008370869021545517947588322083793581852529192500912579560094015867120212711242523672548392160514345774299568940390940653232489808850407256752]

enc = b'\x9c\xc4n\x8dF\xd9\x9e\xf4\x05\x82!\xde\xfe\x012$\xd0\x8c\xaf\xfb\rEb(\x04)\xa1\xa6\xbaI2J\xd2\xb2\x898\x11\xe6x\xa9\x19\x00pn\xf6rs- \xd2\xd1\xbe\xc7\xf51.\xd4\xd2 \xe7\xc6\xca\xe5\x19\xbe'

'''

拿到题目我们先审计一波代码

想要恢复明文我们需要先获取到m的实部和虚部，然后解密ChaCha20加密，对于最后一步的解密是很简单的，关键就是恢复m的实部和虚部

1
2
3
m = Complex(getRandomRange(1, n), getRandomRange(1, n))

mh = {(m >> bits << bits).tolist()}

这里的m是个复数，而且这里很明显是m的高位泄露

那么接下来要干的事就很清晰了

既然是在复数域下，那我们就有

m = re + im * i

那么这里的高位泄露就可以表示为 $$

加密过程非常简单 c=m^{3} $$

那么这里就是复数的立方了 m3 = (re + im ⋅ i)3 = (re3 − 3 ⋅ re ⋅ im2) + (3 ⋅ re2 ⋅ im − im3) ⋅ i 这里出题的预期是解结式然后cooper，但是二元cooper可以直接出了,那么我们只用利用实部来列方程就好

我们设re的低位是x,im的虚部是y，则有方程 c = (re + x)3 − 3 * （re + x） * (im + y)2 这里利用二元cooper解出x,y我们就可以成功恢复m了

接下来就是解ChaCha20了。这个没啥说的了

这里对系数稍微解释一下m是移位，也就是格的维度，d代表的是方程中最高系数的幂

对于128位的泄露，通常我们m=2或者3，这里最高次幂是3，毫无疑问的d=3

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
from sage.all import *

from Crypto.Cipher import ChaCha20

import hashlib

import itertools

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.coefficient_matrix()

 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 []

n = 24240993137357567658677097076762157882987659874601064738608971893024559525024581362454897599976003248892339463673241756118600994494150721789525924054960470762499808771760690211841936903839232109208099640507210141111314563007924046946402216384360405445595854947145800754365717704762310092558089455516189533635318084532202438477871458797287721022389909953190113597425964395222426700352859740293834121123138183367554858896124509695602915312917886769066254219381427385100688110915129283949340133524365403188753735534290512113201932620106585043122707355381551006014647469884010069878477179147719913280272028376706421104753

mh = [3960604425233637243960750976884707892473356737965752732899783806146911898367312949419828751012380013933993271701949681295313483782313836179989146607655230162315784541236731368582965456428944524621026385297377746108440938677401125816586119588080150103855075450874206012903009942468340296995700270449643148025957527925452034647677446705198250167222150181312718642480834399766134519333316989347221448685711220842032010517045985044813674426104295710015607450682205211098779229647334749706043180512861889295899050427257721209370423421046811102682648967375219936664246584194224745761842962418864084904820764122207293014016, 15053801146135239412812153100772352976861411085516247673065559201085791622602365389885455357620354025972053252939439247746724492130435830816513505615952791448705492885525709421224584364037704802923497222819113629874137050874966691886390837364018702981146413066712287361010611405028353728676772998972695270707666289161746024725705731676511793934556785324668045957177856807914741189938780850108643929261692799397326838812262009873072175627051209104209229233754715491428364039564130435227582042666464866336424773552304555244949976525797616679252470574006820212465924134763386213550360175810288209936288398862565142167552]

C = [5300743174999795329371527870190100703154639960450575575101738225528814331152637733729613419201898994386548816504858409726318742419169717222702404409496156167283354163362729304279553214510160589336672463972767842604886866159600567533436626931810981418193227593758688610512556391129176234307448758534506432755113432411099690991453452199653214054901093242337700880661006486138424743085527911347931571730473582051987520447237586885119205422668971876488684708196255266536680083835972668749902212285032756286424244284136941767752754078598830317271949981378674176685159516777247305970365843616105513456452993199192823148760, 21112179095014976702043514329117175747825140730885731533311755299178008997398851800028751416090265195760178867626233456642594578588007570838933135396672730765007160135908314028300141127837769297682479678972455077606519053977383739500664851033908924293990399261838079993207621314584108891814038236135637105408310569002463379136544773406496600396931819980400197333039720344346032547489037834427091233045574086625061748398991041014394602237400713218611015436866842699640680804906008370869021545517947588322083793581852529192500912579560094015867120212711242523672548392160514345774299568940390940653232489808850407256752]

enc = b'\x9c\xc4n\x8dF\xd9\x9e\xf4\x05\x82!\xde\xfe\x012$\xd0\x8c\xaf\xfb\rEb(\x04)\xa1\xa6\xbaI2J\xd2\xb2\x898\x11\xe6x\xa9\x19\x00pn\xf6rs- \xd2\xd1\xbe\xc7\xf51.\xd4\xd2 \xe7\xc6\xca\xe5\x19\xbe'

mh_re,mh_im=mh

R.<x,y> = PolynomialRing(Zmod(n))

f = (mh_re+x)^3-3*(mh_re+x)*(mh_im+y)^2 - C[0]

res=small_roots(f,(2^128,2^128),m=2,d=3)  

print(res)

m_re=mh_re+int(res[0][0])

m_im=mh_im+int(res[0][1])

flag = ChaCha20.new(key=hashlib.sha256(str(m_re + m_im).encode()).digest(), nonce=b'Pr3d1ctmyxjj').decrypt(enc).decode()

print(flag)

#[(200140573956551184845123803212115015633, 62109784561410747979732334460991877433)]

#XYCTF{Welcome_to_XYCTF_Now_let_us_together_play_Crypto_challenge}

趣题

知道部分高，低位

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


p, q = getPrime(1024), getPrime(1024)
N = p * q
p0 = p ^ (bytes_to_long(flag)<<444)     
m = bytes_to_long(flag)
c = pow(m, 65537, N)
print(len(flag))
print('c=',c)
print('N=',N)
print('p0=',p0)


# 54    

# c= 6187845844052645335477666563187579997555293403110620879123121166924703361821847984760733842049752886698011561451715570810292323756091403783920480396052120046379755571530451812078574368413924390017994278703794257118954968480994077586245800902748815905644287545189605031883291488844527496906890127546594960138582150272568163575590734246290813150131949296550974206595456421136190026954855755623761557179760444906148376433584795779131477110538212742401420633087881506416368853221110426491868881029814841479615979710066371796507692025126150957315754738584387325388998533227577023142894876376702128870643448600352603905149

# N= 14195810221536708489210274086946022255792382922322850338983263099316341767896809249586174293795778082892237356582757544364274847341220303582304283372889068290282580493623042441421715338444710303281638639785784613434328659529884972238348336971186339482788748316527376410510261228354155806341136524162787121212184386900663470590652770503564816948407257603737938414126069053610568675347826390537145556511048774030823322301932088595499671755944744816524811272617200683384649389274196659297432212847319503330409792704612575414010711158873031786577877685578976140462539734553598745329712188216200905451774357282278403189943

# p0= 111984935426070810628244029907949697819351004665202173622240566580193974673163315128983603277856218378729883402496424467491406698035050254407170555432448523469880166015507303737468316933545613178461925283040643344197452758878116752692499745309765526523083790825015522124083482964296662782850606081657447935191

这里我们会发现m左移了444位后和p异或，那么也就意味着p的低444位是不变的，因为这里左移过后就是0

image-20250507141049448

但是这里的p是1024位的，只知道444位的话我们还打不了cooper

根据flag长度是54，转成int数据就432bit，左移444位后是876位，异或之后，p的高(1024 - 876) = 148位也是不变的。所以我们有了p的部分高位和低位

已知592位我们就可以打cooper了

第一步肯定是先要求出p知道的高位和低位了

1
2
3
4
5
phigh = p0 >> 876 <<876

tmp = int("1" * 444,2)

plow = p0 & tmp

后面的cooper还是跟之前的一样即可

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
36
37
38
39
import gmpy2

from Crypto.Util.number import *

p0 = 111984935426070810628244029907949697819351004665202173622240566580193974673163315128983603277856218378729883402496424467491406698035050254407170555432448523469880166015507303737468316933545613178461925283040643344197452758878116752692499745309765526523083790825015522124083482964296662782850606081657447935191

c = 6187845844052645335477666563187579997555293403110620879123121166924703361821847984760733842049752886698011561451715570810292323756091403783920480396052120046379755571530451812078574368413924390017994278703794257118954968480994077586245800902748815905644287545189605031883291488844527496906890127546594960138582150272568163575590734246290813150131949296550974206595456421136190026954855755623761557179760444906148376433584795779131477110538212742401420633087881506416368853221110426491868881029814841479615979710066371796507692025126150957315754738584387325388998533227577023142894876376702128870643448600352603905149

n = 14195810221536708489210274086946022255792382922322850338983263099316341767896809249586174293795778082892237356582757544364274847341220303582304283372889068290282580493623042441421715338444710303281638639785784613434328659529884972238348336971186339482788748316527376410510261228354155806341136524162787121212184386900663470590652770503564816948407257603737938414126069053610568675347826390537145556511048774030823322301932088595499671755944744816524811272617200683384649389274196659297432212847319503330409792704612575414010711158873031786577877685578976140462539734553598745329712188216200905451774357282278403189943

e = 65537

phigh = p0 >> 876 <<876

tmp = int("1" * 444,2)

plow = p0 & tmp

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

f = phigh + x*2**444 + plow    # x*2**444 将x移动到正确的位置

f = f.monic()

res = f.small_roots(X=2^432,beta=0.4)

if res != []:

  p = int(phigh + res[0]*2**444+plow)

  print("p =",p)

  q = n // p

  d = gmpy2.invert(e,(p-1)*(q-1))

  m = pow(c,d,n)

  print(long_to_bytes(int(m)))

MiniL 2025 rsasign

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
from Crypto.Util.number import bytes_to_long, getPrime, inverse

from secret import flag

def genKeys(nbits):

  e = 0x10001

  p = getPrime(nbits // 2)

  q = getPrime(nbits // 2)

  n = p * q

  phi = n - (p + q) + 1

  d = inverse(e, phi)

  pubkey = (n, e)

  prikey = (d, p, q)

  

  return pubkey, prikey

def encrypt(msg, pubkey):

  m = bytes_to_long(msg)

  n, e = pubkey

  c = pow(m, e, n)

  return c

def get_gift(prikey):

  a = bytes_to_long(b'miniL')

  b = bytes_to_long(b'mini7')

  p, q = prikey[1:]

  phi = (p - 1)*(q - 1)

  giftp = p + a

  giftq = q + b

  gift = pow((giftp + giftq + a*b), 2, phi)

  return gift >> 740

if __name__ == "__main__":

  nbits = 1024

  pubkey, prikey = genKeys(nbits)

  c = encrypt(flag, pubkey)

  gift = get_gift(prikey)

  with open('output.txt', 'a') as f:

    f.write('pubkey = ' + str(pubkey) + '\n')

    f.write('c = ' + str(c) + '\n')

    f.write('gift = ' + str(gift) + '\n')

pubkey = (65537,103894244981844985537754880154957043605938484102562158690722531081787219519424572416881754672377601851964416424759136080204870893054485062449999897173374210892603308440838199225926262799093152616430249061743215665167990978654674200171059005559869946978592535720766431524243942662028069102576083861914106412399)

c = 50810871938251627005285090837280618434273429940089654925377752488011128518767341675465435906094867261596016363149398900195250354993172711611856393548098646094748785774924511077105061611095328649875874203921275281780733446616807977350320544877201182003521199057295967111877565671671198186635360508565083698058

gift = 2391232579794490071131297275577300947901582900418236846514147804369797358429972790212

首先题目给出的是gift的高位

1
gift = pow((giftp + giftq + a*b), 2, phi)

看到gift的线性关系，可以先展开 gift = (p + a + q + b + a * b)2 mod  phi 这里phi = n − (p + q) + 1

因此我们可以认为phi的高位就是n的高位，所以可以直接用 n 代替 phi，解得(p+q)的高位

现在知道了p*q，（p+q）的高位，那么解方程可以得到的p或者q的高位，这里我们解结式

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
36
37
from Crypto.Util.number import *

from gmpy2 import gmpy2

\#from sage.matrix.matrix2 import Matrix

def resultant(f1, f2, var):

  return Matrix.determinant(f1.sylvester_matrix(f2, var))

n=103894244981844985537754880154957043605938484102562158690722531081787219519424572416881754672377601851964416424759136080204870893054485062449999897173374210892603308440838199225926262799093152616430249061743215665167990978654674200171059005559869946978592535720766431524243942662028069102576083861914106412399

gift =2391232579794490071131297275577300947901582900418236846514147804369797358429972790212

gift=gift<<740

p, q = QQ['x, y'].gens()

f = n-p*q

g = (p+q)**2-4*(n-(p+q)+1) - gift

h = f.resultant(g, q)

print([f, g])

print([h, factor(h)])

PR.<x> = PolynomialRing(RealField(1000))

h = PR(h)

print(h)

res =h.monic().roots()

print(res)

得到了p的高位，下面自然是来打cooper，这里p泄露了229位，可以打cooper

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
36
from Crypto.Util.number import *

import gmpy2

c = 50810871938251627005285090837280618434273429940089654925377752488011128518767341675465435906094867261596016363149398900195250354993172711611856393548098646094748785774924511077105061611095328649875874203921275281780733446616807977350320544877201182003521199057295967111877565671671198186635360508565083698058

n=103894244981844985537754880154957043605938484102562158690722531081787219519424572416881754672377601851964416424759136080204870893054485062449999897173374210892603308440838199225926262799093152616430249061743215665167990978654674200171059005559869946978592535720766431524243942662028069102576083861914106412399

p=8501639590121977595053523738818375259679414794730106020578368658056270529108719142843616239876180609592408042971719162819965092838486348749800524648844787

p_high=p>>229<<229

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

f = p_high+x

res = f.small_roots(X = 2^229,beta=0.4,epsilon=0.01)

print(res)

if res != 0:

  p = p_high+int(res[0])

  q = n//p

  phi = (p-1)*(q-1)

  d = gmpy2.invert(65537,phi)

  m= pow(c,d,n)

  print(long_to_bytes(m))
#[119002501248222579736269858969778348009982530327788722167912373692341]
#b'miniL{D0_Y@U_Li)e_T&@_RRRSA??}'