这次 tough cookie 分类没有全部做出来，有一道题卡住了，想到了可能的解法，但是没有去实践

实际上就是事后诸葛亮

Silky

题目描述

记 $B = 5, n = 19, D = 110, t = 128, l = 4 D B / t$。服务器先生成一个元素都在 $[-B, B]$ 内的整数向量 $k \in \mathbb{Z}^{n}$。

然后有一个 silky 运算：找一个元素都在 $[-B(D+1), B(D+1)]$ 的向量 $R \in \mathbb{Z}^{n}$，计算 $R’ = R - k$，满足 $R’$ 的元素均在 $[-BD, BD]$ 内。

我们有大约 $5 l t = 20 D B$ 次鸡喙 得到 $R$ 的值，然后需要恢复出 $k$ 的值。如果能恢复出 $k$ 的值，那么就能得到 flag

我的解答

一般这种看起来没什么特别性质，但是能够请求大量数据的题目都没什么特别的巧，都可以用机器学习的视角来重新审视：能不能找到一些特征，特别是统计意义上的特征，来判别 $k$ 的取值？

进一步注意到 $k$ 的每一个元素的取值都只有 11 种，所以实际上就是个 11 分类问题。然后乍一看因为 $k$ 的元素与元素之间都（似乎）是独立的，所以可以根据 $R$ 每个元素的取值去统计频数。

然后我当时尝试，直接去比较频数的交叉熵是不行的（10 组数据出不来，但是 100 组数据能出来），直接比较最小值也是不行的（能正确预测 $k$ 的部分元素，但是不能把所有的元素给预测对），我当时卡在这里就没往下做了。当时 V 说关注频数最小值就行了。我他妈卡了好久，就是因为我看了半天代码，以为 silky 运算返回的是 $R’$！所以看了半天，$R’$ 怎么看都只是满足均匀分布的而已的，也没直接看出什么统计特征来，麻

然后看回到问题本身，其实非常简单：因为返回的是 $R$ 的值，所以关注第 $i$ 个元素：要想使得 $R’_{i} \in [-BD, BD]$，那么 $R_i$ 必须在 $[-BD+k_i, BD+k_i] \subsetneq [-B(D+1), B(D+1)]$ 中。在多次（$20BD$ 次）采样中，可以认为 $-BD + k_i$ 就是所有 $R_i$ 的最小值，于是就可以直接依据这样求出 $BD$ 来

原来是他妈的返回的是 $R$，好弱智啊，西八

复盘的时候，还发现当时本地模拟 pull 数据的时候，采样的组数给写错了，麻上加麻

代码如下：

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
from pwn import *
from Crypto.Util.number import *
from tqdm import trange
import re


class Gao:
    def __init__(self):
        self.conn = process(['sage', 'another.sage'])
        # self.conn = remote("91.107.133.165", "33337")
        self.wtf = []

    def gao_one(self):
        self.conn.sendlineafter('[Q]uit\n', 'm')
        for i in range(1100 // 16):
            s = self.conn.recvline().strip().decode()
            wtf = re.findall(r'\((.*?)\)', s)
            wtf = [list(map(int, x.split(' '))) for x in wtf]
            self.wtf.extend(wtf)

    def submit(self, k: list[int]):
        self.conn.sendlineafter('[Q]uit\n', 'g')
        self.conn.sendlineafter('key: \n', ','.join(map(str, k)))

    def gao(self):
        for i in trange(10):
            self.gao_one()
            
        B, D = 5, 110
        keys = []
        for i in range(len(self.wtf[0])):
            min_wtf = min([x[i] for x in self.wtf])
            key_i = min_wtf + B * D
            keys.append(key_i)
        
        self.submit(keys)
        self.conn.interactive()

if __name__ == '__main__':
    g = Gao()
    g.gao()

然后通过交叉熵来统计频数的分布差异其实也是可做的，但是碰到频率为 0 的时候，要如实返回无穷大，这是因为的交叉熵的定义 $p_i \log q_i$ 中，频率 $p_i$ 通常是非常小，且波动大，如果不能通过 $q_i$ 这一项反映出差异的话，其实就会看不出任何东西；然后 ChatGPT 建议计数型频数可以考虑卡方距离，但是还是一点，就是还是需要在“除以零”的时候返回无穷大。这样的话，也只有不遇到“除以零”的时候，也就是可能的取值一致的时候，才会返回非无穷大的值。代码如下：

当然更关键的还是数据组数不够的问题

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
#!/usr/bin/env sage

from sage.all import *

import sys
from Crypto.Util.number import *
from collections import Counter
from tqdm import trange
import pickle

B, n = 5, 19
D, t = 110, 128

def randroad(B):
    return vector(ZZ,[randint(-B, B) for _ in range(n)])

def roadband():
    return randroad(B * (D + 1))

def silky(key):
    while True:
        R = roadband()
        _R = R - key
        if min(_R) >= - B * D and max(_R) <= B * D:
            return R

ans = [[Counter() for j in range(11)] for i in range(t)]

def get_data():
    global B, n, D, t
    l = int(4 * D * B / t)
    c, key = 0, randroad(B)
    motherfucker = []
    for i in range(10):
        R = [silky(key) for _ in range(int(l * t // 2))]
        R = R[:len(R) // 16 * 16]
        motherfucker.extend(R)

    return key, motherfucker

def train(key, motherfucker):
    for i in range(n):
        wtf = [mf[i] for mf in motherfucker]
        ct = Counter(wtf)
        ki = key[i]
        ans[i][ki + 5].update(ct)

import math

def counter_to_prob(counter):
    """将Counter转换为概率分布（归一化）"""
    total = sum(counter.values())
    return {k: v / total for k, v in counter.items()}

def cross_entropy(c1, c2, epsilon=1e-100):
    """计算两个Counter的交叉熵"""
    # 转换为概率分布
    p = counter_to_prob(c1)
    q = counter_to_prob(c2)
    
    # 获取所有可能的键（并集）
    all_keys = set(p.keys()) | set(q.keys())
    
    # 计算交叉熵
    entropy = 0.0
    for key in all_keys:
        # P(x) 和 Q(x)，如果键不存在则概率为 0
        px = p.get(key, 0)
        qx = q.get(key, epsilon)  # 避免 log(0)
        
        # 仅当 P(x) > 0 时计算该项
        if px > 0:
            entropy += -px * math.log(qx)
    
    return entropy

def chi_square_distance(c1: Counter, c2: Counter):
    c1_ = counter_to_prob(c1)
    c2_ = counter_to_prob(c2)
    
    # 合并所有键
    keys = set(c1.keys()) | set(c2.keys())
    
    distance = 0.0
    for k in keys:
        p = c1_.get(k, 0)
        q = c2_.get(k, 0)
        if q == 0 and p == 0:
            continue
        elif q == 0:  # 避免除零
            # 统计上，q = 0 且 p > 0 会导致统计量无穷大
            return math.inf
        distance += (p - q) ** 2 / q
    return distance

def val(key, motherfucker):
    key_ = []
    for i in range(n):
        wtf = [mf[i] for mf in motherfucker]
        ct = Counter(wtf)
        current_min_ce = 1e4
        current_key = -999
        for j in range(11):
            # ce = chi_square_distance(ct, ans [i][j])
            ce = cross_entropy(ct, ans[i][j])
            if ce < current_min_ce:
                current_min_ce = ce
                current_key = j - 5
        # DEBUG
        if current_key != key[i]:
            print(f'ERROR: {i = }')
            print(f'{key[i] = }, {current_key = }')
            print(f'{chi_square_distance(ct, ans[i][key[i] + 5]) = }')
            print(f'{chi_square_distance(ct, ans[i][current_key + 5]) = }')
            print()
        key_.append(current_key)
    print(f'{key = }')
    print(f'{key_ = }')

if __name__ == '__main__':
    # for i in trange(1000):
    #     key, mf = get_data()
    #     train(key, mf)
    # with open('2.pickle', 'wb') as f:
    #     pickle.dump(ans, f)

    with open('2.pickle', 'rb') as f:
        ans = pickle.load(f)

    key, mf = get_data()
    val(key, mf)

写成交互：

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
from pwn import *
from Crypto.Util.number import *
import pickle
from tqdm import trange
import re
from collections import Counter

# context.log_level = 'debug'
# context.proxy = (socks.HTTP, '172.27.224.1', 7890)

import math

def counter_to_prob(counter: Counter):
    """将Counter转换为概率分布（归一化）"""
    total = sum(counter.values())
    return {k: v / total for k, v in counter.items()}

def cross_entropy(c1: Counter, c2: Counter, epsilon=1e-100):
    """计算两个Counter的交叉熵"""
    # 转换为概率分布
    p = counter_to_prob(c1)
    q = counter_to_prob(c2)
    
    # 获取所有可能的键（并集）
    all_keys = set(p.keys()) | set(q.keys())
    
    # 计算交叉熵
    entropy = 0.0
    for key in all_keys:
        # P(x) 和 Q(x)，如果键不存在则概率为 0
        px = p.get(key, 0)
        qx = q.get(key, epsilon)  # 避免 log(0)
        
        # 仅当 P(x) > 0 时计算该项
        if px > 0:
            entropy += -px * math.log(qx)
    
    return entropy

def chi_square_distance(c1: Counter, c2: Counter):
    c1_ = counter_to_prob(c1)
    c2_ = counter_to_prob(c2)
    
    # 合并所有键
    keys = set(c1.keys()) | set(c2.keys())
    
    distance = 0.0
    for k in keys:
        p = c1_.get(k, 0)
        q = c2_.get(k, 0)
        if q == 0 and p == 0:
            continue
        elif q == 0:  # 避免除零
            # 统计上，q = 0 且 p > 0 会导致统计量无穷大
            return math.inf
        distance += (p - q) ** 2 / q
    return distance

class Gao:
    def __init__(self):
        self.conn = process(['sage', 'another.sage'])
        # self.conn = remote("91.107.133.165", "33337")
        self.t = 19
        self.wtf = []
        self.load_ans()

    def load_ans(self):
        with open('2.pickle', 'rb') as f:
            self.ans = pickle.load(f)

    def gao_one(self):
        self.conn.sendlineafter('[Q]uit\n', 'm')
        for i in range(1100 // 16):
            s = self.conn.recvline().strip().decode()
            wtf = re.findall(r'\((.*?)\)', s)
            wtf = [list(map(int, x.split(' '))) for x in wtf]
            self.wtf.extend(wtf)
                
    def get_key(self):
        ans, wtf = self.ans, self.wtf
        
        # Transpose wtf
        wtf = list(zip(*wtf))
        
        key_ = []
        for i in range(self.t):
            ct = Counter(wtf[i])
            current_min_ce = 1e4
            current_key = -999
            for j in range(11):
                ce = chi_square_distance(ct, ans[i][j])
                # ce = cross_entropy(ct, ans [i][j])
                if ce < current_min_ce:
                    current_min_ce = ce
                    current_key = j - 5

            key_.append(current_key)
        return key_

    def submit(self, k: list[int]):
        self.conn.sendlineafter('[Q]uit\n', 'g')
        self.conn.sendlineafter('key: \n', ','.join(map(str, k)))

    def gao(self):
        for i in trange(10):
            self.gao_one()
            
        keys = self.get_key()        
        self.submit(keys)
        self.conn.interactive()

if __name__ == '__main__':
    g = Gao()
    g.gao()

交叉熵和卡方距离都能解出 key 来，之前不能解出 key 来就是因为本地模拟的时候，采样数据组数写少了，麻

Sobata II

题目描述

与 Sobata 类似，但是有不同。不同的地方我都标出来了：

生成随机的 196 位素数 $p$ 满足 $p \equiv 1 \pmod 6$。椭圆曲线定义在有限域 $\mathbb{F} = \mathbb{F}_{p^2}$ 上，模多项式为 $x^2 + 13 x + 37$。然后生成随机的椭圆曲线 $E_\mathbb{F}: y^2 = x^3 + d$，并且生成 $\mathbb{F}$ 下的 3-torsion $a$ 和 2-torsion $b$：

  • $a \ne 1$ 且 $a^3 = 1$
  • $b \ne 1$ 且 $b^2 = 1$

并且生成一个随机的 $c$。假设 flag 为 $m$，则产生一个点 $P(m+\delta, y) := P(m_1, y)$，其中 $\delta$ 为一个不小于 0 的最小的数使得 $P \in E_\mathbb{F}$

远程有以下操作：

  • 加密 flag 对于点 $P(m_1, y)$，先算出点 $Q(am_1, by)$，然后返回 $c Q$
  • Walking 输入一个 $E_p$ 上的点 $R(x, y)$，先算出点 $Q(ax, by)$，然后返回 $c Q$
  • Jumping 输入一个 $E_p$ 上的点 $R(x, y)$，以及一个整数 $n$。先算得 $c’$ 为 $c$ 模有限域 $\mathbb{F}$ 阶的 $n$ 次方，也就是 $c’ = c^{n} \bmod{|\mathbb{F}|}$。服务器先算出点 $Q(ax, by)$，然后返回 $c’ Q$

就，jumping 这个选项名字挺让人难蚌的

试得到 $m$。

我的解答

这里主要比较坑爹的是这里模有限域 $\mathbb{F_{p^2}}$ 的阶，也就是模 $p^2$，而非模椭圆曲线的阶，所以就难搞；不过素数 $p$ 位数只有 196 位 又弥补了这一部分。

回顾一下 Sobata 的解题流程：

  1. 生成随机的 $a, b$，有 $1/2$ 的成功率
  2. 通过 加密 flag，拿到 $T = cQ$
  3. 利用 Jumping，输入 $R(a^{-1} x_T, b^{-1} y_T)$，以及 $n=-1$，此时服务器返回的是 $c^{-1} T = Q$，然而这里会寄
  4. 算出 $m_1 = a^{-1} x_{Q}$
  5. 通过 long_to_bytes(m1) 看到 flag

上面的这个寄的地方是因为实际上这个 $c^{-1}$ 是对模 $p^2$ 的逆，而非对模 $|E_\mathbb{F}|$ 的逆。然后因为这里我们能拿到的结果都是 $E_\mathbb{F}$ 上的结果，所以我们必须直面解 $E_\mathbb{F}$ 上的离散对数问题。

然后我觉得他这个素数 $p$ 的位数被弄得这么小，就是为了解这个离散对数问题的，但是我对 $E_\mathbb{F}$ 下的离散对数求法不是很熟（只会个 Pohlig-Hellman），幸好在比赛的过程中，有沛公这么给力的队友帮我接这个离散对数，这里要谢谢沛公；而反观某个叛徒，在关键时刻背信弃义，所作所为，令人唾弃！

然后这里还可以注意两个事实：

  1. 因为不需要提交结果以获得 flag，所以这个离散对数可以本地算
  2. 可以通过重复连接服务器刷参数，让点 $T$ 的阶尽可能光滑

在实操的时候，我发现椭圆曲线的阶 $|E_\mathbb{F}|$ 很可能具有 $p+1$ 这个因子，虽然不知道为啥。然后沛公就能直接利用双线性配对，把点怼到 $\mathbb{F}_{p^2}$ 里面搞了。感觉有点像 MOV，但是 MOV 是对点的嵌入度有要求的。这样也行，不明觉厉。

所以上面的第 2 步要改成输入 $n=1$，并输入一个阶为 $p+1$ 的点 $T’$ 然后就得到了 $Q’ = c T’$，求解该离散对数问题得到 $c$ 的值即可。

以下是沛公的离散对数求解代码：

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
import sys
from Crypto.Util.number import *

def pollig_hellman_add_group(y, g, group_order, identity=None, verbose=True):
    # we do not handle the case p^e with large e (e >= 2)
    fs = factor(group_order)
    mods = []
    dlogs = []
    for p, e in fs:
        if verbose:
            print(f"[+] Sub dlog in  group with order {p}^{e}")
        sub_order = ZZ(p ** e)
        sub_mulc = group_order // sub_order
        # new_y = sub_mulc * y
        # new_g = sub_mulc * g
        # sub_log = bsgs_add_group(new_y, new_g, sub_order, identity, False)
        # sub_log = bsgs_add_group(new_y, new_g, sub_order, identity, False)
        new_y = y**sub_mulc
        new_g = g**sub_mulc
        sub_log = new_y.log(new_g)

        if verbose:
            print(f"   Sub dlog  x = {sub_log} % {sub_order}")
        mods.append(sub_order)
        dlogs.append(sub_log)
    return crt(dlogs, mods)


p = 
d = 

R.<x> = PolynomialRing(GF(p))
f = x^2 + 13 * x + 37
f = R(f)
F.<g> = GF(p^2, modulus = f)
E = EllipticCurve(F, [0, d])

encP = 

a = 
b = 

a = F(a)
b = F(b)

# gen P 随机生成一个阶为 p+1 的点
# while True:
#    P = E.random_element()
#    if (p+1)//2 * P != E(0):
#        break

# 发送给服务器的点 P = 
P = 

P = E(P)

P_order = P.order()
if P_order != p + 1:
    raise Exception(f'GG: {P_order = }')
    exit()

while True:
    Q = E.random_element()
    if (p+1)//2 * Q != E(0) and P.weil_pairing(Q, p+1) != 1:
        print(Q)
        break
# send P and get cP
# 从服务器的点 kP cP

cP = 
cP = E(cP)

gg = P.weil_pairing(Q, p+1)
hh = cP.weil_pairing(Q, p+1)

# solve Fp^2 dlp

c = pollig_hellman_add_group(hh, gg, p+1)

QQ = inverse_mod(c, p+1) * E(encP)
Px = QQ[0] / a

flagx = Px - 1404 * g
print(flagx)
print(long_to_bytes(int(flagx)))

看上去就是利用了和 MOV 类似的配对手法。

然后就是根据 Sobata 改的交互代码，这里加了一个 loguru 库来储存好不容易从服务器上 pull 下来的数：

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
from pwn import *
from sage.all import *
from Crypto.Util.number import *
from tqdm import tqdm
from loguru import logger
import time
import signal

# 自定义超时异常
class TimeoutError(Exception):
    pass

# 超时信号处理函数
def timeout_handler(signum, frame):
    raise TimeoutError("Operation timed out")

# 设置信号处理器（只需设置一次）
signal.signal(signal.SIGALRM, timeout_handler)

logger.add(f'log/log_{int(time.time())}.txt')

class Gao:
    def __init__(self):
        # self.conn = process(['sage', 'another.sage'])
        self.conn = remote("91.107.252.0", "11173")
        # self.conn = remote("91.107.161.140", "11173")
        F, a = PolynomialRing(ZZ, 'a').objgen()
        self.PR, self.g = F.quotient(a**2 + 13 * a + 37, 'g').objgen()
    
    def get_fp2(self):
        g = self.g
        return eval(self.conn.recvline().decode().strip())

    def recv_P(self):
        self.conn.sendlineafter('[Q]uit\n', 'e')
        self.conn.recvuntil('is: ')
        self.P = self.get_fp2()
    
    def to_fp2(self, x, g):
        b, a = x.list()
        return a * g + b

    def walk_P(self):
        x1, y1 = self.P
        self.conn.sendlineafter('[Q]uit\n', 'w')
        self.conn.sendlineafter('E:', f'{x1},{y1}')
        self.conn.recvuntil('is: ')
        x2, y2 = self.get_fp2()
        d1 = y1**2 - x1**3
        d2 = y2**2 - x2**3
        diff = d2 - d1
        p = gcd(diff[0], diff[1])
        p = factor(p)[-1][0]
        R, a = PolynomialRing(GF(p), 'a').objgen()
        Fp2, g = GF(p**2, 'g', modulus=R(a**2 + 13 * a + 37)).objgen()
        d1 = self.to_fp2(d1, g)
        x1 = self.to_fp2(x1, g)
        y1 = self.to_fp2(y1, g)
        self.E = EllipticCurve(Fp2, [0, d1])
        self.P = self.E((x1, y1))
        self.p = p
        self.Fp2 = Fp2
        self.g = g

    def check_p(self):
        try:
            signal.alarm(2)
            fac = factor(self.p + 1)
            signal.alarm(0)
        except TimeoutError:
            logger.error('factorization timed out')
            return False
        for p, alpha in fac:
            if p**alpha > 2**49:
                logger.error(f'fact too big: {(p**alpha).nbits()}')
                return False
        logger.success(f'Find p!')
        return True

    def get_flag(self):
        self.conn.sendlineafter('[Q]uit\n', 'j')
        # x1, y1 = self.P.xy()
        
        def get_n_torsion(n):
            g = self.Fp2.random_element()
            order = g.multiplicative_order()
            return g ** (order // n)
        
        while True:
            x1, y1 = self.E.random_element().xy()
            a = get_n_torsion(3)
            b = get_n_torsion(2)
            ax1 = a**-1 * x1
            by1 = b**-1 * y1
            if (ax1, by1) in self.E:
                AX = self.E((ax1, by1))
                if ((self.p + 1) * AX == self.E(0)) and (((self.p + 1) // 2) * AX != self.E(0)):
                    break

        self.conn.sendlineafter('E:', f'{ax1},{by1}')
        self.conn.sendlineafter('point:', '1')
        self.conn.recvuntil('is: ')
        x2, y2 = self.get_fp2()
        P2 = self.E((x2, y2))
        # Backup
        logger.info(f'{self.p = }')
        logger.info(f'{a = }')
        logger.info(f'{b = }')
        logger.info(f'{self.P = }')
        logger.info(f'{x1 = }')
        logger.info(f'{y1 = }')
        logger.info(f'{self.E = }')
        logger.info(f'{P2 = }')

    def gao(self):
        self.recv_P()
        self.walk_P()
        if not self.check_p():
            return False
        for i in range(5):
            self.get_flag()
        self.conn.interactive()

if __name__ == '__main__':
    while True:
        g = Gao()
        if not g.gao():
            g.conn.close()

这里变量的对应关系为：

  • self.p 素数 $p$
  • a, b torsion
  • self.P flag 的倍点，对应沛公离散对数求解代码里面的 encP
  • x1：发送给服务器的点的横坐标 $x_{T’}$，对应沛公离散对数求解代码里面的 P 的横坐标
  • y1：发送给服务器的点的纵坐标 $y_{T’}$，对应沛公离散对数求解代码里面的 P 的纵坐标
  • self.E 椭圆曲线，主要是用来拿椭圆曲线的参数 $d$
  • P2 $T’$ 的倍点 $Q’$，对应沛公离散对数求解代码里面的 cP

比赛的时候，我开 4 个进程跟服务器交互。一开始，我为了图方便，直接把 flag 的倍点送到里面，等了半天等到了一组数，结果运行沛公的离散对数求解，结果代码弄不出解来。然后搞半天（此时已是深夜）我发现，flag 对应的点的阶是不为 $p+1$ 的！，也就是说，倍点的阶也是 $p+1$ 的约数，不为 $p+1$，所以不满足沛公求解代码的前提条件，西八！！！

而且这个玩意儿跟 flag 具体取值有关，在本地没有测试出来

最后才发现可以钦定一个阶为 $p+1$ 的点往里送，继续跟服务器交互，然后等了又快一个小时，总算拿到了阶较光滑的另一组数据，然后送到沛公求解代码里面就赢了。flag 为：

1
CCTF{Ecc_5tRong_cRyPto!}

赛后复盘

如果赌 $|E_\mathbb{F}|$ 最大素数为 $2^{50}$ 的话，好像 Pohlig-Hellman 也能行。我本地测试的 $2^{25}$ 级别的点遍历运算大概是 15 至 20 分钟，也就是整个离散对数求解可能要一个半小时左右。

然后我还向 ChatGPT 指导请教了一下 P.weil_pairing(Q, p+1) 的含义，加深了一下对 weil pairing 的理解，这个第三个参数就是配对的阶，通常记作 $r$：

  • Weil 配对是定义在 $E[r] \times E[r] \to \mu_r$ 上的一个双线性映射。
  • 其中 $E[r]$ 是椭圆曲线上所有 $r$-阶点组成的子群，$\mu_r \subset \mathbb{F}_{q^k}^\times$ 是 $r$-次单位根的集合。
  • 在代码接口里，必须明确告诉函数：我们是在哪个阶 $r$ 的子群上做配对。所以第三个参数就是这个整数 $r$。

然后是 weil pairing 是用的场景：点的阶要是 $p^k-1$ 的约数，且 $k$ 要小。所以这里嵌入度是 2，可以用双线性配对来解。

然后在有限域乘法群上，DLP 可以用 指数分解 / NFS，其复杂度是次指数级 $L(1/3)$，比 Pohlig-Hellman 的 $O(\sqrt{r})$ 要快得多。

也就是说这个 $\mu_r$ 是 $r$ 次单位根的集合，转到 $\mathbb{F}_{q^k}^\times$ 了之后，就能利用这个指数分解；但是如果直接用指数分解的话，好像也要蛮久的时间，所以还是得赌它的阶不能过大，要结合 Pohlig-Hellman 来一起玩。

或许看懂了这个配对的意义之后，我也能改动第三个参数为点 $P$ 真实的阶，或许也能出

总之，这题细节上还是挺搞心态的，尤其是要赌参数。

Toffee

题目描述

题目基于一个参数已知而且挺标准的椭圆曲线，且已知生成元点 $G$ 的坐标。

题目基于标准的 ECDSA，我们 有任意次鸡喙 和远程服务器互动

题目先生成一组 $(u, v, k)$，并有以下选项

  • 返回 Toffee 函数结果 记 $T(x) = (u x + v) \bmod n$，输入 $x$，输出 $T(x)$
  • ECDSA 签名 输入一个消息 $m$，先用 $k = T(k)$ 更新 $k$ 的值，然后再用 ECDSA 签名消息 $(r, s)$，满足 $ks \equiv H(m) + r x \pmod{n}$

试求 flag，即私钥 $x$。

我的解答

首先肯定想着恢复出 $u$, $v$ 的值，这个直接根据 $T(0) = v, T(1) = u + v$ 求出来。

然后就是这个迭代更新 $k$ 这一步了，这里不是采取的纯随机，而是采取的线性相关式子更新，而且系数还是已知的，那这就简单了，直接连着两次签名，列式子解关于 $k, x$ 的线性方程组就行了：

代码如下：

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
from pwn import *
from sage.all import *
from Crypto.Util.number import *
import pickle
from tqdm import trange
from hashlib import sha512

class Gao:
    def __init__(self):
        # self.conn = process(['sage', 'another.sage'])
        self.conn = remote("91.107.133.165", "31111")
        self.rlist = []
        self.slist = []

        self.p = 0xaeaf714c13bfbff63dd6c4f07dd366674ebe93f6ec6ea51ac8584d9982c41882ebea6f6e7b0e959d2c36ba5e27705daffacd9a49b39d5beedc74976b30a260c9
        self.a, self.b = -7, 0xd3f1356a42265cb4aec98a80b713fb724f44e747fe73d907bdc598557e0d96c5
        self._n = 0xaeaf714c13bfbff63dd6c4f07dd366674ebe93f6ec6ea51ac8584d9982c41881d942f0dddae61b0641e2a2cf144534c42bf8a9c3cb7bdc2a4392fcb2cc01ef87
        self.x = 0xa0e29c8968e02582d98219ce07dd043270b27e06568cb309131701b3b61c5c374d0dda5ad341baa9d533c17c8a8227df3f7e613447f01e17abbc2645fe5465b0
        self.y = 0x5ee57d33874773dd18f22f9a81b615976a9687222c392801ed9ad96aa6ed364e973edda16c6a3b64760ca74390bb44088bf7156595f5b39bfee3c5cef31c45e1
        self.msg = b'DBTJJ5cm'
        self.h = bytes_to_long(sha512(self.msg).digest())

    def gao_one(self):
        m = self.msg
        self.conn.sendlineafter('[Q]uit\n', 's')
        self.conn.sendlineafter('message: \n', m)
        self.conn.recvuntil('r = ')
        r = eval(self.conn.recvline())
        self.conn.recvuntil('s = ')
        s = eval(self.conn.recvline())
        self.rlist.append(r)
        self.slist.append(s)

    def gao_uv(self):
        self.conn.sendlineafter('[Q]uit\n', 'g')
        self.conn.sendlineafter('seed: \n', '0')
        v = eval(self.conn.recvline().strip().decode().split('=')[1])

        self.conn.sendlineafter('[Q]uit\n', 'g')
        self.conn.sendlineafter('seed: \n', '1')
        u = eval(self.conn.recvline().strip().decode().split('=')[1]) - v

        self.v = v % self._n
        self.u = u % self._n
        print(f'{self.u = }')
        print(f'{self.v = }')

    def solve_k(self):
        u, v = self.u, self.v
        r0, r1 = self.rlist
        s0, s1 = self.slist
        n = self._n
        h = self.h
        A = matrix(Zmod(n), [[  s0, -r0],
                             [u*s1, -r1]])
        b = vector(Zmod(n), [h, h - v * s1])
        k, x = A.solve_right(b)
        print(f'{long_to_bytes(int(x)) = }')

    def gao(self):
        self.gao_uv()
        for i in trange(2):
            self.gao_one()
        self.solve_k()

if __name__ == '__main__':
    g = Gao()
    g.gao()

解得 flag 为

1
CCTF{4fFin3Ly_r3lA7eD_n0nCE5_aR3_!n5eCuR3!}