2023年春秋杯网络安全联赛-春季赛-Crypto

Match
Created At :
Count:1.8k Views 👀 :
  1. checkin
  2. backdoor
  3. magic_dlp
  4. Cisticola
  5. ecdsa

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

当时的思路：

Pell解第一步求出x、y。

$enc1 = (233n^2+1)^{part1} \space mod \space n^3$

$enc2 = (yn+1)^{part2} \space mod \space n^3$

一开始我想着是解离散对数问题，但似乎有限时间内解不出，不知道能不能化简。后面在佬的提示下从二项式定理入手，拆开得到：

$enc1 = (part1 \cdot 233 \cdot n^2 + 1) \space mod \space n^3$

$enc2 = (\frac{part2 \cdot (part2-1)}{2} \cdot (y\cdot n)^2+part2 \cdot (y\cdot n) + 1)\space mod \space n^3$

然后用sage解方程，但因为逆元不存在解不出结果，然后就卡这了。

看了wp后我直接亚麻呆住了，括号里的其实都比$n^3$小，所以直接算就好，我。。。

D = 1117
x = 87897747594260774254246835664214545379849
y = 2629972211566463612149241455626172190220

n = ...
enc1 = ...
enc2 = ...

part1 = (enc1 - 1) // (233*pow(n,2))
enc2 = enc2 % pow(n,2)
part2 = (enc2 - 1) // (y*n)
print(long_to_bytes(part1) + long_to_bytes(part2))

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)

把z按题目给的表示出来就能直接解，

#sage
(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)
c = b'\x1a\xfb\xa2\xe1\x86\x04\xfak\x9a\xa3\xd15\xb8\x16\x1d\xbc\xa9S\xf5;\xfa\xf1\x08dn~\xd4\x94\xa4;^*\xf6\xd7\xf10\xa3\xe1k`\x1f-\xef\x80\x16\x80\x80\xe2'
E = EllipticCurve(GF(P), [A, B])
G = E(G)
M1 = E(M1)
M2 = E(M2)
B_ = E(B_)
z = M1 - w*G - a*x*M1 - x*b*G
k2 = sha256(str(z[0]).encode()).digest()[:6]
k2 = bytes_to_long(k2)
shared_key2 = k2 * B_
key = md5(str(int(shared_key2[0])).encode()).digest()
cipher = AES.new(key, AES.MODE_ECB)
flag = cipher.decrypt(c)
print(flag)

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

超椭圆曲线，暂时无能为力

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 = }")

上半段CBC模式下的AES，下半段构造p下的多项式。问题在通过多项式求出key，即系数。

看下半段都做了些什么事。

  1. 将列表Q转为多项式环R中的多项式
  2. 生成长为18的列表，前17个数在600以内，最后一个数固定为600
  3. 同样生成长为18的列表，前17个是随机的长16字节的字节串转16进制，最后一个数固定为key的16进制值
  4. for循环计算多项式，最后一项的系数为key的值

佬的wp看不懂阿

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

标准曲线SECP256k1，其阶可求：

p = ecdsa.SECP256k1.generator.order()
print(p)
#115792089237316195423570985008687907852837564279074904382605163141518161494337

下面两行的过程其实就是DSA签名过程：

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

可以得到下面的关系：

  • $k_1 = k_0 + e_1$
  • $k_2 = k_0 + e_2$
  • $k_1 \cdot s_1 \equiv SHA(m_1) + r_1 \cdot key$
  • $k_2 \cdot s_2 \equiv SHA(m_2) + r_2 \cdot key$

将s移到右边，再两式相减可得：

$e_1 - e_2 = s_1^{-1} \cdot SHA(m_1) - s_2^{-1} \cdot SHA(m_2) + key \cdot (s_1^{-1} \cdot r_1 - s_2^{-1} \cdot r_2)$

$ = k_1 - k_2$

$key = Δe+(s_2^{-1} \cdot SHA(m_2) - s_1^{-1} \cdot SHA(m_1)) \cdot (s_1 \cdot r_1^{-1} - s_2 \cdot r_2^{-1})$

因为e是16位的素数，可以爆破出key来。

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

p = 115792089237316195423570985008687907852837564279074904382605163141518161494337
m1 = b'This is the first message.'
m2 = b'Here is another message.'
h1 = bytes_to_long(sha1(m1).digest())
h2 = bytes_to_long(sha1(m2).digest())
sig1 = '3f4a6f288e35a4397201d246a98c1f9cfa463e67717fbbdcbd26d7fac75f875855455c2bfb355f7f593ffbe4c4bd1fc729cc129976b56905639100c8ac716b37'
sig2 = '9f563b21f0ee31b2f7a1a8c6edc8ff23b63e0a9d5dd4a699ecc3164871b4982df51bb2feb4bc06c578afd21d3e6227231dd5fe1d8440f3dcd025fd3ea68f5516'
r1 = bytes.fromhex(sig1[:64])
s1 = bytes.fromhex(sig1[64:])

r2 = bytes.fromhex(sig2[:64])
s2 = bytes.fromhex(sig2[64:])
r1 = bytes_to_long(r1)
r2 = bytes_to_long(r2)
s1 = bytes_to_long(s1)
s2 = bytes_to_long(s2)

s1_ = inverse(s1,p)
s2_ = inverse(s2,p)
k = (r1*s1_ - r2*s2_)
enc = 'cc66d251bfa54954890c81dc1c607bae716573949f327db18aa1f4c0f420b8d29dc7e7ff9edb17b90306bd2aa753fc3fd4dafb9cc4b771cbdd79000ef05a40c0'
enc = bytes.fromhex(enc)
for e in range(-2**16,2**16):
    # mod q
    x = (e+h2*s2_ - h1*s1_) * inverse(k,p) % p
    key = long_to_bytes(x)
    m = xor(sha512(key).digest(), enc)
    if b'flag' in m:
        print(m)
        break

当$Δk$小于等于128bits时可造格解：

设$A = (s_1^{-1} \cdot r_1 - s_2^{-1} \cdot r_2)$，$B = s_1^{-1} \cdot SHA(m_1) - s_2^{-1} \cdot SHA(m_2) $

造格：$Δk = A \cdot key + B$，$key(240bits)$

$\begin{pmatrix} p \ A & 2^{16}/2^{240} \ B & &2^{16} \ \end{pmatrix}$

import hashlib
sig1 = '3f4a6f288e35a4397201d246a98c1f9cfa463e67717fbbdcbd26d7fac75f875855455c2bfb355f7f593ffbe4c4bd1fc729cc129976b56905639100c8ac716b37'
sig2 = '9f563b21f0ee31b2f7a1a8c6edc8ff23b63e0a9d5dd4a699ecc3164871b4982df51bb2feb4bc06c578afd21d3e6227231dd5fe1d8440f3dcd025fd3ea68f5516'
enc = 'cc66d251bfa54954890c81dc1c607bae716573949f327db18aa1f4c0f420b8d29dc7e7ff9edb17b90306bd2aa753fc3fd4dafb9cc4b771cbdd79000ef05a40c0'
r1=bytes_to_long(bytes.fromhex(sig1[:len(sig1)//2]))
s1=bytes_to_long(bytes.fromhex(sig1[len(sig1)//2:]))
h1=bytes_to_long(hashlib.sha1(b'This is the first message.').digest())
r2=bytes_to_long(bytes.fromhex(sig2[:len(sig2)//2]))
s2=bytes_to_long(bytes.fromhex(sig2[len(sig2)//2:]))
h2=bytes_to_long(hashlib.sha1(b'Here is another message.').digest())
p=ecdsa.SECP256k1.generator.order()

RR=RationalField(256)
M=Matrix(RR,3,3)
M[0,0]=p
M[1,0]=ZZ(inverse(s1,p)*r1 %p)-ZZ(inverse(s2,p)*r2 %p)
M[2,0]=ZZ(inverse(s1,p)*h1 %p)-ZZ(inverse(s2,p)*h2 %p)
M[2,2]=2^16
M[1,1]=2^16/2^240
M.LLL()
#[12538 529916052714421365211802626556164022962456609322782019794355446252399179/26959946667150639794667015087019630673637144422540572481103610249216 65536]

2023春秋杯春季赛Crypto方向全解_无趣的浅的博客-CSDN博客

春秋杯春季赛2023 - ZimaB1ue - 博客园 (cnblogs.com)

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1666739907@qq.com

©2022-2023 Luino

Built with Hexo and 3-hexo theme

github