2020 网鼎杯-青龙组 WriteUp

🏛️ 组织架构

  • 支持单位：国家网络与信息安全信息通报中心、深圳市人民政府、广东省公安厅

  • 联合主办：深信服科技股份有限公司、北京永信至诚科技股份有限公司

  • 联合协办：阿里巴巴、百度、腾讯、奇安信、清华大学网络科学与网络空间研究院、中国科学院信息工程研究所等

📝 赛事概况

  • 赛事定位：”朱雀组” 是第二届 “网鼎杯” 四场官方线上资格赛的首场比赛

  • 参赛对象：主要面向全国高等院校、职业院校以及社会参赛队伍

  • 比赛时间：2020 年 5 月 10 日 9:00 - 17:00，时长 8 小时

  • 晋级名额：资格赛晋级名额为 130 支队伍

Crypto

boom（签到）

博客地址：http://www.fzwjscj.xyz/index.php/archives/27/

第一题是求 MD5

第二题解方程

第三题同理

最后拿到 flag

you raise me up（模幂离散对数）

题目

1
2
3
n = 2 ** 512
m = random.randint(2, n-1) | 1
c = pow(m, bytes_to_long(flag), n)

也就是 c ≡ m ^ e (mod 2 ^ 512)

并且 m 被强制为奇数

1
m = random.randint(2, n-1) | 1

奇数在模 2 ^ 512 下一定有乘法逆元（因为与模数互素），所以它属于乘法群

这是一个模 2 的幂下的离散对数问题，一般离散对数很难，但模 2 的幂的群结构很特殊——它的阶是 2 ^ 511

因为 φ(2 ^ 512) = 2 ^ 511

但我们可以利用 “模 4” 这个小的模数先偷看一点信息，这个信息就是指数 e 的奇偶性

规律：底数为 3 (mod 4) 时，奇数次幂永远是 3 (mod 4)，偶数次幂永远是 1 (mod 4)

题目给出的 m 和 c 满足

1
2
m % 4 = 3
c % 4 = 3

所以指数 e 必为奇数

因为 e 是奇数，它可以写成

1
e = 2x + 1

代入原方程

1
c ≡ m ^ (2x + 1) (mod 2 ^ 512)

两边同时乘 m 的模逆

1
2
3
c * m ^ (-1) ≡ m ^ (2x + 1) * m ^ (-1) (mod 2 ^ 512)

c * m ^ (-1) ≡ m ^ 2x (mod 2 ^ 512)

令 g = m ^ 2，h = c * m ^ (-1)

1
g ^ x ≡ h (mod 2 ^ 512)

现在是要解出这个 x，因为 m 是奇数，m ^ 2 模 8 一定等于 1

任何奇数的平方减 1 都能被 8 整除

所以，我们可以把 g 写成

1
2
3
4
g = 1 + 8u
  = 1 + 2 ^ 3 * u

(u 是某个奇数)

在模 2 的幂的乘法群结构中有一个经典结论，对于形如 1 + 2^s * u（u为奇数） 且 s >= 2 的元素

它在模 2 ^ k 下的阶就是 2 ^ (k - s)

这里 k = 512, s = 3，所以 g 的阶就是

1
ord(g) = 2 ^ 509

这意味着，g 的 2 ^ 509 次方才会第一次回到 1

g 的所有幂次形成了一个有 2 ^ 509 个元素的循环圈。我们要求的指数 x 就在 0 到 2 ^ 509 - 1 之间。这个范围虽然大，但它的结构（阶是 2 的幂）给了我们可乘之机

我们已知 g ^ x ≡ h (mod 2 ^ 512)

并且 g 的阶是 r = 509，即 g 的幂次是一个 509 位的二进制数就能完全覆盖的圈

这个算法的精髓就是：我们可以一位一位地确定指数 x 的二进制位，从最低位到最高位

假设我们要求的指数 x 的二进制表示是

我们的目标是求出每一个 b_i（0 或 1）

假设我们已经通过某种方法求出了 x 的最低 i 位。我们把这部分已知的数值记作 x_i

例如，如果已知最低两位是 01，那 x_2 = 1

现在 x 可以拆成两部分

1
x = x_i + (剩下的高位部分)

因为 g 是奇数，与 2 ^ 512 互素，所以 g ^ (x_i) 一定有逆元，记作 g ^ (-x_i)

1
2
3
g ^ x ≡ h (mod 2 ^ 512)

g ^ x_i * g ^ (-x_i) ≡ 1 (mod 2 ^ 512)

对原等式 g ^ x ≡ h 两边乘以 g ^ (-x_i)

1
2
3
g ^ x * g ^ (-x_i) ≡ h * g ^ (-x_i) (mod 2 ^ 512)

     g ^ (x - x_i) ≡ h * g ^ (-x_i) (mod 2 ^ 512)

我们把右边这个已知的数值叫做 t

1
t ≡ h * g ^ (-x_i) (mod 2 ^ 512)

那么根据上面的等式，自然就有：

1
t ≡ g ^ (x - x_i) (mod 2 ^ 512)

因为 x_i 恰好包含了 x 的低 i 位，所以相减之后，低 i 位全部变成 0

于是我们可以写成

这里：

  • b_i * 2 ^ i 就是我们要找的第 i 位的值（只能是 0 或 1）

  • q 是更高位的总和，每一项至少包含因子 2 ^ (i + 1)，所以可以提取 2 ^ (i + 1) 出来，剩下的用 q 表示

我们想 “过滤” 掉高位 q，只留下 b_i 的信息。因为 g 的阶是 2 ^ r，我们可以利用一个性质：

如果一个指数包含 2 ^ r 这个因子，那一项就会变成 1

于是，我们故意把等式两边都升到 2 ^ (r - 1 - i) 次方

1
2
3
t ^ {2 ^ (r - 1 - i)} ≡ {g ^ (x - x_i)} ^ {2 ^ (r - 1 - i)} (mod 2 ^ 512)

t ^ {2 ^ (r - 1 - i)} ≡ g ^ {(x - x_i) * 2 ^ (r - 1 - i)} (mod 2 ^ 512)

代入 x - x_i 表达式

所以，我们现在得到

1
t ^ {2 ^ (r - 1 - i)} ≡ g ^ {b_i * 2 ^ (r - 1) + (q * 2 ^ r)}

现在指数里有一项是 q * 2 ^ r，我们可以把它拆开

1
2
g ^ {b_i * 2 ^ (r - 1) + (q * 2 ^ r)} = g ^ {b_i * 2 ^ (r - 1)} * g ^ (q * 2 ^ r)
                                      = g ^ {b_i * 2 ^ (r - 1)} * {g ^ (2 ^ r)} ^ q

因为 g 的阶是 2 ^ r，也就是说 g ^ (2 ^ r) ≡ 1 (mod 2 ^ 512)，所以：

1
2
{g ^ (2 ^ r)} ^ q ≡ 1 ^ q
                  ≡ 1

于是整个式子简化为

1
t ^ {2 ^ (r - 1 - i)} ≡ g ^ {b_i * 2 ^ (r - 1)}

现在指数只剩下 b_i * 2 ^ (r - 1)，因为 b_i 只能是 0 或 1，所以只有两种情况

  • 如果 b_i = 0，指数为 0 * 2 ^ (r - 1) = 0，于是 t ^ {2 ^ (r - 1 - i)} ≡ g ^ 0 ≡ 1

  • 如果 b_i = 1，指数为 1 * 2 ^ (r - 1)，于是 t ^ {2 ^ (r - 1 - i)} ≡ g ^ {2 ^ (r - 1)}

如何在实际算法中判断？？？我们预先计算好 “标记值”：

1
marker = g ^ {2 ^ (r - 1)} (mod 2 ^ 512)

这个 marker 有一个特点：它不等于 1，但是它的平方等于 1

因为

1
[g ^ {2 ^ (r - 1)}] ^ 2 = g ^ (2 ^ r) = 1

在每一步（第 i 位），我们计算

1
val = t ^ {2 ^ (r - 1 - i)} (mod 2 ^ 512)

然后判断：

  • 若 val == 1，则第 i 位是 0

  • 若 val == marker，则第 i 位是 1

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
m = 391190709124527428959489662565274039318305952172936859403855079581402770986890308469084735451207885386318986881041563704825943945069343345307381099559075

c = 6665851394203214245856789450723658632520816791621796775909766895233000234023642878786025644953797995373211308485605397024123180085924117610802485972584499

N = 2 ** 512


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


def v2(x):
    """
    返回 x 中因子 2 的次数。
    例如 v2(40) = 3，因为 40 = 2^3 * 5。
    """
    return (x & -x).bit_length() - 1


def order_power_two(g, N):
    """
    计算 g 在模 N 下的阶。
    本题中阶一定是 2 的幂，所以不断平方直到等于 1。
    如果 g 的阶为 2^r，则返回 r。
    """
    cur = g % N
    r = 0

    while cur != 1:
        cur = pow(cur, 2, N)
        r += 1

    return r


def dlog_power2(g, h, N, r):
    """
    求解 g^x = h mod N
    其中 ord(g) = 2^r。

    使用逐 bit 的 Pohlig-Hellman 思路。
    """
    x = 0
    gx = 1

    # g^(2^(r-1)) 是阶为 2 的元素
    marker = pow(g, 1 << (r - 1), N)

    for i in range(r):
        # 去掉已经恢复出来的低 i 位
        t = h * pow(gx, -1, N)
        t %= N

        # 判断第 i 位
        val = pow(t, 1 << (r - 1 - i), N)

        if val == 1:
            bit = 0
        elif val == marker:
            bit = 1
            x |= 1 << i
            gx = gx * pow(g, 1 << i, N)
            gx %= N
        else:
            raise ValueError("discrete log failed at bit %d" % i)

    return x


# m ≡ 3 mod 4, c ≡ 3 mod 4，所以 e 为奇数
assert m % 4 == 3
assert c % 4 == 3

# e = 2x + 1
# c = m^(2x+1)
# c * m^(-1) = (m^2)^x
g = pow(m, 2, N)
h = c * pow(m, -1, N)
h %= N

print("[+] v2(g - 1) =", v2(g - 1))

r = order_power_two(g, N)
print("[+] ord(g) = 2^%d" % r)

x = dlog_power2(g, h, N, r)

e = 2 * x + 1

flag = long_to_bytes(e)

print("[+] e =", e)
print("[+] flag =", flag)