0%

2022年春秋杯网络安全联赛春季赛·Crypto WP

2022年春秋杯网络安全联赛春季赛·Crypto

勇者山峰与传说殿堂都看了题

九点开始守着看的是勇者山峰

当时只有了一道300分的题

notKnapsack

题目

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
#!/usr/bin/python3
# -*- coding: utf-8 -*-
import random

from Crypto.Util.number import bytes_to_long
from secret import FLAG

assert FLAG.startswith(b'flag{') and FLAG.endswith(b'}')

q = 210767327475911131359308665806489575328083

flag_bin = bin(bytes_to_long(FLAG[5:-1]))[2:]
l = len(flag_bin)

n = random.randint(l, 2*l)
cipher = []
for _ in range(n):
r = [random.randint(2, q-2) for _ in range(l)]
s = 1
for i in range(l):
s = s * r[i] ** int(flag_bin[i]) % q
cipher.append([r, s])

with open('output.txt', 'w') as f:
f.write(str(cipher))

对output简单处理了下,然后分析加密代码,可知这是累积的特殊背包问题,搜寻无果,z3不好用。

仔细看题目,说不是背包,或许另有妙计。

时间已过去两个半小时。

十一点半,刷新发现又上了一道500分题

Train

题目

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
from Crypto.Util.number import*
from hashlib import sha256
import socketserver
import signal
import string
import random
from secret import flag

banner = br'''
.oooooo..o oooo oooo ooooooooooooo o8o
d8P' `Y8 `888 `888 8' 888 `8 `"'
Y88bo. ooo. .oo. .oo. .oooo. 888 888 888 oooo d8b .oooo. oooo ooo. .oo.
`"Y8888o. `888P"Y88bP"Y88b `P )88b 888 888 888 `888""8P `P )88b `888 `888P"Y88b
`"Y88b 888 888 888 .oP"888 888 888 888 888 .oP"888 888 888 888
oo .d8P 888 888 888 d8( 888 888 888 888 888 d8( 888 888 888 888
8""88888P' o888o o888o o888o `Y888""8o o888o o888o o888o d888b `Y888""8o o888o o888o o888o
'''

n0 = 30798082519452208630254982405300548841337042015746308462162479889627080155514391987610153873334549377764946092629701
g = 64146569863628228208271069055817252751116365290967978172021890038925428672043

def TrainHash(msg):
n = n0
msg = map(ord,msg)
for i in msg :
n = g * (n+i)
n = n & (1<<383)
return n - 0xf5e33dabb114514

table = string.ascii_letters+string.digits

MENU = br'''
<OPTION>
'''

class Task(socketserver.BaseRequestHandler):
def _recvall(self):
BUFF_SIZE = 2048
data = b''
while True:
part = self.request.recv(BUFF_SIZE)
data += part
if len(part) < BUFF_SIZE:
break
return data.strip()

def send(self, msg, newline=True):
try:
if newline:
msg += b'\n'
self.request.sendall(msg)
except:
pass

def recv(self, prompt=b'SERVER <INPUT>: '):
self.send(prompt, newline=False)
return self._recvall()

def proof_of_work(self):
proof = (''.join([random.choice(table)for _ in range(20)])).encode()
sha = sha256(proof).hexdigest().encode()
self.send(b"[+] sha256(XXXX+" + proof[4:] + b") == " + sha )
XXXX = self.recv(prompt = b'[+] Plz Tell Me XXXX :')
if len(XXXX) != 4 or sha256(XXXX + proof[4:]).hexdigest().encode() != sha:
return False
return sha.decode()

def handle(self):
signal.alarm(30)
FirstBlockHash = self.proof_of_work()
if not FirstBlockHash:
self.request.close()
self.send(banner)
self.send(b"\nPlease give me 2 strings that are same when are hashed =.= ")
string1 = self.recv().decode()
string2 = self.recv().decode()

if TrainHash(string1) == TrainHash(string2):
self.send(b'\nJust do it!~ You can do more!')
if string2.encode()[-50:] == string1.encode()[-50:]:
self.send(flag)
self.send(b"\nConnection has been closed =.= ")
self.request.close()

class ThreadedServer(socketserver.ThreadingMixIn, socketserver.TCPServer):
pass

class ForkedServer(socketserver.ForkingMixIn, socketserver.TCPServer):
pass

if __name__ == "__main__":
HOST, PORT = '0.0.0.0', 10012
print("HOST:POST " + HOST+":" + str(PORT))
server = ForkedServer((HOST, PORT), Task)
server.allow_reuse_address = True
server.serve_forever()

简单审计代码,不了解的hash方式。

无所谓,朴素地想着先写py脚本连上靶机互动一下

结果,发了两个字符串flag,直接送给我了flag🤔

回去看代码,发现确实没限定string长度,不好的题目

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
import socket
import sys

HOST = '写自己的HOST' # str
PORT = 自己的端口 # int

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect((HOST, PORT))
a = str(s.recv(1024))
print(a)
print(s.recv(1024))
data = ''.join(a.strip("\n"))
sha_key = ''.join(data.split(')')[0]).split('+')[-1] # like: dygRhRVGRA146H43
print(sha_key)
sha_data = data.split('== ')[-1][:-3] # like: d06a5396ad875acdf0796cc5b0c083170e38728847085cfd99dadaeda71a3d17
print(sha_data)
import hashlib


# 第一关 sha256
def decry(data):
s = hashlib.sha256() # Get the hash algorithm.
s.update(data.encode()) # Hash the data.
b = s.hexdigest() # Get he hash value.
return b


list1 = ["A", "B", "C", "D", "E", "F", "G", "H", "I", "J",
"K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z", "a", "b", "c", "d", "e", "f",
"g", "h", "i", "j", "k", "l", "m", "n", "o",
"p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z", 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ]


def yi():
for a in list1:
for b in list1:
for c in list1:
for d in list1:
flag = "{0}{1}{2}{3}{4}".format(a, b, c, d, sha_key)
flag_sha = decry(flag)
flag1 = flag[0:4]

if str(flag_sha) == str(sha_data):
print('恭喜!')
return str(flag1)


s.send((yi()+'\n').encode())
print(s.recv(1024))
print(s.recv(1024))
s.send('flag\n'.encode())
s.send('flag\n'.encode())
print(s.recv(1024))
print(s.recv(1024))
print(s.recv(1024))
print(s.recv(1024))

做核酸、洗澡、睡觉等事件干扰,下午三点左右方才又来看题。

想着勇者山峰没什么了,就登陆了传说殿堂

🤔奇妙啊,一样的题,一样的打法

发现绝对厉害的都在传说殿堂,相对厉害的全在勇者山峰

(到比赛结束前,传说殿堂出一道密码就已经是前30了,勇者前90

image-20220507204308159

然后就去看了

TrainPlus

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
from MD_Train import MD00Plus
from hashlib import sha256
import socketserver
import signal
import string
import random
import os
from secret import flag


banner = br'''
ooooooooooooo o8o ooooooooo. oooo
8' 888 `8 `"' `888 `Y88. `888
888 oooo d8b .oooo. oooo ooo. .oo. 888 .d88' 888 oooo oooo .oooo.o
888 `888""8P `P )88b `888 `888P"Y88b 888ooo88P' 888 `888 `888 d88( "8
888 888 .oP"888 888 888 888 888 888 888 888 `"Y88b.
888 888 d8( 888 888 888 888 888 888 888 888 o. )88b
o888o d888b `Y888""8o o888o o888o o888o o888o o888o `V88V"V8P' 8""888P'
'''
table = string.ascii_letters+string.digits
sec = os.urandom(random.randrange(1,26))
GreatThing = os.urandom(16)

class Task(socketserver.BaseRequestHandler):
def _recvall(self):
BUFF_SIZE = 2048
data = b''
while True:
part = self.request.recv(BUFF_SIZE)
data += part
if len(part) < BUFF_SIZE:
break
return data.strip()

def send(self, msg, newline=True):
try:
if newline:
msg += b'\n'
self.request.sendall(msg)
except:
pass

def recv(self, prompt=b'SERVER <INPUT>: '):
self.send(prompt, newline=False)
return self._recvall()

def proof_of_work(self):
proof = (''.join([random.choice(table)for _ in range(20)])).encode()
sha = sha256(proof).hexdigest().encode()
self.send(b"[+] sha256(XXXX+" + proof[4:] + b") == " + sha )
XXXX = self.recv(prompt = b'[+] Plz Tell Me XXXX :')
if len(XXXX) != 4 or sha256(XXXX + proof[4:]).hexdigest().encode() != sha:
return False
return sha.decode()

def handle(self):
signal.alarm(30)
FirstBlockHash = self.proof_of_work()
if not FirstBlockHash:
self.request.close()


self.send(banner)
self.send(b":) My Great Thing:" + GreatThing )
self.send(b":) The MD00Plus of my GREATTHING:" + MD00Plus(sec).encode())

for i in range(25):
self.send(b"Please tell me the msg ")
msg = self.recv()
self.send(b"Please tell me the hash you can forcast.")
msg,Hash = msg.split(b',')
msg = bytes.fromhex(msg.decode())
Hash = bytes.fromhex(Hash.decode())
if GreatThing not in msg:
self.send(b"[!]INVALID!")
continue
elif MD00Plus(sec + msg).encode() == Hash:
self.send(flag)
break
else:
self.send(b'You Wrong!')

self.request.close()

class ThreadedServer(socketserver.ThreadingMixIn, socketserver.TCPServer):
pass

class ForkedServer(socketserver.ForkingMixIn, socketserver.TCPServer):
pass

if __name__ == "__main__":
HOST, PORT = '0.0.0.0', 10114
print("HOST:POST " + HOST+":" + str(PORT))
server = ForkedServer((HOST, PORT), Task)
server.allow_reuse_address = True
server.serve_forever()
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
def MD00Plus(message: bytes):
h0 = 0x114514ab
h1 = 0x1919810a
h2 = 0xa0189191
h3 = 0xba415411

R = (7, 12, 17, 22) * 4 + (5, 9, 14, 20) * 4 + (4, 11, 16, 23) * 4 + (6, 10, 15, 21) * 4
K = (0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee,
0xf57c0faf, 0x4787c62a, 0xa8304613, 0xfd469501, 0x698098d8,
0x8b44f7af, 0xffff5bb1, 0x895cd7be, 0x6b901122, 0xfd987193,
0xa679438e, 0x49b40821, 0xf61e2562, 0xc040b340, 0x265e5a51,
0xe9b6c7aa, 0xd62f105d, 0x02441453, 0xd8a1e681, 0xe7d3fbc8,
0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed, 0xa9e3e905,
0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a, 0xfffa3942, 0x8771f681,
0x6d9d6122, 0xfde5380c, 0xa4beea44, 0x4bdecfa9, 0xf6bb4b60,
0xbebfbc70, 0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x04881d05,
0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665, 0xf4292244,
0x432aff97, 0xab9423a7, 0xfc93a039, 0x655b59c3, 0x8f0ccc92,
0xffeff47d, 0x85845dd1, 0x6fa87e4f, 0xfe2ce6e0, 0xa3014314,
0x4e0811a1, 0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391)

F = lambda x, y, z: ((x & y) | ((~x) & z))
G = lambda x, y, z: ((x & z) | (y & (~z)))
H = lambda x, y, z: (x ^ y ^ z)
I = lambda x, y, z: (y ^ (x | (~z)))

L = lambda x, n: ((x << n) | (x >> (32 - n))) & 0xffffffff
W = lambda i4, i3, i2, i1: (i1 << 24) | (i2 << 16) | (i3 << 8) | i4
reverse = lambda x: (x << 24) & 0xff000000 | (x << 8) & 0x00ff0000 | \
(x >> 8) & 0x0000ff00 | (x >> 24) & 0x000000ff

ascii_list = list(map(lambda x: x, message))
msg_length = len(ascii_list) * 8
ascii_list.append(128)

while (len(ascii_list) * 8 + 64) % 512 != 0:
ascii_list.append(1)

for i in range(8):
ascii_list.append((msg_length >> (8 * i)) & 0xff)

for i in range(len(ascii_list) // 64):
a, b, c, d = h0, h1, h2, h3
for j in range(64):
if 0 <= j <= 15:
f = F(b, c, d) & 0xffffffff
g = j
elif 16 <= j <= 31:
f = G(b, c, d) & 0xffffffff
g = ((5 * j) + 1) % 16
elif 32 <= j <= 47:
f = H(b, c, d) & 0xffffffff
g = ((3 * j) + 5) % 16
else:
f = I(b, c, d) & 0xffffffff
g = (7 * j) % 16
aa, dd, cc = d, c, b
s = i * 64 + g * 4
w = W(ascii_list[s], ascii_list[s + 1], ascii_list[s + 2], ascii_list[s + 3])
bb = (L((a + f + K[j] + w) & 0xffffffff, R[j]) + b) & 0xffffffff
a, b, c, d = aa, bb, cc, dd
h0 = (h0 + a) & 0xffffffff
h1 = (h1 + b) & 0xffffffff
h2 = (h2 + c) & 0xffffffff
h3 = (h3 + d) & 0xffffffff
h0, h1, h2, h3 = reverse(h0), reverse(h1), reverse(h2), reverse(h3)
digest = (h0 << 96) | (h1 << 64) | (h2 << 32) | h3
return hex(digest)[2:].rjust(32, '0')

明显感觉到复杂,没什么人出加上自己调试了半天,交互不好,作罢

看回了传说殿堂第一题

bob’s enc

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
from secret import *
import random

prime = 2141
print len(flag)
flag = map(ord,flag)
flag1 = flag[:21]
flag2 = flag[21:]
row = 64

def add(msg1,msg2):
return [(x+y)%prime for x,y in zip(msg1,msg2)]

def multi(msg1,msg2):
out = []
for l in msg1:
s = 0
for x,y in zip(l,msg2):
s += (x*y)%prime
s %= prime
out.append(s)
return out
def genkey(leng):
l = [[] for i in range(row)]
for x in range(row):
for i in range(leng):
l[x].append(random.randint(0,511))
return l

key = genkey(len(flag1))
print key

cipher1 = multi(key,flag1)

print cipher1

cipher2 = multi(key,flag2)

noise = [random.randint(0,6) for i in range(row)]
print add(noise,cipher2)
1
2
3
[[185, 96, 351, 118, 421, 449, 350, 349, 388, 95, 341, 327, 29, 156, 399, 283, 292, 461, 445, 120, 126], [495, 358, 192, 300, 279, 277, 478, 335, 231, 241, 178, 314, 453, 251, 133, 391, 213, 132, 254, 388, 46], [428, 44, 100, 483, 12, 311, 57, 443, 289, 90, 478, 495, 399, 89, 324, 275, 322, 99, 343, 489, 133], [420, 358, 472, 260, 267, 136, 303, 491, 390, 248, 430, 117, 154, 244, 62, 217, 204, 334, 277, 231, 325], [11, 96, 61, 67, 456, 361, 292, 278, 424, 237, 345, 109, 475, 473, 29, 250, 195, 430, 114, 13, 199], [17, 91, 330, 73, 384, 134, 437, 161, 166, 185, 499, 491, 342, 129, 348, 162, 478, 216, 189, 311, 502], [396, 437, 98, 421, 120, 443, 113, 432, 9, 476, 243, 122, 416, 508, 287, 45, 84, 322, 504, 287, 251], [187, 489, 407, 204, 127, 10, 302, 101, 389, 113, 469, 184, 249, 131, 113, 18, 350, 106, 486, 406, 295], [265, 425, 30, 478, 471, 211, 162, 323, 163, 205, 187, 422, 452, 226, 230, 367, 478, 229, 365, 395, 294], [360, 193, 180, 253, 337, 453, 16, 352, 243, 107, 171, 46, 25, 234, 46, 479, 267, 267, 171, 188, 127], [379, 360, 109, 360, 403, 343, 75, 306, 138, 40, 41, 253, 428, 401, 464, 495, 21, 296, 319, 410, 440], [28, 209, 1, 233, 458, 266, 301, 359, 469, 304, 264, 368, 339, 25, 490, 343, 404, 488, 275, 262, 274], [180, 372, 133, 341, 29, 352, 326, 89, 323, 479, 68, 76, 247, 225, 159, 163, 180, 160, 171, 7, 322], [322, 295, 28, 467, 361, 169, 190, 71, 456, 140, 456, 202, 295, 424, 428, 18, 286, 233, 470, 303, 429], [234, 37, 128, 175, 282, 509, 54, 186, 177, 23, 348, 487, 473, 377, 81, 225, 154, 511, 364, 120, 280], [262, 82, 383, 490, 128, 448, 289, 420, 239, 374, 392, 149, 217, 398, 441, 480, 453, 503, 318, 285, 418], [0, 347, 223, 381, 469, 208, 424, 435, 404, 64, 107, 73, 490, 116, 445, 392, 194, 287, 66, 325, 261], [99, 26, 489, 114, 3, 351, 494, 174, 369, 354, 379, 187, 90, 202, 286, 37, 48, 397, 298, 65, 499], [455, 114, 349, 401, 5, 139, 314, 227, 134, 258, 270, 135, 287, 332, 298, 272, 167, 43, 271, 484, 177], [448, 78, 479, 324, 170, 7, 230, 173, 214, 65, 91, 497, 68, 391, 44, 205, 364, 471, 460, 312, 122], [452, 360, 448, 169, 240, 496, 302, 3, 354, 266, 46, 22, 151, 498, 461, 314, 169, 88, 30, 487, 258], [282, 222, 260, 503, 106, 420, 315, 307, 202, 238, 224, 329, 351, 190, 137, 294, 171, 309, 19, 186, 391], [69, 501, 283, 96, 159, 459, 437, 192, 293, 479, 79, 49, 299, 205, 177, 360, 36, 414, 118, 194, 270], [6, 419, 459, 254, 97, 455, 445, 239, 277, 278, 226, 23, 146, 151, 273, 378, 141, 281, 480, 388, 213], [181, 508, 347, 447, 467, 351, 503, 262, 375, 74, 49, 48, 364, 492, 400, 305, 25, 207, 278, 163, 11], [320, 94, 400, 15, 201, 53, 130, 137, 219, 57, 20, 239, 467, 352, 373, 395, 58, 4, 446, 332, 41], [205, 385, 446, 185, 470, 268, 308, 461, 265, 75, 75, 104, 108, 14, 334, 499, 207, 363, 94, 505, 363], [299, 292, 112, 203, 7, 240, 499, 343, 396, 482, 383, 61, 476, 101, 187, 265, 428, 53, 24, 342, 201], [421, 286, 305, 79, 324, 216, 163, 193, 362, 57, 472, 449, 169, 33, 280, 202, 237, 376, 382, 2, 1], [379, 33, 151, 51, 353, 295, 145, 220, 147, 251, 90, 344, 96, 31, 185, 250, 270, 420, 365, 373, 356], [228, 299, 87, 113, 458, 52, 26, 228, 294, 97, 384, 493, 380, 209, 257, 20, 375, 2, 316, 129, 492], [479, 346, 57, 488, 183, 185, 18, 422, 209, 318, 461, 159, 469, 145, 44, 58, 441, 490, 510, 194, 192], [254, 398, 510, 159, 371, 280, 331, 23, 99, 150, 175, 151, 42, 473, 164, 35, 97, 174, 115, 24, 270], [280, 76, 254, 293, 491, 76, 128, 301, 240, 357, 192, 372, 343, 34, 386, 468, 313, 41, 285, 507, 282], [271, 91, 507, 16, 128, 8, 326, 102, 355, 371, 313, 292, 433, 2, 459, 14, 258, 498, 146, 446, 309], [386, 88, 502, 4, 399, 272, 49, 69, 51, 465, 291, 289, 417, 271, 374, 337, 46, 393, 19, 429, 91], [407, 35, 337, 51, 41, 460, 222, 448, 499, 381, 59, 468, 440, 216, 86, 236, 91, 18, 123, 68, 145], [384, 30, 454, 419, 275, 164, 72, 195, 489, 458, 419, 148, 269, 150, 358, 188, 109, 27, 42, 34, 123], [500, 184, 195, 193, 68, 19, 329, 511, 280, 69, 113, 124, 102, 274, 43, 374, 408, 64, 314, 309, 473], [72, 145, 242, 2, 367, 371, 143, 166, 325, 74, 414, 94, 269, 196, 124, 94, 14, 351, 111, 465, 503], [70, 47, 439, 170, 306, 82, 233, 36, 346, 234, 157, 468, 83, 85, 424, 157, 258, 120, 270, 136, 286], [442, 173, 254, 271, 420, 507, 297, 473, 296, 511, 98, 133, 37, 498, 468, 17, 260, 318, 168, 490, 124], [50, 35, 252, 472, 406, 400, 439, 89, 309, 393, 332, 324, 260, 215, 8, 322, 357, 252, 124, 358, 457], [93, 102, 478, 224, 428, 10, 238, 368, 113, 502, 148, 7, 395, 97, 73, 306, 40, 395, 9, 254, 319], [282, 277, 295, 425, 59, 21, 136, 230, 207, 1, 29, 170, 14, 337, 371, 437, 359, 10, 100, 374, 24], [3, 270, 289, 179, 434, 489, 470, 343, 478, 156, 177, 72, 13, 266, 475, 23, 148, 102, 210, 270, 323], [464, 466, 277, 191, 426, 20, 266, 33, 41, 249, 452, 475, 265, 421, 282, 250, 233, 287, 495, 170, 300], [379, 35, 137, 106, 155, 81, 154, 382, 30, 237, 294, 478, 321, 384, 48, 111, 150, 4, 454, 446, 28], [57, 355, 94, 253, 297, 424, 415, 480, 68, 356, 415, 73, 41, 171, 491, 130, 92, 180, 506, 326, 463], [279, 43, 202, 35, 397, 257, 120, 11, 231, 369, 221, 332, 47, 236, 58, 278, 75, 117, 33, 130, 358], [142, 335, 339, 112, 38, 82, 426, 211, 174, 389, 137, 96, 431, 113, 112, 500, 145, 44, 313, 96, 187], [246, 211, 400, 415, 294, 234, 367, 46, 371, 479, 412, 197, 204, 498, 18, 140, 67, 237, 510, 457, 298], [258, 3, 136, 284, 149, 161, 456, 122, 114, 383, 251, 240, 453, 227, 330, 33, 241, 160, 306, 254, 409], [391, 115, 92, 102, 359, 182, 489, 313, 204, 275, 206, 447, 436, 286, 229, 377, 374, 162, 22, 384, 40], [427, 491, 362, 240, 358, 296, 154, 178, 278, 284, 324, 422, 52, 295, 490, 56, 39, 378, 174, 202, 496], [29, 454, 436, 6, 287, 82, 154, 474, 92, 272, 400, 238, 352, 140, 386, 504, 19, 32, 334, 30, 450], [469, 123, 353, 422, 175, 260, 294, 18, 268, 479, 60, 114, 456, 55, 403, 446, 166, 259, 294, 215, 48], [404, 187, 426, 362, 296, 239, 226, 416, 306, 336, 1, 448, 47, 403, 367, 357, 501, 425, 310, 41, 303], [339, 115, 478, 416, 10, 90, 188, 229, 217, 441, 288, 152, 394, 219, 422, 376, 325, 375, 6, 454, 238], [226, 226, 149, 107, 418, 419, 209, 108, 87, 127, 202, 320, 179, 234, 87, 335, 195, 5, 273, 142, 115], [464, 177, 77, 101, 76, 19, 73, 397, 296, 34, 360, 107, 491, 460, 510, 342, 198, 118, 105, 337, 239], [464, 25, 191, 113, 455, 129, 247, 488, 303, 27, 242, 423, 336, 125, 283, 332, 244, 372, 175, 276, 49], [211, 367, 406, 314, 177, 496, 320, 385, 193, 51, 423, 80, 258, 44, 154, 362, 215, 296, 260, 424, 160], [384, 161, 92, 402, 414, 443, 129, 279, 272, 224, 294, 319, 75, 169, 242, 85, 315, 402, 4, 268, 88]]
[1702, 795, 740, 373, 535, 1308, 1050, 502, 40, 672, 1354, 1843, 515, 231, 774, 65, 978, 1340, 455, 2137, 733, 307, 1604, 723, 1023, 1253, 275, 1817, 404, 2035, 267, 1475, 14, 2127, 15, 487, 317, 757, 290, 541, 100, 951, 2049, 1042, 1404, 1676, 655, 1460, 1532, 273, 916, 1454, 1690, 1628, 1751, 1656, 139, 156, 2102, 264, 243, 455, 1564, 2072]
[884, 1584, 681, 1713, 1916, 609, 1840, 177, 1723, 1049, 254, 864, 1671, 121, 2021, 1353, 1290, 1891, 556, 1786, 1553, 1548, 727, 1967, 1800, 422, 1559, 1290, 642, 1406, 441, 1928, 395, 279, 1125, 1273, 99, 1131, 395, 76, 733, 416, 924, 571, 506, 822, 877, 887, 860, 1755, 1385, 1861, 1754, 1851, 1046, 1724, 1866, 1427, 378, 351, 146, 1367, 756, 505]

la佬一🩸,好奇心拉满,于是开始研究起来了

化简,易得解flag1要点:单模多元线性同余方程

就着csdn现学,效率过低🤔

放弃之际,在github上搜到了优秀的代码

处理好数据,解方程,得到前半段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
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
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
#!/usr/bin/python2
# -*- coding: utf-8 -*-

'''
Author @55-AA
19 July, 2016
'''

import copy


def gcd(a, b):
"""
Return the greatest common denominator of integers a and b.
gmpy2.gcd(a, b)
"""
while b:
a, b = b, a % b
return a


def lcm(a, b):
return a * b / (gcd(a, b))


def egcd(a, b):
"""
ax + by = 1
ax ≡ 1 mod b
Return a 3-element tuple (g, x, y), the g = gcd(a, b)
gmpy2.gcdext(a, b)
"""
if a == 0:
return (b, 0, 1)
else:
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)


def mod_inv(a, m):
"""
ax ≡ 1 mod m
gmpy2.invert(a, m)
"""
g, x, y = egcd(a, m)
assert g == 1
return x % m


def int2mem(x):
"""
0x12233 => '\x33\x22\x01'
"""
pad_even = lambda x: ('', '0')[len(x) % 2] + x
x = list(pad_even(format(x, 'x')).decode('hex'))
x.reverse()
return ''.join(x)


def mem2int(x):
"""
'\x33\x22\x01' => 0x12233
"""
x = list(x)
x.reverse()
return int(''.join(x).encode('hex'), 16)


###########################################################
# class
###########################################################
class GaussMatrix:
"""
A*X ≡ B (mod p),p为大于0的整数。

高斯消元求解模线性方程组。先化简为上三角,然后回代求解。
当r(A) <= n时,一定有多解;
当r(A) == n时,有多解或唯一解;
当r(A) != r(A~)时,无解。
r(A)为系数矩阵的秩,r(A)为增广矩阵的秩,n为未知数的个数。

http://www.docin.com/p-1063811671.html讨论了gcd(|A|, m) = 1时的LU分解解法,
本文包括了gcd(|A|, m) > 1时的解法,

化简原则:
1、系数与模互质
2、系数加某一行n次后,对应的系数与模的GCD最小
3、将1或2得到的系数移到对角线上

初始化参数:
matrix:方程组的增广矩阵(最后一列为常数项)。
matrix = [
[ 69, 75, 78, 36, 58],
[ 46, 68, 51, 26, 42],
[ 76, 40, 42, 49, 11],
[ 11, 45, 2, 45, 1],
[ 15, 67, 60, 14, 72],
[ 76, 67, 73, 56, 58],
[ 67, 15, 68, 54, 75],
]
mod:模数

函数:
gauss():求解方程

输出变量:
error_str:出错的信息
count:解的数量
"""

def __init__(self, matrix, mod):
self.matrix = copy.deepcopy(matrix)
self.d = None

self.r = len(matrix)
self.c = len(matrix[0])
self.N = len(matrix[0]) - 1
self.mod = mod
self.count = 1
self.error_str = "unknown error"

def verify_solution(self, solution):
for d in self.matrix:
result = 0
for r in map(lambda x, y: 0 if None == y else x * y, d, solution):
result += r
if (result % self.mod) != ((d[-1]) % self.mod):
return 0
return 1

def swap_row(self, ra, rb):
(self.d[ra], self.d[rb]) = (self.d[rb], self.d[ra])

def swap_col(self, ca, cb):
for j in range(self.r):
(self.d[j][ca], self.d[j][cb]) = (self.d[j][cb], self.d[j][ca])

def inv_result(self, r, n):
"""
求解第n个未知数,r已经获得的解。形如:[None,None, ..., n+1, ...]

a*x ≡ b(mod m)
x有解的条件:gcd(a,m) | b。也即a,m互质时一定有解,不互质时,b整除gcd(a,m)也有解,否则无解。
解的格式为:x0+k(m/gcd(a,m)),其中x0为最小整数特解,k为任意整数。
返回[x0, x1, ...xn],其中x0 < x1 < xn < m。
"""
b = self.d[n][self.N]
a = self.d[n][n]
m = self.mod
k = gcd(a, m)
for j in xrange(n + 1, self.N):
b = (b - (self.d[n][j] * r[j] % m)) % m

if 1 == k:
return [mod_inv(a, m) * b % m]
else:
if k == gcd(k, b):
a /= k
b /= k
m /= k

x0 = mod_inv(a, m) * b % m
x = []
for i in xrange(k):
x.append(x0 + m * i)
return x
return None

def find_min_gcd_row_col(self, i, j):
# 查找直接互质的对角线系数
for k in xrange(i, self.r):
for l in xrange(j, self.c - 1):
if (1 == gcd(self.d[k][l], self.mod)):
return [k, l]

def add_min_gcd(a, b, m):
r = [m, 1]
g = gcd(a, b)
if g:
i = a / g
for j in xrange(i):
g = gcd((a + j * b) % m, m)
if g < r[0]:
r[0] = g
r[1] = j
if g == 1:
break
return r

# 查找加乘后GCD最小的对角线系数
# [加乘后的最大公约数,加乘的倍数,要化简的行号,加乘的行号,要化简的列号]
r = [self.mod, 1, i, i + 1, j]
for k in xrange(i, self.r):
for kk in xrange(k + 1, self.r):
for l in range(j, self.c - 1):
rr = add_min_gcd(self.d[k][l], self.d[kk][l], self.mod)
if rr[0] < r[0]:
r[0] = rr[0]
r[1] = rr[1]
r[2] = k
r[3] = kk
r[4] = l
pass
if (1 == rr[0]):
break
g = r[0]
n = r[1]
k = r[2]
kk = r[3]
l = r[4]

if n and g < self.mod:
self.d[k] = map(lambda x, y: (x + n * y) % self.mod, self.d[k], self.d[kk])
return [k, l]

def mul_row(self, i, k, j):
a = self.d[k][j]
b = self.d[i][j]

def get_mul(a, b, m):
k = gcd(a, m)
if 1 == k:
return mod_inv(a, m) * b % m
else:
if k == gcd(k, b):
return mod_inv(a / k, m / k) * (b / k) % (m / k)
return None

if b:
mul = get_mul(a, b, self.mod)
if None == mul:
print_matrix(self.d)
assert (mul != None)
self.d[i] = map(lambda x, y: (y - x * mul) % self.mod, self.d[k], self.d[i])

def gauss(self):
"""
返回解向量,唯一解、多解或无解(None)。
例如:[[61, 25, 116, 164], [61, 60, 116, 94], [61, 95, 116, 24], [61, 130, 116, 129], [61, 165, 116, 59]]
"""

self.d = copy.deepcopy(self.matrix)
for i in xrange(self.r):
for j in xrange(self.c):
self.d[i][j] = self.matrix[i][j] % self.mod # 把负系数变成正系数

if self.r < self.N:
self.d.extend([[0] * self.c] * (self.N - self.r))

# 化简上三角
index = [x for x in xrange(self.N)]
for i in range(self.N):
tmp = self.find_min_gcd_row_col(i, i)
if (tmp):
self.swap_row(i, tmp[0])
(index[i], index[tmp[1]]) = (index[tmp[1]], index[i])
self.swap_col(i, tmp[1])
else:
self.error_str = "no min"
return None

for k in range(i + 1, self.r):
self.mul_row(k, i, i)

# print_matrix(self.d)
if self.r > self.N:
for i in xrange(self.N, self.r):
for j in xrange(self.c):
if self.d[i][j]:
self.error_str = "r(A) != r(A~)"
return None

# 判断解的数量
for i in xrange(self.N):
self.count *= gcd(self.d[i][i], self.mod)

if self.count > 100:
self.error_str = "solution too more:%d" % (self.count)
return None

# 回代
result = [[None] * self.N]
for i in range(self.N - 1, -1, -1):
new_result = []
for r in result:
ret = self.inv_result(r, i)
if ret:
for rr in ret:
l = r[:]
l[i] = rr
new_result.append(l)

else:
self.error_str = "no inv:i=%d" % (i)
return None

result = new_result

# 调整列变换导致的未知数顺序变化
for i in xrange(len(result)):
def xchg(a, b):
result[i][b] = a

map(xchg, result[i][:], index)

return result


###########################################################
# test
###########################################################
def print_array(x):
prn = "\t["
for j in x:
if j:
prn += "%3d, " % j
else:
prn += " 0, "

print prn[:-2] + "],"


def print_matrix(x):
print "["
for i in x:
print_array(i)
print "]"


def random_test(times):
import random
for i in xrange(times):
print "\n============== random test %d ==============\n" % i
mod = random.randint(5, 999)
col = random.randint(2, 30)
row = random.randint(2, 30)

solution = map(lambda x: random.randint(0, mod - 1), [xc for xc in xrange(col)])

matrix = []
for y in xrange(row):
array = map(lambda x: random.randint(0, mod), [xc for xc in xrange(col)])

t = 0
for j in map(lambda x, y: 0 if None == y else x * y, array, solution):
t += j
array.append(t % mod)

matrix.append(array)

run_test(mod, solution, matrix)


def static_test_ex():
mod = 37
solution = [6, 10, 5, 11, 32, 39, 6, 42, 7, 18, 21, 8, 8, 27]
matrix = [
[32, 43, 11, 27, 14, 41, 27, 20, 0, 37, 7, 12, 9, 16, 12],
[23, 35, 31, 25, 46, 27, 48, 0, 4, 19, 43, 11, 31, 24, 36],
[48, 10, 47, 1, 42, 26, 0, 21, 10, 23, 7, 5, 13, 32, 41],
[15, 0, 6, 24, 6, 36, 4, 36, 18, 46, 33, 20, 4, 20, 39],
[4, 37, 3, 39, 26, 33, 13, 32, 23, 11, 45, 45, 29, 32, 35],
[38, 8, 38, 47, 1, 34, 36, 46, 47, 0, 22, 23, 21, 31, 21],
[21, 3, 17, 15, 46, 42, 7, 17, 12, 37, 30, 3, 14, 12, 16],
[7, 22, 14, 31, 31, 19, 34, 46, 9, 33, 12, 18, 4, 15, 32],
[13, 41, 35, 25, 19, 9, 44, 8, 0, 42, 15, 20, 3, 47, 29],
[36, 21, 36, 13, 37, 40, 21, 39, 2, 16, 26, 4, 15, 2, 23],
[41, 19, 28, 2, 42, 24, 27, 21, 21, 35, 3, 18, 7, 22, 36],
[42, 34, 17, 40, 26, 7, 14, 0, 7, 46, 30, 14, 34, 22, 39],
[18, 1, 40, 38, 17, 45, 24, 34, 34, 9, 32, 24, 9, 2, 45],
[43, 2, 1, 29, 47, 48, 28, 37, 10, 23, 35, 34, 37, 44, 35],
]

run_test(mod, solution, matrix)


def static_test():
mod = 26
solution = [23, 15, 19, 13, 25, 17, 24, 18, 11]
matrix = [
[11, 12, 7, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 11, 12, 7, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 11, 12, 7],
[14, 18, 23, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 14, 18, 23, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 14, 18, 23],
[17, 5, 19, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 17, 5, 19, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 17, 5, 19],
]

for i in xrange(len(matrix)):
t = 0
for j in map(lambda x, y: 0 if None == y else x * y, matrix[i], solution):
t += j
matrix[i].append(t % mod)

run_test(mod, solution, matrix)


def run_test(mod, solution, matrix):
print "row = %d, col = %d" % (len(matrix), len(matrix[0]) - 1)
print "mod = %d" % (mod)
print "solution =", solution

print "matrix ="
print_matrix(matrix)

g = GaussMatrix(matrix, mod)

ret = g.gauss()
if not ret:
print "error:"
print_matrix(g.d)
print "error_str:", g.error_str
else:
print "times:", g.count
print "result:"
print_matrix(ret)


if __name__ == "__main__":
data = []
with open('/Users/wenhui/Downloads/bob_enc_5d6979d05829e676ea3154e4be14d553/out.txt') as f:
for i in f.readlines():
data.append(i)

key = []
eval('key.append({0})'.format(data[0]))
key = key[0]

s = []
eval('s.append({0})'.format(data[1]))
s = s[0]

matrix = []
tmp = []
for i in range(len(key)):
tmp = key[i]
tmp.append(s[i])
matrix.append(tmp)
mod = 2141
s = GaussMatrix(matrix, mod)
flag1 = s.gauss()
print flag1 # [[102, 108, 97, 103, 123, 49, 52, 101, 54, 102, 50, 51, 54, 45, 57, 101, 98, 57, 45, 52, 54]]

for i in flag1:
tmp = []
for each in i:
tmp.append(chr(each))
print ''.join(tmp)
# [[102, 108, 97, 103, 123, 49, 52, 101, 54, 102, 50, 51, 54, 45, 57, 101, 98, 57, 45, 52, 54]]
# flag{14e6f236-9eb9-46

困惑于flag2的长度几何,以及噪声的消除方法

这里了解到了LWE

LWE问题

容错学习问题 (LWE问题, Learning With Errors)是一个机器学习领域中的怀疑难解问题,由Oded Regev 在2005年提出,他因此赢得2018年哥德尔奖。这是一个极性学习问题的一般形式。

但很可惜,一小时内没有成功利用之

比赛结束后,回到勇者山峰,发现密码也三道题了

  • notKnapsack
  • bob’s enc
  • TrainPlus

传说殿堂也三道

  • bob’s enc
  • Train
  • TrainPlus

总体而言,难度上,300分的notKnapsack = TrainPlus > bob’s enc >> Train

以及,传说殿堂远远没有勇者山峰卷🤔

传说殿堂

勇者山峰

后续再跟着其他师傅wp复现吧。

Bob’enc

以下为赛后复现,我决定尽可能多的挖掘此题价值

当时的困惑

  • 题目生成列表时,行数列数究竟多少没看懂
  • flag2多长
  • LWE如何用

现在的未知

  • 解题的矩阵思维
  • sage命令背后的数学含义
  • 过了几个月,学校教的线代已忘

先上师傅总的题解(…Orz

题解

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
# sage
from sage.all import *
from sage.modules.free_module_integer import IntegerLattice
from random import randint
import sys
from itertools import starmap
from operator import mul

with open('out', 'r') as f:
key = eval(f.readline())
c1 = eval(f.readline())
c2 = eval(f.readline())

prime = 2141

K = matrix(Zmod(prime), key[:21])
C1 = vector(Zmod(prime), c1[:21])
m1 = K.inverse() * C1 # m1 = K\C1
flag = ''
for i in m1:
flag += chr(i)
print(flag)


# Babai's Nearest Plane algorithm
def Babai_closest_vector(M, G, target):
small = target
for _ in range(5):
for i in reversed(range(M.nrows())):
c = ((small * G[i]) / (G[i] * G[i])).round()
small -= M[i] * c
return target - small


m = 64
n = 21
q = prime

A_values = key
b_values = c2

A = matrix(ZZ, m + n, m)
for i in range(m):
A[i, i] = q
for x in range(m):
for y in range(n):
A[m + y, x] = A_values[x][y]
lattice = IntegerLattice(A, lll_reduce=True)

gram = lattice.reduced_basis.gram_schmidt()[0]
target = vector(ZZ, b_values)
res = Babai_closest_vector(lattice.reduced_basis, gram, target)

R = IntegerModRing(q)
M = Matrix(R, A_values)
ingredients = M.solve_right(res)

for i in ingredients:
flag += chr(i)
print(flag)

flag1

C1 = multi(key, flag1)

对于multi,赛时我的理解是:单模多元线性同余方程

单模多元线性同余方程

其中out里第一个大列表给了Key(所有ki),第二个列表给了C1(上图左端所有C),所以我找到解此方程的代码,跑出来就是解了。

值得一提,看题目可知,这有64个方程,21个未知量,所以实际跑解方程的代码让C1 = C1[:21]也可

而在高深的密码人看来,C1是由定义在整数域上的p模环矩阵K向量F [f1, f2, …, f21]得到的:

矩阵K

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
[185  96 351 118 421 449 350 349 388  95 341 327  29 156 399 283 292 461 445 120 126]
[495 358 192 300 279 277 478 335 231 241 178 314 453 251 133 391 213 132 254 388 46]
[428 44 100 483 12 311 57 443 289 90 478 495 399 89 324 275 322 99 343 489 133]
[420 358 472 260 267 136 303 491 390 248 430 117 154 244 62 217 204 334 277 231 325]
[ 11 96 61 67 456 361 292 278 424 237 345 109 475 473 29 250 195 430 114 13 199]
[ 17 91 330 73 384 134 437 161 166 185 499 491 342 129 348 162 478 216 189 311 502]
[396 437 98 421 120 443 113 432 9 476 243 122 416 508 287 45 84 322 504 287 251]
[187 489 407 204 127 10 302 101 389 113 469 184 249 131 113 18 350 106 486 406 295]
[265 425 30 478 471 211 162 323 163 205 187 422 452 226 230 367 478 229 365 395 294]
[360 193 180 253 337 453 16 352 243 107 171 46 25 234 46 479 267 267 171 188 127]
[379 360 109 360 403 343 75 306 138 40 41 253 428 401 464 495 21 296 319 410 440]
[ 28 209 1 233 458 266 301 359 469 304 264 368 339 25 490 343 404 488 275 262 274]
[180 372 133 341 29 352 326 89 323 479 68 76 247 225 159 163 180 160 171 7 322]
[322 295 28 467 361 169 190 71 456 140 456 202 295 424 428 18 286 233 470 303 429]
[234 37 128 175 282 509 54 186 177 23 348 487 473 377 81 225 154 511 364 120 280]
[262 82 383 490 128 448 289 420 239 374 392 149 217 398 441 480 453 503 318 285 418]
[ 0 347 223 381 469 208 424 435 404 64 107 73 490 116 445 392 194 287 66 325 261]
[ 99 26 489 114 3 351 494 174 369 354 379 187 90 202 286 37 48 397 298 65 499]
[455 114 349 401 5 139 314 227 134 258 270 135 287 332 298 272 167 43 271 484 177]
[448 78 479 324 170 7 230 173 214 65 91 497 68 391 44 205 364 471 460 312 122]
[452 360 448 169 240 496 302 3 354 266 46 22 151 498 461 314 169 88 30 487 258]

向量F

1
[102, 108, 97, 103, 123, 49, 52, 101, 54, 102, 50, 51, 54, 45, 57, 101, 98, 57, 45, 52, 54]

C1 = K✖️F

1
(1702, 795, 740, 373, 535, 1308, 1050, 502, 40, 672, 1354, 1843, 515, 231, 774, 65, 978, 1340, 455, 2137, 733)

经过验证,矩阵与向量相乘为每行对应项相乘再求和,以下

1
2
3
4
5
6
7
8
m = [102, 108, 97, 103, 123, 49, 52, 101, 54, 102, 50, 51, 54, 45, 57, 101, 98, 57, 45, 52, 54]
k = '185 96 351 118 421 449 350 349 388 95 341 327 29 156 399 283 292 461 445 120 126'.split(' ')
k = [int(i) for i in k if i]
sum = 0
for i in range(len(m)):
sum += (m[i] * k[i]) % 2141
print(sum % 2141)
# 1702

故不用复杂的求解多个同余方程,可以直接让$K^{-1}*C1$,即可得到:F

  • 注意,这里必须左乘$K^{-1}$,即:$C1 = K*F; K^{-1}*C1 = F$
    • 也就是说F是列向量?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from sage.all import *
from sage.modules.free_module_integer import IntegerLattice
from random import randint
import sys
from itertools import starmap
from operator import mul

with open('out', 'r') as f:
key = eval(f.readline())
c1 = eval(f.readline())
c2 = eval(f.readline())

prime = 2141

# 矩阵求解的思维
K = matrix(Zmod(prime), key[:21]) # 一来,21行足够;二来方阵才可求逆
C1 = vector(Zmod(prime), c1[:21])
m1 = K.inverse() * C1
flag = ''
for i in m1:
flag += chr(i)
print(flag)

整数域上的环,奇妙!

flag2

1
noise = [random.randint(0,6) for i in range(64)]
  1. C2 = multi(Key, flag2)

  2. C2 = add(noise, C2)

噪声打断了思绪,得重新整理整理。

赛时也了解到了LWE,但因为不知原理,不懂使用,故无所突破。

按照当时的想法,认为此法能消掉noise就很🐮了,但赛后发现可以直接给到flag2🐮🐮🐮

水平、时间有限,LWE系统的原理学习暂先搁置,先试着读读看使用方法与代码

LWE

简单翻译翻译,在此题中,则是给定Key矩阵,先令矩阵Key*向量flag2后再与noise相加,故:

  • A = Key
  • s = flag2
  • e = noise
  • b = C2

而LWE问题就是给A、b, 求s

所以一开始所惊叹的‘能直接求出flag2’,在此印证

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
#脚本2-大规模
#Sage
from sage.modules.free_module_integer import IntegerLattice
from random import randint
import sys
from itertools import starmap
from operator import mul

# Babai's Nearest Plane algorithm
# from: http://mslc.ctf.su/wp/plaidctf-2016-sexec-crypto-300/
def Babai_closest_vector(M, G, target):
small = target
for _ in range(1):
for i in reversed(range(M.nrows())):
c = ((small * G[i]) / (G[i] * G[i])).round()
small -= M[i] * c
return target - small

# A一般为key
# b为密文
# e为噪声
# s为flag(下面的ingredients

m = # A行数
n = # A列数
q = # 模数

A_values =
b_values =

A = matrix(ZZ, m + n, m)
for i in range(m):
A[i, i] = q
for x in range(m):
for y in range(n):
A[m + y, x] = A_values[x][y]
lattice = IntegerLattice(A, lll_reduce=True)
print("LLL done")
gram = lattice.reduced_basis.gram_schmidt()[0]
target = vector(ZZ, b_values)
res = Babai_closest_vector(lattice.reduced_basis, gram, target)
print("Closest Vector: {}".format(res))

R = IntegerModRing(q)
M = Matrix(R, A_values)
ingredients = M.solve_right(res)

print("Ingredients: {}".format(ingredients))

for row, b in zip(A_values, b_values):
effect = sum(starmap(mul, zip(map(int, ingredients), row))) % q
assert(abs(b - effect) < 2 ** 37)

print("ok")

也发现,我们不需要知道flag2的长度

收获

  • 矩阵、向量解题思路
  • LWE消除噪音
  • 加深对sage的了解