HZNUCTF2023 预赛
easyDSA
def solve_k(l):
for i in range(512):
if (l + 1 + i - 448) % 512 == 0:
return i
def padding(msg):
l = len(msg)
k = solve_k(l)
l64 = bin(l)[2:].rjust(64, '0') # what if msg is too long, how?
# so mention the condition in guideline of Algorithm
msg = msg + '1' + '0' * k + l64
assert len(msg) % 512 == 0
return msg, l, k
def iteration():
pass
def ring_shift_left(x, num):
x = bin(x)[2:].rjust(32, '0') # shift in 32 bit, take care of it
x = int(x[num:] + x[:num], 2)
return x
def p0(x):
return x ^ ring_shift_left(x, 9) ^ ring_shift_left(x, 17)
def p1(x):
return x ^ ring_shift_left(x, 15) ^ ring_shift_left(x, 23)
def extending(msg):
WW = []
for i in range(len(msg) // 512):
W = ['0' for _ in range(132)]
msgi = msg[i * 512:(i + 1) * 512]
# 512 ====> 16 * 32
for ii in range(len(msgi) // 32):
W[ii] = msgi[ii * 32:(ii + 1) * 32]
assert len(W[ii]) == 32
for j in range(16, 68):
# how to xor word, change to number or bytes?
# number, of course
W[j] = p1(int(W[j - 16], 2) ^ int(W[j - 9], 2) ^ ring_shift_left(int(W[j - 3], 2), 15)) ^ \
ring_shift_left(int(W[j - 13], 2), 7) ^ int(W[j - 6], 2)
W[j] = bin(W[j])[2:]
W[j] = W[j].rjust(32, '0')
for j in range(68, 132):
W[j] = int(W[j - 68], 2) ^ int(W[j - 68 + 4], 2)
W[j] = bin(W[j])[2:]
W[j] = W[j].rjust(32, '0')
WW.append(W)
return WW
def cons(j):
if 0 <= j <= 15:
return 0x79cc4519
elif 16 <= j <= 63:
return 0x7a879d8a
def bool_ff(param, j):
x, y, z = param
if 0 <= j <= 15:
return x ^ y ^ z
elif 16 <= j <= 63:
return (x & y) | (x & z) | (y & z)
def bool_gg(param, j):
x, y, z = param
if 0 <= j <= 15:
return x ^ y ^ z
elif 16 <= j <= 63: # take care of not
if len(bin(x)[2:]) < 32:
ans = ''
x = bin(x)[2:].rjust(32, '0')
y = bin(y)[2:].rjust(32, '0')
z = bin(z)[2:].rjust(32, '0')
for i in range(0, 32):
if x[i] == '0':
ans += str((int(x[i], 2) & int(y[i], 2)) | (1 & int(z[i], 2)))
elif x[i] == '1':
ans += str((int(x[i], 2) & int(y[i], 2)) | (0 & int(z[i], 2)))
return int(ans, 2)
elif len(bin(x)[2:]) == 32:
return (x & y) | (~x & z)
def cf(v, w):
W, W_ = w[:68], w[68:]
# for i in W:
# print(hex(int(i, 2)), end=' ')
# for i in W_:
# print(hex(int(i, 2)), end=' ')
# print()
v = bin(v)[2:].rjust(256, '0')
A, B, C, D, E, F, G, H = [v[_ * 32:(_ + 1) * 32] for _ in range(256 // 32)]
for j in range(64):
# be care of plus, it may surpass 32 bits
# remember j mod 32, or output will be wrong
tmp = (ring_shift_left(int(A, 2), 12) + int(E, 2) + ring_shift_left(cons(j), j % 32)) & 0xffffffff
SS1 = ring_shift_left(tmp, 7)
SS1 = bin(SS1)[2:].rjust(32, '0')
SS2 = int(SS1, 2) ^ ring_shift_left(int(A, 2), 12)
SS2 = bin(SS2)[2:].rjust(32, '0')
tmp = (bool_ff([int(A, 2), int(B, 2), int(C, 2)], j) + int(D, 2) + int(SS2, 2) + int(W_[j], 2)) & 0xffffffff
TT1 = bin(tmp)[2:].rjust(32, '0')
tmp = (bool_gg([int(E, 2), int(F, 2), int(G, 2)], j) + int(H, 2) + int(SS1, 2) + int(W[j], 2)) & 0xffffffff
TT2 = bin(tmp)[2:].rjust(32, '0')
D = C.rjust(32, '0')
C = ring_shift_left(int(B, 2), 9)
C = bin(C)[2:].rjust(32, '0')
B = A.rjust(32, '0')
A = TT1.rjust(32, '0')
H = G.rjust(32, '0')
G = ring_shift_left(int(F, 2), 19)
G = bin(G)[2:].rjust(32, '0')
F = E.rjust(32, '0')
E = p0(int(TT2, 2))
E = bin(E)[2:].rjust(32, '0')
# print(j, end=' ')
# for i in [A, B, C, D, E, F, G, H]:
# print(hex(int(i, 2)), end=' ')
# print()
ans = A + B + C + D + E + F + G + H
ans = int(ans, 2)
return ans
def SM3(msg):
msg = bytes_to_long(msg)
if msg.bit_length() % 4 != 0:
msg = (4 - (msg.bit_length() % 4)) * '0' + bin(msg)[2:]
msg, l, k = padding(msg)
# extend
W = extending(msg)
# iteration
vi = IV
n = (l + k + 65) // 512
for i in range(n):
res = cf(vi, W[i])
vi = vi ^ res
return hex(vi)[2:]
import itertools
def small_roots(f, bounds, m=1, d=None):
if not d:
d = f.degree()
R = f.base_ring()
N = R.cardinality()
f /= f.coefficients().pop(0)
f = f.change_ring(ZZ)
G = Sequence([], f.parent())
for i in range(m + 1):
base = N ^ (m - i) * f ^ i
for shifts in itertools.product(range(d), repeat=f.nvariables()):
g = base * prod(map(power, f.variables(), shifts))
G.append(g)
B, monomials = G.coefficient_matrix()
monomials = vector(monomials)
factors = [monomial(*bounds) for monomial in monomials]
for i, factor in enumerate(factors):
B.rescale_col(i, factor)
B = B.dense_matrix().LLL()
B = B.change_ring(QQ)
for i, factor in enumerate(factors):
B.rescale_col(i, 1 / factor)
H = Sequence([], f.parent().change_ring(QQ))
for h in filter(None, B * monomials):
H.append(h)
I = H.ideal()
if I.dimension() == -1:
H.pop()
elif I.dimension() == 0:
roots = []
for root in I.variety(ring=ZZ):
root = tuple(R(root[var]) for var in f.variables())
roots.append(root)
return roots
return []
from Crypto.Util.number import *
(r1, s1) = (43665657147136977892760835332544097729763754398125679419859037123212964274095, 11372107439153704547599978617809027960018057676066118055075660375442954789009)
(r2, s2) = (29184887007213204285288676779168140587575609668559831035949650649308618592275, 5011738292572181542092375902756977363590922060964162373234404450451520414798)
p = 31961141251107494919420190534228520246958409864267239760354623819192809291490262139213317490432416411403367763443527530375117617196123131270496004125231254335150221348901335274505489844222882171272650010562960614279185073793274638651086760235178963210965828168433516820007716846876686795459738332444629111764967204355463398049697867061034126529189537688874999118692225915790053920062142349951686250122300061810240375783724631961234942175580462986265098353263395579346466921241016500821787793395554444982717141449909744838267161237273856377774256250949274635575801148994817767751541256849860886577256992383324866941911
q = 69375998045163628324086568160767337544901252262545889505892695427466730978301
g = 23095306638137759877487469277470910487928442296144598697677211337473146684728707820084075779044942034329888686699655576145455963231144004571165817481066424910959951439014314776050521403558035997997820617824839889597136772108383034876458141163933312284054415480674388788905935457149956424898637134087874179010376667509489926236214865373552518669840236207944772752416668193786003948717604980584661094548997197117467440864460714843246250800575997370964173558788145639802963655916833143883799542309432910222224223561677245110195809587171802538978009246887077924173034608600837785506594525481696000424121705524449481831586
y = 30195133393879069638917191223585579396119430591488890396938821804398771785068454607425044458865556053274470709839502680269466948174813926392729790863065933078609827279352860810689776644132512095691760326095517755483748554008211568781998662554432781285208646921699265866446498342049913829592480268053599307065979016922204438675164034767731708343084371572648019835171087671868322447023378942812010740490724160077164191297435291229504616686997442254543493394641023587237077429236872101951650325361004443988267286616139798736713430746804524113024341440435623834197278500144543476528466395780355874841379098027115073850819
IV = 0x7380166f4914b2b9172442d7da8a0600a96f30bc163138aae38dee4db0fb0e4e
default_hm1 = b'HZNUCTFRound#1'
default_hm2 = b'HZNUCTFRound#1'
hm1 = int(SM3(default_hm1), 16)
hm2 = int(SM3(default_hm2), 16)
hm =19905280947443115569469777697852124038269468456842113763109865796452965095134
roots = [15744441039285451081, 631339]
k1 = int(roots[0])
k2 = k1**2+roots[1]
x = (s1*k1-hm)*inverse(r1,q)%q
print(hex(x))
print(x)
print(long_to_bytes(x))
#HZNUCTF{JU57_@N_e@SY_5QU4RE_K!}
噫
用rust写的简单仿射密码
from Crypto.Util.number import *
with open('C:\\Users\\86153\\Desktop\\2.txt','rb') as f:
ciphertext = f.readlines()
c = b''.join(ciphertext).decode()
print(c)
flag = ''
increment = 52
inc = []
for i in c:
m = ((ord(i)-increment)*inverse(37,127))%127
increment += ord(i)%127
inc.append(52)
inc.append(increment)
flag += chr(m)
print(inc)
print(flag)
rabinOT
不经意传输1对1，
from Crypto.Util.number import *
from pwn import remote
from gmpy2 import gcd,iroot
e = 65537
x = 9
for i in range(400):
re = remote('43.156.230.30', 10001)
re.recvuntil(b'n = ')
n =int(re.recvline().decode().strip())
re.recvuntil(b'c = ')
c = int(re.recvline().decode().strip())
re.sendline(str(x).encode())
re.recvuntil(b'a =')
a = int(re.recvline().decode().strip())
p = gcd(a-3,n)
print(p)
if p>1:
print(a)
q = n//p
print(p)
print(q)
phi = (p-1)*(q-1)
d = inverse(e,phi)
print(long_to_bytes(pow(c,d,n)))
break
re.interactive()
side-channel
侧信道攻击 ，HITB 2017 Hack in the card I ，新加坡ctf赛中的原题，这里只是换成了高位到低位的快速幂。原题wp阐述的非常详细，这篇不再做过多描述
from random import randint
from Crypto.Util.number import *
e = 16059123945822694365158124950198825543484999519589187888337200553255798544440036832262284563838976515808578129291536616599557509264533073851159103105883072060720056631597958188429575916683604682603283361472163393387285175934398999920713460521688171388856936854606011599111757398384341169379550343011380822651520763942589923801782398753464143234709393484148664365254994860713155476167800961464275898199226390381810969888945023697984476906037653190402170336314921539242675073226168525550913706593532778562652428903475444637793556112819371434228940595513275038805389841060879447191510666943970447241850404552926199602519
n = 23676198353119272891587164142576908690376901293686314942784353146059194045274633032364567515126717515053410457120247729623176193595913335169727137670521232494953911307651873224240918425478358455021118904693825635883056533658237193708645648054998837744523526377375370015128407346231287149043212742478188696880965471297198589414377055357200554254450863749395859378259685909927883404933139662201392110242455689394258060803403855280967030411722557398887495577523627779690177862295719147486918280447692742391730411876509056043404048460252304050528824186627531118009773552255554195757232387432726685926648422550200240296689
c = 0x6a415f728907e12e2af16275da3de93f29640272116b61e36963241eabe10d63b40ace499ed4b5228acc331ff43eabae8c2ffc3ad563397dc9f67e1156000501ca74dddcb540b4de9ef5ddfd1cfc30ff012ea6542bc41c59e694e227d0f2b0e6f3e242df0e1484b02715afefe7ade7375bdd39f9230b705b63efa6d1b11e68caacb5e0dbd83c8204d2cb029722b1cf5ab148a5be7bab10519c0e2f12db9195fa6e2a974f2d6c16aa0cae44d8090c821ee3a344c0756e23cc6d1932155a334648a4a06285b80d4961c3652dba963107cb10e8b7dee5ebd677529486c8b54d230cd65e015767d23b9c79ed2d1a5a068e907b285a4ad65e4b0c2de727252a85f480
with open('C:\\Users\\86153\\Desktop\\data.txt') as f:
data =f.read().split(',')
data = [eval(i) for i in data]
print('point number:', len(data))
start_point = 0 # 开始分析的点
mid = 50 # 采样点间隔
fence = 228 # 高低电平分界线
bin_array = []
for point_index in range(start_point, len(data), mid):
if data[point_index] > fence:
bin_array.append(1)
else:
bin_array.append(0)
bin_array2 = []
flag1 = 0
flag2 = 0
for x in bin_array:
if x:
if flag1:
flag2 = 1
else:
flag1 = 1
else:
if flag2:
bin_array2.append(1)
else:
bin_array2.append(0)
flag1 = 0
flag2 = 0
def power_mod(a, b, c):
ans = 1
a %= c
while b > 0:
if b % 2 == 1:
ans = (ans * a) % c
b //= 2
a = (a * a) % c
return ans
# d_bin = bin_array2[::-1]
d_bin = bin_array2
d = "".join(str(x) for x in d_bin)
print(d)
d_int = int(d,2)
print(d_int)
print(long_to_bytes(power_mod(c,d_int,n)))
for _ in range(100):
m = randint(0, n - 1)
c = pow(m, e, n)
assert power_mod(c, d_int, n) == m or pow(c,d_int,n)==m
print('d =', d_int)
你的背包
没写出来，有空补一下。