2020 新春战疫网络安全公益赛 WriteUp

🏛️ 组织架构

  • 赛事由永信至诚旗下的春秋 Game 与 i 春秋团队牵头主办

  • 联合发起方：包括安全狗、百度、哔哩哔哩、滴滴、京东、快手、美团、腾讯、小米、字节跳动等在内的 34 家互联网公司及知名企业

  • 联合命题战队：Nu1L、Venom、Xp0int、W&M、kn0ck、VIDAR-TEAM、Ginkgo、Timekeeper、SU、0RAYS等 10 支国内知名网络安全战队参与了命题，并将酬劳兑换为物资捐赠

  • 专家委员会：邀请了 Atum、L1n3、Pcat、seabreeze、Veneno7、吴炜等技术领袖组成专家委员会，负责赛事质量把关

🏆 比赛结果与影响

  • 本次比赛不设现金奖励，官方也未公布完整的个人排名榜单，其核心成果体现在公益捐赠上

  • 公益捐赠：大赛以参赛选手、联合发起单位、出题人及获奖选手的共同名义，向疫区捐赠了 180 箱医疗防护物资，并通过中国邮政的防疫物资运输通道，直接送达武汉市第一医院等一线医护人员手中

  • 赛事评价：作为 2020 年第一场网络安全界大规模比赛，它汇聚了多方安全力量，用网安人特有的方式践行了社会责任，获得了参赛者的一致好评

Misc

磁盘套娃

Crypto

simple_math（RSA Wilson 定理 + 利用 ed 同余关系分解 n）

pasted_1789308771771_cix0re.png

题目核心代码如下

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
def gen_p():
    A = gen_prime(513)
    print("A:", A)
    B = (A - 1) // 2
    C = A - randint(1e3, 1e5)
    print("C:", C)
    
    N1 = gen_N(A, B)
    N2 = gen_N(A, C)
    seed1 = 2019 * N1 + 2020 * N2
    return sympy.nextprime(seed1)

def gen_q():
    p = getPrime(1024)
    q = getPrime(1024)
    assert(p < q)
    n = p * q
    print("n:", n)

    e = getRandomNBitInteger(50)
    phi = (p - 1) * (q - 1)
    while gcd(e, phi) != 1:
        e = getRandomNBitInteger(50)

    d = invert(e, phi)
    print("e*d:", e * d)

    seed2 = 2020 * p - 2019 * q
    if seed2 < 0:
        seed2 = (-1) * seed2

    return sympy.nextprime(seed2)

最后加密

1
2
3
4
5
_E = 65537
_P = gen_p()
_Q = gen_q()
_M = bytes_to_long(flag)
_C = pow(_M, _E, _P * _Q)

所以真正用来加密 flag 的 RSA 模数是 N = _P * _Q，我们要分别恢复 _P 和 _Q

题目给了 A 和 C，并且

1
2
3
4
B = (A - 1) // 2
N1 = B! mod A
N2 = C! mod A
_P = nextprime(2019 * N1 + 2020 * N2)

其中 C = A - randint(1e3, 1e5)，所以 C 和 A 非常接近

令 k = A - C，附件里实际算出来 k = 67381，也就是说 C = A - 67381

如果直接算 C! mod A 肯定不行，因为 C 是一个 513 bit 级别的大数

Wilson 定理一句话：如果 A 是素数，那么 (A - 1)! ≡ -1 (mod A)

阶乘定义是 n! = 1 * 2 * 3 * …… * n，也就是说 1 * 2 * 3 * …… * (A - 1) ≡ A - 1 (mod A)

因为 -1 + A = A - 1，所以 A - 1 ≡ -1 (mod A)

由同余的传递性，得到 (A - 1)! ≡ -1 ≡ A - 1 (mod A)

题目里 C = A - K，因为 K 是正整数，且 K < A，所以 1 < C < A

也就是说 C 是 1 到 A - 1 之间的一个整数

因此 1 * 2 * 3 * …… * (A - 1) 可以拆成两段：第一段是从 1 到 C，第二段是从 C + 1 到 A - 1

1
(A - 1)! = (1 * 2 * 3 * …… * C) * ((C + 1) * (C + 2) * …… * (A - 1))

而 1 * 2 * 3 * …… * C = C!，所以

1
2
(A - 1)! = (1 * 2 * 3 * …… * C) * ((C + 1) * (C + 2) * …… * (A - 1))
(A - 1)! = C! * ((C + 1) * (C + 2) * …… * (A - 1))

又因为 C = A - K，所以 K = A - C，于是

1
2
C + 1 = A - K + 1 = A - (K - 1)
C + 2 = A - K + 2 = A - (K - 2)

一直到最后 A - 1 = A - 1，所以第二段变成 (A - (K - 1) * A - (K - 2) * …… * (A - 1))

在模 A 下

1
2
3
4
A - (K - 1) ≡ -(K - 1)
A - (K - 2) ≡ -(K - 2)
……
A - 1 ≡ -1

所以第二段模 A 等于 (-(K - 1) * (-(K - 2)) * …… * (-1))

一共有 K - 1 个负号，所以 (-1) ^ (K - 1) * (K - 1) * (K - 2) * …… * 1

也就是 (-1) ^ (K - 1) * (K - 1)!，再代回去

1
2
(A - 1)! = C! * ((C + 1) * (C + 2) * …… * (A - 1))
(A - 1)! ≡ C! * (-1) ^ (K - 1) * (K - 1)!

由于 A 是素数，Wilson 定理得到 (A - 1)! ≡ -1 (mod A)

所以 -1 ≡ C! * (-1) ^ (K - 1) * (K - 1)! (mod A)

两边同时乘以 (-1) ^ (K - 1)

1
2
3
-1 * (-1) ^ (K - 1) = (-1) ^ k

(C! * (-1) ^ (K - 1) * (K - 1)!) *  (-1) ^ (K - 1) = C! * (K - 1)!

所以 (-1) ^ k ≡ C! * (K - 1)! (mod A)，两边同时乘以 (K - 1)! 的逆元

因为 A 是素数，且 K - 1 < A，所以 1 * 2 * 3 * …… * (K - 1) = (K - 1)! 与 A 互素，即

1
gcd((K - 1)!, A) = 1

所以 (K - 1)! 在模 A 下存在逆元，设这个逆元为 inv = ((K - 1)!) ^ (-1) (mod A)

1
2
(-1) ^ k * inv ≡ C! * (K - 1)! * inv (mod A)
(-1) ^ k * inv ≡ C! * ((K - 1)! * inv) (mod A)

因为 (K - 1)! * inv = 1 (mod A)

1
2
3
4
(-1) ^ k * inv ≡ C! * ((K - 1)! * inv) (mod A)
(-1) ^ k * inv ≡ C! (mod A)
(-1) ^ k * ((K - 1)!) ^ (-1) ≡ C! (mod A)
C! ≡ (-1) ^ k * ((K - 1)!) ^ (-1) (mod A)

因此 N2 = C! (mod A) = (-1) ^ k * ((K - 1)!) ^ (-1) (mod A)

接下来继续恢复 N1 = ((A - 1) // 2)! mod A，令 m = (A - 1) / 2

根据 Wilson 定理：(A - 1)! ≡ -1 mod A，把 (A - 1)! 从 m 处切开

1
(A - 1)! = (1 * 2 * 3 * …… * m) * ((m + 1) * (m + 2) * …… * (A - 1))

前半段为 1 * 2 * 3 * …… * m = m!，后半段在模 A 下

1
2
3
4
m + 1 = -m (mod A)
m + 2 = -(m - 1) (mod A)
……
A - 1 = -1 (mod A)

所以

1
(m + 1) * (m + 2) * …… * (A - 1) ≡ (-m) * (-(m - 1)) * …… * (-1) (mod A)

这里一共有 m 个负号，所以

1
(-m) * (-(m - 1)) * …… * (-1) = (-1) ^ m * m * (m - 1) * …… * 1

而 m * (m - 1) * …… * 1 = m!，所以

1
2
3
4
5
(m + 1) * (m + 2) * …… * (A - 1) ≡ (-m) * (-(m - 1)) * …… * (-1) (mod A)
(m + 1) * (m + 2) * …… * (A - 1) ≡ (-1) ^ m * m! (mod A)

(A - 1)! ≡ (-1) ^ m * m! * m! (mod A)
(A - 1)! ≡ (-1) ^ m * (m!) ^ 2 (mod A)

由 Wilson 定理：(A - 1)! ≡ -1 (mod A)，所以

1
2
(A - 1)! ≡ (-1) ^ m * (m!) ^ 2 (mod A)
      -1 ≡ (-1) ^ m * (m!) ^ 2 (mod A)

因为 A ≡ 3 (mod 4)，设 A = 4t + 3，则

1
2
3
m = (A - 1) / 2
  = (4t + 3 - 1) / 2
  = 2t + 1

因为 m 是奇数，因此

1
2
3
(-1) ^ m = (-1) ^ (2t + 1)
         = (-1) ^ (2t) * (-1) ^ 1
         = -1

代入 -1 ≡ (-1) ^ m * (m!) ^ 2 (mod A) 中，得到

1
2
-1 ≡ (-1) ^ m * (m!) ^ 2 (mod A)
-1 ≡ (-1) * (m!) ^ 2 (mod A)

两边同时乘以 −1

1
2
1 ≡ (m!) ^ 2 (mod A)
(m!) ^ 2 ≡ 1 (mod A)

而 N1 ≡ m! (mod A)，所以 N1 ^ 2 ≡ 1 (mod A) 

1
2
3
N1 ^ 2 ≡ 1 (mod A)
N1 ^ 2 - 1 ≡ 0 (mod A)
(N1 - 1)(N1 + 1) ≡ 0 (mod A)

因为 A 是素数，所以 A | (N1 - 1) 或 A | (N1 + 1)，于是

1
N1 ≡ 1 (mod A) 或 N1 ≡ -1 (mod A)

即 N1 = 1 或 N1 = A - 1

题目里

1
2
seed1 = 2019 * N1 + 2020 * N2
   _p = nextprime(seed1)

所以对 N1 的两个取值，分别计算一次 seed1，得到两个候选 _p

当 N1 = 1 时，得到 _P = 29980405391237365494597168525833309900267720449837722663797882464292688736399471276643180209621186905684266642360886383187160507504219009609357296973525651439

题目给了

1
2
n = p * q
ed = e * d

其中 e * d ≡ 1 mod phi(n)，所以 e * d - 1 = k * phi(n)

也就是说，题目泄露了 ed，相当于泄露了一个 phi(n) 的倍数

对于任意与 n 互素的随机数 a，都有 a ^ (ed - 1) ≡ 1 (mod n)

把 ed - 1 拆成 ed - 1 = 2 ^ s * r，其中 r 是奇数，然后取随机底数 a，计算

1
x = pow(a, r, n)

不断平方 x = x ^ 2 mod n，如果某一步出现 x ^ 2 ≡ 1 mod n，但是

1
2
x != 1
x != -1 mod n

那么 x 是模 n 下的非平凡平方根，可以用 gcd(x - 1, n) 分解出 n 的一个因子

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
import re
import math
import random
import sympy


def long_to_bytes(x: int) -> bytes:
    return x.to_bytes((x.bit_length() + 7) // 8, "big")


def read_params(filename="simple_math.py"):
    with open(filename, "r", encoding="utf-8") as f:
        data = f.read()

    A = int(re.search(r"A:(\d+)", data).group(1))
    C = int(re.search(r"C:(\d+)", data).group(1))
    n = int(re.search(r"n:(\d+)", data).group(1))
    ed = int(re.search(r"e\*d:(\d+)", data).group(1))
    ciphertext = int(re.search(r"ciphertext:(\d+)", data).group(1))

    return A, C, n, ed, ciphertext


def recover_N2(A, C):
    """
    N2 = C! mod A
    C = A - k

    Wilson:
        (A - 1)! ≡ -1 mod A

    又有：
        (A - 1)! = C! * (C + 1) * ... * (A - 1)

    由于 C = A - k：
        (C + 1) ... (A - 1)
        ≡ (-1)^(k-1) * (k-1)! mod A

    所以：
        C! ≡ (-1)^k * inverse((k-1)!) mod A
    """
    k = A - C

    fac = 1
    for i in range(1, k):
        fac = fac * i % A

    N2 = pow(-1, k, A) * pow(fac, -1, A) % A
    return N2


def factor_from_ed(n, ed):
    """
    已知 ed，分解 n。

    因为：
        ed ≡ 1 mod phi(n)

    所以：
        ed - 1 是 phi(n) 的倍数。

    利用 ed - 1 = 2^s * r，r 为奇数。
    通过寻找模 n 下的非平凡平方根分解 n。
    """
    k = ed - 1

    s = 0
    r = k
    while r % 2 == 0:
        s += 1
        r //= 2

    while True:
        a = random.randrange(2, n - 1)
        g = math.gcd(a, n)
        if g > 1:
            return g, n // g

        x = pow(a, r, n)

        if x == 1 or x == n - 1:
            continue

        for _ in range(s):
            y = pow(x, 2, n)

            if y == 1:
                p = math.gcd(x - 1, n)
                if 1 < p < n:
                    q = n // p
                    return min(p, q), max(p, q)

            if y == n - 1:
                break

            x = y


def main():
    A, C, n, ed, ciphertext = read_params("simple_math.py")

    e = 65537

    # ---------- recover _P ----------
    N2 = recover_N2(A, C)

    # N1 = ((A-1)//2)! mod A
    # 由 Wilson 可知 N1^2 ≡ 1 mod A
    # 所以 N1 只可能是 1 或 A-1，两个都试。
    N1_candidates = [1, A - 1]

    # ---------- recover _Q ----------
    p, q = factor_from_ed(n, ed)
    seed2 = abs(2020 * p - 2019 * q)
    Q = sympy.nextprime(seed2)

    # ---------- decrypt ----------
    for N1 in N1_candidates:
        seed1 = 2019 * N1 + 2020 * N2
        P = sympy.nextprime(seed1)

        phi = (P - 1) * (Q - 1)

        if math.gcd(e, phi) != 1:
            continue

        d = pow(e, -1, phi)
        m = pow(ciphertext, d, P * Q)
        flag = long_to_bytes(m)

        if flag.startswith(b"flag{"):
            print(flag.decode())
            return

    print("failed")


if __name__ == "__main__":
    main()