2024网鼎杯

记录2024网鼎杯Crypto部分题解

青龙组

Crypto01

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

p = getPrime(512)
q = getPrime(512)
n = p * q
d = getPrime(299)
e = inverse(d,(p-1)*(q-1))
m = bytes_to_long(flag)
c = pow(m,e,n)
hint1 = p >> (512-70)
hint2 = q >> (512-70)

print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")
print(f"hint1 = {hint1}")
print(f"hint2 = {hint2}")

n = 73787944575265560659337066998651559854008554735456318333076159883563615536562553619509791556832630227860528135540580555475313775587694656733939337337162684083504013096398383073623252469953554083296109377792508578226035938969407231689553680824348024184291021105154956244179599769690508760502010020180061720019
e = 29567393844922147731100606267534953994449203725806042726345753844983783164567752859600595704301680439820601788437000356006329166887506988972343037285018001864800437750191409728833296698465447150521119258782212680439802048101817052671603259114861564484544609221844909301043673563931709693327971992359139371227
c = 45450360465574139870481845301350579669043708378076876540990465420189044791001300484095663295849190297258585508686905534568744689506644183459090297899984297370341547866178062353877908003401151052692574668213473397829536065790283637478791675039086877921443504800597649778898977086137114431286134700385182325815
hint1 = 954676601865566077628
hint2 = 599256795156046227992

和2023领航杯复赛的bd一模一样,之前有记录过,可以看我的这篇博客2023江苏省领航杯 | DexterJie’Blog

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
import time
time.clock = time.time

debug = True

strict = False

helpful_only = True
dimension_min = 7 # 如果晶格达到该尺寸,则停止移除
# 显示有用矢量的统计数据
def helpful_vectors(BB, modulus):
nothelpful = 0
for ii in range(BB.dimensions()[0]):
if BB[ii,ii] >= modulus:
nothelpful += 1
print(nothelpful, "/", BB.dimensions()[0], " vectors are not helpful")

# 显示带有 0 和 X 的矩阵
def matrix_overview(BB, bound):
for ii in range(BB.dimensions()[0]):
a = ('%02d ' % ii)
for jj in range(BB.dimensions()[1]):
a += '0' if BB[ii,jj] == 0 else 'X'
if BB.dimensions()[0] < 60:
a += ' '
if BB[ii, ii] >= bound:
a += '~'
#print (a)

# 尝试删除无用的向量
# 从当前 = n-1(最后一个向量)开始
def remove_unhelpful(BB, monomials, bound, current):
# 我们从当前 = n-1(最后一个向量)开始
if current == -1 or BB.dimensions()[0] <= dimension_min:
return BB

# 开始从后面检查
for ii in range(current, -1, -1):
# 如果它没有用
if BB[ii, ii] >= bound:
affected_vectors = 0
affected_vector_index = 0
# 让我们检查它是否影响其他向量
for jj in range(ii + 1, BB.dimensions()[0]):
# 如果另一个向量受到影响:
# 我们增加计数
if BB[jj, ii] != 0:
affected_vectors += 1
affected_vector_index = jj

# 等级:0
# 如果没有其他载体最终受到影响
# 我们删除它
if affected_vectors == 0:
#print ("* removing unhelpful vector", ii)
BB = BB.delete_columns([ii])
BB = BB.delete_rows([ii])
monomials.pop(ii)
BB = remove_unhelpful(BB, monomials, bound, ii-1)
return BB

# 等级:1
#如果只有一个受到影响,我们会检查
# 如果它正在影响别的向量
elif affected_vectors == 1:
affected_deeper = True
for kk in range(affected_vector_index + 1, BB.dimensions()[0]):
# 如果它影响哪怕一个向量
# 我们放弃这个
if BB[kk, affected_vector_index] != 0:
affected_deeper = False
# 如果没有其他向量受到影响,则将其删除,并且
# 这个有用的向量不够有用
#与我们无用的相比
if affected_deeper and abs(bound - BB[affected_vector_index, affected_vector_index]) < abs(bound - BB[ii, ii]):
#print ("* removing unhelpful vectors", ii, "and", affected_vector_index)
BB = BB.delete_columns([affected_vector_index, ii])
BB = BB.delete_rows([affected_vector_index, ii])
monomials.pop(affected_vector_index)
monomials.pop(ii)
BB = remove_unhelpful(BB, monomials, bound, ii-1)
return BB
# nothing happened
return BB

"""
Returns:
* 0,0 if it fails
* -1,-1 如果 "strict=true",并且行列式不受约束
* x0,y0 the solutions of `pol`
"""
def boneh_durfee(pol, modulus, mm, tt, XX, YY):
"""
Boneh and Durfee revisited by Herrmann and May

在以下情况下找到解决方案:
* d < N^delta
* |x|< e^delta
* |y|< e^0.5
每当 delta < 1 - sqrt(2)/2 ~ 0.292
"""

# substitution (Herrman and May)
PR.<u, x, y> = PolynomialRing(ZZ) #多项式环
Q = PR.quotient(x*y + 1 - u) # u = xy + 1
polZ = Q(pol).lift()

UU = XX*YY + 1

# x-移位
gg = []
for kk in range(mm + 1):
for ii in range(mm - kk + 1):
xshift = x^ii * modulus^(mm - kk) * polZ(u, x, y)^kk
gg.append(xshift)
gg.sort()

# 单项式 x 移位列表
monomials = []
for polynomial in gg:
for monomial in polynomial.monomials(): #对于多项式中的单项式。单项式():
if monomial not in monomials: # 如果单项不在单项中
monomials.append(monomial)
monomials.sort()

# y-移位
for jj in range(1, tt + 1):
for kk in range(floor(mm/tt) * jj, mm + 1):
yshift = y^jj * polZ(u, x, y)^kk * modulus^(mm - kk)
yshift = Q(yshift).lift()
gg.append(yshift) # substitution

# 单项式 y 移位列表
for jj in range(1, tt + 1):
for kk in range(floor(mm/tt) * jj, mm + 1):
monomials.append(u^kk * y^jj)

# 构造格 B
nn = len(monomials)
BB = Matrix(ZZ, nn)
for ii in range(nn):
BB[ii, 0] = gg[ii](0, 0, 0)
for jj in range(1, ii + 1):
if monomials[jj] in gg[ii].monomials():
BB[ii, jj] = gg[ii].monomial_coefficient(monomials[jj]) * monomials[jj](UU,XX,YY)

#约化格的原型
if helpful_only:
# #自动删除
BB = remove_unhelpful(BB, monomials, modulus^mm, nn-1)
# 重置维度
nn = BB.dimensions()[0]
if nn == 0:
print ("failure")
return 0,0

# 检查向量是否有帮助
if debug:
helpful_vectors(BB, modulus^mm)

# 检查行列式是否正确界定
det = BB.det()
bound = modulus^(mm*nn)
if det >= bound:
print ("We do not have det < bound. Solutions might not be found.")
print ("Try with highers m and t.")
if debug:
diff = (log(det) - log(bound)) / log(2)
print ("size det(L) - size e^(m*n) = ", floor(diff))
if strict:
return -1, -1
else:
print ("det(L) < e^(m*n) (good! If a solution exists < N^delta, it will be found)")

# display the lattice basis
if debug:
matrix_overview(BB, modulus^mm)

# LLL
if debug:
print ("optimizing basis of the lattice via LLL, this can take a long time")

#BB = BB.BKZ(block_size=25)
BB = BB.LLL()

if debug:
print ("LLL is done!")

# 替换向量 i 和 j ->多项式 1 和 2
if debug:
print ("在格中寻找线性无关向量")
found_polynomials = False

for pol1_idx in range(nn - 1):
for pol2_idx in range(pol1_idx + 1, nn):

# 对于i and j, 构造两个多项式

PR.<w,z> = PolynomialRing(ZZ)
pol1 = pol2 = 0
for jj in range(nn):
pol1 += monomials[jj](w*z+1,w,z) * BB[pol1_idx, jj] / monomials[jj](UU,XX,YY)
pol2 += monomials[jj](w*z+1,w,z) * BB[pol2_idx, jj] / monomials[jj](UU,XX,YY)

# 结果
PR.<q> = PolynomialRing(ZZ)
rr = pol1.resultant(pol2)


if rr.is_zero() or rr.monomials() == [1]:
continue
else:
print ("found them, using vectors", pol1_idx, "and", pol2_idx)
found_polynomials = True
break
if found_polynomials:
break

if not found_polynomials:
print ("no independant vectors could be found. This should very rarely happen...")
return 0, 0

rr = rr(q, q)

# solutions
soly = rr.roots()

if len(soly) == 0:
print ("Your prediction (delta) is too small")
return 0, 0

soly = soly[0][0]
ss = pol1(q, soly)
solx = ss.roots()[0][0]
return solx, soly

def example():
############################################
# 随机生成数据
##########################################
#start_time =time.perf_counter
start =time.clock()
size=512
length_N = 2*size;
ss=0
s=70
M=1 # the number of experiments
delta = 299/1024
# p = random_prime(2^512,2^511)
for i in range(M):
# p = random_prime(2^size,None,2^(size-1))
# q = random_prime(2^size,None,2^(size-1))
# if(p<q):
# temp=p
# p=q
# q=temp
N = 73787944575265560659337066998651559854008554735456318333076159883563615536562553619509791556832630227860528135540580555475313775587694656733939337337162684083504013096398383073623252469953554083296109377792508578226035938969407231689553680824348024184291021105154956244179599769690508760502010020180061720019
e = 29567393844922147731100606267534953994449203725806042726345753844983783164567752859600595704301680439820601788437000356006329166887506988972343037285018001864800437750191409728833296698465447150521119258782212680439802048101817052671603259114861564484544609221844909301043673563931709693327971992359139371227
c = 45450360465574139870481845301350579669043708378076876540990465420189044791001300484095663295849190297258585508686905534568744689506644183459090297899984297370341547866178062353877908003401151052692574668213473397829536065790283637478791675039086877921443504800597649778898977086137114431286134700385182325815
hint1 = 954676601865566077628 # p高位
hint2 = 599256795156046227992 # q高位
# print ("p真实高",s,"比特:", int(p/2^(512-s)))
# print ("q真实高",s,"比特:", int(q/2^(512-s)))

# N = p*q;


# 解密指数d的指数( 最大0.292)



m = 7 # 格大小(越大越好/越慢)
t = round(((1-2*delta) * m)) # 来自 Herrmann 和 May 的优化
X = floor(N^delta) #
Y = floor(N^(1/2)/2^s) # 如果 p、 q 大小相同,则正确
for l in range(int(hint1),int(hint1)+1):
print('\n\n\n l=',l)
pM=l;
p0=pM*2^(size-s)+2^(size-s)-1;
q0=N/p0;
qM=int(q0/2^(size-s))
A = N + 1-pM*2^(size-s)-qM*2^(size-s);
#A = N+1
P.<x,y> = PolynomialRing(ZZ)
pol = 1 + x * (A + y) #构建的方程

# Checking bounds
#if debug:
#print ("=== 核对数据 ===")
#print ("* delta:", delta)
#print ("* delta < 0.292", delta < 0.292)
#print ("* size of e:", ceil(log(e)/log(2))) # e的bit数
# print ("* size of N:", len(bin(N))) # N的bit数
#print ("* size of N:", ceil(log(N)/log(2))) # N的bit数
#print ("* m:", m, ", t:", t)

# boneh_durfee
if debug:
##print ("=== running algorithm ===")
start_time = time.time()


solx, soly = boneh_durfee(pol, e, m, t, X, Y)


if solx > 0:
#print ("=== solution found ===")
if False:
print ("x:", solx)
print ("y:", soly)

d_sol = int(pol(solx, soly) / e)
ss=ss+1

print ("=== solution found ===")
print ("p的高比特为:",l)
print ("q的高比特为:",qM)
print ("d=",d_sol)

if debug:
print("=== %s seconds ===" % (time.time() - start_time))
#break
print("ss=",ss)
#end=time.process_time
end=time.clock()
print('Running time: %s Seconds'%(end-start))
if __name__ == "__main__":
example()

这个脚本是基于人家实验的,有点乱

跑出d之后解RSA

1
2
3
4
5
6
7
d = 687038469975940863290260221773243585573217566356221334458982642899243861704377289553340363
n = 73787944575265560659337066998651559854008554735456318333076159883563615536562553619509791556832630227860528135540580555475313775587694656733939337337162684083504013096398383073623252469953554083296109377792508578226035938969407231689553680824348024184291021105154956244179599769690508760502010020180061720019
c = 45450360465574139870481845301350579669043708378076876540990465420189044791001300484095663295849190297258585508686905534568744689506644183459090297899984297370341547866178062353877908003401151052692574668213473397829536065790283637478791675039086877921443504800597649778898977086137114431286134700385182325815

m = pow(c,d,n)
print(bytes.fromhex(hex(m)[2:]))
# wdflag{39769372-2155-4c99-9ec2-6683c4451ed6}

Crypto02

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
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
# coding: utf-8
#!/usr/bin/env python2

import gmpy2
import random
import binascii
from hashlib import sha256
from sympy import nextprime
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Util.number import long_to_bytes
from FLAG import flag
#flag = 'wdflag{123}'

def victory_encrypt(plaintext, key):
key = key.upper()
key_length = len(key)
plaintext = plaintext.upper()
ciphertext = ''

for i, char in enumerate(plaintext):
if char.isalpha():
shift = ord(key[i % key_length]) - ord('A')
encrypted_char = chr((ord(char) - ord('A') + shift) % 26 + ord('A'))
ciphertext += encrypted_char
else:
ciphertext += char

return ciphertext

victory_key = "WANGDINGCUP"
victory_encrypted_flag = victory_encrypt(flag, victory_key)

p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
a = 0
b = 7
xG = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
yG = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
G = (xG, yG)
n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
h = 1
zero = (0,0)

dA = nextprime(random.randint(0, n))

if dA > n:
print("warning!!")

def addition(t1, t2):
if t1 == zero:
return t2
if t2 == zero:
return t2
(m1, n1) = t1
(m2, n2) = t2
if m1 == m2:
if n1 == 0 or n1 != n2:
return zero
else:
k = (3 * m1 * m1 + a) % p * gmpy2.invert(2 * n1 , p) % p
else:
k = (n2 - n1 + p) % p * gmpy2.invert((m2 - m1 + p) % p, p) % p
m3 = (k * k % p - m1 - m2 + p * 2) % p
n3 = (k * (m1 - m3) % p - n1 + p) % p
return (int(m3),int(n3))

def multiplication(x, k):
ans = zero
t = 1
while(t <= k):
if (k &t )>0:
ans = addition(ans, x)
x = addition(x, x)
t <<= 1
return ans

def getrs(z, k):
(xp, yp) = P
r = xp
s = (z + r * dA % n) % n * gmpy2.invert(k, n) % n
return r,s

z1 = random.randint(0, p)
z2 = random.randint(0, p)
k = random.randint(0, n)
P = multiplication(G, k)
hA = multiplication(G, dA)
r1, s1 = getrs(z1, k)
r2, s2 = getrs(z2, k)

print("r1 = {}".format(r1))
print("r2 = {}".format(r2))
print("s1 = {}".format(s1))
print("s2 = {}".format(s2))
print("z1 = {}".format(z1))
print("z2 = {}".format(z2))

key = sha256(long_to_bytes(dA)).digest()
cipher = AES.new(key, AES.MODE_CBC)
iv = cipher.iv
encrypted_flag = cipher.encrypt(pad(victory_encrypted_flag.encode(), AES.block_size))
encrypted_flag_hex = binascii.hexlify(iv + encrypted_flag).decode('utf-8')

print("Encrypted flag (AES in CBC mode, hex):", encrypted_flag_hex)

# output
# r1 = 80932673752923845218731053671144903633094494351596082125742241568755353762809
# r2 = 80932673752923845218731053671144903633094494351596082125742241568755353762809
# s1 = 11239004842544045364097722042148768449026688243093666008376082303522447245154
# s2 = 97301123368608673469588981075767011435222146576812290449372049839046298462487
# z1 = 84483328065344511722319723339101492661376118616972408250436525496870397932079
# z2 = 114907157406602520059145833917511615616817014350278499032611638874752053304591
# ('Encrypted flag (AES in CBC mode, hex):', u'd8851c55edec1114a6d7a4d6d5efbba4611a39216ec146d2e675194dd0d5f768bee1b09799a133ffda1d283c4f6db475834cbe52c38c88736c94795c137490be')

首先是ECDSA签名k的复用,原理如下
$$
s_1 \equiv k^{-1}(z_1 + r_1d_A) \mod n
$$

$$
s_2 \equiv k^{-1}(z_2 + r_2d_A) \mod n
$$

这里$r_1 = r_2$,所以两式相减有
$$
s_1 - s_2 \equiv k^{-1}(z_1-z_2) \mod n
$$
所以
$$
k \equiv (z_1-z_2)\times (s_1-s_2)^{-1} \mod n
$$
有了k之后根据$s\equiv k^{-1}(z + rd_A)\mod n$就可以恢复$d_A$

然后解CBC得到victory_encrypted_flag

再根据加密逻辑写一个解密代码即可,最后把大写符号改为小写符号

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
from Crypto.Cipher import AES
from Crypto.Util.number import *
import gmpy2
from hashlib import *
from Crypto.Util.Padding import unpad

def victory_decrypt(ciphertext, key):
key = key.upper()
key_length = len(key)
m = ""
for i,char in enumerate(ciphertext):
if ord('A') <= char <= ord('Z') or ord('a') <= char <= ord('z'):
shift = ord(key[i % key_length]) - ord('A')
tmp = chr((char - ord('A') - shift) % 26 + ord('A'))
m += tmp
else:
m += chr(char)
return m

p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
a = 0
b = 7
xG = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
yG = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
G = (xG, yG)
n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
r1 = 80932673752923845218731053671144903633094494351596082125742241568755353762809
r2 = 80932673752923845218731053671144903633094494351596082125742241568755353762809
s1 = 11239004842544045364097722042148768449026688243093666008376082303522447245154
s2 = 97301123368608673469588981075767011435222146576812290449372049839046298462487
z1 = 84483328065344511722319723339101492661376118616972408250436525496870397932079
z2 = 114907157406602520059145833917511615616817014350278499032611638874752053304591
victory_key = "WANGDINGCUP"

c = bytes.fromhex("d8851c55edec1114a6d7a4d6d5efbba4611a39216ec146d2e675194dd0d5f768bee1b09799a133ffda1d283c4f6db475834cbe52c38c88736c94795c137490be")

k = gmpy2.invert((s1-s2),n)*(z1-z2) % n
r_ = gmpy2.invert(r1,n)

d = ((k * s1) - z1)*r_ % n

key = sha256(long_to_bytes(d)).digest()
iv = c[:16]
encrypted_flag = c[16:]
cipher = AES.new(key, AES.MODE_CBC,iv)
decrypted_flag = cipher.decrypt(encrypted_flag)
print(decrypted_flag)
flag = victory_decrypt(unpad(decrypted_flag,16),victory_key)
print(flag)
# WDFLAG{27F8DECFDB040ABB2D0DDBA70AD0484D}
print(flag.lower())
# wdflag{27f8decfdb040abb2d0ddba70ad0484d}

白虎组

Crypto01

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

block_size = 64
rounds = 14

P_permutation = Permutations(list(range(block_size))).random_element()
inverse_P_permutation = [P_permutation.index(i) for i in range(block_size)]

MASK = 0b1110001001111001000110010000100010101111101100101110100001001001
IV = 7

b2i = lambda x: Integer(sum([x[i] * 2**i for i in range(len(x))]))

def pad(x):
padlen = block_size - len(x) % block_size
return x + bytes([padlen] * padlen)

def P(x):
bit_x = x.bits()
if len(bit_x) < block_size:
bit_x.extend([0] * (block_size - len(bit_x)))
bit_x = [bit_x[P_permutation[i]] for i in range(block_size)]
return b2i(bit_x)

def P_inv(x):
bit_x = x.bits()
if len(bit_x) < block_size:
bit_x.extend([0] * (block_size - len(bit_x)))
bit_x = [bit_x[inverse_P_permutation[i]] for i in range(block_size)]
return b2i(bit_x)

def S(x):
x1 = x
x2 = x << IV & MASK
x3 = x << IV & ((1 << block_size) - 1) | MASK
return x1 ^ x2 ^ x3

def encrypt(message_block, key):
ret = message_block
for i in range(rounds):
ret = P_inv(S(P(ret)) ^ key)
return ret

from secret import flag
from hashlib import md5

message = pad(flag)
message = [Integer(bytes_to_long(message[i:i+8])) for i in range(0, len(message), 8)]

key = int(md5(flag).hexdigest(), 16) & ((1 << block_size) - 1)

ciphertext = [encrypt(m, key) for m in message]

print(ciphertext)
print(P_permutation)
"""
[]
[]
"""

这题主要是encrypt中14轮ret = P_inv(S(P(ret)) ^ key)的迭代,逐一分析P(x),S(x),P_inv(x)

可以知道P(x)P_inv(x)就是单纯的置换。可以把置换用矩阵的形式表达
$$
P(x) =
\begin{pmatrix}
P_{1,1} & … & P_{1,64}\
\vdots & \ddots & \vdots \
P_{64,1} & … & P_{64,64}
\end{pmatrix}
\times
\begin{pmatrix}
x_1 & … & x_{64}
\end{pmatrix}
$$

1
2
3
4
5
6
7
8
9
10
P_matrix = matrix(GF(2),64,64)
for i, perm_index in enumerate(P_permutation):
P_matrix[i,perm_index] = 1

def P(x):
bit_x = x.bits()
if len(bit_x) < block_size:
bit_x.extend([0] * (block_size - len(bit_x)))
bit_x = P_matrix * vector(GF(2),bit_x)
return b2i(vector(ZZ,bit_x).list())

这样就用矩阵的形式等效替代了原来的P(x)

同理P_inv就很简单了,用$P^{-1}$乘上$x$向量就好了

1
2
3
4
5
6
def P_inv(x):
bit_x = x.bits()
if len(bit_x) < block_size:
bit_x.extend([0] * (block_size - len(bit_x)))
bit_x = P_matrix^(-1) * vector(GF(2),bit_x)
return b2i(vector(ZZ,bit_x).list())

接下来分析S(x)

1
2
3
4
5
def S(x):
x1 = x
x2 = x << IV & MASK
x3 = x << IV & ((1 << block_size) - 1) | MASK
return x1 ^ x2 ^ x3

这里的x3其实等效于x3 = x << IV & ((1 << block_size) - 1)

此时S(x)中只有&^两个运算。我们可以用GF(2)下的矩阵乘法表示&,用GF(2)下的加法表示^,那么就有
$$
S(x) =\begin{pmatrix}
A_{1,1} & … & A_{1,64}\
\vdots & \ddots & \vdots \
A_{64,1} & … & A_{64,64}
\end{pmatrix}
\times
\begin{pmatrix}
x_1 & … & x_{64}
\end{pmatrix}
+
\begin{pmatrix}
b_1 & … & b_{64}
\end{pmatrix}
$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
A = matrix(GF(2),64,64)
for i in range(64):
A[i,i] = 1

for i in range(64):
j = i - IV
if j >= 0:
A[i,j] = 1

b = vector(GF(2),64)
for i in range(64):
if (MASK >> i) & 1:
b[i] = 1

def S(x):
bit_x = x.bits()
if len(bit_x) < block_size:
bit_x.extend([0] * (block_size - len(bit_x)))
bit_x = vector(GF(2),bit_x)
res = A * bit_x + b
return b2i(vector(ZZ,res))

目前为止我们已经用矩阵的形式表示了三个函数

再看加密函数

1
2
3
4
5
def encrypt(message_block, key):
ret = message_block
for i in range(rounds):
ret = P_inv(S(P(ret)) ^ key)
return ret

^key可以看作再加上一个k向量,k是key的二进制形式

一轮加密:
$$
ret = P^{-1}(A(Px) + b + k)
$$
展开有
$$
ret = P^{-1}APx + P^{-1}b + P^{-1}k
$$
记$T = P^{-1}AP$,$U = P^{-1}b$。那么14轮加密后
$$
ret = T^{14}x + (T^{13}+T^{12} +…+I)U + (T^{13}+T^{12} +…+I)P^{-1}k
$$
注意到加密的时候是把flag的每八位进行分组之后再加密。那我们可以利用flag头wdflag{,再爆破一位,即可获得第一组明文(此外,密文的最后两个值是一样的,可以说明后面两组明文是填充,也可以爆破填充内容来获得另外的明密文对,都可以解得k)。那么对于上面的式子,我们只有k是未知的,可以解矩阵方程得到k
$$
k = (T^{13}+T^{12} +…+I)^{-1}P[ret - T^{14}x -(T^{13}+T^{12} +…+I)U]
$$
求得k之后再解密即可

利用flag头

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
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
from Crypto.Util.number import *

cipher =
P_permutation =
block_size = 64
rounds = 14

inverse_P_permutation = [P_permutation.index(i) for i in range(block_size)]

MASK = 0b1110001001111001000110010000100010101111101100101110100001001001
IV = 7

b2i = lambda x: Integer(sum([x[i] * 2**i for i in range(len(x))]))

P_matrix = matrix(GF(2),64,64)
for i, perm_index in enumerate(P_permutation):
P_matrix[i,perm_index] = 1

def P(x):
bit_x = x.bits()
if len(bit_x) < block_size:
bit_x.extend([0] * (block_size - len(bit_x)))
bit_x = P_matrix * vector(GF(2),bit_x)
return b2i(vector(ZZ,bit_x).list())

def P_inv(x):
bit_x = x.bits()
if len(bit_x) < block_size:
bit_x.extend([0] * (block_size - len(bit_x)))
bit_x = P_matrix^(-1) * vector(GF(2),bit_x)
return b2i(vector(ZZ,bit_x).list())

A = matrix(GF(2),64,64)
for i in range(64):
A[i,i] = 1

for i in range(64):
j = i - IV
if j >= 0:
A[i,j] = 1

b = vector(GF(2),64)
for i in range(64):
if (MASK >> i) & 1:
b[i] = 1

def S(x):
bit_x = x.bits()
if len(bit_x) < block_size:
bit_x.extend([0] * (block_size - len(bit_x)))
bit_x = vector(GF(2),bit_x)
res = A * bit_x + b
return b2i(vector(ZZ,res))


T = P_matrix^(-1)*A*P_matrix
U = P_matrix^(-1)*b
tmp = sum(T^i for i in range(rounds))

keys=[]
for i in "0123456789abcdef":
c = cipher[0].bits()
while len(c) != 64:
c += [0]
c = vector(GF(2),c)
m = b"wdflag{" + i.encode()
x = Integer(bytes_to_long(m)).bits()
while len(x) != 64:
x += [0]
x = vector(GF(2),x)
c -= T^rounds * x
c -= tmp*U
try:
P_invk = tmp.solve_right(c)
k = P_matrix*P_invk
key = sum([int(k[j])*2^j for j in range(len(k))])
keys.append(key)
except:
pass

def decrypt(c,key):
ret = c.bits()
k = key.bits()
while len(ret) != 64:
ret += [0]
while len(k) != 64:
k += [0]
ret = vector(GF(2),ret)
k = vector(GF(2),k)
ret -= tmp * P_matrix^(-1) * k
ret -= (tmp * U)
x = (T^14)^(-1) * ret
m = long_to_bytes(b2i(vector(ZZ,x)))
return m

for key in keys:
m = [decrypt(c,key) for c in cipher]
flag = b""
for i in m:
flag += i
print(flag)

爆破填充内容

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
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
from Crypto.Util.number import *

cipher = []
P_permutation = []
block_size = 64
rounds = 14

inverse_P_permutation = [P_permutation.index(i) for i in range(block_size)]

MASK = 0b1110001001111001000110010000100010101111101100101110100001001001
IV = 7

b2i = lambda x: Integer(sum([x[i] * 2**i for i in range(len(x))]))

P_matrix = matrix(GF(2),64,64)
for i, perm_index in enumerate(P_permutation):
P_matrix[i,perm_index] = 1

def P(x):
bit_x = x.bits()
if len(bit_x) < block_size:
bit_x.extend([0] * (block_size - len(bit_x)))
bit_x = P_matrix * vector(GF(2),bit_x)
return b2i(vector(ZZ,bit_x).list())

def P_inv(x):
bit_x = x.bits()
if len(bit_x) < block_size:
bit_x.extend([0] * (block_size - len(bit_x)))
bit_x = P_matrix^(-1) * vector(GF(2),bit_x)
return b2i(vector(ZZ,bit_x).list())

A = matrix(GF(2),64,64)
for i in range(64):
A[i,i] = 1

for i in range(64):
j = i - IV
if j >= 0:
A[i,j] = 1

b = vector(GF(2),64)
for i in range(64):
if (MASK >> i) & 1:
b[i] = 1

def S(x):
bit_x = x.bits()
if len(bit_x) < block_size:
bit_x.extend([0] * (block_size - len(bit_x)))
bit_x = vector(GF(2),bit_x)
res = A * bit_x + b
return b2i(vector(ZZ,res))


T = P_matrix^(-1)*A*P_matrix
U = P_matrix^(-1)*b
tmp = sum(T^i for i in range(rounds))

keys=[]
for i in range(1,32):
c = cipher[-1].bits()
while len(c) != 64:
c += [0]
c = vector(GF(2),c)
m = bytes([i]) * 8
x = Integer(bytes_to_long(m)).bits()
while len(x) != 64:
x += [0]
x = vector(GF(2),x)
c -= T^rounds * x
c -= tmp*U
try:
P_invk = tmp.solve_right(c)
k = P_matrix*P_invk
key = sum([int(k[j])*2^j for j in range(len(k))])
keys.append(key)
except:
pass

def decrypt(c,key):
ret = c.bits()
k = key.bits()
while len(ret) != 64:
ret += [0]
while len(k) != 64:
k += [0]
ret = vector(GF(2),ret)
k = vector(GF(2),k)
ret -= tmp * P_matrix^(-1) * k
ret -= (tmp * U)
x = (T^14)^(-1) * ret
m = long_to_bytes(b2i(vector(ZZ,x)))
return m

for key in keys:
m = [decrypt(c,key) for c in cipher]
flag = b""
for i in m:
flag += i
print(flag)

Crypto02

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
from Crypto.Util.number import getPrime, isPrime, GCD, inverse

nbits = 2048
gbits = 1000
g = getPrime(int(gbits))
while True:
a = getPrime(int(nbits*0.5)-gbits)
p = 2*g*a + 1
if isPrime(p):
break

while True:
b = getPrime(int(nbits*0.5)-gbits)
q = 2*g*b + 1
if p!=q and isPrime(q):
break
N = p*q
e = 65537

def str2int(s):
return int(s.encode('latin-1').hex(),16)

def int2str(i):
tmp=hex(i)[2:]
if len(tmp)%2==1:
tmp='0'+tmp
return bytes.fromhex(tmp).decode('latin-1')

with open('pubkey.txt','w') as f:
f.write(str(e)+'\n')
f.write(str(N)+'\n')

with open('flag.txt') as f:
plain = str2int(f.read())

c = pow(plain,e,N)
with open('cipher.txt','wb') as f:
f.write(int2str(c).encode('latin-1'))

根据p,q的生成方式(Pollard’s ρ algorithm),可以找到博客[密码学学习笔记 之 浅析Pollard’s rho algorithm及其应用 | Van1sh的小屋](https://jayxv.github.io/2019/11/11/密码学学习笔记之浅析Pollard's rho algorithm及其应用/)

基本上算是原题,拿博客的板子打就好了

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
from Crypto.Util.number import *

def gcd(a, b):
while b:
a, b = b, a%b
return a

def mapx(x):
x=(pow(x,n-1,n)+3)%n #pow(x,n-1,n)是为了减小数值,加速运算,
return x

def pollard_rho(x1,x2):
while True:
x1=mapx(x1)
x2=mapx(mapx(x2))
p=gcd(x1-x2,n)
if (p == n):
print("fail")
return
elif (p!=1):
print("p: "+str(p))
print("q: "+str(n // p))
return p,n // p

n = 49025724928152491719950645039355675823887062840095001672970308684156817293484070166684235178364916522473822184239221170514602692903302575847326054102901449806271709230774063675539139201327878971370342483682454617270705142999317092151456200639975738970405158598235961567646064089356496022247689989925574384915789399433283855087561428970245448888799812611301566886173165074558800757040196846800189738355799057422298556992606146766063202605288257843684190291545600282197788724944382475099313284546776350595539129553760118549158103804149179701853798084612143809757187033897573787135477889183344944579834942896249251191453
p,q = pollard_rho(1,1)

c = open("cipher.txt",'rb').read()
c = int(c.hex(),16)

d = inverse(65537,(p-1)*(q-1))
m = pow(c,d,n)
print(long_to_bytes(m).decode())

朱雀组

Crypto01——unsolved

easy_MNTRU.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
69
70
from sage.all import *
from sage.stats.distributions.discrete_gaussian_integer import DiscreteGaussianDistributionIntegerSampler
from secret import flag

std_limit = 0.01


def get_accurate_Discrete_Gaussian(sigma, limit=std_limit):
factor = 1
while True:
Df = DiscreteGaussianDistributionIntegerSampler(sigma * factor)
if abs(RR(std([Df() for _ in range(2 ** 15)])) - sigma) / sigma < limit:
return Df
factor += 0.01


def ZZ_to_Fq(_vector, _q, _n):
return [int(i % _q) if abs(_q - int(i % _q)) > int(i % _q) else (int(i % _q) - _q) for i in _vector] + [0] * (
_n - len(_vector))


def My_generator(Sampler, _n, limit=std_limit):
while True:
tmp = [Sampler() for _ in range(_n)]
if abs(RR(std(tmp)) - Sampler.sigma) < limit:
return tmp


def generate_key():
while True:
F = Matrix([[PRz(My_generator(Df, d)) for _ in range(n)] for _ in range(n)])
G = Matrix([[PRz(My_generator(Df, d)) for _ in range(k)] for _ in range(n)])
try:
H = F.change_ring(PRqm).inverse() * G.change_ring(PRqm)
H = Matrix([[PRz(Hij.lift()) for Hij in Hi] for Hi in H.transpose()]).transpose()
return F, G, H
except ArithmeticError:
continue


d = 64
q = 12289
p = 17
n = 2
k = 1
sigma_f, sigma_s, sigma_e = 0.4, 0.6, 0.6

PRq = PolynomialRing(Zmod(q), 'xq')
PRp = PolynomialRing(Zmod(p), 'xp')
PRz = PolynomialRing(ZZ, 'xz')
mod_polynomial = PRz.cyclotomic_polynomial(d * 2)
PRqm = PRq.quotient(mod_polynomial)
PRpm = PRp.quotient(mod_polynomial)
Df = get_accurate_Discrete_Gaussian(sigma_f)
Ds = get_accurate_Discrete_Gaussian(sigma_s)
De = get_accurate_Discrete_Gaussian(sigma_e)
m = []
base = int.from_bytes(flag, byteorder='big')
while base > 0:
m.append(int(base % p))
base = base // p
m = PRz(m)

s = vector([PRz(My_generator(Ds, d)) for _ in range(n)])
e = PRz(My_generator(Ds, d))
open('data.txt', 'w').write('H = ' + str([list(vi) for vi in H]) + '\n' + 'c = ' + str(c) + '\n')
"""
H = [[10164*xz^63 + 9000*xz^62 + 8286*xz^61 + 5227*xz^60 + 6181*xz^59 + 5761*xz^58 + 7446*xz^57 + 10719*xz^56 + 12069*xz^55 + 934*xz^54 + 7301*xz^53 + 10310*xz^52 + 3397*xz^51 + 474*xz^50 + 4342*xz^49 + 11687*xz^48 + 3326*xz^47 + 10295*xz^46 + 4112*xz^45 + 12233*xz^44 + 9436*xz^43 + 2831*xz^42 + 6611*xz^41 + 7190*xz^40 + 4559*xz^39 + 5945*xz^38 + 9605*xz^37 + 8836*xz^36 + 7632*xz^35 + 11091*xz^34 + 11966*xz^33 + 6096*xz^32 + 4209*xz^31 + 8470*xz^30 + 3059*xz^29 + 1260*xz^28 + 131*xz^27 + 6057*xz^26 + 4237*xz^25 + 6208*xz^24 + 3906*xz^23 + 9797*xz^22 + 11804*xz^21 + 8216*xz^20 + 4697*xz^19 + 9711*xz^18 + 10839*xz^17 + 2198*xz^16 + 9361*xz^15 + 10790*xz^14 + 2727*xz^13 + 7269*xz^12 + 10677*xz^11 + 12195*xz^10 + 11451*xz^9 + 752*xz^8 + 1282*xz^7 + 2990*xz^6 + 4491*xz^5 + 5352*xz^4 + 3448*xz^3 + 7551*xz^2 + 4702*xz + 427], [2097*xz^63 + 5773*xz^62 + 9022*xz^61 + 8544*xz^60 + 10555*xz^59 + 12163*xz^58 + 514*xz^57 + 5992*xz^56 + 2822*xz^55 + 7486*xz^54 + 9950*xz^53 + 6333*xz^52 + 8917*xz^51 + 4097*xz^50 + 11713*xz^49 + 7495*xz^48 + 1989*xz^47 + 10468*xz^46 + 3808*xz^45 + 5333*xz^44 + 1184*xz^43 + 6871*xz^42 + 4944*xz^41 + 630*xz^40 + 4644*xz^39 + 5582*xz^38 + 2200*xz^37 + 2970*xz^36 + 11908*xz^35 + 1946*xz^34 + 9833*xz^33 + 4771*xz^32 + 652*xz^31 + 3287*xz^30 + 2660*xz^29 + 5133*xz^28 + 6935*xz^27 + 2833*xz^26 + 10788*xz^25 + 12068*xz^24 + 362*xz^23 + 7765*xz^22 + 11454*xz^21 + 6499*xz^20 + 8140*xz^19 + 9100*xz^18 + 1642*xz^17 + 3282*xz^16 + 2028*xz^15 + 3867*xz^14 + 6458*xz^13 + 7408*xz^12 + 2944*xz^11 + 12257*xz^10 + 9911*xz^9 + 6711*xz^8 + 11102*xz^7 + 5603*xz^6 + 2554*xz^5 + 298*xz^4 + 9782*xz^3 + 1928*xz^2 + 2535*xz + 3668]]
c = 6085*xz^63 + 9658*xz^62 + 8682*xz^61 + 2660*xz^60 + 9268*xz^59 + 8059*xz^58 + 6842*xz^57 + 7810*xz^56 + 9166*xz^55 + 10543*xz^54 + 5037*xz^53 + 624*xz^52 + 8735*xz^51 + 7393*xz^50 + 1587*xz^49 + 11955*xz^48 + 9867*xz^47 + 8488*xz^46 + 6883*xz^45 + 8323*xz^44 + 4607*xz^43 + 195*xz^42 + 1357*xz^41 + 4753*xz^40 + 2225*xz^39 + 6728*xz^38 + 9472*xz^37 + 5292*xz^36 + 1132*xz^35 + 8998*xz^34 + 7379*xz^33 + 3055*xz^32 + 4360*xz^31 + 5320*xz^30 + 10615*xz^29 + 7225*xz^28 + 9062*xz^27 + 2879*xz^26 + 2527*xz^25 + 7636*xz^24 + 6341*xz^23 + 456*xz^22 + 1517*xz^21 + 10366*xz^20 + 5444*xz^19 + 2507*xz^18 + 8567*xz^17 + 12055*xz^16 + 6353*xz^15 + 8241*xz^14 + 7436*xz^13 + 11704*xz^12 + 5722*xz^11 + 3808*xz^10 + 11866*xz^9 + 4663*xz^8 + 11430*xz^7 + 7288*xz^6 + 9504*xz^5 + 10292*xz^4 + 1089*xz^3 + 6380*xz^2 + 6417*xz + 1991
"""

Crypto02

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
各位朱雀组参赛选手请注意,平台新增“CRYPTO02”赛题提示:
提示信息如下:请根据提示信息进一步完成解题。

1)RSA模数 n:

0x00b8cb1cca99b6ac41876c18845732a5cbfc875df346ee9002ce608508b5fcf6b60a5ac7722a2d64ef74e1443a338e70a73e63a303f3ac9adf198595699f6e9f30c009d219c7d98c4ec84203610834029c79567efc08f66b4bc3f564bfb571546a06b7e48fb35bb9ccea9a2cd44349f829242078dfa64d525927bfd55d099c024f

2)素数 p 的高位:

0xe700568ff506bd5892af92592125e06cbe9bd45dfeafe931a333c13463023d4f0000000000000000000000000000000000000000000000000000000000000000

3)加密指数 e:

0x10001

4)加密消息文件:flag.enc,你需要读取并解密此文件。

你的任务是通过给定的信息恢复素数 p,计算私钥 d,并解密加密消息以获得 flag。@全体成员

flag.enc

1
2
3
p7盡債3噮?%H仧?C垂粂跈[羀鮟zi盐誗迉??U<§鄡7-筙

猑徽狶€W?5醭*輑8' ?噉H传丏朠 颬/?w?鎬袆4技E\爙d?萘緍僞tx>?

给出p的高256位,爆8位coppersmith

exp

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

n = 0x00b8cb1cca99b6ac41876c18845732a5cbfc875df346ee9002ce608508b5fcf6b60a5ac7722a2d64ef74e1443a338e70a73e63a303f3ac9adf198595699f6e9f30c009d219c7d98c4ec84203610834029c79567efc08f66b4bc3f564bfb571546a06b7e48fb35bb9ccea9a2cd44349f829242078dfa64d525927bfd55d099c024f
p_high = 0xe700568ff506bd5892af92592125e06cbe9bd45dfeafe931a333c13463023d4f
pbits = 512
e = 0x10001
c = bytes_to_long(open('flag.enc','rb').read())


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

Crypto03

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#!/usr/bin/env python3

import random
from sympy import nextprime
from gmpy2 import is_prime
from Crypto.Util.number import getPrime, bytes_to_long
from Secret import flag

m = bytes_to_long(flag)

p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 2999

f = open("out.txt", 'w')

p1 = getPrime(1024)
q1 = nextprime(2024 * p1)
n1 = p1 * q1
f.write("n1 = {0}\n".format(n1))

p2 = getPrime(1024)
q2 = 1
while q2 < p2:
q2 = getPrime(1024)
n2 = p2 * q2
n22 = p2 * p2 + q2 * q2
f.write("n2 = {0}\n".format(n2))
f.write("n22 = {0}\n".format(n22))

r = random.getrandbits(1024)
p3 = r
while not is_prime(p3):
p3 += random.getrandbits(400)
q3 = r
while q3 < p3:
q3 += random.getrandbits(500)
while not is_prime(p3):
q3 += random.getrandbits(500)
n3 = p3 * q3
f.write("n3 = {0}\n".format(n3))

m1 = p1 * m * m + p2 * m + p3
m2 = q1 * m * m + q2 * m + q3
c1 = pow(m1, e, n)
c2 = pow(m2, e, n)

f.write("n = {0}\n".format(n))
f.write("c1 = {0}\n".format(c1))
f.write("c2 = {0}\n".format(c2))
"""
n1 =
n2 =
n22 =
n3 =
n =
c1 =
c2 =
"""

part1

第一部分
$$
n_1 = p\times (2024p + x)
$$
n1 // 2024开根号,爆破一点即可分解n1

part2

第二部分,利用下面两个式子分解n2
$$
n_2 = p\times q
$$

$$
n_{22} = p^2 + q^2
$$

那么有
$$
p+q = \sqrt{n_{22}+ 2n_2}
$$

$$
p-q = \sqrt{n_{22}- 2n_2}
$$

part3

经过测试

t = gmpy2.iroot(n3,2)[0],会发现要么p3 + q3 = 2 * t,要么p3 + q3 = 2*t + 1

那么我们就有了p3 + q3,这很容易就能分解出p3,q3了。

但实际的使用利用的等式是p3 * q3 == n3p3 + q3 == 2*t + 2有点奇怪

三个n都分解了之后用相关消息攻击,e为2999,比较大,用H-GCD

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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
from Crypto.Util.number import *
import gmpy2
import sys

def HGCD(a, b):
if 2 * b.degree() <= a.degree() or a.degree() == 1:
return 1, 0, 0, 1
m = a.degree() // 2
a_top, a_bot = a.quo_rem(x^m)
b_top, b_bot = b.quo_rem(x^m)
R00, R01, R10, R11 = HGCD(a_top, b_top)
c = R00 * a + R01 * b
d = R10 * a + R11 * b
q, e = c.quo_rem(d)
d_top, d_bot = d.quo_rem(x^(m // 2))
e_top, e_bot = e.quo_rem(x^(m // 2))
S00, S01, S10, S11 = HGCD(d_top, e_top)
RET00 = S01 * R00 + (S00 - q * S01) * R10
RET01 = S01 * R01 + (S00 - q * S01) * R11
RET10 = S11 * R00 + (S10 - q * S11) * R10
RET11 = S11 * R01 + (S10 - q * S11) * R11
return RET00, RET01, RET10, RET11

def GCD(a, b):
print(a.degree(), b.degree())
q, r = a.quo_rem(b)
if r == 0:
return b
R00, R01, R10, R11 = HGCD(a, b)
c = R00 * a + R01 * b
d = R10 * a + R11 * b
if d == 0:
return c.monic()
q, r = c.quo_rem(d)
if r == 0:
return d
return GCD(d, r)

sys.setrecursionlimit(500000)

n1 =
n2 =
n22 =
n3 =
n =
c1 =
c2 =
e = 2999

# factor n1
t1 = gmpy2.iroot(n1 // 2024,2)[0]
for i in range(-100000,100000):
p1 = t1 + i
if n1 % p1 == 0:
q1 = n1 // p1
break
if p1 > q1:
p1,q1 = q1,p1

# factor n2
p_add_q = gmpy2.iroot(n22 + 2*n2,2)[0]
p_sub_q = gmpy2.iroot(n22 - 2*n2,2)[0]
p2 = (p_add_q + p_sub_q) // 2
q2 = n2 // p2

if p2 > q2:
p2,q2 = q2,p2

# factor n3
t3 = 2*gmpy2.iroot(n3,2)[0] + 2
p_add_q = t3
p_sub_q = gmpy2.iroot((p_add_q)**2 - 4*n3,2)[0]
p3 = (p_add_q + p_sub_q) // 2
q3 = (p_add_q - p_sub_q) // 2

if p3 > q3:
p3,q3 = q3,p3

p1,q1 = int(p1),int(q1)
p2,q2 = int(p2),int(q2)
p3,q3 = int(p3),int(q3)

###### Franklin-Reiter
R.<x> = PolynomialRing(Zmod(n))
f = (p1 * x * x + p2 * x + p3)^e - c1
g = (q1 * x * x + q2 * x + q3)^e - c2

res = GCD(f,g)

m = -res.monic().coefficients()[0]
print(m)
flag = long_to_bytes(int(m))
print(flag)

玄武组

Crypto01——unsolved

task.sage

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
# SageMath version 10.0, Release Date: 2023-05-20

from sage.all import *
from Crypto.Util.number import *

from secret import flag
flag = flag.lstrip(b"wdflag{").rstrip(b"}")

class ShamirSS:
def __init__(self, coefs, value):
self.coefs = coefs
self.value = value

class ShamirProtocol:
def __init__(self, n_players, threshold, modulus):
self.n_players = n_players
self.threshold = threshold

assert isPrime(modulus), "Modulus must be a prime number"
self.modulus = modulus


def input_share(self, values):
coefs = [
[getRandomRange(1, self.modulus) for _ in range(self.threshold)]
for _ in range(self.n_players)
]

randoms = values + [getRandomRange(1, self.modulus) for _ in range(self.threshold - len(values))]

values = [
sum([r * c for r, c in zip(randoms, coef)]) % self.modulus
for coef in coefs
]

shares = [ShamirSS(coef, value) for coef, value in zip(coefs, values)]
return shares



protocol = ShamirProtocol(len(flag), len(flag) * 2, 257)
values = list(flag)

import os
os.mkdir("shares")

for i in range(10000):
shares = protocol.input_share(values)
save(shares, f"shares/share_{i}.sobj")

shares数据太大

Crypto02——unsolved

main.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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
from Crypto.PublicKey import RSA
from Crypto.Cipher import AES
from pkcs1 import encode, decode
import os
import hashlib
import signal


FLAG = os.getenv("FLAG", "wdflag{******************************}")

class RSA_OT:

def __init__(self, key: RSA):
self.key = key
self.n = key.n
self.e = key.e
self.d = key.d
self.nbyte = key.size_in_bytes()

@staticmethod
def new(nbits: int) -> "RSA_OT":
key = RSA.generate(nbits)
return RSA_OT(key)

def encrypt(self, message: bytes) -> bytes:
padded = encode(message, self.nbyte)
ct = self.key._encrypt(padded)
return int(ct).to_bytes(self.nbyte, "big")

def decrypt(self, ciphertext: bytes) -> bytes:
padded = self.key._decrypt(int.from_bytes(ciphertext, "big"))
return decode(padded)

def show_public_key(self):
print("[+] n =", self.n)
print("[+] e =", self.e)

def run(self, m0, m1):
print("[+] OT Protocol Starts")
m0 = int.from_bytes(encode(m0, self.nbyte), "big")
m1 = int.from_bytes(encode(m1, self.nbyte), "big")
x0 = int.from_bytes(os.urandom(self.nbyte), "big") % self.n
x1 = int.from_bytes(os.urandom(self.nbyte), "big") % self.n
print(f"[+] x0 = {x0}")
print(f"[+] x1 = {x1}")
v = int(input("[+] v = "))
M0 = (m0 + pow(v - x0, self.d, self.n)) % self.n
M1 = (m1 + pow(v - x1, self.d, self.n)) % self.n
print(f"[+] M0 = {M0}")
print(f"[+] M1 = {M1}")
print("[+] OT Protocol Ends")

def xor(a: bytes, b: bytes) -> bytes:
return bytes(x ^ y for x, y in zip(a, b))

def challenge(rounds = 70):
aes_key = os.urandom(32)
xor_key = os.urandom(32)
aes = AES.new(aes_key, AES.MODE_ECB)
rsa_ot = RSA_OT.new(1024)
secrets = [os.urandom(32) for i in range(rounds)]
message_pairs = [(aes_key, xor_key)]
message_pairs += [(aes.encrypt(secret), xor(xor_key, secret)) for secret in secrets]
signal.alarm(120)
print("[+] Sharing secrets through aes or xor, I won't know which one is used.")
rsa_ot.show_public_key()
for i, (m0, m1) in enumerate(message_pairs):
print(f"[+] Round {i + 1}")
rsa_ot.run(m0, m1)
print("[+] All OTs Done!")
verify_hash = hashlib.sha256(b''.join(secrets)).hexdigest()
credential = input("[+] prove that you are honest: ").strip()
if credential == verify_hash:
print("[+] You are an honest player.")
else:
print("[+] Lies detected.")
return

master = hashlib.sha256(aes_key + xor_key).hexdigest()
credential = input("[+] prove that you know both keys: ").strip()

if credential == master:
print(f"[+] Here is your flag: {FLAG}")
else:
print("[+] You are too honest!")
return

if __name__ == "__main__":
challenge()

pkcs1.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
import os

def encode(message, k, ps=None):
'''Take a message of length inferior to k - 11 and return
the concatenation of length k:

0x00 || 0x02 || PS || 0x00 || message

where PS is a random string containing no zero byte of length
k - len(message) - 3.

message - the message to encode, a byte string
k - the length of the padded byte string
ps - a fixed string to use instead of generating a random one, it's
necessary for testing using test vectors,
rnd - the random generator to use, it must conform to the interface of
the random.Random class.
'''
m_len = len(message)
if m_len > k - 11:
raise Exception('MessageTooLong')
ps_len = k - len(message) - 3
if ps:
if len(ps) != ps_len:
raise Exception('wrong ps length', len(ps), ps_len)
else:
ps = b""
while len(ps) != ps_len:
byte = os.urandom(1)
if byte != b"\x00":
ps += byte
return b'\x00\x02' + ps + b'\x00' + message

def decode(message: bytes):
'''
Verify that a padded message conform to the PKCSv1 1.5 encoding and
return the unpadded message.
'''
if message[:2] != b'\x00\x02':
raise Exception('DecryptionError')
i = message.find(b'\x00', 2)
if i == -1:
raise Exception('DecryptionError')
if i < 10:
raise Exception('DecryptionError')
return message[i+1:]

-------------已经到底啦!-------------