0%

CISCN2022·Crypto

初赛

电台签到

题目给了明文、密钥本,需要算出密文且发送出去

根据微信里公众号提示,找到密码本,进行模10运算,得到:

签到

也根据微信里提示,先用BurpSuit抓包发s,然后修改再发上面的数字,即:

  • GET /send?msg=sJ HTTP/1.1

  • GET /send?msg=2975115315066710252297245914J HTTP/1.1

ISO-9798-2(未解)

没有源码文件

1
2
3
4
5
6
7
b'sha256(XXXX+tbEA66kfcvrpWVf7) == ffde1acf2b63699d40134576ad264b709da89e02cfdc8558e57ff3f24fc36fc5\n'
b'Give me XXXX: '

b'[Server]: Please send a 128-bit random number in hex.\n> '
b'[Server]: Your input is rB = 114890189739596232616528541525085912499.\n'
b'[Server]: Encrypt(rA||rB||B, k) (in hex) is ab99f7e937db9988e78194a2dae625de03c13b9d0fc9ba8de822c6b26ee9e9a93f9ee06aa6bdd01025ef1f25d98f9be0\n
[Server]: Please send Encrypt(rB||rA, k) in hex.\n> '

其他

基础挑战码的可信计算1、2、3

非预期

  • linux关键词查找flag
  • root密码toor,重复以上

预期

太菜了,没预期出来

赛后没环境、没文件,没法复现

区块链

实验室区块链方向的师傅出了,最近打算入个门😈

初赛总结

密码出的太❌了,好像啥都有,但正儿八经的、含有数学原理的代码没看到一行👿

实话实说,给我整emo了😭

东北赛区复赛

gcrd2(100)

题目

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
import numpy as np
from flag import T
import random

np.set_printoptions(threshold=np.inf)
def get():
while True:
x = []
for i in range(32):
add = [random.randint(0, 10)] * i + [random.randint(0, 10)] * (32 - i)
x.append(add)
if np.linalg.matrix_rank(x) == 32:
return x


a = np.array(get())
b = np.array(get())

# dot 矩阵乘法
aT = np.dot(a, T)
bT = np.dot(b, T)

with open('out', 'w') as f:
for i in range(32):
f.write(str(str(aT[i, :])[1:-1].replace('\n', '')) + '\n') # 写入aT
for i in range(32):
f.write(str(str(bT[i, :])[1:-1].replace('\n', '')) + '\n') # 写入 bT
f.close()
res = np.dot(bT, np.dot(T, aT))
flag = 0
for i in str(res[:, 0])[1:-1].replace('\n', '').split(' '):
if not i == '':
flag = flag + int(i)
print(flag)

题解

1
2
aT = np.dot(a, T)
bT = np.dot(b, T)

可知:T为矩阵aT、bT的最大右公因子

image-20220618221142293

由gcrd得:

将aT、bT堆叠成$\begin{bmatrix} aT \ bT\end{bmatrix}$,初等行变化 将下端化为0(我理解就是行阶梯形矩阵)

又仔细看a*Tb*T,发现每个数居然也都小于10

可想而知,T应该是极为稀疏的矩阵,最后用matlab的rref()函数,得到单位矩阵,应证猜想

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
aTbT = [8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8;
8, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5;
4, 4, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6;
4, 4, 4, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9;
4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5;
10, 10, 10, 10, 10, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6;
2, 2, 2, 2, 2, 2, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9;
8, 8, 8, 8, 8, 8, 8, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5;
3, 3, 3, 3, 3, 3, 3, 3, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9;
9, 9, 9, 9, 9, 9, 9, 9, 9, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1;
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1;
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1;
2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3;
4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0;
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0;
9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6;
10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0;
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8;
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10;
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2;
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9;
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6;
4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2;
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 10, 10, 10, 10, 10, 10, 10, 10, 10;
3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2;
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 9, 9, 9, 9, 9, 9, 9;
2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1;
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 8, 8, 8, 8;
3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 9, 9, 9, 9;
3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 0, 0, 0;
9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 3, 3;
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 10;
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1;
10, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2;
9, 9, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3;
0, 0, 0, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8;
0, 0, 0, 0, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6;
1, 1, 1, 1, 1, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4;
9, 9, 9, 9, 9, 9, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1;
5, 5, 5, 5, 5, 5, 5, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10;
7, 7, 7, 7, 7, 7, 7, 7, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3;
5, 5, 5, 5, 5, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1;
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8;
3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7;
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0;
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6;
5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4;
3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6;
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6;
3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10;
9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5;
9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7;
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9;
9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10;
10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2;
2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 10, 10, 10, 10, 10, 10, 10, 10, 10;
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 9, 9, 9, 9, 9, 9, 9, 9;
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1;
10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 2, 2, 2, 2, 2, 2;
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9;
10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 6, 6, 6, 6;
5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 4, 4;
10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 1, 1;
4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 0;];

t = rref(aTbT)

舍去下半部分0矩阵,得到32*32的单位阵T

代回题目,得解

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
import hashlib
import numpy as np

with open('out.txt') as f:
aTbT = []
num = 1
for i in f.readlines():
tmp = []

for each in i.replace('\n', '').split(' '):
if each != '':
tmp.append(int(each))
aTbT.append(tmp)
print(str(tmp)[1:-1]+';')
num += 1
aT = aTbT[:32]
bT = np.array(aTbT[32:])

T = []
for i in range(32):
tmp = [0 for i in range(32)]
tmp[i] = 1
T.append(tmp)

res = np.dot(bT, np.dot(T, aT))

flag = 0
for i in str(res[:, 0])[1:-1].replace('\n', '').split(' '):
if not i == '':
flag = flag + int(i)

# print(flag)
f = hashlib.md5()
f.update(str(flag).encode())
print('flag{'+str(f.hexdigest())+'}')

math1(200)

题目

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
import gmpy2
from Crypto.Util.number import *
from flag import flag
assert flag.startswith(b"flag{")
assert flag.endswith(b"}")
message=bytes_to_long(flag)
def keygen(nbit, dbit):
if 2*dbit < nbit:
while True:
a1 = getRandomNBitInteger(dbit)
b1 = getRandomNBitInteger(nbit//2-dbit)

n1 = a1*b1+1

if isPrime(n1):
break
while True:
a2 = getRandomNBitInteger(dbit)
b2 = getRandomNBitInteger(nbit//2-dbit)

n2=a2*b2+1

n3=a1*b2+1
if isPrime(n2) and isPrime(n3):
break
while True:
a3=getRandomNBitInteger(dbit)
if gmpy2.gcd(a3,a1*b1*a2*b2)==1:
v1=(n1-1)*(n2-1) # phi1
k=(a3*inverse(a3,v1)-1)//v1 # k * phi1=k * v1 = ed-1
v2=k*b1+1
if isPrime(v2):
return a3,n1*n2,n3*v2
def encrypt(msg, pubkey):
return pow(msg, pubkey[0], pubkey[1])

nbit = 1024
dbit = 256
e, n1, n2=keygen(nbit, dbit)
print('e =', e)
print('n1 =', n1)
print('n2 =', n2)
c1 = encrypt(message, [e, n1])
c2 = encrypt(message, [e, n2])
print('enc1 =', c1)
print('enc2 =', c2)
# e = 86905291018330218127760596324522274547253465551209634052618098249596388694529
# n1 = 112187114035595515717020336420063560192608507634951355884730277020103272516595827630685773552014888608894587055283796519554267693654102295681730016199369580577243573496236556117934113361938190726830349853086562389955289707685145472794173966128519654167325961312446648312096211985486925702789773780669802574893
# n2 = 95727255683184071257205119413595957528984743590073248708202176413951084648626277198841459757379712896901385049813671642628441940941434989886894512089336243796745883128585743868974053010151180059532129088434348142499209024860189145032192068409977856355513219728891104598071910465809354419035148873624856313067
# enc1 = 71281698683006229705169274763783817580572445422844810406739630520060179171191882439102256990860101502686218994669784245358102850927955191225903171777969259480990566718683951421349181856119965365618782630111357309280954558872160237158905739584091706635219142133906953305905313538806862536551652537126291478865
# enc2 = 7333744583943012697651917897083326988621572932105018877567461023651527927346658805965099102481100945100738540533077677296823678241143375320240933128613487693799458418017975152399878829426141218077564669468040331339428477336144493624090728897185260894290517440392720900787100373142671471448913212103518035775

题解

$n_1 = a_1b_1+1,n_2=a_2b_2+1, n_3 = a_1b_2+1,v_2=kb_1+1$,且都为素数

$\phi _{n{_1}} = (n_1-1)(n_2-1) = a_1a_2b_1b_2=v_1$

$\phi _{n{_2}} = (n_3-1)(v_2-1) = a_1b_2kb_1$

k=(a3*inverse(a3,v1)-1)//v1e=a3知:

$k = \frac{e • dinv(e, \phi_{n_1}) -1}{phi} = \frac{ed-1}{\phi_{n_1}} = \frac{k • \phi_{n_1}}{ \phi_{n_1}} = k$

解题思路也是明确的,知道e了,只要知道一个phi就可以求出对应私钥d,便可求解明文m

试了许多方式,题目说数学很重要,以为是n1间n2相乘后有什么关系,但形式越发复杂,无果

加减乘都无效后,尝试除,起初也没看到直接的破题点

后看着题目math1,猛然想起除法所对应连分数,试着分析了下

$\frac{N2}{N1}=\frac{(a_1b_2+1)(kb_1+1)}{(a_1b_1+1)(a_2b_2+1)}≈\frac{a_1b_2kb_1}{a_1b_1a_2b_2}=\frac{k}{a_2}$

image-20220619094607727

再根据Legendre理论,$\frac{k}{a_2}$为$\frac{N2}{N1}$连分数

便可求出一系列的k、a2可能值

又有 $ed-1=k \phi_{n_1}$,所以:

$$\phi_{n_1} ≡ (-1)*k^{-1} \mod e$$

以及

$$\phi_{n_1} ≡ a_1a_2b_1b_2 = 0 \mod a_2$$

利用中国剩余定理联立之,得到$\phi_{n_1} \mod ea_2$

最后,为进一步确定确定$\phi_{n_1}$值,利用:$|𝜙−N1|=|(n_1−1)(n_2−1)−n_1n_2|=|-n_1−n_2+1|≈n_1+n_2 ≤ 2^{513}$

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
import gmpy2
import libnum
from tqdm import tqdm


N1 = 112187114035595515717020336420063560192608507634951355884730277020103272516595827630685773552014888608894587055283796519554267693654102295681730016199369580577243573496236556117934113361938190726830349853086562389955289707685145472794173966128519654167325961312446648312096211985486925702789773780669802574893
N2 = 95727255683184071257205119413595957528984743590073248708202176413951084648626277198841459757379712896901385049813671642628441940941434989886894512089336243796745883128585743868974053010151180059532129088434348142499209024860189145032192068409977856355513219728891104598071910465809354419035148873624856313067
e = 86905291018330218127760596324522274547253465551209634052618098249596388694529
enc1 = 71281698683006229705169274763783817580572445422844810406739630520060179171191882439102256990860101502686218994669784245358102850927955191225903171777969259480990566718683951421349181856119965365618782630111357309280954558872160237158905739584091706635219142133906953305905313538806862536551652537126291478865



# c = continued_fraction(int(N2) / int(N1))
# sage里int不太对
c = continued_fraction(Integer(N2) / Integer(N1))
for i in tqdm(range(1, 163)):
a2 = c.denominator(i)
k = c.numerator(i)
if gmpy2.gcd(k, e) != 1:
continue
tmp = gmpy2.invert(k, e)
res = (-1*tmp) % e
phi_ = crt(res, 0, e, a2)
bound = e * a2 // gmpy2.gcd(e, a2) # lcm

phi1 = phi_ + (N1 // bound) * bound - 3 * bound # phi1
d1 = gmpy2.invert(e, phi1)
flag = libnum.n2s(int(pow(enc1, d1, N1)))
if b"flag" in flag:
print(flag)

总而言之 我们用中国剩余定理得到了$\phi(n_1)$,而他不是真正的$\phi(n_1)$,,可以理解为真正的$phi(n_1) \mod e*a2$的余数

我们需要扩大它 即:$\phi(n_1) = crt结果+k•e•a2$

但$e•a2$才512bit ,简单估计一下,$\phi(n_1)$与n1相近,应该是1024bit左右

如果直接从crt结果开始 从k=1开始遍历 太慢了!

需要适当的「放缩」来选择合适的范围来遍历,以加速,$\phi(n_1)$与N1相近, 就本能的往N1上靠近

于是有 phi1 = phi_ + (N1 // bound) * bound

但显然 phi1的初始值(还没开始遍历k扩大) 是有可能大于N1的,就得缩小

这里可以大致估计的 按照期望 a1b1 、a2b2、ea2大小应该差不多,差了 a1b1 + a2b2 差不多就差了$2•e•a2$即$2•bound$

但前面加了 phi_ 保险起见应该再减多一个$e•a2$,经调试,的确如此
image-20220707213016894

Rand0m3(200)

题目

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
#!/usr/bin/python3
# Rand0m3
import os, sys
import struct

def _print(content, end = None):
if end != None:
print(content, end = end)
else:
print(content)
sys.stdout.flush()

def read_flag():
with open("flag", "r") as f:
res = f.read()
return res

def print_prompt():
_print("1. encrypt input")
_print("2. decrypt input")
_print("3. encrypt flag")
_print("4. exit")
_print(">> ", end = "")

def read_int():
return int(read_string())

def read_string():
return input().strip()

def get_random_u8():
return struct.unpack("<B", os.urandom(1))[0]

def encrypt(s, k):
res = ""
if k <= len(s):
_print("[!] key shold be larger then len(pt) for safty!!")
return ""
for i, c in enumerate(s):
enc = (get_random_u8() + k * i) % 0xff
enc = ord(c) ^ enc
res += hex(enc)[2:].rjust(2, "0")
return res

def decrypt(s, k):
_print("[*] Give me the paper about predicting urandoGive me the paper about predicting urandomm")
_print("[*] ...Then i'll decrypt your input ;)")
return ""

if __name__ == "__main__":
flag = read_flag()
while True:
print_prompt()
c = read_int()
if c == 1:
_print("key >> ", end = "")
key = read_int()
_print("pt >> ", end = "")
pt = read_string()
_print("result : %s"%encrypt(pt, key))
elif c == 2:
_print("key >> ", end = "")
key = read_int()
_print("ct >> ", end = "")
ct = read_string()
_print("result : %s"%decrypt(ct, key))
elif c == 3:
_print("key >> ", end = "")
key = read_int()
_print("result : %s"%encrypt(flag, key))
elif c == 4:
_print("bye!!")
exit(0)
else:
_print("invalid option...")

题解

巧,上个月刷到原题了,当时没写出来

赛后跟着wp尝试复现了下,居然撞上了

察觉后,觉得略有不同,在交互上卡了好一会,最后发现确实是一致的

想清楚了,思路也清晰

首先,关注题目中的加密代码

1
2
3
4
5
6
7
8
9
10
def encrypt(s, k):
res = ""
if k <= len(s):
_print("[!] key shold be larger then len(pt) for safty!!")
return ""
for i, c in enumerate(s): # i 为index位置, c为s[i]
enc = (get_random_u8() + k * i) % 0xff # 0到254
enc = ord(c) ^ enc # 唯独不可能与异或0b11111111异或
res += hex(enc)[2:].rjust(2, "0") # 补齐两位
return res

破题点在于% 0xff,这样导致第一步的enc范围固定下来,只能是0到254

其后,enc = ord(c) ^ enc,那么ord(c)就不可能与0b11111111(255)异或

所以为确定一位flag字符,只要进行多次encrypt,在0到255中排除到只剩1个数,那么它就是flag[i]^255(key不妨就设为255)的结果

那么,都确定好后,根据异或可逆性质再异或回来即可

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
from pwn import *

p = remote('172.16.30.220', 58005) # 记得改ip 端口
key = 255

p.sendlineafter('>> ', '3') # 模式3
p.sendlineafter('key >> ', '255') # 输入key值
p.recvuntil('result : ') # 准备接受enc(flag, key)

enc_flag = p.recvline()
flag_len = len(enc_flag) // 2
flag_set = [list(range(256)) for _ in range(flag_len)] # 存放每一位可能的flag_enc
flag = [0 for x in range(flag_len)] # flag初始化为一串0

while True:
p.sendlineafter('>> ', '3')
p.sendlineafter('key >> ', '255')
p.recvuntil('result : ')

enc_flag = bytes.fromhex(p.recvline()[:-1].decode())

for i in range(flag_len):
if flag_set[i].count(enc_flag[i]) == 1:
flag_set[i].remove(enc_flag[i])

if len(flag_set[i]) == 1:
flag[i] = chr(flag_set[i][-1] ^ key)

print([len(x) for x in flag_set])

if 0 not in flag: # 校验完毕
break

print(''.join(flag))

fcsr (未解)

  • 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
    from random import getrandbits

    bits = 80
    mask = 2 ** bits - 1
    feedback = 0xae985dff26619fc58623dc8aaf46d5903dd4254e # ???


    class Task:
    def __init__(self, key, iv):
    self.key = key
    self.iv = iv
    self.filter = feedback
    self.state = (self.iv << bits) | self.key # 或运算
    self.C = 0

    S = [0] * 20 # [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
    for i in range(20):
    self.clock()
    S[i] = self.F()

    self.state = 0
    for i in range(20):
    shift = i * 8
    self.state |= (S[i] << shift)

    self.C = 0
    for _ in range(162):
    self.clock()

    def clock(self):
    tmp = self.state & 1
    if tmp:
    fb = feedback
    else:
    fb = 0
    self.state = self.state >> 1
    buffer = self.state ^ self.C
    self.C &= self.state

    self.C ^= (buffer & fb)
    buffer ^= fb
    self.state = buffer

    def F(self):
    buffer = self.filter & self.state
    buffer ^= ((buffer >> 32) & 0xffffffff)
    buffer ^= ((buffer >> 64) & 0xffffffff)
    buffer ^= ((buffer >> 96) & 0xffffffff)
    buffer ^= ((buffer >> 128) & 0xffffffff)
    buffer = buffer & 0xffffffff
    buffer ^= (buffer >> 16)
    buffer ^= (buffer >> 8)

    return buffer & 0xff

    def encrypt(self, msg):
    length = len(msg)
    res = b""
    for i in range(length):
    self.clock()
    res += bytes([self.F() ^ msg[i]])
    return res


    key = getrandbits(bits)
    iv = getrandbits(bits)
    print(key)
    print(iv)
    ffcsr = Task(key, iv)
    f = open("hint", "wb")
    for i in range(2 ** 26):
    ffcsr.clock()
    f.write((ffcsr.F().to_bytes(1, "big")))
    f.close()
    flag = b"flag{xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx}"
    f = open("flag", "wb")
    enc = ffcsr.encrypt(flag)
    f.write(enc)
    f.close()
  • flag

  • hint

总结

还有一道fcsr(400分,0解)没出也没细研究

虽然时间上确实有些来不及了,但本质上还是怠惰了、畏难了

要是别的师傅一看赛题,东北赛区的密码师傅就这?

可太丢脸了😢