NepCTF2022 个人输出复盘

2022-08-04 约 1946 字预计阅读 10 分钟

Reverse 手不务正业实录

Crypto-p or s

题目脚本

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57


from secret import keys, flag
from Crypto.Util.number import *
assert(len(keys)==6)
Pbox=[
[0, 3, 6, 9, 10, 11, 13, 16, 18, 19, 20, 24, 25, 27, 28, 29, 30, 31],
[0, 1, 3, 8, 9, 11, 12, 14, 16, 18, 19, 23, 24, 25, 26, 28, 29],
[0, 1, 2, 3, 9, 10, 11, 13, 19, 20, 22, 25, 27, 28, 29, 31],
[0, 2, 3, 5, 6, 7, 8, 13, 16, 19, 21, 25, 26, 27, 28],
[2, 4, 6, 7, 9, 11, 12, 13, 16, 17, 20, 21, 22, 23, 24, 25, 27, 31],
[2, 10, 13, 15, 16, 17, 21, 22, 23, 24, 29, 31],
[1, 2, 8, 11, 12, 13, 16, 17, 19, 21, 22, 24, 25, 26, 27, 28, 30, 31],
[0, 3, 6, 13, 14, 17, 19, 21, 22, 23, 26, 27, 28],
[1, 5, 7, 8, 11, 12, 14, 15, 19, 23, 25, 27, 31],
[0, 2, 3, 6, 7, 8, 9, 10, 11, 12, 16, 18, 19, 22, 23, 24, 25, 26, 27, 28],
[0, 1, 6, 7, 10, 15, 16, 21, 24, 25, 29, 30],
[1, 4, 5, 6, 7, 12, 13, 15, 18, 19, 20, 22, 26, 27, 29, 31],
[0, 3, 5, 8, 9, 17, 21, 22, 24, 25, 26, 27, 30],
[0, 2, 3, 4, 5, 6, 7, 8, 11, 17, 19, 20, 24, 25, 26, 27, 30],
[2, 6, 7, 8, 11, 12, 14, 16, 20, 21, 22, 24, 29, 30, 31],
[0, 2, 5, 6, 7, 8, 9, 10, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 25, 29, 31],
[0, 1, 2, 3, 4, 5, 8, 10, 11, 12, 13, 16, 17, 18, 20, 21, 22, 23, 25, 26, 28, 29, 30],
[3, 5, 6, 8, 10, 13, 14, 17, 19, 20, 21, 22, 24, 26, 27, 29, 30],
[1, 3, 6, 12, 14, 15, 16, 17, 18, 21, 24, 25, 26, 27, 28],
[0, 1, 2, 3, 5, 6, 7, 8, 9, 12, 13, 19, 20, 23, 26, 29, 30],
[3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 16, 20, 21, 22, 25, 26, 27, 28, 29, 30],
[0, 1, 2, 4, 6, 7, 9, 10, 11, 13, 15, 16, 18, 19, 20, 21, 25, 31],
[0, 2, 7, 10, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 25, 29, 31],
[1, 2, 3, 5, 7, 8, 18, 19, 21, 22, 23, 25, 31],
[3, 4, 7, 8, 10, 11, 13, 14, 17, 18, 19, 21, 22, 23, 24, 28, 29],
[0, 2, 6, 7, 8, 10, 11, 12, 13, 16, 18, 19, 21, 23, 31],
[0, 1, 3, 4, 8, 13, 14, 16, 18, 19, 21, 26, 27, 30, 31],
[5, 6, 7, 9, 13, 14, 15, 18, 19, 20, 21, 24, 25, 28],
[1, 3, 4, 5, 6, 7, 11, 14, 16, 17, 19, 20, 21, 22, 23, 25, 30, 31],
[2, 3, 4, 6, 7, 11, 13, 17, 18, 19, 20, 23, 24, 25, 26, 28, 29, 30, 31],
[0, 1, 2, 3, 4, 7, 9, 10, 13, 15, 16, 19, 22, 23, 24, 25, 27],
[0, 1, 3, 4, 12, 16, 18, 19, 26, 30]]

def enc(v, keys):
    t=v
    for i in keys:
       q=[]
       for j in Pbox:
           q.append(sum([t[k] for k in j])%2)
       t=[int(q[j])^int(i[j]) for j in range(32)]
    return t

assert(len(flag)==32)
fb=bin(bytes_to_long(flag))[2:].zfill(32*8)
ciphertext=""
for i in range(0,len(fb),32):
    t=enc([int(j) for j in fb[i:i+32]])
    ciphertext+="".join([str(j) for j in t])
 
print(ciphertext)
'''
0111110000100101000001101011110111101100000010110011101111000101111110111111100100100010001011000101000110110011111101000001001000000101111000001110001111001001100100111000011011101111111101001011100000100100110011111101100111001100111111110001111011101100
'''

GF(2) 上的方程组，4个字符（32bit）一组分段加密，含有未知的 6 个 32 维 key 向量。拿到 key 即可解出 flag。通过 flag 格式可知第一组的明文flag和加密结果，考虑使用这些解出 key。

对于密文的每一位，考虑求出所有 key 向量对其的影响，可以将 6 个 32 维 key 向量对加密结果造成的影响简化成一个 32 维的向量 key'。

设明文$A=[a_1\ a_2\ …\ a_{32}]$，密文为$B=[b_1\ b_2\ …\ b_{32}]$，$key'=[key_1\ key_2\ …\ key_{32}]$则对于每一个$b_i$，可以得到以下方程： $$ [a_1\ a_2\ a_3\ …\ a_{32}]·X_i = b_i + key_i $$

其中$X_i$是一个 32 维列向量。考虑依次将向量$[1\ 0\ 0…0]$、$[0\ 1\ 0…0]$、$[0\ 0\ 1\ …\ 0]$、…、$[0\ 0\ 0…1]$放入黑盒中加密，即可很方便地求出向量$X_i$。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


def simu(v):
    t=v
    for i in range(6):
       q=[]
       for j in Pbox:
           q.append(sum([t[k] for k in j])%2)
       t=[int(q[j]) for j in range(32)]
    return t
res = []
for i in range(32):
	s = [0 for j in range(32)]
	s[i] = 1
	res.append(simu(s))

随后利用已知的第一段明文解出向量key'。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


table = []
for i in range(32):
	q = []
	for j in range(32):
		q.append(res[j][i])
	table.append(q)
ciphertext = "0111110000100101000001101011110111101100000010110011101111000101111110111111100100100010001011000101000110110011111101000001001000000101111000001110001111001001100100111000011011101111111101001011100000100100110011111101100111001100111111110001111011101100"

flagcip = ciphertext[:32]
flagplain = b"flag"
fb = bin(bytes_to_long(flagplain))[2:].zfill(32)
x = [int(j) for j in fb]
cip = [int(j) for j in flagcip]

key = []
for i in range(32):
	key.append((sum([table[i][j]*x[j] for j in range(32)])+cip[i])%2)
print("[+] Key:", key)

然后即可利用这些信息直接求得 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
 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


#from secret import keys
from Crypto.Util.number import *
#assert(len(keys)==6)
Pbox=[
[0, 3, 6, 9, 10, 11, 13, 16, 18, 19, 20, 24, 25, 27, 28, 29, 30, 31],
[0, 1, 3, 8, 9, 11, 12, 14, 16, 18, 19, 23, 24, 25, 26, 28, 29],
[0, 1, 2, 3, 9, 10, 11, 13, 19, 20, 22, 25, 27, 28, 29, 31],
[0, 2, 3, 5, 6, 7, 8, 13, 16, 19, 21, 25, 26, 27, 28],
[2, 4, 6, 7, 9, 11, 12, 13, 16, 17, 20, 21, 22, 23, 24, 25, 27, 31],
[2, 10, 13, 15, 16, 17, 21, 22, 23, 24, 29, 31],
[1, 2, 8, 11, 12, 13, 16, 17, 19, 21, 22, 24, 25, 26, 27, 28, 30, 31],
[0, 3, 6, 13, 14, 17, 19, 21, 22, 23, 26, 27, 28],
[1, 5, 7, 8, 11, 12, 14, 15, 19, 23, 25, 27, 31],
[0, 2, 3, 6, 7, 8, 9, 10, 11, 12, 16, 18, 19, 22, 23, 24, 25, 26, 27, 28],
[0, 1, 6, 7, 10, 15, 16, 21, 24, 25, 29, 30],
[1, 4, 5, 6, 7, 12, 13, 15, 18, 19, 20, 22, 26, 27, 29, 31],
[0, 3, 5, 8, 9, 17, 21, 22, 24, 25, 26, 27, 30],
[0, 2, 3, 4, 5, 6, 7, 8, 11, 17, 19, 20, 24, 25, 26, 27, 30],
[2, 6, 7, 8, 11, 12, 14, 16, 20, 21, 22, 24, 29, 30, 31],
[0, 2, 5, 6, 7, 8, 9, 10, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 25, 29, 31],
[0, 1, 2, 3, 4, 5, 8, 10, 11, 12, 13, 16, 17, 18, 20, 21, 22, 23, 25, 26, 28, 29, 30],
[3, 5, 6, 8, 10, 13, 14, 17, 19, 20, 21, 22, 24, 26, 27, 29, 30],
[1, 3, 6, 12, 14, 15, 16, 17, 18, 21, 24, 25, 26, 27, 28],
[0, 1, 2, 3, 5, 6, 7, 8, 9, 12, 13, 19, 20, 23, 26, 29, 30],
[3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 16, 20, 21, 22, 25, 26, 27, 28, 29, 30],
[0, 1, 2, 4, 6, 7, 9, 10, 11, 13, 15, 16, 18, 19, 20, 21, 25, 31],
[0, 2, 7, 10, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 25, 29, 31],
[1, 2, 3, 5, 7, 8, 18, 19, 21, 22, 23, 25, 31],
[3, 4, 7, 8, 10, 11, 13, 14, 17, 18, 19, 21, 22, 23, 24, 28, 29],
[0, 2, 6, 7, 8, 10, 11, 12, 13, 16, 18, 19, 21, 23, 31],
[0, 1, 3, 4, 8, 13, 14, 16, 18, 19, 21, 26, 27, 30, 31],
[5, 6, 7, 9, 13, 14, 15, 18, 19, 20, 21, 24, 25, 28],
[1, 3, 4, 5, 6, 7, 11, 14, 16, 17, 19, 20, 21, 22, 23, 25, 30, 31],
[2, 3, 4, 6, 7, 11, 13, 17, 18, 19, 20, 23, 24, 25, 26, 28, 29, 30, 31],
[0, 1, 2, 3, 4, 7, 9, 10, 13, 15, 16, 19, 22, 23, 24, 25, 27],
[0, 1, 3, 4, 12, 16, 18, 19, 26, 30]]

def enc(v, keys):
    t=v
    for i in keys:
       q=[]
       for j in Pbox:
           q.append(sum([t[k] for k in j])%2)
       t=[int(q[j])^int(i[j]) for j in range(32)]
    return t
"""
assert(len(flag)==32)
fb=bin(bytes_to_long(flag))[2:].zfill(32*8)
ciphertext=""
for i in range(0,len(fb),32):
    t=enc([int(j) for j in fb[i:i+32]])
    ciphertext+="".join([str(j) for j in t])
 
print(ciphertext)
"""
def calculate_parameter(a, prm, n):
	for i in range(n):
		p = i
		for j in range(i+1, n):
			if a[j][i] > a[p][i]:
				p = j
		for j in range(n+1):
			tmp = a[i][j]
			a[i][j] = a[p][j]
			a[p][j] = tmp
		for j in range(n):
			if not i == j:
				tt = a[j][i] * pow(a[i][i], prm-2, prm)
				for k in range(i, n+1):
					a[j][k] = (a[j][k] - a[i][k] * tt % prm + prm) % prm
	res = []
	for i in range(n):
		res.append(a[i][n] * pow(a[i][i], prm-2, prm) % prm)
	return res

ciphertext = "0111110000100101000001101011110111101100000010110011101111000101111110111111100100100010001011000101000110110011111101000001001000000101111000001110001111001001100100111000011011101111111101001011100000100100110011111101100111001100111111110001111011101100"

flagcip = ciphertext[:32]
flagplain = b"flag"
fb = bin(bytes_to_long(flagplain))[2:].zfill(32)
x = [int(j) for j in fb]
cip = [int(j) for j in flagcip]
def simu(v):
    t=v
    for i in range(6):
       q=[]
       for j in Pbox:
           q.append(sum([t[k] for k in j])%2)
       t=[int(q[j]) for j in range(32)]
    return t
res = []
for i in range(32):
	s = [0 for j in range(32)]
	s[i] = 1
	res.append(simu(s))
table = []
for i in range(32):
	q = []
	for j in range(32):
		q.append(res[j][i])
	table.append(q)

key = []
for i in range(32):
	key.append((sum([table[i][j]*x[j] for j in range(32)])+cip[i])%2)
print("[+] Key:", key)
realflagbin = ""
for i in range(0, len(ciphertext), 32):
	r = [int(j) for j in ciphertext[i:i+32]]
	#print(r)
	for j in range(32):
		r[j] ^= key[j]
	bb = []
	for j in range(32):
		aa = []
		for what in table[j]:
			aa.append(what)
		aa.append(r[j])
		bb.append(aa)
	solved = calculate_parameter(bb, 2, 32)
	realflagbin += "".join([str(j) for j in solved])

print(long_to_bytes(int(realflagbin, 2)))

Crypto-中学数学

题目如下

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


from gmpy2 import *
from Crypto.Util.number import *
from secret import flag
p = getPrime(1024)
q = next_prime(p+(p>>500))
n = p*q 
e = 0x10001
m = bytes_to_long(flag)
c = pow(m, e, n)
'''
n = 13776679754786305830793674359562910178503525293501875259698297791987196248336062506951151345232816992904634767521007443634017633687862289928715870204388479258679577315915061740028494078672493226329115247979108035669870651598111762906959057540508657823948600824548819666985698501483261504641066030188603032714383272686110228221709062681957025702835354151145335986966796484545336983392388743498515384930244837403932600464428196236533563039992819408281355416477094656741439388971695931526610641826910750926961557362454734732247864647404836037293509009829775634926600458845832805085222154851310850740227722601054242115507
c = 6253975396639688013947622483271226838902346034187241970785550830715516801386404802832796746428068354515287579293520381463797045055114065533348514688044281004266071342722261719304097175009672596062130939189624163728328429608123325223000160428261082507446604698345173189268359115612698883860396660563679801383563588818099088505120717238037463747828729693649297904035253985982099474025883550074375828799938384533606092448272306356003096283602697757642323962299153853559914553690456801745940925602411053578841756504799815771173679267389055390097241148454899265156705442028845650177138185876173539754631720573266723359186
'''

看起来 p 和 q 的关系难以处理，但是可以发现 n = p*q 和 p 是正比关系，直接考虑二分p。

完整 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


from gmpy2 import *
from Crypto.Util.number import *
#from secret import flag
#p=getPrime(1024)
#q=next_prime(p+(p>>500))
 
e = 0x10001
n = 13776679754786305830793674359562910178503525293501875259698297791987196248336062506951151345232816992904634767521007443634017633687862289928715870204388479258679577315915061740028494078672493226329115247979108035669870651598111762906959057540508657823948600824548819666985698501483261504641066030188603032714383272686110228221709062681957025702835354151145335986966796484545336983392388743498515384930244837403932600464428196236533563039992819408281355416477094656741439388971695931526610641826910750926961557362454734732247864647404836037293509009829775634926600458845832805085222154851310850740227722601054242115507
c = 6253975396639688013947622483271226838902346034187241970785550830715516801386404802832796746428068354515287579293520381463797045055114065533348514688044281004266071342722261719304097175009672596062130939189624163728328429608123325223000160428261082507446604698345173189268359115612698883860396660563679801383563588818099088505120717238037463747828729693649297904035253985982099474025883550074375828799938384533606092448272306356003096283602697757642323962299153853559914553690456801745940925602411053578841756504799815771173679267389055390097241148454899265156705442028845650177138185876173539754631720573266723359186
R = 117374101720892025379926580554846261172050814835019928395780473173988319063025811236820315274901477473357362631312549265502060280672262331623398126551102411368254100359545898567189007742828060352893742491663283756824477966687393803226060355532504331569001619648536493882952835335488931507816927988398082228539
L = 1
while L < R:
	p = (L+R) >> 1
	q = next_prime(p+(p>>500))
	print(p)
	if p*q == n:
		print("[+]P:", p)
		print("[+]Q:", q)
		break
	if p*q > n:
		R = p
	else:
		L = p

phi = (p-1)*(q-1)
d = invert(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m))

目录

NepCTF2022 个人输出复盘

Crypto-p or s

Crypto-中学数学