被拉来打的，只做了 Crypto。做啥写啥。
100 Points
要么照着题目随便搞搞，要么搜索一下，大部分就是古典密码或者轮换替换，批量一键过题。
Very Smooth
审计 get_smooth_prime，发现 $p-1$ 是光滑质数，所以用 Pollard’s p-1 算法分解质因子：
1
2
3
4
5
6
7
8
9
10
11
| from gmpy2 import powmod, gcd
def factor_smooth_p(N: int) -> (int, int):
a = 2
n = 2
for n in range(2, N)
a = powmod(a, n, N)
res = gcd(a - 1, N)
if res != 1 and res != N:
q = N // res
p = N // q
return p, q
|
然后直接跑就行了。
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
| from gmpy2 import powmod, gcd, lcm
def factor_smooth_p(N):
a = 2
n = 2
for n in range(2, N):
a = powmod(a, n, N)
res = gcd(a - 1, N)
if res != 1 and res != N:
q = N // res
p = N // q
return p, q
if __name__ == "__main__":
e = 0x10001
# copy from file
n = int('', 16)
c = int('', 16)
p, q = factor_smooth_p(n)
m = lcm(p - 1, q - 1)
d = powmod(e, -1, m)
print(bytes.fromhex(hex(powmod(c, d, n))[2:]))
|
Sequences
直接审计 m_func：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| # snippets...
ITERS = int(2e7)
# This will overflow the stack, it will need to be significantly optimized in order to get the answer :)
@functools.cache
def m_func(i):
if i == 0: return 1
if i == 1: return 2
if i == 2: return 3
if i == 3: return 4
return 55692 * m_func(i - 4) - 9549 * m_func(i - 3) + 301 * m_func(
i - 2) + 21 * m_func(i - 1)
# snippets...
if __name__ == "__main__":
sol = m_func(ITERS)
decrypt_flag(sol)
|
$$
f(x) = \begin{cases}x+1, &1\le x\le 3\\21f(x-1)+301f(x-2)-9549f(x-3)+55692f(x-4),&3<x\end{cases}, x\in\N^+
$$
一个非常经典的线性递推。因为 iter 数量有 $2\times10^7$ 次，直接递推也是不太方便的，考虑矩阵快速幂优化线性递推。
$$
\begin{bmatrix}f(x+3)\\f(x+2)\\f(x+1)\\f(x)\end{bmatrix}=\begin{bmatrix}21&301&-9549&55692\\1&0&0&0\\0&1&0&0\\0&0&1&0\end{bmatrix}^x\cdot\begin{bmatrix}f(3)\\f(2)\\f(1)\\f(0)\end{bmatrix}
$$
对这个方法不太了解的可以参考 https://oi-wiki.org/math/fibonacci/#_5。
注意 numpy 默认的数据类型会爆精度，需要手动指定 dtype='object'。同时该取模的地方要取上。
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
| import numpy as np
MOD = 10**10000
def bin_pow(base, exp):
ans = np.array([[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1]],
dtype='object')
while exp:
if (exp & 1) > 0:
ans = ans.dot(base) % MOD
base = base.dot(base) % MOD
exp >>= 1
return ans
def fast_m_func(i):
if i == 0: return 1
if i == 1: return 2
if i == 2: return 3
if i == 3: return 4
arr = np.array([[4], [3], [2], [1]], dtype='object')
coef = np.array(
[[21, 301, -9549, 55692], [1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0]],
dtype='object')
return bin_pow(coef, i - 3).dot(arr)[0][0]
|
Sum-O-Primes
不知道为什么这个题要给 400 points。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| from sympy import symbols, solve
import math
if __name__ == "__main__":
e = 65537
# copy from file
x = int('', 16)
n = int('', 16)
c = int('', 16)
P, Q = symbols('p,q')
# x = p + q
# n = p * q
ret = solve([P + Q - x, P * Q - n], [P, Q], dict=True)
p = ret[0][P]
q = ret[0][Q]
m = math.lcm(p - 1, q - 1)
d = pow(e, -1, m)
print(bytes.fromhex(hex(pow(c, d, n))[2:]))
|
NSA Backdoor
首先 $p-1$ 和 $q-1$ 都是光滑的，直接用 Pollard’s p-1 算法搞出来。
搞出来后注意到我们要求解的式子，是一个离散对数问题：
$$
c= 3^{\text{FLAG}} \pmod n
$$
朴素的 BSGS 复杂度太高，直接算算不了。由于 $n=p\times q$，而 $p$，$q$ 都是光滑质数，而且根据生成方式，$p$ 和 $q$ 的质因子不大，数量也不多，提示我们可以用 Pohlig-Hellman 算法求离散对数。
具体的算法可以参考 https://ctf-wiki.org/crypto/asymmetric/discrete-log/discrete-log/#pohlig-hellman-algorithm。我直接用 sage 算了。
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
| from sage.all import gcd, GF
def factor_smooth_p(N):
a = 2
n = 2
for n in range(2, N):
a = pow(a, n, N)
res = gcd(a - 1, N)
if res != 1 and res != N:
q = N // res
p = N // q
return p, q
if __name__ == "__main__":
# copy from file
n = int('', 16)
c = int('', 16)
p, q = factor_smooth_p(n)
R = GF(p)
x = R(c).log(3)
assert R(3)**x == c
print(bytes.fromhex(hex(x)[2:]))
|