ZJGSUCTF-2019-前身与后世

系里让为这次CTF出一道题,就想弄一道基础的格密码,其实稍微看看书并善用摆渡这题不是太难,然而并没人做出来,分享到这里吧。。。

题目描述

结合材料回答问题

1. 前生

《保密系统的通信理论》标志着密码学作为一门科学就此诞生,《密码学的新方向》提出公钥密码思想让密码学实现了又一次飞跃,Martin Hellman提出了第一个公钥密码算法后,公钥密码飞速发展,已成为安全基石。

2. 后世

公钥密码学自提出到现在已经发展了近40年,它在加密,签名及密码协议各个方面都有了丰富的成果,然而目前广泛使用的非对称加密算法(RSA,ECC,Elgama等)都是基于大整数因子分解,离散对数问题,而Shor提出的量子算法可以在多项式时间内解出这些难题,也就意味着将来量子计算机可用时当前这些算法就不再安全,后量子密码又是一种前途光明的方向了。

题目

勇敢的少年哟,仔细阅读以上材料后,请写下你的感受(当然这不给分),这里给你密文与公钥,试试能不能解出它的明文啪。

给出的题目文件由以下代码生成,解题代码也在此处,简单说下思路,本题是前生是MH背包密码,这在书上就说了不安全并且能用格算法在很短时间内解出,通过百度也会发现已经在CTF比赛上存在过该类题了,在解出第一步后,由题目能猜出第二步应该是一种后量子密码,而且第一步也用到了格算法,那么猜测为GGH算法,同理使用格基规约即可求出AES密钥。。。

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
# -*- coding: utf-8 -*-
"""
Created on Sat Apr 27 09:54:25 2019

@author: WxJun
"""
from sage.all import *
import random
#import gmpy2
import binascii
from codecs import encode,decode
from Crypto.Cipher import AES
from functools import reduce
import numpy as np
def s2v(s):
data = []
for i in range(len(s)//2):
data.append(ord(s[i*2])*(2**8)+ord(s[i*2+1]))
return data
def v2s(v):
"""数字列表(向量)转字符串。
将向量每个元素视作两字节。
args:
v: 向量,如:[123, 13, 456]
return:
返回字符串
"""
b = []
for i in v:
b.append(i//(2**8))
b.append(i%(2**8))
b = ''.join(map(lambda x:chr(x),b))
return b
def hadamard(A):
if not A.is_square():
raise Exception('must be square!')
n = A.dimensions()[0]
muls = reduce(lambda x,y:x*y, map(lambda x:x.norm(), A.rows()))
return (abs(A.det())/muls)**(1./n)

def mh_make_key(n):
privKey = [random.randint(1, 4**n)]
s = privKey[0]
for i in range(1, n):
privKey.append(random.randint(s + 1, 4**(n + i)))
s += privKey[i]
q = random.randint(privKey[n-1] + 1, 2*privKey[n-1])
r = random.randint(1, q)
while gcd(r, q) != 1:
r = random.randint(1, q)
pubKey = [ r*w % q for w in privKey ]
return privKey, q, r, pubKey

def mh_encrypt(plainText, pubKey):
"""使用AES256加密数据,密钥使用pubKey加密"""
if not plainText:
return None
if not isinstance(plainText, bytes):
plainText = plainText.encode('ascii')
msg_bit = bin(int(encode(plainText,'hex'), 16))[2:]
msg_bit = msg_bit.rjust(128, '0')
if len(msg_bit) != len(pubKey):
raise Exception('出错啦!')
cipher = 0
for i, bit in enumerate(msg_bit):
cipher += int(bit)*pubKey[i]
return cipher
def mh_decrypt(cipher, sk, q, r):
pass
def aes_make_key(key_len=128):
key = AES.get_random_bytes(key_len//8)
iv = AES.get_random_bytes(128//8)
return key, iv
def aes_enc(msg, key=None, iv=None, key_len=128):
"""aes加密,加密密钥在内部随机生成。
Args:
msg: 要加密的明文数据。
key: 指定加密密钥,否则随机生成,默认为None
key_len: 密钥的长度,key为None时生效。可选128,192,256,默认128
Return:
一个元组(cipher, key)表示加密后的密文与加密用的key。
"""
if key_len not in (128, 192, 256):
raise Exception('key_len长度错误!')
if not key:
key = 00#AES.get_random_bytes(key_len//8)
if not iv:
iv = key[:16]
if not isinstance(msg, bytes):
msg = msg.encode('utf8')
msg += b'\x00' * (16 - len(msg)%16)
aes = AES.new(key, AES.MODE_CBC, iv)
cipher = aes.encrypt(msg)
return cipher, key, iv
def aes_dec(cipher, key, iv):
if cipher and key and iv:
aes = AES.new(key, AES.MODE_CBC, iv)
return aes.decrypt(cipher)
def mh_crack(A, S):
"""使用格基规约算法求SVP破解MH密码。
Args:
A: 背包密码的公钥,为向量。
S: 密文,为一个大数。
Return:
返回解密后的明文。
"""
dims = len(A)+1
B = Matrix(ZZ, dims)
# fill in the identity matrix
for i in range(dims-1):
B[i, i] = 1
B[i, -1] = A[i]
B[-1, -1] = -int(S)
res = B.LLL()
for i in range(0, dims):
# print solution
M = res.row(i).list()
flag = True
for m in M:
if m != 0 and m != 1:
flag = False
break
if flag:
print(i, M)
M = ''.join(str(j) for j in M)
M = M[:-1]
M = hex(int(M, 2))[2:-1]
return decode(M, 'hex')

def ggh_make_key(n, gh=0.9, bh=0.2, try_time=1000):
"""生成GGH加密的密钥
Args:
n: 安全参数,及矩阵大小,n x n
gh: 优质基hadamard比率
bh: 劣质基hadamard比率
try_time: 尝试次数
Returns:
(sk, pk, r)
"""
def gen_det_one_matrix(n):
"""生成秩为1的矩阵(实际算法正负1都可以)"""
det_one_matrix = Matrix.identity(n)
for i in range(n):
for j in range(i):
if random.random() > 0.5:
det_one_matrix[i,j] = random.randint(-100,100)
return det_one_matrix
if False:
sk = np.random.randint(-100, 100, size=(n,n))

else:
for i in range(try_time):
sk = np.random.randint(-100, 100, size=(n,n))
sk = Matrix(ZZ, sk)
print('raw sk H:'+ str(hadamard(sk)))
sk = sk.LLL()
h = hadamard(sk)
print('lll sk H' + str(h))
if h >= gh:
break
if i == try_time - 1:
return None
pk = sk
U = None
for i in range(try_time):
U = gen_det_one_matrix(n)
pk = U*pk
h = hadamard(pk)
if h <= bh:
break
if i == try_time - 1:
return None
r = np.random.randint(-3,3,size=(n,))
r = Matrix(ZZ, r.tolist())
return sk, pk, r
def ggh_encrypt(msg, pk, r):
if isinstance(msg, str):
msg_len = len(msg)
v = s2v(msg)
m = matrix(ZZ,v)
else:
m = msg
pk_len = pk.dimensions()[0]
print('msg:', str(m))
e = m*pk + r
return e
#msg_len
def ggh_decrypt(cipher, sk, pk):
v = cipher*(sk.inverse())
v = matrix_round(v)
print(v)
return v*sk*pk.inverse()
def ggh_test():
V = matrix(ZZ,[
[81,15,17,60,29],
[-53,7,49,46,-11],
[2,84,6,-68,-97],
[11,-96,92,70,-70],
[28,-58,98,-89,24]])
U = matrix(ZZ,[
[16,111,139,-16,-95],
[-91,-642,-747,185,471],
[-103,-677,-1133,492,524],
[-21,-145,-190,55,111],
[-10,-86,9,-82,62]])
print(hadamard(V))
W = matrix(ZZ,[
[-7145,19739,-4237,3949,-15400],
[40384,-113685,25691,-13165,75236],
[45356,-179080,54894,27526,92497],
[9317,-29008,7336,-1039,18230],
[4600,4280,-5798,-16426,7011]
])
W1 = U*V
print(hadamard(W1))
print(hadamard(W))
m = matrix(ZZ,[-78,48,5,66,89])
r = matrix(ZZ,[-9,-5,1,-2,4])
e = ggh_encrypt(m,W,r)
mm = ggh_decrypt(e,V,W)
mm1 = ggh_decrypt(e,W.LLL(),W)
raw_input('##')
def matrix_round(A):
rs, cs = A.dimensions()
for i in range(rs):
for j in range(cs):
A[i,j] = round(A[i,j])
return A
def main():
#fun = ForFun()
#cipher, key = fun.aes_enc('zjgsctf{hahahahahahha}')
#test_case = b'\xfcG\xe9&fao\xca\xb3:^\xaf\xb4G\xdc\xd8'
#fun.ggh_make_key(8)
#a = fun.aes_make_key()

# md5(B2taMa0_DiDiDi,32) = 932b4f54526f8006387fc1f1298ecd58
flag = 'ZJGSUCTF{932b4f54526f8006387fc1f1298ecd58}'
aes_key = b'\x18\x1a\x16\xd5\xcc\xb5wz\x1d\x95\xe6\xfe\xd6\x06\xeb\x93'
aes_iv = b'\x06|\x84\xb1\x8a\x1c\x1c4V\x8d0\xd5\xbf\x02\x8d\xfc'
#fun.mh_make_key()
#with open('aes_key.txt', 'w') as f:
# f.write()
sk, q, r, pk = mh_make_key(128)
key_cipher = mh_encrypt(aes_key,pk)
with open('mh_test.txt', 'w') as f:
f.write('pk:{}\nkey_cipher:{}\n'.format(str(pk),str(key_cipher)))
msg = mh_crack(pk,key_cipher)
sk, pk, r = ggh_make_key(8)
iv_cipher = ggh_encrypt(aes_iv,pk,r)
msg = ggh_decrypt(iv_cipher, pk.BKZ(), pk)
print('dec:', msg)
with open('ggh_test.txt', 'w') as f:
f.write('pk:{}\niv_cipher:{}\n'.format(str(pk), str(iv_cipher)))
flag_aes_cipher = aes_enc(flag, aes_key, aes_iv)[0]
with open('flag_aes_cipher', 'wb') as f:
f.write(flag_aes_cipher)

#ggh_test()
#print(makeKey(64)[3])
main()