糖醋小鸡块的blog
0%

2023-CNSS-Summer-wp-crypto

发表于 更新于 分类于 Valine：

要给自己学校的招新赛出题了，于是混进CNSS招新赛前的夏令营找找出题灵感，不得不说，很多题目都出的很不错，难度与知识点控制的很好，于是在此记录一下。

Rank：3

image-20230916080626025

Crypto Guideline

签到题，标志着crypto方向题目的开始，直接提交flag即可。

flag:

cnss{Welcome to the world of cryptography!}




cyclic group

题目描述：

1
可以找到我藏在循环群中的flag吗？

题目内容：

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  ## secret is a local file, flag is unknown to you

p = getPrime(1024)
m = bytes_to_long(flag)
e = getPrime(512)
c = 1
for i in range(e):
    c *= m   
    c %= p

print('p =', p)
print('e =', e)
print('c =', c)

'''
p = 134994058501022133829793113756450648798182080773931273262418798773562440624857106163310596590759607340807163876539520282102901165977612358002331391089851066812663281502398201018663717659213732276911585751665516661301930410244101046617666467321456930120075263141242119953757880295718825254018040413826880843763
e = 12927587515508549311645504126259938927362775210786958053823827936884288861306268493761629822045846148118653977616493302703588300283111036739875491883808759
c = 46583597391505868783218970830156160405763802889228578452060606957717500160663392513770581781157233604314178955789908254475724009921579917780127649365498088467948777432657442293331639740286781008682662602974865442032279819833194544535317410041738966384493317240586005380761492762248899523164168679218802048162
'''

可以看到，实际上就是：

因此直接幂乘e关于p-1的逆元即可。而本题的题目名字cyclic group指代的是循环群，在这里即是在说，由于模数p为素数，那么群Z*(p)的阶就为p-1，因此其中任意一个元素满足：

因此可以直接求指数关于p-1的逆元求解题目。


exp.py：

1
2
3
4
5
6
7
8
from Crypto.Util.number import *

p = 134994058501022133829793113756450648798182080773931273262418798773562440624857106163310596590759607340807163876539520282102901165977612358002331391089851066812663281502398201018663717659213732276911585751665516661301930410244101046617666467321456930120075263141242119953757880295718825254018040413826880843763
e = 12927587515508549311645504126259938927362775210786958053823827936884288861306268493761629822045846148118653977616493302703588300283111036739875491883808759
c = 46583597391505868783218970830156160405763802889228578452060606957717500160663392513770581781157233604314178955789908254475724009921579917780127649365498088467948777432657442293331639740286781008682662602974865442032279819833194544535317410041738966384493317240586005380761492762248899523164168679218802048162

d = inverse(e,p-1)
print(long_to_bytes(pow(c,d,p)))

flag:

cnss{Unbelievable! You know the key of cyclic group!}




cnss娘的代码Ⅰ

题目描述：

1
cnss娘写了一段感觉意义不明的代码，你能帮她找到flag吗？

题目：

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)
key = []
for i in range(4):
    key.append(getPrime(128))
    
secret = []
for i in range(4):
    secret.append(m % key[i])
    
print('key =', key)
print('secret =', secret)

'''
key = [179283057970236760812385016853348861313, 243730152305882610684268424505624182831, 276375013783217805474364273321195364813, 338363147025326331069698214354955107607]
secret = [42312333420922777926503668120694248887, 188911830445106862831548334980052602782, 202272400826094059912187609891368651300, 16939666639933430404336668949000187621]

简洁明了地考察中国剩余定理。


exp.py：

1
2
3
4
5
6
7
8
from Crypto.Util.number import * 
from sympy.ntheory.modular import crt
#使用如：M = crt(n,c)[0]
key = [179283057970236760812385016853348861313, 243730152305882610684268424505624182831, 276375013783217805474364273321195364813, 338363147025326331069698214354955107607]
secret = [42312333420922777926503668120694248887, 188911830445106862831548334980052602782, 202272400826094059912187609891368651300, 16939666639933430404336668949000187621]

M = crt(key,secret)[0]
print(long_to_bytes(M))

flag:

cnss{Wow!Chinese remainder theorem is so interseting!}




RSA Ⅰ

题目描述：

1
Can you factorize n ?

题目：

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

m = bytes_to_long(flag)
p = getPrime(512)
q = getPrime(512)
n = p*q


e=65537
c = pow(m,e,n)
mask = getPrime(512)
print(f'c = {c}')
print(f'n = {n}')
print(f'mask = {mask}')
print(p|mask)
print(p&mask)

#c = 64949799997326584007544788513993497249594769744995858720976935000014197232306799968807213667255871030075230919683627404813038995304033226711042639925325815395252041199650244620814678407788637241064396318107929964286966081900052163098825412222835465966640369222321472659135622216530966800717417560715221275591
#n = 106750680418525866311589462967145265327203310954735134383588573660691518247034803380198999333962213971657327515092895034635965957228036264848532931376595751503164297061094511187060069380048933807326213369464059701069965785612620370291933800122445966488267918733547599024267999872488061941892122230382138042783
#mask = 12270330408774238331968219216635392599519489634111741706590917012819298856158311310855782884352875794146685141255943386189197362902992928716839082520848927
#13112112110892990771168306272793201342028151601627796725313855804865001339738164412798270175076178951452110894792943424133718769511979832250960465757056799
#11731832079629748669705816329667815638461774924918417348984676937048335348013101619038697983623814812736529127108466295988845879378764866277739393693264401

题目给了n的一个素因子p与mask的&及|位运算结果，那么对于每一位，可以简单枚举一下所有可能性：

  • &运算为1，则p该位为1
  • &运算为0，|运算为1，则当mask该位为1时，p该位为0；当mask该位为0时，p该位为1
  • &运算为0，|运算为0，则p该位为0

因此可以还原p的所有比特位，进而解密RSA。


exp.py：

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 *

c = 64949799997326584007544788513993497249594769744995858720976935000014197232306799968807213667255871030075230919683627404813038995304033226711042639925325815395252041199650244620814678407788637241064396318107929964286966081900052163098825412222835465966640369222321472659135622216530966800717417560715221275591
n = 106750680418525866311589462967145265327203310954735134383588573660691518247034803380198999333962213971657327515092895034635965957228036264848532931376595751503164297061094511187060069380048933807326213369464059701069965785612620370291933800122445966488267918733547599024267999872488061941892122230382138042783
mask = 12270330408774238331968219216635392599519489634111741706590917012819298856158311310855782884352875794146685141255943386189197362902992928716839082520848927
gift1 = 13112112110892990771168306272793201342028151601627796725313855804865001339738164412798270175076178951452110894792943424133718769511979832250960465757056799
gift2 = 11731832079629748669705816329667815638461774924918417348984676937048335348013101619038697983623814812736529127108466295988845879378764866277739393693264401
e = 65537

strmask = bin(mask)[2:]
strgift1 = bin(gift1)[2:]
strgift2 = bin(gift2)[2:]

strp = []
for i in range(len(strmask)):
    if(strgift2[i] == "1"):
        strp.append("1")
    else:
        if(strgift1[i] == "1" and strmask[i] == "0"):
            strp.append("1")
        elif(strgift1[i] == "1" and strmask[i] == "1"):
            strp.append("0")
        else:
            strp.append("0")

p = int("".join(strp),2)
q= n//p       
phi = (p-1)*(q-1)
d = inverse(e,phi)
m = pow(c,d,n)
print(long_to_bytes(m))

flag:

cnss{1t_s33ms_bit_is_useful}




cnss娘的代码 Ⅱ

题目描述：

1
2
cnss娘最近在研究一类数论中的难题，你可以帮助她吗？
Hint: SageMath的使用可以让你事半功倍

题目：

1
2
3
4
5
6
7
8
9
10
11
12
from Crypto.Util.number import *
from secret import flag  

p = 149223181221309438217142971731290162048502071683234438807455153639165894737664410172266260056805353255967638568356843140306590887937
m = bytes_to_long(flag)
g = 7
h = pow(g, m, p)

print('h =', h)

'''
106414500627466044750537699496116452216938505790285966641538755230718107434518035561502262320845803494959251547594598724676292650073

直接用sage求解离散对数即可。


exp.ipynb：

1
2
3
4
5
6
7
8
from Crypto.Util.number import *

p = 149223181221309438217142971731290162048502071683234438807455153639165894737664410172266260056805353255967638568356843140306590887937
g = 7
h = 106414500627466044750537699496116452216938505790285966641538755230718107434518035561502262320845803494959251547594598724676292650073

m=discrete_log(mod(h,p),mod(g,p))
print(long_to_bytes(m))

flag:

cnss{Congratulation! You crack the DLP problem!}




cnss娘的代码 Ⅲ

题目描述：

1
2
cnss娘最近在学习线性代数，你可以帮她解出这道题吗？
Hint:Sage 中自带有 Matrix 和 Vector 类。

题目：

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

assert len(flag) == 40
p = 9536720961414799253
u = []
for i in range(0, 40, 5):
    u.append(bytes_to_long(flag[i:i+5]))
u = vector(u)
A = random_matrix(Zmod(p), 8)
v = u * A

print('A =', A)
print('v =', v)

'''
A = [7907672172473958392 4938237561047760432 5072996306459844921  800347085054263333 2241217299487989740 5452520396763079026 7354205761061650589 5632270298193588206]
[6856262700627435223 7218982369550725117 3069216736555490147 9043167152368671477 6651431740452419751 2904199636400840775 1984801523985180355 9424612078019686546]
[ 190015986177831045  594687507332748466 2546708346651205091 3864956414971412519 2586812319675472372 2541554633306459284 2840981234492698127  400426130440806923]
[ 354930743948767363  374079227033274174 7821379197355217415 4073976921774664952 8974661879090783904 8725597754431417139 1723115467249027682  914056616366301410]
[9032929938905307703  569436029465728354 3230536280479973685 9499318835507740454  460664783708095350 3815328100857956310 6866516203996475375 9142528333783640721]
[6647724854667560614 1564543033588842443  980081446425820918 4482664640152609224 9361385831487208956 5729265277086036438 8521779175294512538 7872078731489374461]
[2426759667632064565 2564361116290067541 5109836057988930695 3948680632682199428 8561341181219447072 5099840518920477627 9347277712921710222 4364598388067284951]
[2143804620259054744 4318231909289693782 6284698432978577252 5529804751795288609 7903556036971407808 3730126758887833322 8782120630459581951 9050476736532525999]
v = (4088048241727106122, 258857328202723850, 7303598013681209756, 3446975206276714926, 176458751236949790, 8151363680348349027, 8771366063042882128, 9003511237633705064)

'''

直接在sage中求解逆矩阵即可

exp.ipynb：

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

p = 9536720961414799253
A = [[7907672172473958392,4938237561047760432,5072996306459844921,800347085054263333,2241217299487989740,5452520396763079026,7354205761061650589,5632270298193588206],
[6856262700627435223,7218982369550725117,3069216736555490147,9043167152368671477,6651431740452419751,2904199636400840775,1984801523985180355,9424612078019686546],
[190015986177831045,594687507332748466,2546708346651205091,3864956414971412519,2586812319675472372,2541554633306459284,2840981234492698127,400426130440806923],
[354930743948767363,374079227033274174,7821379197355217415,4073976921774664952,8974661879090783904,8725597754431417139,1723115467249027682,914056616366301410],
[9032929938905307703,569436029465728354,3230536280479973685,9499318835507740454,460664783708095350,3815328100857956310,6866516203996475375,9142528333783640721],
[6647724854667560614,1564543033588842443,980081446425820918,4482664640152609224,9361385831487208956,5729265277086036438,8521779175294512538,7872078731489374461],
[2426759667632064565,2564361116290067541,5109836057988930695,3948680632682199428,8561341181219447072,5099840518920477627,9347277712921710222,4364598388067284951],
[2143804620259054744,4318231909289693782,6284698432978577252,5529804751795288609,7903556036971407808,3730126758887833322,8782120630459581951,9050476736532525999]]

ans = [4088048241727106122, 258857328202723850, 7303598013681209756, 3446975206276714926, 176458751236949790, 8151363680348349027, 8771366063042882128, 9003511237633705064]
A = matrix(A)
ans = matrix(ans)

flag = ans * A.inverse()
print(flag)

#得到flag后转化为字符串
flag = [256128467098287645152364579619033136532012336082411188262170716121111141373910417997647279385874168289963422098883372524388175789168151018039664118938/201110710500527103391704345109970877861492963385688540350899980246056954432876844511421798766202341953924005687593642435623584608348351172354206968203,-275157020682273200260243873388370073035487413746791277567209773631463468440360425377838149581773104213153845176881963804588249058534505227929576082442/201110710500527103391704345109970877861492963385688540350899980246056954432876844511421798766202341953924005687593642435623584608348351172354206968203,205418055261423253440834873996888852743735400527184165431288083430874722579052114104669136088527642186595043026543683492544648632576976821633919688987/67036903500175701130568115036656959287164321128562846783633326748685651477625614837140599588734113984641335229197880811874528202782783724118068989401,18887682222057954947813918789359532063827948125435329591909175563625225112660734620218938715145807440112704581336669611824654566923603748916776016972/67036903500175701130568115036656959287164321128562846783633326748685651477625614837140599588734113984641335229197880811874528202782783724118068989401,-25792447761509638420556125881168126603544490324749544374648563355312526747005861915100426458158515036632551136815312658182069136958880193280291853604/201110710500527103391704345109970877861492963385688540350899980246056954432876844511421798766202341953924005687593642435623584608348351172354206968203,263743295233022646271965564265774549530140797857736570979958721892220519418537528753856004044323800915867363751008926223858363297878551362225736657993/201110710500527103391704345109970877861492963385688540350899980246056954432876844511421798766202341953924005687593642435623584608348351172354206968203,-839256526384408301445325525932265486477039492555936647496320730347707472223889935476141937534810747723549651396954028900430020396698162916210131940419/201110710500527103391704345109970877861492963385688540350899980246056954432876844511421798766202341953924005687593642435623584608348351172354206968203,165200370960939593750718733159922760922513289005013438437371715048231002848101266223391623531454692435044072426966916629687643829467166749676754679429/67036903500175701130568115036656959287164321128562846783633326748685651477625614837140599588734113984641335229197880811874528202782783724118068989401]
for i in flag:
    print(str(long_to_bytes(int(i % p)))[2:-1],end = "")

flag:

cnss{Line8ar alg3ebra 1s 50 i0mportant!}




HomoBlock

题目描述：

1
你是一个，一个一个一个Homo啊啊啊啊啊啊啊

题目：

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 secret import flag
from Crypto.Util.number import bytes_to_long, getRandomNBitInteger
from random import getrandbits
from os import urandom

assert flag.startswith(b'cnss{I_a') and flag.endswith(b'}')
assert len(flag)%8==0
MASK1 = getRandomNBitInteger(32)|(0xffffffff00000000)
MASK2 = getRandomNBitInteger(32)<<32
ROUND = 5
def genKey():
    tmp = []
    for i in range(ROUND):
        tmp.append(getRandomNBitInteger(64))
def NotHomoFunction(x,iv,key):
    return ((x<<iv)&MASK1)^((x>>iv)|MASK2)^key

def encrypt(message,iv,key):
    cipher = bytes_to_long(message)
    for i in range(ROUND):
        cipher = NotHomoFunction(cipher,iv,key)
    return cipher

cipher = []
iv = 32
key = getRandomNBitInteger(64)
for i in range(0,len(flag),8):
    cipher.append(encrypt(flag[i:i+8],iv,key))

print(cipher)
print(iv)
print(MASK2)

""" 
[4840951631397558164, 5492303526413306583, 6271460196030786735, 6127905759336302986, 601209385465514967]
32
16500653344889503744

观察加密方式，发现具有以下特点:

  • 明文按长度为8分组，分别加密
  • 每一轮交换上一轮得到结果的高低32位，然后异或 MASK2 ，异或key。

可以发现，这样交换4次后就会恢复初值，所以实际交换5次后，就能得到初始值异或 MASK2 并异或key的结果。又因为明文的第一部分已经给出，所以可以根据这个明文恢复key，后续逐步恢复即可。


exp.py：

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

flag = b'cnss{I_a'
f0 = bytes_to_long(flag)
p = [4840951631397558164, 5492303526413306583, 6271460196030786735, 6127905759336302986, 601209385465514967]
MASK2 = 16500653344889503744
f1 = p[0]
hf0, lf0 = (f0 >> 32, f0 % (2 ** 32))
hf1, lf1 = (f1 >> 32, f1 % (2 ** 32))
hk = hf1 ^ lf0 ^ (MASK2 >> 32)
lk = lf1 ^ hf0
key = (hk << 32) + lk

flag = ''
for i in p:
	l, h = ((i ^ MASK2 ^ key) >> 32, (i ^ MASK2 ^ key) % (2 ** 32))
	flag += long_to_bytes((h << 32) | l).decode()
print(flag)

flag:

cnss{I_am_n0t_HHHHHHoooommmmmmmoooo0000}




ezLFSR

题目描述：

1
2
3
do you know LFSR?
Hint1:考点： LFSR流密码
Hint2:可以使用 z3solver 。

题目：

task.py：

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 secret import mask,seed
from Crypto.Util.number import long_to_bytes
class LFSR():
    def __init__(self, seed, mask, length):
        self.length_mask = 2 ** length - 1
        self.mask = mask & self.length_mask
        self.state = seed & self.length_mask

    def next(self):
        next_state = (self.state << 1) & self.length_mask
        i = self.state & self.mask & self.length_mask
        output = 0
        while i != 0:
            output ^= (i & 1)
            i = i >> 1
        next_state ^= output
        self.state = next_state
        return output

    def getrandbit(self, nbit):
        output = 0
        for _ in range(nbit):
            output = (output << 1) ^ self.next()
        return output
def encrypt(cipher, ipath, opath):
    ifile=open(ipath,'rb')
    ofile=open(opath,'wb')
    plaintext=ifile.read()
    for ch in plaintext:
        c=ch^cipher.getrandbit(8)
        ofile.write(long_to_bytes(c))
    ifile.close()
    ofile.close()

lfsr = LFSR(seed, mask, 16)
encrypt(lfsr,'flag.txt','cipher.enc')
print(f'seed = {seed}')

# seed = 37285

cipher.enc：

1
E3306EA1B67E13D02B59A0DEA270AD8C3AF0110FBF60C07740A699A5918E7DC5

注意到mask也仅取了低16位，那么爆破的范围也仅有65536，因此直接爆破出符合要求的明文串即可。


exp.py：

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
from Crypto.Util.number import long_to_bytes
class LFSR():
    def __init__(self, seed, mask, length):
        self.length_mask = 2 ** length - 1
        self.mask = mask & self.length_mask
        self.state = seed & self.length_mask

    def next(self):
        next_state = (self.state << 1) & self.length_mask
        i = self.state & self.mask & self.length_mask
        output = 0
        while i != 0:
            output ^= (i & 1)
            i = i >> 1
        next_state ^= output
        self.state = next_state
        return output

    def getrandbit(self, nbit):
        output = 0
        for _ in range(nbit):
            output = (output << 1) ^ self.next()
        return output

seed = 37285
hex_string = "E3306EA1B67E13D02B59A0DEA270AD8C3AF0110FBF60C07740A699A5918E7DC5"
# 每两个字符一组拆分
split_hex = [hex_string[i:i+2] for i in range(0, len(hex_string), 2)]

c = []
for i in split_hex:
    c.append(int(i,16))

for i in range(2**16):
    mask = i
    lfsr = LFSR(seed, mask, 16)
    clist = []
    for ch in c:
        temp=ch^lfsr.getrandbit(8)
        clist.append(chr(temp))
    str1 = "".join(clist)
    if("cnss" in str1):
        print(str1)

运行时间大概需要不到1分钟。

flag:

cnss{Y0u_can_brust_0r_F1nd_seed}

从flag串以及hint可以看出，本题应该是可以通过LFSR的方式恢复明文的，但是数量级太小，没必要。




RSA Ⅱ

题目描述：

1
2
It's more difficult than RSA Ⅰ,right? Can you factorize n ?
Hint:查找有关RSA攻击的资料是一个很重要的技能。

并提供了一篇论文链接：1506.pdf (iacr.org)

题目：

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 *
from secret import flag

m = bytes_to_long(flag)
p = getPrime(512)
q = getPrime(512)

n = p*q
mask1 = 8802124635072632944677646490123224379036416333544329119490072003355821545476873187055484863111312282268555945525261726909784693138184611507738758202965723
mask2 = 10267484648659998697412163107809730542736732193409802323765378917769614002176050843098384409535095473863894691160595931186139418791709781214996751031082601

e=65537
c = pow(m,e,n)
mask1 = getPrime(512)
mask2 = getPrime(512)

print(f'c = {c}')
print(f'n = {n}')
print(f'mask1 = {mask1}')
print(f'mask2 = {mask2}')
print(f'h1 = {p&mask1}')
print(f'h2 = {q&mask2}')


'''
c = 21645208345867622053024283678631971385301103104312441336174301067402923208233033116071987870811290403578077414872467955871236843078200772311176723821275372545792521252126496488134168455430882670865862282658077115199048181151105823370547063726203692258934054391552916645628374539820099986794258298843501009240
n = 87282921750815275717132715603847471604654006135344540742956637574882193904171665195367477260090328888053170090015909620539666069545618781812315864580009968838414539707616636379202667918204792277927294032362873240288573251987386601263377458038218959813925307265939433229169884527274177006792047369788293125409
mask1 = 8802124635072632944677646490123224379036416333544329119490072003355821545476873187055484863111312282268555945525261726909784693138184611507738758202965723
mask2 = 10267484648659998697412163107809730542736732193409802323765378917769614002176050843098384409535095473863894691160595931186139418791709781214996751031082601
h1 = 6706231204421711988537353586716977912583550778985616494052350868539347641557164021930575245010900470979740623857738159245103694128834121517146255441177729
h2 = 6704397956705493482354535847135592349486638396996488745737387153856868045426992197309829534096366784379171117205125136777653995357887539312554042026362473

相较于RSA1，这一次不能根据位运算结果完全确定出p、q的比特位了，不过仍然可以利用以下线索还原：

  • &运算为1，则p该位必为1
  • &运算为0，mask该位为1，则p该位必为0

而当&运算为0，mask也为0时，p的该比特位就存在两种结果，无法完全确定。可是这题不仅给了p，还给了q的位运算结果，因此我们可以利用下面这一点信息，从高位向低位进行深度优先搜索，显著降低复杂度：

1
2
1、将p、q当前确定的二进制位后方全部填充0，直至填满512位，此时p、q乘积应小于n。
2、将p、q当前确定的二进制位后方全部填充1，直至填满512位，此时p、q乘积应大于n。

如此就能在极短时间内还原出p、q。


exp.py：

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

e = 65537
c = 21645208345867622053024283678631971385301103104312441336174301067402923208233033116071987870811290403578077414872467955871236843078200772311176723821275372545792521252126496488134168455430882670865862282658077115199048181151105823370547063726203692258934054391552916645628374539820099986794258298843501009240
n = 87282921750815275717132715603847471604654006135344540742956637574882193904171665195367477260090328888053170090015909620539666069545618781812315864580009968838414539707616636379202667918204792277927294032362873240288573251987386601263377458038218959813925307265939433229169884527274177006792047369788293125409
mask1 = 8802124635072632944677646490123224379036416333544329119490072003355821545476873187055484863111312282268555945525261726909784693138184611507738758202965723
mask2 = 10267484648659998697412163107809730542736732193409802323765378917769614002176050843098384409535095473863894691160595931186139418791709781214996751031082601
h1 = 6706231204421711988537353586716977912583550778985616494052350868539347641557164021930575245010900470979740623857738159245103694128834121517146255441177729
h2 = 6704397956705493482354535847135592349486638396996488745737387153856868045426992197309829534096366784379171117205125136777653995357887539312554042026362473
mask1 = str(bin(mask1)[2:])
mask2 = str(bin(mask2)[2:])
h1 = str(bin(h1)[2:])
h2 = str(bin(h2)[2:])

def find(p,q):
    l = len(p)
    tmp0 = p + (512-l)*"0"
    tmp1 = p + (512-l)*"1"
    tmq0 = q + (512-l)*"0"
    tmq1 = q + (512-l)*"1"
    if(int(tmp0,2)*int(tmq0,2) > n):
        return 
    elif(int(tmp1,2)*int(tmq1,2) < n):
        return

    if(l == 512):
        #print(tmp0)
        print(int(tmp0,2))
        print(int(tmq0,2))
        
    else:
        if((mask1[l] == "1" and h1[l] == "1") and (mask2[l] == "1" and h2[l] == "1")):
            find(p+"1",q+"1")
        elif((mask1[l] == "1" and h1[l] == "1") and (mask2[l] == "1" and h2[l] == "0")):
            find(p+"1",q+"0")
        elif((mask1[l] == "1" and h1[l] == "1") and (mask2[l] == "0" and h2[l] == "0")):
            find(p+"1",q+"0")
            find(p+"1",q+"1")
        elif((mask1[l] == "1" and h1[l] == "0") and (mask2[l] == "1" and h2[l] == "1")):
            find(p+"0",q+"1")
        elif((mask1[l] == "1" and h1[l] == "0") and (mask2[l] == "1" and h2[l] == "0")):
            find(p+"0",q+"0")
        elif((mask1[l] == "1" and h1[l] == "0") and (mask2[l] == "0" and h2[l] == "0")):
            find(p+"0",q+"1")
            find(p+"0",q+"0")

        elif((mask1[l] == "0" and h1[l] == "0") and (mask2[l] == "1" and h2[l] == "1")):
            find(p+"0",q+"1")
            find(p+"1",q+"1")
        elif((mask1[l] == "0" and h1[l] == "0") and (mask2[l] == "1" and h2[l] == "0")):
            find(p+"0",q+"0")
            find(p+"1",q+"0")
        elif((mask1[l] == "0" and h1[l] == "0") and (mask2[l] == "0" and h2[l] == "0")):
            find(p+"0",q+"0")
            find(p+"0",q+"1")
            find(p+"1",q+"0")
            find(p+"1",q+"1")

tempp = ""
tempq = ""

#find(tempp,tempq)
P = 10172774442863868719013872884099170294615753094066736187886125116462340120031133533430755779832487215255546434139069419394249074006281284289077492708469893
Q = 8580050824978592226795441601299432164577158891190171233964440597982925469924083252289609500726234367555160732119333211934059529993446003001925910065317613
phi = (P-1)*(Q-1)
d = inverse(e,phi)
m = pow(c,d,n)
print(long_to_bytes(m))

flag:

cnss{A1g0r1thm_1s_5o_hard_for_Me!}




BabyLattice

题目描述：

1
2
Do you know SVP and LLL?
Hint:在解决本题的过程中你会接触到格(Lattice)的一些基本概念,以及LLL算法。

题目：

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 *
from secret import flag


assert len(flag) == 32
flagArg = []
for i in range(0,32,8):
    flag_tmp = bytes_to_long(flag[i:i+8])
    assert flag_tmp < 2**64
    flagArg.append(flag_tmp)

class Equation:
    def __init__(self,arg):
        assert len(arg)==4
        self.arg = arg
        self.modulus = getRandomInteger(512)
    def output(self):
        ans = 0
        print(f"the modulus is {self.modulus}")
        for i in range(4):
            tmp = getRandomInteger(512)
            print(f'The number of the {i} round is {tmp}')
            ans+=self.arg[i]*tmp
        ans = ans%self.modulus
        print(f'The result is {ans}')

EzLineModulus = Equation(flagArg)
EzLineModulus.output()

#the modulus is 4653980939589101565044285021945025573290906789132633751963110127801187748089540230208429714310516635848025358481189017398970169440484136391436220837417791
#The number of the 0 round is 7163515288721018524391838724005494502072524058809935946689587023614778895762400663698973734684519790842142248155478226513293289043832391054661263177469005
#The number of the 1 round is 13155134533945105613277690072743652931283618211062662861216511364398097684219572559463369279253337759860439150691008846033587645344197431244106331100681641
#The number of the 2 round is 8450640520436960190933104494093081291057363628588171820766164606066614201483259024304043681871965360847257453187101669512010469318096007617859083021766564
#The number of the 3 round is 798383352075970107818638521362593273862636131165588181505120596765884650403289567593307005746576184176902675297124272602141002375036927828390204063589274
#The result is 58831711102590059067743519228568722360433408071362335858674496753241059990433991177195518029785828762522018556332340356592798263267784406825183284767956

招新赛前的夏令营就出Lattice的题目了。。确实狠

不过确实是最基础的Lattice题目了，大致思路就是列出线性关系式，转化为矩阵形式，并保证较短向量都在等式右侧，即可对构造出来的格进行规约得到短向量。


exp.ipynb：

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 *

n = 4653980939589101565044285021945025573290906789132633751963110127801187748089540230208429714310516635848025358481189017398970169440484136391436220837417791
a1 = 7163515288721018524391838724005494502072524058809935946689587023614778895762400663698973734684519790842142248155478226513293289043832391054661263177469005
a2 = 13155134533945105613277690072743652931283618211062662861216511364398097684219572559463369279253337759860439150691008846033587645344197431244106331100681641
a3 = 8450640520436960190933104494093081291057363628588171820766164606066614201483259024304043681871965360847257453187101669512010469318096007617859083021766564
a4 = 798383352075970107818638521362593273862636131165588181505120596765884650403289567593307005746576184176902675297124272602141002375036927828390204063589274
ans = 58831711102590059067743519228568722360433408071362335858674496753241059990433991177195518029785828762522018556332340356592798263267784406825183284767956
inv = inverse(a1,n)
L = Matrix(ZZ, [[1, 0, 0, 0,-ans*inv],
                [0, 1, 0, 0,a2*inv],
                [0, 0, 1, 0,a3*inv],
                [0, 0, 0, 1,a4*inv],
                [0, 0, 0, 0,n]])

v = L.LLL()[0]

print(str(long_to_bytes(abs(v[4])))[2:-1],end = "")
for i in range(1,len(v)-1):
    print(str(long_to_bytes(abs(v[i])))[2:-1],end = "")

flag:

cnss{W0w!Y0u_know_WhatisL4ttice}

（有关格的问题本篇不会展开讲，因为它需要对一些基本原理的了解，想要明白此类问题需要先自行查阅一些格相关的基本概念）




ezSignature

题目描述：

1
2
3
4
5
这样使用数字签名是否安全呢？
nc 43.156.14.141 6943

Hint1:推荐使用pwntools进行交互。
Hint2:建议先了解 DSA 数字签名流程。

题目：

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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
from Crypto.Util.number import *
from hashlib import sha256
import socketserver
import signal
import string
from random import *
from secret import flag
from Crypto.PublicKey import DSA

table = string.ascii_letters + string.digits


class DigitalSignatureAlgorithm:
    def __init__(self, key):
        self.p = key.p
        self.q = key.q
        self.g = key.g
        self.y = key.y
        self.x = key.x
        self.k = randint(1, self.q - 1)

    def sign(self, m):
        k = self.k
        h = bytes_to_long(sha256(m).digest())
        r = pow(self.g, k, self.p) % self.q
        s = inverse(k, self.q) * (h + self.x * r) % self.q
        return r, s

    def verify(self, m, signature):
        r, s = signature
        if (not (1 <= r <= self.q - 1)) or (not (1 <= s <= self.q - 1)):
            return False
        z = bytes_to_long(sha256(m).digest())
        w = inverse(s, self.q)
        u1 = (z * w) % self.q
        u2 = (r * w) % self.q
        v = (pow(self.g, u1, self.p) * pow(self.y, u2, self.p)) % self.p % self.q
        return r == v


myDSA = DigitalSignatureAlgorithm(DSA.generate(1024))
MENU = br'''
[1] Sign.
[2] Verify.
[3] Get_public_key.
[4] Exit.
'''


class Task(socketserver.BaseRequestHandler):
    def _recvall(self):
        BUFF_SIZE = 2048
        data = b''
        while True:
            part = self.request.recv(BUFF_SIZE)
            data += part
            if len(part) < BUFF_SIZE:
                break
        return data.strip()

    def send(self, msg, newline=True):
        try:
            if newline:
                msg += b'\n'
            self.request.sendall(msg)
        except:
            pass

    def recv(self, prompt=b'[-] '):
        self.send(prompt, newline=False)
        return self._recvall()

    def proof_of_work(self):
        proof = (''.join([choice(table) for _ in range(12)])).encode()
        sha = sha256(proof).hexdigest().encode()
        self.send(b"[+] sha256(XXXX+" + proof[4:] + b") == " + sha)
        XXXX = self.recv(prompt=b'[+] Plz Tell Me XXXX :')
        if len(XXXX) != 4 or sha256(XXXX + proof[4:]).hexdigest().encode() != sha:
            return False
        return True

    def sign(self):
        m1 = b'I want to tell you a secret'
        m2 = b'Can you find it?'
        signature1 = myDSA.sign(m1)
        signature2 = myDSA.sign(m2)
        self.send(b'Your signature1 is:' + str(signature1).encode())
        self.send(b'Your signature2 is:' + str(signature2).encode())

    def verify(self):
        m = self.recv(b'message:')
        r = int(self.recv(b'r:'))
        s = int(self.recv(b's:'))
        signature = (r, s)
        if m == b"I'm Admin.I want flag.":
            if myDSA.verify(m, signature):
                self.send(b'Hello there.This is what you want.')
                self.send(flag)
            else:
                self.send(b'Who are U?Get out!')
                return False
        else:
            self.send(b'Who are U?Get out!')

    def get_public_key(self):
        self.send(b'p = ' + str(myDSA.p).encode())
        self.send(b'q = ' + str(myDSA.q).encode())
        self.send(b'g = ' + str(myDSA.g).encode())
        self.send(b'y = ' + str(myDSA.y).encode())


    def handle(self):
        signal.alarm(30)
        if not self.proof_of_work():
            self.send(b'You must pass the P0W!!!')
            self.request.close()
        while 1:
            self.send(MENU)
            option = int(self.recv(prompt=b'Give me your option:'))
            if option == 1:
                self.sign()
            elif option == 2:
                self.verify()
                break
            elif option == 3:
                self.get_public_key()
            else:
                break
        self.request.close()


class ThreadedServer(socketserver.ThreadingMixIn, socketserver.TCPServer):
    pass


if __name__ == "__main__":
    HOST, PORT = '0.0.0.0', 10001

    print("HOST:POST " + HOST + ":" + str(PORT))
    server = ThreadedServer((HOST, PORT), Task)
    server.allow_reuse_address = True
    server.serve_forever()

一道靶机交互题，代码较长，但是其实大部分是交互相关的函数，细读发现是很正常的DSA，需要用给定明文通过他的验签操作。（如果不熟悉DSA签名流程，一定要自行查阅了解一下）

检查代码发现漏洞出在sign，由于交互开始时，随机密钥k就不会再变动，因此两个明文共用了k用作签名，因此直接使用共享k攻击即可，具体原理也很简单，自行搜索共享k攻击即可。进阶的还有对线性k、指数k等相关攻击方式。

exp.py：

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 *
from hashlib import sha256

p = 172961942888113119438093761564402163853274437530074061334853565231663662473345365517029153614577994838261528197758562341350007269014020447862968046418219322983982857376325091297503076457294884011022491521807290579653731078712552375942815577480924479760060089879761373677236785972440188569442167867715538948131
q = 1238294525750070611176801188652181858159488474961
g = 75657702601417227921344829575623735976532473731371029415534443940309702116075857552168402559956825576158353466597825895213717785384352099702983338787137184850387592826820271959589796127014544636714131043162304391677607332131259874984936943058742638800688694139378157588974460944304847089533750902878536046649
y = 7749296960818920297640684628219596188301310658741359444363507697372166821952159177715756651776536866582220227892407461198512231438360662343916445812054004711764127526569139925464723782772657462476688091598602960531766048824996984183046388253897618420503521674510979988799110962834514762035965219607971731464

r1,s1 = (952312130113235199710494038379463278196320139331, 246708316787437486170638565016913560785356026546)
r2,s2 = (952312130113235199710494038379463278196320139331, 604408984593559575502554675534691666132540008638)

m1 = b'I want to tell you a secret'
m2 = b'Can you find it?'
h1 = bytes_to_long(sha256(m1).digest())
h2 = bytes_to_long(sha256(m2).digest())

k = (h1-h2)*inverse(s1-s2,q)
x = (k*s1 - h1)*inverse(r1,q) % q

m = b"I'm Admin.I want flag."
h = bytes_to_long(sha256(m).digest())
r = pow(g, k, p) % q
s = inverse(k, q) * (h + x * r) % q
print(r)
print(s)

(这题没有完整脚本，拿着这个r，s去交互就可以了；因为比较懒，当时直接用xshell连接上后手动过的sha256爆破，手动提交的r，s。。所以就没有完整pwntools交互脚本)

flag:

cnss{1ts_Dr4nger0us_t0_u5eThe_Same_K}




StrangeCurve

题目描述：

1
The Cruve is SOO0000 Strange!

题目：

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

assert flag[:5]=='cnss{' and flag[-1] == '}'

flag_k = bytes_to_long(flag[5:-1].encode())

p = 1096126227998177188652856107362412783873814431647
a = 0
b = 5
E = EllipticCurve(GF(p), [a, b])

assert E.order() == p 
base_point = E(626099523290649705896889901241128842906228328604,886038875771695334071307095455656761758842526929)

assert base_point in E
assert flag_k < p 

Q = flag_k*base_point
print(Q)

# (240653647745552223089451307742208085297121769374 : 1041806436100548540817642210994295951394712587396 : 1)

椭圆曲线加密，下面这行是重要信息：

1
assert E.order() == p

因此可以确定是Smart’s attack。


exp.ipynb：

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

def SmartAttack(P,Q,p):
    E = P.curve()
    Eqp = EllipticCurve(Qp(p, 2), [ ZZ(t) + randint(0,p)*p for t in E.a_invariants() ])

    P_Qps = Eqp.lift_x(ZZ(P.xy()[0]), all=True)
    for P_Qp in P_Qps:
        if GF(p)(P_Qp.xy()[1]) == P.xy()[1]:
            break

    Q_Qps = Eqp.lift_x(ZZ(Q.xy()[0]), all=True)
    for Q_Qp in Q_Qps:
        if GF(p)(Q_Qp.xy()[1]) == Q.xy()[1]:
            break

    p_times_P = p*P_Qp
    p_times_Q = p*Q_Qp

    x_P,y_P = p_times_P.xy()
    x_Q,y_Q = p_times_Q.xy()

    phi_P = -(x_P/y_P)
    phi_Q = -(x_Q/y_Q)
    k = phi_Q/phi_P
    return ZZ(k)


p = 1096126227998177188652856107362412783873814431647
a = 0
b = 5
E = EllipticCurve(GF(p), [a, b])

P = E(626099523290649705896889901241128842906228328604,886038875771695334071307095455656761758842526929)
Q = E(240653647745552223089451307742208085297121769374,1041806436100548540817642210994295951394712587396)

n = SmartAttack(P, Q, p)
print("cnss{" + str(long_to_bytes(n))[2:-1] + "}")

flag:

cnss{DLPise45y_if5pecia1}




一🔪一个牛头人

题目描述：

1
学了NTRU,就要NTR u(❌)

题目：

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
from random import shuffle, getrandbits
from secret import flag
from Crypto.Util.number import *
Zx = PolynomialRing(ZZ, 'x')
x = Zx.gen()


def convolution(f, g, R):
    return (f * g) % R


def balancedmod(f, q, R):
    g = list(map(lambda x: ((x + q//2) % q) - q//2, f.list()))
    return Zx(g) % R


def random_poly(n, d1, d2):
    assert d1 + d2 <= n
    result = d1 * [1] + d2 * [-1] + (n - d1 - d2) * [0]
    shuffle(result)
    return Zx(result)


def invert_poly_mod_prime(f, R, p):
    T = Zx.change_ring(Integers(p)).quotient(R)
    return Zx(lift(1 / T(f)))


def invert_poly_mod_powerof2(f, R, q):  # Hensel Lemma 
    g = invert_poly_mod_prime(f, R, 2)
    e = log(q, 2)
    for i in range(1, e):
        g = ((2 * g - f * g ** 2) % R) % q
    return g


class NTRUCipher:
    def __init__(self, N, p, q, d):
        self.N = N
        self.p = p
        self.q = q
        self.d = d
        self.R = x ** N - 1
        # key generation
        self.g = random_poly(self.N, d, d)
        
        while True:
            try:
                self.f = random_poly(self.N, d + 1, d)
                self.fp = invert_poly_mod_prime(self.f, self.R, self.p)
                self.fq = invert_poly_mod_powerof2(self.f, self.R, self.q)
                break
            except:
                pass

        self.h = balancedmod(self.p * convolution(self.fq, self.g, self.R), self.q, self.R)
    def getPubKey(self):
        return self.h
    def encrypt(self, m):
        r = random_poly(self.N, self.d, self.d)
        return balancedmod(convolution(self.h, r, self.R) + m, self.q, self.R)

    def decrypt(self, c):
        a = balancedmod(convolution(c, self.f, self.R), self.q, self.R)
        return balancedmod(convolution(a, self.fp, self.R), self.p, self.R)

    def encode(self, val):
        poly = 0
        for i in range(self.N):
            poly += ((val % self.p) - self.p // 2) * (x ** i)
            val //= self.p
        return poly

    def decode(self, poly):
        result = 0
        ll = poly.list()
        for idx, val in enumerate(ll):
            result += (val + self.p // 2) * (self.p ** idx)
        return result

    def poly_from_list(self, l: list):
        return Zx(l)


if __name__ == '__main__':
    N = 160
    d = 30
    p = 3
    q = 65536

    cipher = NTRUCipher(N, p, q, d) 
    print("[PubKey]---------")
    h = cipher.getPubKey()
    print(f'h = {h}')
    msg = bytes_to_long(flag)
    encode_msg = cipher.encode(msg)
    c = cipher.encrypt(encode_msg)
    print("[Cipher]---------")
    print(f'c = {c}')
    mm = cipher.decrypt(c)
    decode_msg = cipher.decode(mm)
    assert decode_msg == msg
    
    
'''
[PubKey]---------
h = -11891*x^159 + 16347*x^158 - 32137*x^157 + 14988*x^156 + 16657*x^155 - 25785*x^154 - 21976*x^153 - 31745*x^152 - 4232*x^151 + 29569*x^150 + 27140*x^149 + 19617*x^148 - 16656*x^147 + 8925*x^146 + 8728*x^145 - 8802*x^144 - 10794*x^143 - 28159*x^142 - 6454*x^141 - 10259*x^140 - 19169*x^139 - 14357*x^138 + 3501*x^137 + 9885*x^136 - 7441*x^135 + 18268*x^134 - 27183*x^133 + 26085*x^132 + 19147*x^131 + 17153*x^130 - 22887*x^129 + 32476*x^128 - 21698*x^127 + 19138*x^126 + 11585*x^125 + 22755*x^124 - 5920*x^123 + 7581*x^122 + 25973*x^121 + 13787*x^120 - 22762*x^119 + 29207*x^118 - 17916*x^117 - 11502*x^116 + 18275*x^115 + 318*x^114 - 6890*x^113 - 22751*x^112 - 27677*x^111 - 11114*x^110 + 8623*x^109 - 15725*x^108 - 6835*x^107 - 8288*x^106 - 5235*x^105 - 28697*x^104 + 10696*x^103 + 17117*x^102 + 24696*x^101 - 7801*x^100 - 31874*x^99 - 17668*x^98 - 11204*x^97 + 19147*x^96 + 24644*x^95 - 29380*x^94 - 26237*x^93 - 27390*x^92 + 19982*x^91 + 4074*x^90 - 17248*x^89 - 11027*x^88 - 32690*x^87 + 5124*x^86 - 20823*x^85 - 11779*x^84 + 13781*x^83 + 29356*x^82 - 9740*x^81 - 31484*x^80 - 540*x^79 + 32360*x^78 + 24795*x^77 - 8864*x^76 + 17363*x^75 + 9670*x^74 + 32268*x^73 + 17961*x^72 + 6388*x^71 + 580*x^70 + 128*x^69 + 339*x^68 + 3412*x^67 - 4519*x^66 - 25056*x^65 + 6096*x^64 + 18720*x^63 - 5338*x^62 + 16910*x^61 + 3353*x^60 + 15433*x^59 - 28053*x^58 - 18883*x^57 + 7688*x^56 - 31198*x^55 + 9950*x^54 - 9388*x^53 + 21235*x^52 + 2847*x^51 + 24383*x^50 + 19431*x^49 + 21244*x^48 - 8498*x^47 - 28998*x^46 + 962*x^45 + 20579*x^44 + 28002*x^43 - 6040*x^42 + 4241*x^41 + 11655*x^40 - 32419*x^39 + 21531*x^38 + 7348*x^37 - 5503*x^36 + 29820*x^35 + 28896*x^34 + 8754*x^33 + 17978*x^32 + 7552*x^31 + 27240*x^30 - 29515*x^29 - 20322*x^28 + 2201*x^27 + 8857*x^26 - 50*x^25 - 3780*x^24 - 12138*x^23 + 10893*x^22 + 23133*x^21 + 6142*x^20 - 23798*x^19 - 15236*x^18 + 32564*x^17 + 25683*x^16 - 24010*x^15 - 4355*x^14 + 22552*x^13 - 27155*x^12 + 27649*x^11 + 17781*x^10 + 7115*x^9 + 27465*x^8 - 4369*x^7 + 24882*x^6 - 11675*x^5 - 612*x^4 + 12361*x^3 + 20120*x^2 + 6190*x - 10843
[Cipher]---------
c = -26801*x^159 - 25103*x^158 + 29811*x^157 - 12251*x^156 - 13386*x^155 - 28030*x^154 - 16511*x^153 + 23761*x^152 + 28329*x^151 - 16406*x^150 + 30931*x^149 + 5326*x^148 + 19877*x^147 - 23165*x^146 - 31540*x^145 - 7923*x^144 + 5880*x^143 - 27078*x^142 - 25436*x^141 - 17162*x^140 + 1471*x^139 + 14486*x^138 + 7702*x^137 - 29890*x^136 + 29315*x^135 + 558*x^134 - 22429*x^133 - 361*x^132 + 19049*x^131 - 30437*x^130 - 32610*x^129 - 3024*x^128 - 4313*x^127 + 29174*x^126 - 2837*x^125 - 2812*x^124 + 13450*x^123 - 15001*x^122 - 25791*x^121 - 8702*x^120 - 4968*x^119 - 15340*x^118 + 31744*x^117 - 32478*x^116 + 19737*x^115 - 12629*x^114 - 27847*x^113 + 27322*x^112 - 31375*x^111 + 14777*x^110 + 29825*x^109 - 25883*x^108 - 13335*x^107 + 32517*x^106 + 14871*x^105 - 7287*x^104 + 13398*x^103 - 32710*x^102 + 20805*x^101 + 29734*x^100 - 14579*x^99 + 17483*x^98 - 16864*x^97 - 26745*x^96 + 3254*x^95 + 7280*x^94 - 29046*x^93 - 7531*x^92 - 8791*x^91 + 15033*x^90 - 1125*x^89 - 14713*x^88 - 12273*x^87 + 8616*x^86 + 2486*x^85 + 31810*x^84 + 27795*x^83 - 21731*x^82 + 21743*x^81 - 27595*x^80 - 3592*x^79 - 27206*x^78 - 32156*x^77 + 32124*x^76 - 11212*x^75 - 6662*x^74 - 23103*x^73 - 3660*x^72 - 31043*x^71 - 17131*x^70 + 24544*x^69 - 32326*x^68 - 31047*x^67 + 19814*x^66 + 10874*x^65 - 8449*x^64 + 11744*x^63 + 2245*x^62 - 967*x^61 + 9120*x^60 + 8983*x^59 - 24573*x^58 + 24885*x^57 + 15649*x^56 - 18970*x^55 + 7354*x^54 - 12282*x^53 - 22474*x^52 + 4395*x^51 + 8428*x^50 - 32592*x^49 + 25980*x^48 - 4599*x^47 + 16310*x^46 + 18559*x^45 + 22897*x^44 + 19080*x^43 - 26065*x^42 - 9*x^41 + 29202*x^40 + 2121*x^39 - 5004*x^38 + 5299*x^37 - 28301*x^36 - 13519*x^35 + 24241*x^34 + 529*x^33 - 20574*x^32 - 27391*x^31 + 31976*x^30 + 22824*x^29 - 31410*x^28 - 20976*x^27 + 21661*x^26 - 15132*x^25 + 1905*x^24 - 30870*x^23 + 18109*x^22 - 17373*x^21 + 5342*x^20 - 22447*x^19 + 1893*x^18 - 17545*x^17 + 30097*x^16 - 21731*x^15 + 17390*x^14 + 10991*x^13 - 5384*x^12 + 15960*x^11 + 24268*x^10 - 29867*x^9 + 22532*x^8 + 10133*x^7 - 26576*x^6 - 5742*x^5 - 16252*x^4 + 13019*x^3 - 25984*x^2 + 14004*x + 22500

'''

一个普通的NTRU多项式密码，也是与格有关的，其具体原理可以参考：(甚至详细阐述了每个函数的作用)

Translation of LatticeHacks · K1rit0’s Blog


exp.ipynb：

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 *

n = 160
d = 30
p = 3
q = 65536
PR = PolynomialRing(ZZ, name = 'x')
x = PR.gen()
R = PR.quotient_ring(x ^ n - 1, names = 'y')
y = R.gen()

pubkey = -11891*x^159 + 16347*x^158 - 32137*x^157 + 14988*x^156 + 16657*x^155 - 25785*x^154 - 21976*x^153 - 31745*x^152 - 4232*x^151 + 29569*x^150 + 27140*x^149 + 19617*x^148 - 16656*x^147 + 8925*x^146 + 8728*x^145 - 8802*x^144 - 10794*x^143 - 28159*x^142 - 6454*x^141 - 10259*x^140 - 19169*x^139 - 14357*x^138 + 3501*x^137 + 9885*x^136 - 7441*x^135 + 18268*x^134 - 27183*x^133 + 26085*x^132 + 19147*x^131 + 17153*x^130 - 22887*x^129 + 32476*x^128 - 21698*x^127 + 19138*x^126 + 11585*x^125 + 22755*x^124 - 5920*x^123 + 7581*x^122 + 25973*x^121 + 13787*x^120 - 22762*x^119 + 29207*x^118 - 17916*x^117 - 11502*x^116 + 18275*x^115 + 318*x^114 - 6890*x^113 - 22751*x^112 - 27677*x^111 - 11114*x^110 + 8623*x^109 - 15725*x^108 - 6835*x^107 - 8288*x^106 - 5235*x^105 - 28697*x^104 + 10696*x^103 + 17117*x^102 + 24696*x^101 - 7801*x^100 - 31874*x^99 - 17668*x^98 - 11204*x^97 + 19147*x^96 + 24644*x^95 - 29380*x^94 - 26237*x^93 - 27390*x^92 + 19982*x^91 + 4074*x^90 - 17248*x^89 - 11027*x^88 - 32690*x^87 + 5124*x^86 - 20823*x^85 - 11779*x^84 + 13781*x^83 + 29356*x^82 - 9740*x^81 - 31484*x^80 - 540*x^79 + 32360*x^78 + 24795*x^77 - 8864*x^76 + 17363*x^75 + 9670*x^74 + 32268*x^73 + 17961*x^72 + 6388*x^71 + 580*x^70 + 128*x^69 + 339*x^68 + 3412*x^67 - 4519*x^66 - 25056*x^65 + 6096*x^64 + 18720*x^63 - 5338*x^62 + 16910*x^61 + 3353*x^60 + 15433*x^59 - 28053*x^58 - 18883*x^57 + 7688*x^56 - 31198*x^55 + 9950*x^54 - 9388*x^53 + 21235*x^52 + 2847*x^51 + 24383*x^50 + 19431*x^49 + 21244*x^48 - 8498*x^47 - 28998*x^46 + 962*x^45 + 20579*x^44 + 28002*x^43 - 6040*x^42 + 4241*x^41 + 11655*x^40 - 32419*x^39 + 21531*x^38 + 7348*x^37 - 5503*x^36 + 29820*x^35 + 28896*x^34 + 8754*x^33 + 17978*x^32 + 7552*x^31 + 27240*x^30 - 29515*x^29 - 20322*x^28 + 2201*x^27 + 8857*x^26 - 50*x^25 - 3780*x^24 - 12138*x^23 + 10893*x^22 + 23133*x^21 + 6142*x^20 - 23798*x^19 - 15236*x^18 + 32564*x^17 + 25683*x^16 - 24010*x^15 - 4355*x^14 + 22552*x^13 - 27155*x^12 + 27649*x^11 + 17781*x^10 + 7115*x^9 + 27465*x^8 - 4369*x^7 + 24882*x^6 - 11675*x^5 - 612*x^4 + 12361*x^3 + 20120*x^2 + 6190*x - 10843
pubkey = R(pubkey)
c = -26801*x^159 - 25103*x^158 + 29811*x^157 - 12251*x^156 - 13386*x^155 - 28030*x^154 - 16511*x^153 + 23761*x^152 + 28329*x^151 - 16406*x^150 + 30931*x^149 + 5326*x^148 + 19877*x^147 - 23165*x^146 - 31540*x^145 - 7923*x^144 + 5880*x^143 - 27078*x^142 - 25436*x^141 - 17162*x^140 + 1471*x^139 + 14486*x^138 + 7702*x^137 - 29890*x^136 + 29315*x^135 + 558*x^134 - 22429*x^133 - 361*x^132 + 19049*x^131 - 30437*x^130 - 32610*x^129 - 3024*x^128 - 4313*x^127 + 29174*x^126 - 2837*x^125 - 2812*x^124 + 13450*x^123 - 15001*x^122 - 25791*x^121 - 8702*x^120 - 4968*x^119 - 15340*x^118 + 31744*x^117 - 32478*x^116 + 19737*x^115 - 12629*x^114 - 27847*x^113 + 27322*x^112 - 31375*x^111 + 14777*x^110 + 29825*x^109 - 25883*x^108 - 13335*x^107 + 32517*x^106 + 14871*x^105 - 7287*x^104 + 13398*x^103 - 32710*x^102 + 20805*x^101 + 29734*x^100 - 14579*x^99 + 17483*x^98 - 16864*x^97 - 26745*x^96 + 3254*x^95 + 7280*x^94 - 29046*x^93 - 7531*x^92 - 8791*x^91 + 15033*x^90 - 1125*x^89 - 14713*x^88 - 12273*x^87 + 8616*x^86 + 2486*x^85 + 31810*x^84 + 27795*x^83 - 21731*x^82 + 21743*x^81 - 27595*x^80 - 3592*x^79 - 27206*x^78 - 32156*x^77 + 32124*x^76 - 11212*x^75 - 6662*x^74 - 23103*x^73 - 3660*x^72 - 31043*x^71 - 17131*x^70 + 24544*x^69 - 32326*x^68 - 31047*x^67 + 19814*x^66 + 10874*x^65 - 8449*x^64 + 11744*x^63 + 2245*x^62 - 967*x^61 + 9120*x^60 + 8983*x^59 - 24573*x^58 + 24885*x^57 + 15649*x^56 - 18970*x^55 + 7354*x^54 - 12282*x^53 - 22474*x^52 + 4395*x^51 + 8428*x^50 - 32592*x^49 + 25980*x^48 - 4599*x^47 + 16310*x^46 + 18559*x^45 + 22897*x^44 + 19080*x^43 - 26065*x^42 - 9*x^41 + 29202*x^40 + 2121*x^39 - 5004*x^38 + 5299*x^37 - 28301*x^36 - 13519*x^35 + 24241*x^34 + 529*x^33 - 20574*x^32 - 27391*x^31 + 31976*x^30 + 22824*x^29 - 31410*x^28 - 20976*x^27 + 21661*x^26 - 15132*x^25 + 1905*x^24 - 30870*x^23 + 18109*x^22 - 17373*x^21 + 5342*x^20 - 22447*x^19 + 1893*x^18 - 17545*x^17 + 30097*x^16 - 21731*x^15 + 17390*x^14 + 10991*x^13 - 5384*x^12 + 15960*x^11 + 24268*x^10 - 29867*x^9 + 22532*x^8 + 10133*x^7 - 26576*x^6 - 5742*x^5 - 16252*x^4 + 13019*x^3 - 25984*x^2 + 14004*x + 22500
c = R(c)

def balance_mod(f, q):
    g = list(((f[i] + q // 2) % q) - q // 2 for i in range(n))
    return R(g)

def invert_mod_prime(f, p):
    T = R.base().change_ring(Integers(p)).quotient(x ^ n - 1)
    return R(1 / T(f))

def dec(c, prikey):
    f, fp = prikey
    a = balance_mod(c * f, q)
    return balance_mod(a * fp, p)

def crack(pubkey, c):
    A = Matrix(ZZ, 2 * n, 2 * n)
    hp = inverse(p, q) * pubkey
    hp_list = list(hp)
    for i in range(n):
        A[i, i] = q
    for i in range(n, 2 * n):
        for j in range(n):
            A[i, j] = hp_list[(j - i) % n]
        A[i, i] = 1
    AL = A.BKZ()
    for row in AL:
        try:
            f = R(row[n:].list())
            fp = invert_mod_prime(f, p)
            return dec(c, (f, fp))
            break # may failed with shortest vector(return more if failed)
        except:
            pass
        
m = crack(pubkey, c)

m = m.list()
for i in range(len(m)):
    m[i] += 1
    m[i] = str(m[i])
str1 = "".join(m[::-1])
temp = int(str1,3)
print(long_to_bytes(temp))

(可能需要跑几分钟)

flag:

cnss{NTRU_w1th_un5afe_par4}




MidLattice

题目描述：

1
看上去像gcd，但是有区别

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import hashlib
from Crypto.Util.number import *
pbit = 500
qbit = 550
rbit = 200
def get_sample():
    x_list  = []
    p = getPrime(pbit)
    for i in range(120):
        q = getPrime(qbit)
        r = getPrime(rbit)
        x_list.append(q*p + 2*r)
    return x_list,p
sample,p = get_sample()
flag = 'cnss{'+hashlib.sha256(long_to_bytes(p)).hexdigest()+'}'
with open("output.txt", "w") as file:
    file.write(str(sample))

以及一个output.txt

题目描述的很明确了，agcd问题(近似公约数问题)，也与格相关，不进行展开。


exp.ipynb：

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
from itertools import permutations
import hashlib

P_bits = 500
Q_bits = 550
R_bits = 200
e = 0x1337
N = #自行代入
X = 2**R_bits
m = len(N)

PR = PolynomialRing(ZZ, names=[str('x%d' % i) for i in range(1, 1 + m)])

h = 3
u = 1
variables = PR.gens()

gg = []
monomials = [variables[0]**0]
for i in range(m):
    gg.append(N[i] - variables[i])
    monomials.append(variables[i])

print(len(monomials), len(gg))
print('monomials:', monomials)

B = Matrix(ZZ, len(gg), len(monomials))
for ii in range(len(gg)):
    for jj in range(len(monomials)):
        if monomials[jj] in gg[ii].monomials():
            B[ii, jj] = gg[ii].monomial_coefficient(monomials[jj]) * monomials[jj]([X] * m)

B = B.LLL()
print('-' * 32)

new_pol = []
for i in range(len(gg)):
    tmp_pol = 0
    for j in range(len(monomials)):
        tmp_pol += monomials[j](variables) * B[i, j] / monomials[j]([X] * m)
    new_pol.append(tmp_pol)

if len(new_pol) > 0:
    Ideal = ideal(new_pol[:m-1])
    GB = Ideal.groebner_basis()
    function_variables = var([str('y%d' % i) for i in range(1, 1 + m)])
    res = solve([pol(function_variables) for pol in GB], function_variables)

    print('got %d basis' % len(GB))
    print('solved result:')
    print(res)
    PRRR.< x, y> = PolynomialRing(QQ)
    q = abs(PRRR(res[0][0](x, y)).coefficients()[0].denominator())
    p = N[-1] // q

    flag = 'cnss{'+hashlib.sha256(long_to_bytes(p)).hexdigest()+'}'
    print(flag)

也需要跑几分钟才出结果，能更精确地调整参数的话可能可以减少耗时。

flag:

cnss{dde0cc3ac3539c66a74ed445a81c3f5b12938c286fa569a3b143b72369c708c9}




铜匠的世界

题目描述：

1
怎样在2^512个可能中找到唯一的答案呢？

题目：

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 math import isqrt
from secret import flag


m = bytes_to_long(flag)
p, q = getPrime(512), getPrime(512)
n = p * q
e = 65537
c = pow(m, e, n)
hint = isqrt(p) ^ isqrt(q)

print(f'{n = }')
print(f'{c = }')
print(f'{hint = }')


'''
n = 85404423344841677974087657659736161235661371072424467828040714876602706438511794670195915251038316685200550396898521246532238184171610202260808362573973358649489859739377219665083353960986881177279315590581777896976153899765953910931555330824054172366095461986394627542626117519624886018101305667394230690241
c = 19771222413844352631385715488753476758377273736688852768996964594019231638669697870409256892886494956719082541038530128231778575768552216334354854019126139003782852207071549956953446472517410158388833668611141062328959917017080292879996106665465487753670322759387144032463518586362415629216383494479440197516
hint = 34903932064178830653499046348212332783401351910283782992020948402621276719605
'''

如果给的是p^q，题目是容易的，只需要按照RSA Ⅱ类似的思路进行深搜即可。而给的是isqrt(p) ^ isqrt(q)，很容易会有思路如下：

  • 对n开根，得到isqrt(p*q)
  • 将isqrt(p*q) 看作n，将isqrt(p) ^ isqrt(q)看作p^q，转化成上面给定p^q的问题求解

看上去没什么问题，可是实际操作就会发现存在两点问题：

  • 由于一些低位误差，有一些可能正确的根号p、q高位被舍弃。
  • 即使得到了正确的isqrt(p)与isqrt(q)，各自平方后与真正的p、q还有至少256比特的差距，即使是用coppersmith也完全满足不了使用条件。

因此不能再使用RSA Ⅱ中的返回条件进行按位查找了。此时搜索题目，发现了佬的类似的题目思路：

https://blog.maple3142.net/2023/06/12/seetf-2023-writeups/#shard

这样子查找成功后，还需要对低位进行一定程度的爆破后才能使用coppersmith，并且参数要卡的比较死，比如epsilon取0.03虽然快一些，但是跑不出结果，因此只能取0.01甚至更小，但这个就会耗费很长时间。遗憾的是我也没有想出更好的办法。


exp_step1.ipynb：(求出可能的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
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 getPrime
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
from secrets import randbelow
from hashlib import sha256
from gmpy2 import iroot
import os
from re import findall
from subprocess import check_output
from binteger import Bin
import time


def small_roots(self, X=None, beta=1.0, epsilon=None, **kwds):
    from sage.misc.verbose import verbose
    from sage.matrix.constructor import Matrix
    from sage.rings.real_mpfr import RR

    N = self.parent().characteristic()

    if not self.is_monic():
        raise ArithmeticError("Polynomial must be monic.")

    beta = RR(beta)
    if beta <= 0.0 or beta > 1.0:
        raise ValueError("0.0 < beta <= 1.0 not satisfied.")

    f = self.change_ring(ZZ)

    P, (x,) = f.parent().objgens()

    delta = f.degree()

    if epsilon is None:
        epsilon = beta / 8
    verbose("epsilon = %f" % epsilon, level=2)

    m = max(beta**2 / (delta * epsilon), 7 * beta / delta).ceil()
    verbose("m = %d" % m, level=2)

    t = int((delta * m * (1 / beta - 1)).floor())
    verbose("t = %d" % t, level=2)

    if X is None:
        X = (0.5 * N ** (beta**2 / delta - epsilon)).ceil()
    verbose("X = %s" % X, level=2)

    # we could do this much faster, but this is a cheap step
    # compared to LLL
    g = [x**j * N ** (m - i) * f**i for i in range(m) for j in range(delta)]
    g.extend([x**i * f**m for i in range(t)])  # h

    B = Matrix(ZZ, len(g), delta * m + max(delta, t))
    for i in range(B.nrows()):
        for j in range(g[i].degree() + 1):
            B[i, j] = g[i][j] * X**j

    f = sum([ZZ(B[0, i] // X**i) * x**i for i in range(B.ncols())])
    R = f.roots()

    ZmodN = self.base_ring()
    roots = set([ZmodN(r) for r, m in R if abs(r) <= X])
    Nbeta = N**beta
    return [root for root in roots if N.gcd(ZZ(self(root))) >= Nbeta]


pq = 85404423344841677974087657659736161235661371072424467828040714876602706438511794670195915251038316685200550396898521246532238184171610202260808362573973358649489859739377219665083353960986881177279315590581777896976153899765953910931555330824054172366095461986394627542626117519624886018101305667394230690241
c = 19771222413844352631385715488753476758377273736688852768996964594019231638669697870409256892886494956719082541038530128231778575768552216334354854019126139003782852207071549956953446472517410158388833668611141062328959917017080292879996106665465487753670322759387144032463518586362415629216383494479440197516
hint = 34903932064178830653499046348212332783401351910283782992020948402621276719605


def dfs(spv, i):
    if i >= 256:
        yield Bin(spv, 256), Bin(Bin(spv).int ^^ hint, 256)
    if i >= 256:
        return
    for b in (1, 0):
        spv[i] = b
        tsp = Bin(spv).int
        tsq = tsp ^^ hint
        p = tsp**2
        q = tsq**2
        if 0 <= (pq - p * q) <= 2 ** (1024 - i + 1) and 0 <= (
            iroot(pq,2)[0] - tsp * tsq
        ) <= 2 ** (512 - i + 1):
            yield from dfs(spv[:], i + 1)


spv = [0] * 256
results = []
for spc, sqc in dfs(spv, 0):
    d = pq - spc.int**2 * sqc.int**2
    results.append((d, spc.int, sqc.int))
for i, (_, spci, sqci) in enumerate(sorted(results)):
    1
    #print((spci - (iroot(pq,2)[0] // sqci)).bit_length())
print(results)

def copp_factor(sp, leak=5):
    for tb in range(1 << leak):
        #print("copp", tb, int(time.time()))
        shift = 256 - leak + 1
        P = Zmod(pq)["x"]
        x = P.gen()
        f = sp.int**2 + (x << shift) + 2*tb + 1
        f = f.monic()
        X = 2 ** (256 - leak - 1)
        beta = 0.499
        eps = 0.01
        rs = f.small_roots(X=X, beta=beta, epsilon=eps)
        #rs = small_roots(f, X=X, beta=beta, epsilon=eps)
        if len(rs):
            print(sp.int**2 + (tb << shift) + int(rs[0]))


for i, (_, spci, _) in enumerate(sorted(results)):
    copp_factor(Bin(spci, 256))

将运行结果填充至下面脚本中的sqrtplist中


exp_step2.ipynb：

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
from Crypto.Util.number import *
from gmpy2 import iroot
import hashlib
import itertools
#coppersmith
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 = 85404423344841677974087657659736161235661371072424467828040714876602706438511794670195915251038316685200550396898521246532238184171610202260808362573973358649489859739377219665083353960986881177279315590581777896976153899765953910931555330824054172366095461986394627542626117519624886018101305667394230690241
c = 19771222413844352631385715488753476758377273736688852768996964594019231638669697870409256892886494956719082541038530128231778575768552216334354854019126139003782852207071549956953446472517410158388833668611141062328959917017080292879996106665465487753670322759387144032463518586362415629216383494479440197516

sqrtplist = #自行代入

leak = 6
count = 0
for i in range(len(sqrtplist)):
    print(i)
    sp = sqrtplist[i][1]
    for tb in range(1 << leak):
        #print("copp", tb, int(time.time()))
        shift = 256 - leak
        PR.<x> = PolynomialRing(Zmod(N))
        f = sp**2 + (tb << shift) + x
        f = f.monic()
        X = 2 ** (256 - leak)
        beta = 0.499
        eps = 0.01
        res = f.small_roots(X=X, beta=beta, epsilon=eps)
        if(res!=[]):
            print(res)
            print(sp**2 + (tb << shift) + res[0])

p = 6756521617869105417915102754795944450583448652752246233837766079298009351893501307888859133738834804209006551446537605217981998432259279870915861077557549
q = N//p
e = 65537
phi = (p-1)*(q-1)
d = inverse(e,phi)
m = pow(c,d,N)
print(long_to_bytes(m))

跑出结果可能需要6个小时到10个小时不等。如果你有更好的方式欢迎在评论区留言！

flag:

cnss{We hav3 n0 0ther ch0ice but c0ppersm1th.}




总结

题目质量确实很不错，每道题目考察的知识点很有针对性，准备好好借鉴参考(开偷)。