被拉来打的，只做了 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:]))