春秋杯WP｜2023春秋杯春季赛之crypto篇

WriteUp 1年前 (2023) admin

513 0 0

作者：rec

简介：东南大学SUS战队成员，联合战队r3kapig成员，联合战队N0wayBack成员。因为太怕痛所以技能点全点密码学了（其实是因为不会其他的方向）

crypyo篇

checkin

from Crypto.Util.number import *
from secret import flag, x, y

def keygen(nbit):
p, q = [getPrime(nbit) for _ in range(2)]
return (p, q)

p, q = keygen(1024)
n = p * q

t = len(flag)//2
part1 = bytes_to_long(flag[:t])
part2 = bytes_to_long(flag[t:])

D = 1117
x =
y =
assert x**2 - D * y**2 == 1

enc1 = pow(233 * n ** 2 + 1, part1, n ** 3)
enc2 = pow(y * n + 1, part2, n ** 3)

print(f'n = {n}')
print(f'enc1 = {enc1}')
print(f'enc2 = {enc2}')

'''
n = 14381700422128582509148801752355744589949207890477326887251636389639477554903212313766087310581920423926674144511237847467160303159477932732842314969782540035709454603184976310835433114879043016737665256729350745769071186849072915716081380191025215059636548339167264601163525017898164466972776553148697204889820118261937316228241099344357088387154112255824092894798716597134811437852876763391697588672779069166285303075312833415574850549277205130215394422655325352478386576833373623679069271857652029364332047485797407322257853316210866532938722911480593571175419708834718860211036796987231227104370259051299799633809
enc1 = 7213976567554002619445032200800186986758840297933991288547009708561953107405266725278346810536664670987171549114913443730366439254199110599202411546254632702440251000149674899033994570393935743323319736976929843596350656674709510612789987746895513057821629144725499933366382123251520676386059405796801097683107223771674383940907066300331503757142088898427893069444164604408189686282018392714450005250018004986102062209998463347007934222341910941474212611569508001910685822097788669516018081617394144015000387497289693096617795809933540456797387940627782045397249431573540932386564021712811633992948508497879189416719996092292320828635490820907122756459412206735413770335545012892724496210585503157766011075566023635046144730429791359690237088629187946232458937292767085665897489251315749496284368726255508362410603108788759785472319449267909859926786774679533591222665476101832482161295321411313525830843915966136814748249906589458905410141906965538387896747375546846618213595165688661941876715858338407833641907024891922856719044736945863722003318526031957256722493189062624177017279248142024760515092698242159769372410662895078523142768353100643884341413944795392762315999109544070401451087596138520908569234305384182336436670714204963907240715652950621301644972412252424876159530992
enc2 = 15954854445966181136742750543358176358186230663706091821454832527034640100670779737656720251005109942306013877086451482243141488450122353285697850016200364912263403464109626937525725210545566742746628476797261121321515812788726862118315480354196115424526212965145342675007815411995594752584377871686965531829990461770047418586001518916553661158567047779694730702789677326905844275827365395845945286695577426050334364557405151339008293258932006267159313380746863008928500607405457044370494583863960981060999695448408234857505591647503423149271589648863473472196402149897680041851877198062464480400493467334040101779732999029043327947071232256187123316057998759518569161852646625701393295408789279678540894319137126821001853808931387200759810381958895695749251834840804088478214013923869059004663359509316215974475427057000629842098545503905230785431115754636129549758888267877395566717448365986552725726428222769339088308242580851434964429627168365161743834285778996916154182286570122208454025753108647581888781783757375011437394936853319184725324597963035778640646869326035848170752766298225095197226934969602554875402243303906613183431896300664684256018886119255870435413622515792072064528098344111446380223430819596310173312668368618931885819458529703118195242890075359424013033800260927722161030183373647798407301688760998313223874318513944409702828538509864933624724225689414495687466779277994989628367119101
'''

soluti2on

题目分为两个部分，第一部分求解满足等式的(x, y)，第二部分求解flag的值

part2

enc1 = pow(233 * n ** 2 + 1, part1, n ** 3)
enc2 = pow(y * n + 1, part2, n ** 3)

n是2048bit的大整数，直接求解离散对数是不可行的使用二项式定理展开分析，对于enc1：

即：

对于enc2的分析思路是相同的，只需要在模n^2下进行分析即可：

即：flag的第一部分可以直接求出，第二部分需要首先求解y的值然后求出

part1

D = 1117
x = 
y = 
assert x**2 - D * y**2 == 1

题目考察的是佩尔Pell方程对于这个方程只需要掌握如下几点（省略数学推导）

可以使用连分数的方法，使用的连分数求出方程的一组小的特解(x0, y0)
可以使用线性迭代的方法，根据特解求出方程的所有解

线性迭代方程：

枚举所有可能的y后，代入到前述式子求得flag第二部分可能的值，筛选明文信息即可

exp

from Crypto.Util.number import *
n = 14381700422128582509148801752355744589949207890477326887251636389639477554903212313766087310581920423926674144511237847467160303159477932732842314969782540035709454603184976310835433114879043016737665256729350745769071186849072915716081380191025215059636548339167264601163525017898164466972776553148697204889820118261937316228241099344357088387154112255824092894798716597134811437852876763391697588672779069166285303075312833415574850549277205130215394422655325352478386576833373623679069271857652029364332047485797407322257853316210866532938722911480593571175419708834718860211036796987231227104370259051299799633809
enc1 = 7213976567554002619445032200800186986758840297933991288547009708561953107405266725278346810536664670987171549114913443730366439254199110599202411546254632702440251000149674899033994570393935743323319736976929843596350656674709510612789987746895513057821629144725499933366382123251520676386059405796801097683107223771674383940907066300331503757142088898427893069444164604408189686282018392714450005250018004986102062209998463347007934222341910941474212611569508001910685822097788669516018081617394144015000387497289693096617795809933540456797387940627782045397249431573540932386564021712811633992948508497879189416719996092292320828635490820907122756459412206735413770335545012892724496210585503157766011075566023635046144730429791359690237088629187946232458937292767085665897489251315749496284368726255508362410603108788759785472319449267909859926786774679533591222665476101832482161295321411313525830843915966136814748249906589458905410141906965538387896747375546846618213595165688661941876715858338407833641907024891922856719044736945863722003318526031957256722493189062624177017279248142024760515092698242159769372410662895078523142768353100643884341413944795392762315999109544070401451087596138520908569234305384182336436670714204963907240715652950621301644972412252424876159530992
enc2 = 15954854445966181136742750543358176358186230663706091821454832527034640100670779737656720251005109942306013877086451482243141488450122353285697850016200364912263403464109626937525725210545566742746628476797261121321515812788726862118315480354196115424526212965145342675007815411995594752584377871686965531829990461770047418586001518916553661158567047779694730702789677326905844275827365395845945286695577426050334364557405151339008293258932006267159313380746863008928500607405457044370494583863960981060999695448408234857505591647503423149271589648863473472196402149897680041851877198062464480400493467334040101779732999029043327947071232256187123316057998759518569161852646625701393295408789279678540894319137126821001853808931387200759810381958895695749251834840804088478214013923869059004663359509316215974475427057000629842098545503905230785431115754636129549758888267877395566717448365986552725726428222769339088308242580851434964429627168365161743834285778996916154182286570122208454025753108647581888781783757375011437394936853319184725324597963035778640646869326035848170752766298225095197226934969602554875402243303906613183431896300664684256018886119255870435413622515792072064528098344111446380223430819596310173312668368618931885819458529703118195242890075359424013033800260927722161030183373647798407301688760998313223874318513944409702828538509864933624724225689414495687466779277994989628367119101

def solve_pell(N, numTry = 100):
 cf = continued_fraction(sqrt(N))
    for i in range(numTry):
        denom = cf.denominator(i)
        numer = cf.numerator(i)
        if numer**2 - N * denom**2 == 1:
            return int(numer), int(denom)
    return None, None

D = 1117
x, y = solve_pell(N=D)

flag1 = int((enc1 - 1) // n**2 * inverse(233, n) % n)
xi, yi = x, y
for _ in range(100):
    flag2 = int((enc2%n**2 - 1) // n * inverse(yi, n) % n)
    flag = long_to_bytes(flag1) + long_to_bytes(flag2)
    if len(flag) < 100:
        print(flag)
        break
    xi, yi = x*xi+D*y*yi, x*yi+y*xi
# flag{11e89e28-4e27-47f0-a7c7-8e66c18881be}

backdoor

from Crypto.Util.number import *
from Crypto.Util.Padding import pad
from random import randint
from Crypto.Util.strxor import strxor
from Crypto.Cipher import AES
from hashlib import sha256
from hashlib import md5

flag = b'xxx'

def Get_Parameters():
    w = getPrime(25)
    a = getPrime(15)
    b = getPrime(15)
    x = getPrime(30)
    return w,a,b,x

def Malicious_ECDH():
    w,a,b,x = Get_Parameters()
    
    P = getPrime(512)
    A = getRandomNBitInteger(30)
    B = getRandomNBitInteger(40)
    F = GF(P)
    E = EllipticCurve(F, [A, B])
    G = E.random_point()
    k1 = getRandomNBitInteger(50)
    M1 = k1 * G
    
    Y = x * G
    t = randint(0,1)
    t = 1
    z = (k1 - w * t) * G + (-a*k1 - b) * Y
    k2 = sha256(str(z[0]).encode()).digest()[:6]
    k2 = bytes_to_long(k2)
    M2 = k2 * G
    k_rec = getRandomNBitInteger(50)
    B_ = k_rec * G
    shared_key1 = k_rec * M2 
    shared_key2 = k2 * B_
    assert shared_key1 == shared_key2
    
    print((w,a,b,x))
    print((A,B,P))
    print(G.xy())
    print(M1.xy())
    print(M2.xy())
    print(B_.xy())
    return shared_key1

def easy_enc(pt,key):
    key = md5(str(int(key[0])).encode()).digest()
    cipher = AES.new(key, AES.MODE_ECB)
    ct = cipher.encrypt(pad(pt,16))
    print(ct)
    
key = Malicious_ECDH()
easy_enc(flag,key)
'''
(31889563, 31153, 28517, 763220531)
(1064988096, 802063264240, 12565302212045582769124388577074506881895777499095598016237085270545754804754108580101112266821575105979557524040668050927829331647411956215940656838233527)
(359297413048687497387015267480858122712978942384458634636826020013871463646849523577260820163767471924019580831592309960165276513810592046624940283279131, 9290586933629395882565073588501573863992359052743649536992808088692463307334265060644810911389976524008568647496608901222631270760608733724291675910247770)
(10930305358553250299911486296334290816447877698513318419802777123689138630792465404548228252534960885714060411282825155604339364568677765849414624286307139, 7974701243567912294657709972665114029771010872297725947444110914737157017082782484356147938296124777392629435915168481799494053881335678760116023075462921)
(497353451039150377961380023736260648366248764299414896780530627602565037872686230259859191906258041016214805015473019277626331812412272940029276101709693, 8439756863534455395772111050047162924667310322829095861192323688205133726655589045018003963413676473738236408975953021037765999542116607686218566948766462)
(5516900502352630982628557924432908395278078868116449817099410694627060720635892997830736032175084336697081211958825053352950153336574705799801251193930256, 10314456103976125214338213393161012551632498638755274752918126246399488480437083278584365543698685202192543021224052941574332651066234126608624976216302370)
b'x1axfbxa2xe1x86x04xfakx9axa3xd15xb8x16x1dxbcxa9Sxf5;xfaxf1x08dn~xd4x94xa4;^*xf6xd7xf10xa3xe1k`x1f-xefx80x16x80x80xe2'
'''

solution

题目本质上实现了一次ECDH密钥交换

M2 = k2 * G
B_ = k_rec * G
shared_key = k_rec * k2 * G

注意k2的产生方式

z = (k1 - w * t) * G + (-a*k1 - b) * Y
k2 = sha256(str(z[0]).encode()).digest()[:6]
k2 = bytes_to_long(k2)

其中w，t，a，b，x，Y均已知，k1未知但M1已知，将z中含k1的项进行转化

z = k1*G - a*k1*Y + (-w*t*G - b*Y)
z = M1 - a*x*M1 + (-w*t*G - b*Y)

z式所有项的值均已知，k2的值即可计算出，进而计算出交换密钥解密flag即可

exp

from Crypto.Util.number import *
from Crypto.Util.Padding import pad
from random import randint
from Crypto.Util.strxor import strxor
from Crypto.Cipher import AES
from hashlib import sha256
from hashlib import md5

w, a, b, x = (31889563, 31153, 28517, 763220531)
A, B, P = (1064988096, 802063264240, 12565302212045582769124388577074506881895777499095598016237085270545754804754108580101112266821575105979557524040668050927829331647411956215940656838233527)
G = (359297413048687497387015267480858122712978942384458634636826020013871463646849523577260820163767471924019580831592309960165276513810592046624940283279131, 9290586933629395882565073588501573863992359052743649536992808088692463307334265060644810911389976524008568647496608901222631270760608733724291675910247770)
M1 = (10930305358553250299911486296334290816447877698513318419802777123689138630792465404548228252534960885714060411282825155604339364568677765849414624286307139, 7974701243567912294657709972665114029771010872297725947444110914737157017082782484356147938296124777392629435915168481799494053881335678760116023075462921)
M2 = (497353451039150377961380023736260648366248764299414896780530627602565037872686230259859191906258041016214805015473019277626331812412272940029276101709693, 8439756863534455395772111050047162924667310322829095861192323688205133726655589045018003963413676473738236408975953021037765999542116607686218566948766462)
B_ = (5516900502352630982628557924432908395278078868116449817099410694627060720635892997830736032175084336697081211958825053352950153336574705799801251193930256, 10314456103976125214338213393161012551632498638755274752918126246399488480437083278584365543698685202192543021224052941574332651066234126608624976216302370)
ct = b'x1axfbxa2xe1x86x04xfakx9axa3xd15xb8x16x1dxbcxa9Sxf5;xfaxf1x08dn~xd4x94xa4;^*xf6xd7xf10xa3xe1k`x1f-xefx80x16x80x80xe2'

E = EllipticCurve(GF(P), [A, B])
G, M1, M2, B_ = [E(_) for _ in [G, M1, M2, B_]]

t = 1
z = M1 - w*t* G - a*x*M1 - b*x*G
k2 = sha256(str(z[0]).encode()).digest()[:6]
k2 = bytes_to_long(k2)
key = k2 * B_

key = md5(str(int(key[0])).encode()).digest()
cipher = AES.new(key, AES.MODE_ECB)
pt = cipher.decrypt(ct)
print(pt)
# flag{63259ab8-4916-4095-8888-d92c2b003e18}

magic_dlp

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from hashlib import sha256
from base64 import b64encode
from secret import flag


p = random_prime(2 ^ 256) 
sx = randint(1, p-1) 
g = 3 
PR.<x> = PolynomialRing(GF(p)) 
f = sum(randint(0, 2^128)*x**i for i in range(2*g + 1 + 1)) 
sy = f(sx).nth_root(2) 
HC = HyperellipticCurve(f, 0) 
J = HC.jacobian()(GF(p)) 
r = randint(0, 2^40) 
D1 = randint(1, p-1)*J(HC((sx, sy))) 
D2 = r*D1 
 
key = sha256(str(r).encode()).digest() 
aes = AES.new(key, AES.MODE_ECB) 
ct = aes.encrypt(pad(flag, 16)) 
print(p) 
print(D1) 
print(D2) 
print(b64encode(ct).decode()) 

"""
28250322002421485740011517298787354630342182411922678481506757706584776470549
(x^3 + 14837843646688223376620895623918856834301419791450189502644075689674679307565*x^2 + 11342007530582447297077768070260591643434731986676417772353996440271447424229*x + 17253160355772506039833501683117771635464243068672344160916188778934194482626, y + 11583638164648709615113883733024362701865856309079457013197399476805753481773*x^2 + 14799567073594539924214272546716232642453764116619810153125493046155930087914*x + 9020351128638199743425310619576234999021949822922952447017982687315971687269)
(x^3 + 24086141351204484270563731092873802082275121784385117167214060247819862896159*x^2 + 12580133579221229248448771717453263525988015199573816289207551576399335707433*x + 2025561351219044126154032254344655853662339878505961213456370741923912105725, y + 3024337373411188543472600372581043552807342888844351463589310783585361491167*x^2 + 22142729345652208596100988590287276835636512968984185855026844080502870977199*x + 24006419269594097580414614133924457311337109216133817568627246946606650903690)
IuhuwMMbrawsh63urhYqbaFHbXIhhHoiECUKqlg29b6ZxEg8QnD2Iy7QerX4kBj0
"""

solution

题目分为两个部分，第一部分需要恢复多项式f进而得到超椭圆曲线方程，第二部分需要在超椭圆曲线上求解离散对数问题，恢复flag的值

Hyper Elliptic Curve

Neal Koblitz在1989年提出了超椭圆曲线密码体制（HCC），它是基于有限域上超椭圆曲线的Jacobian上的离散对数问题。至于超椭圆曲线具体是什么东西，我也不太清楚。不过我们可以类比普通的椭圆曲线来理解

PR.<x> = PolynomialRing(GF(p)) 
f = ...
h = ...
HC = HyperellipticCurve(f, h)
J = HC.jacobian()(GF(p))

u = ...
v = ...
G = J([u, v])

点(u, v)满足：

同时曲线上的点定义了加法规则，结果仍然落在该曲线上已知点G与点xG，求解x是困难的->HCDLP问题

part1

根据超椭圆曲线的两个点D1，D2，我们已知：

使用中国剩余定理即得到：其中u1*u2是6次多项式，那么得到的f0就是5次多项式。然而f是7次多项式，需要进一步分析此处有一个隐含的条件：f是一个系数比较小的多项式

p = random_prime(2 ^ 256)
...
f = sum(randint(0, 2^128)*x**i for i in range(2*g + 1 + 1))

考虑在模u1*u2下分析多项式f：

其中

那么对于格子：

易知目标短向量：

因此使用格基规约方法可以求解多项式f的全部系数

p = 28250322002421485740011517298787354630342182411922678481506757706584776470549
g = 3 
R.<x> = GF(p)[]

D1x = x^3 + 14837843646688223376620895623918856834301419791450189502644075689674679307565*x^2 + 11342007530582447297077768070260591643434731986676417772353996440271447424229*x + 17253160355772506039833501683117771635464243068672344160916188778934194482626
D2x = x^3 + 24086141351204484270563731092873802082275121784385117167214060247819862896159*x^2 + 12580133579221229248448771717453263525988015199573816289207551576399335707433*x + 2025561351219044126154032254344655853662339878505961213456370741923912105725
D1y = (11583638164648709615113883733024362701865856309079457013197399476805753481773*x^2 + 14799567073594539924214272546716232642453764116619810153125493046155930087914*x + 9020351128638199743425310619576234999021949822922952447017982687315971687269)
D2y = (3024337373411188543472600372581043552807342888844351463589310783585361491167*x^2 + 22142729345652208596100988590287276835636512968984185855026844080502870977199*x + 24006419269594097580414614133924457311337109216133817568627246946606650903690)

f = crt([D1y^2, D2y^2], [D1x, D2x])
mod = D1x * D2x
L = block_matrix([
    [matrix(ZZ, [int(_) for _ in (x^6%mod)]),    1, 0, 0],
    [matrix(ZZ, [int(_) for _ in (x^7%mod)]),    0, 1, 0],
    [ZZ(p),                                      0, 0, 0],
    [matrix(ZZ, [int(_) for _ in f]),            0, 0, ZZ(p)],
]).LLL()
f = R([abs(_) for _ in L[-1][:-1]])
print(f%D1x == D1y^2%D1x, f%D2x == D2y^2%D2x)
# True True

part2

恢复了多项式f后，我们即得到超椭圆曲线的方程，接下来需要在曲线上求解离散对数问题

r = randint(0, 2^40) 
D1 = randint(1, p-1)*J(HC((sx, sy))) 
D2 = r*D1 

key = sha256(str(r).encode()).digest() 
aes = AES.new(key, AES.MODE_ECB) 
ct = aes.encrypt(pad(flag, 16))

此处r的范围是比较小的，我们可以使用BSGS算法在的复杂度求出r的值 BSGS算法本质上是一种使用空间复杂度换取时间复杂度的算法，此处不展开讲解

def BSGS(L, R, sub):
    import tqdm
    
    m, dic = sqrt(sub).round(), dict()
    ga = 0 * L
    for i in tqdm.tqdm(range(m + 1)):
        dic[str(ga)] = i
        ga = ga + L
    gb = -m * L
    for i in tqdm.tqdm(range(sub//m + 1)):
        h = str(R)
        if h in dic:
            sk = i*m + dic[h]
            print(f"{sub} ==> {sk}")
            return ZZ(sk)
        R = R + gb
    return None

exp

from Crypto.Cipher import AES
from hashlib import sha256
from base64 import b64decode

def BSGS(L, R, sub):
    import tqdm
    
    m, dic = sqrt(sub).round(), dict()
    ga = 0 * L
    for i in tqdm.tqdm(range(m + 1)):
        dic[str(ga)] = i
        ga = ga + L
    gb = -m * L
    for i in tqdm.tqdm(range(sub//m + 1)):
        h = str(R)
        if h in dic:
            sk = i*m + dic[h]
            print(f"{sub} ==> {sk}")
            return ZZ(sk)
        R = R + gb
    return None

p = 28250322002421485740011517298787354630342182411922678481506757706584776470549
g = 3 
R.<x> = GF(p)[]

D1x = x^3 + 14837843646688223376620895623918856834301419791450189502644075689674679307565*x^2 + 11342007530582447297077768070260591643434731986676417772353996440271447424229*x + 17253160355772506039833501683117771635464243068672344160916188778934194482626
D2x = x^3 + 24086141351204484270563731092873802082275121784385117167214060247819862896159*x^2 + 12580133579221229248448771717453263525988015199573816289207551576399335707433*x + 2025561351219044126154032254344655853662339878505961213456370741923912105725
D1y = - (11583638164648709615113883733024362701865856309079457013197399476805753481773*x^2 + 14799567073594539924214272546716232642453764116619810153125493046155930087914*x + 9020351128638199743425310619576234999021949822922952447017982687315971687269)
D2y = - (3024337373411188543472600372581043552807342888844351463589310783585361491167*x^2 + 22142729345652208596100988590287276835636512968984185855026844080502870977199*x + 24006419269594097580414614133924457311337109216133817568627246946606650903690)

f = crt([D1y^2, D2y^2], [D1x, D2x])
mod = D1x * D2x
L = block_matrix([
    [matrix(ZZ, [int(_) for _ in (x^6%mod)]),    1, 0, 0],
    [matrix(ZZ, [int(_) for _ in (x^7%mod)]),    0, 1, 0],
    [ZZ(p),                                      0, 0, 0],
    [matrix(ZZ, [int(_) for _ in f]),            0, 0, ZZ(p)],
]).LLL()
f = R([abs(_) for _ in L[-1][:-1]])
print(f%D1x == D1y^2%D1x, f%D2x == D2y^2%D2x)

HC = HyperellipticCurve(f, 0) 
J = HC.jacobian()(GF(p)) 
D1 = J([D1x, D1y])
D2 = J([D2x, D2y])
# r = BSGS(D1, D2, 2^40)
r = 251909161016
print(D1*r == D2)

enc = b'IuhuwMMbrawsh63urhYqbaFHbXIhhHoiECUKqlg29b6ZxEg8QnD2Iy7QerX4kBj0'
key = sha256(str(r).encode()).digest() 
aes = AES.new(key, AES.MODE_ECB) 
flag = aes.decrypt(b64decode(enc))
print(flag)
# flag{72825d3f-74f0-0a0e-ba1c-895eee99dc29}

stream

# Problem by rec, with nothing.
import os
import utils
import secret
from Crypto.Util.number import *

gift = utils.LFSR(seed=bytes_to_long(os.urandom(16)), mask=secret.mask).leak()
lfsr = utils.LFSR(seed=bytes_to_long(os.urandom(16)), mask=secret.mask)

assert b'flag' in secret.message
enc = b''.join([
    long_to_bytes(
        int(''.join([str(next(lfsr)) for _ in range(8)]), 2) ^ m
    ) for m in secret.message
]).hex()

print(f"{gift = }n{enc = }")
'''
gift = [1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1]
enc = '4709fb814f73b4e58fcc2fd17c0818a1e03ee236d75567b82e44a42c07e760ab09ebe30c76e6af1ea0753c2fc6128f8dfe47da897e17f7b6cf6526845e1cef287772584f767fdac88e60e388190e9792b46017908d1cde476b9943ffa820141d3439c7a904cc74aeb0e3c6fbb5f00b88c812215978b85da1ef1e216e19e4e903c88f9d62bb62e4b10671dd548d3c12ab7808b52c6724b08925ec648de3d8ef20b227571dabf18e8866739d0f2d13b941f10c11f23d31a5a7c4bb25c724d0ed9edaf51953540935f42190c8017bb8fae61e22d57f9543e9b316364be991ea18149bf966270a05f9c21fac2395373ec318750c3471b58e4254625237fd606969b276689db0bf0bab2d6a0dcd49d792ec2c044d1fbee2221fb08cbfc88b339a0da44c38c3b28eed3ec096f4f138276e0633b3691e4af375ea5b22e765dc0c43fb3067e115d24435e714a530c02473a11fc97e07d2167f9c1730b869bf360dd5bd9ab8bf42a474a837046e9c5a695e860ced0e5f1bd17ad00ce2db11df372d3a23ea429c590466ef0e63b4c6dc6669c6a86ac0350958ff5d33059c0ac92270392970e3fe1af565269146d8c42214f10ee13d9728835bcae0ade16bc44808beaa94b5c6f1d7d71e5aa35f6aabcefff2b462862e44d7f8ad57b55e3c5e8275f83585b9e60aab22ab20585b5a6cd93d291da66bc24cfbfe931b1a1efca4245284f59088ff8fcbe7011da16344cb0c9ac7dc3bf559759798aede311f8a326f37172b20b320cea08e9e8550ba30996c6b961de35619574d206ef4c6fc30cb78345be1eb01b095141337f6ecf37878bccf8ee07d2b9b4751b73aa1dea7e0d9f661b5ea9790ddc195d2827433011725be3ecc06a8a83198ea1e95eb310ea40fcd18449bba1d221f20be9c52f2e95aadc726e49480516dbbfba71465d1880d201bf2d1fd4ab87f7a56e7cbc329431f985e0b62da972417fc7dca0d525802769b7b1df98367ed2b1bbfb3981f3f1beb7ac7754771b15a3554d7a58e865fae9804e0a4f54288d5661e589052bd8af1cd8f1d53593b34583efaf9a17a9ff2898c91145e05b193db8a2ae9794684b80d3e8cec882e4541a8f9ddd745875006e8d987c8dcbc7457cd738acbee1e3bee296870d7ce1e4c5ebb0f11838c02a8784a4596afa8d068d7b1e448a46cdb91e29dce9a9a8835449c5ec3c4bf3b10ece44346b0d4c3eeb499e85f99fb2f9b0eec01fb0599473c9933c22047b77d5e589db2b01b80d7fc61b66df7f612b8b3500ba8f314e8e7489842b3fecd3743d67cf38bb4b6b05e928de3f2edc61733b9e1368bc4ff83018f90ac9dfdfc7f170bdfb583d9a24cc48cfa0073ca512a4f8d87ce8c07e6431338b505bade203c684df8105b8f7069d7dad3a2b038fb57c3385f4bbabf557ac97627fcfc47c0d3513d284dd5553fb61bc4f328f69027e247e64a45d8fffcf6db3f4a67c76a75'
'''

nbits = 128


class LFSR:
    def __init__(self, seed, mask):
        self.s, self.mask = seed, mask
        self.nmask = (1 << nbits) - 1

    def __next__(self):
        res = self.s & self.mask
        out = sum([res >> i for i in range(nbits)]) & 1
        self.s = ((self.s << 1) ^ out) & self.nmask
        return out

    def leak(self):
        return [next(self) for _ in range(2 * nbits - 8)]

solution

题目分为两个部分，第一部分需要根据leak恢复mask的值，第二部分需要根据不连续泄露的LFSR内部状态恢复初始状态，进而恢复整个密钥流解密得到flag

part1

已知：对于n bit的LFSR，已知连续2*n bit的密钥流，即可恢复其mask的值可以使用（1）BM算法；（2）解矩阵方程方法此处我们对剩余的8 bit密钥流进行爆破，使用sagemath实现的BM算法即可求解mask的所有可能值

def solve_gift(gift):
    from sage.matrix.berlekamp_massey import berlekamp_massey

    res = berlekamp_massey([GF(2)(i) for i in gift])
    mask = int(''.join(str(_) for _ in res.coefficients(sparse=false)[:-1]), 2)
    return mask

part2

根据题目的提示，可以猜测加密原文是由可打印字符串构成的，这一条件意味着明文字符的8位ascii码最高位为0 利用这一条件，我们可以每隔8bit泄露1bit密钥流对于LFSR泄露不连续密钥流的情况，我们进行如下分析：

已知LFSR的线性反馈过程：

对于GF(2)上的矩阵：

显然有：

进一步地：

因此如果我们泄露了第i位的密钥流比特，对应的第一列即为初始状态与该比特之间的线性关系总计泄露了n比特时，我们即得到一个n*n的矩阵，在GF(2)上求解矩阵方程即可恢复初始状态

def solve_leak(mask, leak):
    mask = [int(_) for _ in bin(mask)[2:].zfill(nbits)]
    C = matrix(GF(2), nbits, nbits)
    for i in range(nbits-1):C[i+1, i] = 1
    for i in range(nbits):C[i, -1] = mask[i]

    M = list()
    for i in range(nbits):M += [(C^(8*i+1)).T[-1].list()]

    res = (vector(GF(2), leak) / matrix(GF(2), M).T).list()
    seed = int(''.join(str(_) for _ in res), 2)
    return seed

exp

from Crypto.Util.number import *
import tqdm
nbits = 128


class LFSR:
    def __init__(self, seed, mask):
        self.s, self.mask = seed, mask
        self.nmask = (1 << nbits) - 1

    def __next__(self):
        res = self.s & self.mask
        out = sum([res >> i for i in range(nbits)]) & 1
        self.s = ((self.s << 1) ^^ out) & self.nmask
        return out


def solve_gift(gift):
    from sage.matrix.berlekamp_massey import berlekamp_massey

    res = berlekamp_massey([GF(2)(i) for i in gift])
    mask = int(''.join(str(_) for _ in res.coefficients(sparse=false)[:-1]), 2)
    return mask


def solve_leak(mask, leak):
    mask = [int(_) for _ in bin(mask)[2:].zfill(nbits)]
    C = matrix(GF(2), nbits, nbits)
    for i in range(nbits-1):C[i+1, i] = 1
    for i in range(nbits):C[i, -1] = mask[i]

    M = list()
    for i in range(nbits):M += [(C^(8*i+1)).T[-1].list()]

    res = (vector(GF(2), leak) / matrix(GF(2), M).T).list()
    seed = int(''.join(str(_) for _ in res), 2)
    return seed


gift = [1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1]
enc = '4709fb814f73b4e58fcc2fd17c0818a1e03ee236d75567b82e44a42c07e760ab09ebe30c76e6af1ea0753c2fc6128f8dfe47da897e17f7b6cf6526845e1cef287772584f767fdac88e60e388190e9792b46017908d1cde476b9943ffa820141d3439c7a904cc74aeb0e3c6fbb5f00b88c812215978b85da1ef1e216e19e4e903c88f9d62bb62e4b10671dd548d3c12ab7808b52c6724b08925ec648de3d8ef20b227571dabf18e8866739d0f2d13b941f10c11f23d31a5a7c4bb25c724d0ed9edaf51953540935f42190c8017bb8fae61e22d57f9543e9b316364be991ea18149bf966270a05f9c21fac2395373ec318750c3471b58e4254625237fd606969b276689db0bf0bab2d6a0dcd49d792ec2c044d1fbee2221fb08cbfc88b339a0da44c38c3b28eed3ec096f4f138276e0633b3691e4af375ea5b22e765dc0c43fb3067e115d24435e714a530c02473a11fc97e07d2167f9c1730b869bf360dd5bd9ab8bf42a474a837046e9c5a695e860ced0e5f1bd17ad00ce2db11df372d3a23ea429c590466ef0e63b4c6dc6669c6a86ac0350958ff5d33059c0ac92270392970e3fe1af565269146d8c42214f10ee13d9728835bcae0ade16bc44808beaa94b5c6f1d7d71e5aa35f6aabcefff2b462862e44d7f8ad57b55e3c5e8275f83585b9e60aab22ab20585b5a6cd93d291da66bc24cfbfe931b1a1efca4245284f59088ff8fcbe7011da16344cb0c9ac7dc3bf559759798aede311f8a326f37172b20b320cea08e9e8550ba30996c6b961de35619574d206ef4c6fc30cb78345be1eb01b095141337f6ecf37878bccf8ee07d2b9b4751b73aa1dea7e0d9f661b5ea9790ddc195d2827433011725be3ecc06a8a83198ea1e95eb310ea40fcd18449bba1d221f20be9c52f2e95aadc726e49480516dbbfba71465d1880d201bf2d1fd4ab87f7a56e7cbc329431f985e0b62da972417fc7dca0d525802769b7b1df98367ed2b1bbfb3981f3f1beb7ac7754771b15a3554d7a58e865fae9804e0a4f54288d5661e589052bd8af1cd8f1d53593b34583efaf9a17a9ff2898c91145e05b193db8a2ae9794684b80d3e8cec882e4541a8f9ddd745875006e8d987c8dcbc7457cd738acbee1e3bee296870d7ce1e4c5ebb0f11838c02a8784a4596afa8d068d7b1e448a46cdb91e29dce9a9a8835449c5ec3c4bf3b10ece44346b0d4c3eeb499e85f99fb2f9b0eec01fb0599473c9933c22047b77d5e589db2b01b80d7fc61b66df7f612b8b3500ba8f314e8e7489842b3fecd3743d67cf38bb4b6b05e928de3f2edc61733b9e1368bc4ff83018f90ac9dfdfc7f170bdfb583d9a24cc48cfa0073ca512a4f8d87ce8c07e6431338b505bade203c684df8105b8f7069d7dad3a2b038fb57c3385f4bbabf557ac97627fcfc47c0d3513d284dd5553fb61bc4f328f69027e247e64a45d8fffcf6db3f4a67c76a75'

enc = bytes.fromhex(enc)
leak = [int(bin(enc[i])[2:].zfill(8)[0]) for i in range(nbits)]
for suffix in tqdm.tqdm(range(2**8)):
    try:
        mask = solve_gift(gift + [int(_) for _ in bin(suffix)[2:].zfill(8)])
        seed = solve_leak(mask, leak)
    except:
        continue
    
    lfsr = LFSR(seed, mask)
    msg = b''.join([long_to_bytes(int(''.join([str(next(lfsr)) for _ in range(8)]), 2) ^^ c) for c in enc])
    if b'flag' in msg:
        print(msg)
        break
# flag{5c84a7cf-c548-5b02-f5b8-140c334f653f}

Cisticola

#!/usr/bin/env sage
# Problem by rec, with nothing.
import Q
import secret
import os
import random
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad

key = os.urandom(16)
cipher = AES.new(key=key, iv=bytes(range(16)), mode=AES.MODE_CBC)
enc = cipher.encrypt(pad(secret.flag, 16)).hex()
print(f"{enc = }")

p = 1439830214451992034013504859825496348425599138552815552028441481225682951310010651304957987750558339128649248859043607574873717185051113737355019502086518775325158336557488060325293103679742942484012852921804371007968007851081933599
R.<x> = PolynomialRing(GF(p))
Q = R(Q.Q)

t = 17
pos = random.sample(range(600), t) + [600]
poly = [int(os.urandom(16).hex(), 16) for _ in range(t)] + [int(key.hex(), 16)]
hint = 0
for i in range(t+1):
    hint = (hint + poly[i]*x^pos[i]) % Q
print(f"{pos = }n{hint = }")

solution

题目给出了一个430次的多项式Q，600次的目标多项式poly，以及poly系数对应的位置注意到p是768bit，相比之下多项式poly的系数是很小的，因此我们可以使用与magic_dlp题目相似的思路进行分析

对于格子：

其中A是的系数，B是hint的系数可知目标短向量：

由于多项式是稀疏的，所以此处只选取pos对应位置构造格子，减小格子的维度然而由于Q是430次多项式，格子L的规模仍然过大（约430+20=450维），格基规约的复杂度是我们无法承受的，因此需要进行优化具体地：

我们在A、B中只选择一些列进行格基规约即可
我们甚至可以省略一些pos的系数不求，因为有一些pos对应的多项式有很多系数为0，删去不会影响对应位置的格基规约

此外，由于题目本质上是线性系统，因此也可以直接求解矩阵方程恢复多项式poly的系数

exp

https://raw.githubusercontent.com/chunqiugame/cqb_writeups/master/2023cqb_cjs/Cisticola-exp.py

ecdsa

import os
import ecdsa
import hashlib
from Crypto.Util.number import *
from Crypto.Util.strxor import strxor as xor
import secret

p = getPrime(256)
gen = lambda: p + getPrime(16)
pad = lambda m: m + os.urandom(32 - len(m) % 32)

key = os.urandom(30)
sk = ecdsa.SigningKey.from_secret_exponent(
    secexp=bytes_to_long(key),
    curve=ecdsa.SECP256k1
)
sig1 = sk.sign(data=b'This is the first message.', k=gen()).hex()
sig2 = sk.sign(data=b'Here is another message.', k=gen()).hex()
enc = xor(hashlib.sha512(key).digest(), pad(secret.flag)).hex()

print(f"{sig1 = }n{sig2 = }n{enc = }")
'''
sig1 = '3f4a6f288e35a4397201d246a98c1f9cfa463e67717fbbdcbd26d7fac75f875855455c2bfb355f7f593ffbe4c4bd1fc729cc129976b56905639100c8ac716b37'
sig2 = '9f563b21f0ee31b2f7a1a8c6edc8ff23b63e0a9d5dd4a699ecc3164871b4982df51bb2feb4bc06c578afd21d3e6227231dd5fe1d8440f3dcd025fd3ea68f5516'
enc = 'cc66d251bfa54954890c81dc1c607bae716573949f327db18aa1f4c0f420b8d29dc7e7ff9edb17b90306bd2aa753fc3fd4dafb9cc4b771cbdd79000ef05a40c0'
'''

solution

ecdsa签名：其中n为椭圆曲线的阶，x为签名私钥，h为消息哈希，k是每次签名引入的随机数题目使用python-ecdsa库进行ecdsa签名，关键代码在于题目使用自定义的随机数k生成算法

p = getPrime(256)
gen = lambda: p + getPrime(16)

显然对于两次签名，使用的随机数k1，k2相差很小即：

其中dp=p1-p2是一个较小的值，此处直接对dp的值进行爆破，即可恢复私钥x的值

exp

import hashlib
import tqdm
from Crypto.Util.number import *
from Crypto.Util.strxor import strxor as xor


sig1 = '3f4a6f288e35a4397201d246a98c1f9cfa463e67717fbbdcbd26d7fac75f875855455c2bfb355f7f593ffbe4c4bd1fc729cc129976b56905639100c8ac716b37'
sig2 = '9f563b21f0ee31b2f7a1a8c6edc8ff23b63e0a9d5dd4a699ecc3164871b4982df51bb2feb4bc06c578afd21d3e6227231dd5fe1d8440f3dcd025fd3ea68f5516'
enc = 'cc66d251bfa54954890c81dc1c607bae716573949f327db18aa1f4c0f420b8d29dc7e7ff9edb17b90306bd2aa753fc3fd4dafb9cc4b771cbdd79000ef05a40c0'
m1 = b'This is the first message.'
m2 = b'Here is another message.'
n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

enc = bytes.fromhex(enc)
h1, h2 = [int(hashlib.sha1(_).hexdigest(), 16) for _ in [m1, m2]]
r1, s1 = [int(_, 16) for _ in [sig1[:len(sig1)//2], sig1[len(sig1)//2:]]]
r2, s2 = [int(_, 16) for _ in [sig2[:len(sig2)//2], sig2[len(sig2)//2:]]]

for dk in tqdm.tqdm(range(2**17)):
    key = (dk*s1*s2-h1*s2+h2*s1)*inverse(r1*s2-r2*s1, n)%n
    flag = xor(enc, hashlib.sha512(long_to_bytes(key)).digest())
    if b'flag' in flag:
        print(flag)
        break
# flag{2f64731e-785b-4259-4566-3d17554bfb7b}

+ + + + + + + + + + +

CTF大本营练习链接：

https://www.ichunqiu.com/competition

春秋杯网络安全联赛将持续打造网络安全新社区，希望更多参赛选手通过比赛结识志同道合的朋友以及交流经验和技巧，欢迎更多伙伴加入春秋杯赛事宇宙，期待大家再次相聚，继续挑战新高度，探索更广阔的宇宙星河！

春秋杯赛事交流QQ群：277328440；

春秋杯赛事交流群（微信群），进群请先加楠辞微信：h40215_

+ + + + + + + + + + +

原文始发于微信公众号（春秋伽玛）：春秋杯WP｜2023春秋杯春季赛之crypto篇

版权声明：admin 发表于 2023年6月13日上午9:00。
转载请注明：春秋杯WP｜2023春秋杯春季赛之crypto篇 | CTF导航

Hack-a-Sat 3 – 2022 Final

admin

704

春秋云镜-Initial打靶记录

admin

看雪·众安 2021 KCTF 秋季赛 | 第二题设计思路及解析

admin

473

Vuln-Drive 2 – bi0sCTF22

admin

498

LEVERAGING BINARY NINJA IL TO REVERSE A CUSTOM ISA: CRACKING THE “POT OF GOLD” 37C3

admin

yoshi-camp 2022 winter参加記【Day 0-1】

admin

653

暂无评论

您必须登录才能参与评论！

立即登录

暂无评论...

春秋杯WP｜2023春秋杯春季赛之crypto篇

作者：rec

简介：东南大学SUS战队成员，联合战队r3kapig成员，联合战队N0wayBack成员。因为太怕痛所以技能点全点密码学了（其实是因为不会其他的方向）

crypyo篇

checkin

soluti2on

part2

part1

exp

backdoor

solution

exp

magic_dlp

solution

Hyper Elliptic Curve

part1

part2

exp

stream

solution

part1

part2

exp

Cisticola

solution

exp

ecdsa

solution

exp

2023 年安询杯 ez_cpp 题解

NahamCon 2023 Writeup

相关文章

暂无评论

相关文章

春秋杯WP｜2023春秋杯春季赛之crypto篇

作者：rec

简介：东南大学SUS战队成员，联合战队r3kapig成员，联合战队N0wayBack成员。因为太怕痛所以技能点全点密码学了（其实是因为不会其他的方向）

crypyo篇

checkin

soluti2on

part2

part1

exp

backdoor

solution

exp

magic_dlp

solution

Hyper Elliptic Curve

part1

part2

exp

stream

solution

part1

part2

exp

Cisticola

solution

exp

ecdsa

solution

exp

2023 年安询杯 ez_cpp 题解

NahamCon 2023 Writeup

相关文章

暂无评论

广告位

相关文章