点击此处获得更好的阅读体验
WriteUp来源
来自Bellin的博客
解题思路
这次的crypto题目简直离谱，虽然有难度，但是都是前面比赛出现过的原题的一丢丢魔改就拿来出题。所以基本上你会Google基本就能AK。
这个的原题writeup链接：Pokajeon / Kapojeon 2020
server 源代码
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#!/usr/bin/env python3
from decimal import *
import math
import random
import struct
# from flag import flag
flag=b"123456"*6
assert (len(flag) == 48)
msg1 = flag[:24]
msg2 = flag[24:]
primes = [2]
for i in range(3, 90):
f = True
for j in primes:
if i * i < j:
break
if i % j == 0:
f = False
break
if f:
primes.append(i)
print(primes)
getcontext().prec = 100
keys = []
for i in range(len(msg1)):
keys.append(Decimal(primes[i]).ln())
print(keys)
sum_ = Decimal(0.0)
for i, c in enumerate(msg1):
# print(i,c)
sum_ += c * Decimal(keys[i])
ct = math.floor(sum_ * 2 ** 256)
print(ct)
sum_ = Decimal(0.0)
for i, c in enumerate(msg2):
sum_ += c * Decimal(keys[i])
ct = math.floor(sum_ * 2 ** 256)
print(ct)
类似0/1背包问题，将[3,89]的素数的自然对数值作为密钥，然后和flag的每个byte乘后累加，最后再乘以2256。
恢复方法是低密度攻击。然后不管这些，其实魔改writeup的代码即可
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# sagemath
import math
from decimal import *
import random
import struct
getcontext().prec = int(100)
primes = [2]
for i in range(3, 90):
f = True
for j in primes:
if i * i < j:
break
if i % j == 0:
f = False
break
if f:
primes.append(i)
keys = []
for i in range(len(primes)):
keys.append(Decimal(int(primes[i])).ln())
arr = []
for v in keys:
arr.append(int(v * int(16) ** int(64)))
ct = 425985475047781336789963300910446852783032712598571885345660550546372063410589918
# ct = 597952043660446249020184773232983974017780255881942379044454676980646417087515453
def encrypt(res):
h = Decimal(int(0))
for i in range(len(keys)):
h += res[i] * keys[i]
ct = int(h * int(16)**int(64))
return ct
def f(N):
ln = len(arr)
A = Matrix(ZZ, ln + 1, ln + 1)
for i in range(ln):
A[i, i] = 1
A[i, ln] = arr[i] // N
A[ln, i] = 64
A[ln, ln] = ct // N
res = A.LLL()
for i in range(ln + 1):
flag = True
for j in range(ln):
if -64 <= res[i][j] < 64:
continue
flag = False
break
if flag:
vec = [int(v + 64) for v in res[i][:-1]]
ret = encrypt(vec)
if ret == ct:
print(N, bytes(vec))
else:
print("NO", ret, bytes(vec))
for i in range(2, 10000):
print(i)
f(i)
Flag
1
flag{715c39c3-1b46-4c23-8006-27b43eba2446}