这次 head scratcher 分类由于人力短缺，以及水平不得行，所以全军覆没了。虽然爆零了，但是至少 1997 的各位都战斗到最后，搏至无憾了。反观某个叛徒，在他人唆使之下叛逃 1997，利令智昏，得不偿失！

从 discord 到 QQ 的 1997 交流群，一副阻挡叛徒的铁幕已经降落下来

Alice Sig Slip (x)

题目描述

题目基于 EdDSA，使用的曲线为 ED25519，用 RFC8032 的参数（生成元 $G$ 固定）生成一个密钥 $(x, P)$ 满足 $P = x G$，然后有 5 组消息 $m_i, i = 0, 1, 2, 3, 4$，然后对这个消息签名得到 5 组数据 $(P, r_i, s_i, m_i)$ 其中 $P = x G$ 为公钥。这些数据可以排列成一个矩阵：

然后题目会涂掉一些数，变成下面这样：

我们需要把 $?$ 中的数字补上，让这几组数据都能通过 EdDSA 的签名验证。如果能做到的话，则得到 flag。

我的解答 (x)

对于上面矩阵的最后一行：直接填 $(P, r_0, s_0, m_0)$ 即可；

对于上面矩阵的倒数第二行：直接生成一组 EdDSA 公钥 $P’ = x’ G$ 然后用其签名，得到 $(r’, s’)$ 即可；

对于上面矩阵的倒数第四行：直接复制 $P$ 即可；

所以难点还是在第三行：怎么提供 $P’, r’$，使得验签式满足

先走一下代码审计，看看能不能在他的实现里面找到一些猫腻。

在比赛时，我有发现一点：在 eddsa.import_public_key(encoded=public_key) 中，会根据不同的密钥长度判断不同的加密算法：，具体可见 Crypto/Signature/eddsa.py L41，具有 ed25519 和 ed448 两种形式。我有在想能不能通过输入过长的密钥让检验走 ed448，从而利用到一些什么东西但是好像并不能利用到什么东西。

然后就是去找验签的过程，在 Crypto/Signature/eddsa.py L209：

  • 同样会先根据密钥的长度（实例化的时候已经做掉了）来判断走 ed25519 的验签，走到 Crypto/Signature/eddsa.py L244
  • 前面那个 dom2 应该会取空字符串
  • 计算 $k = \mathrm{SHA512}(dom2 || r || P || msg) \bmod n$
  • 然后检验签名是否成立

等于说这里的 $r$ 和 $P$ 是会共同影响到 $k$ 的计算，但是后面验签的时候验证：

是否成立

也是就是说，由于有 SHA512 哈希的存在，并不知道如何通过 $R$ 和 $P$ 来

赛后复盘

其实这道题目没做出来主要是对 EdDSA 本身的运作机制不是很了解，甚至说完全想当然，很多细节上的东西全凭主观臆断了。当然，这也和 1997 EdDSA 专家：托林在比赛的时间段没啥空有关，但是不可能把宝全部押在一个人身上。但是呢，对于临阵叛逃、负输出的行为，1997 是零容忍的。

实际上，维基百科对 EdDSA 的阐述 就很详细了：

  • EdDSA 是利用 $\mathbb{F}_{q}$ 上的椭圆曲线 $E$，其 $\mathbb{F}_{q}$ 关系点群 $E(\mathbb {F} _{q})$ 的阶数为 $\#E(\mathbb {F} _{q})=2^{c}\ell$，其中 $\ell$ 是一个大素数且 $2^{c}$ 被称为辅因子
  • 基点 $B\in E(\mathbb {F} _{q})$ 的阶数为 $\ell$

也就是说，和 DSA 一样，EdDSA 对点的操作是在一个子群中进行的；特别地，在 ed25519 中，$c=3$，也就是说 有个 8 倍的差距！虽然无论在题目代码还是在 EdDSA 库的工程实现中，都有对无穷远点的拒绝判断，但是没有拒绝其他点的判断！这个是我请教了 maple3142 之后才发现的，由衷感谢！

虽然如此，但是实际上 EdDSA 的具体实现中会把 order 给写死成基点 $B$ 的阶数 $\ell$，具体实现可以找到 Crypto/PublicKey/ECC.py L112，直接利用查表的方式，根据 curve_name 找到一组参数；特别地，ed25519 的参数存放于 Crypto/PublicKey/_edwards.py 中，可以看到参数中的 order 是奇数，因为这个 order 是 $B$ 的 order。在比赛的时候，我有尝试去打印出这个 order，然后发现它是个奇素数，就没有往下深挖了，还是因为缺少对 EdDSA 的一个 big picture 才导致当时做的时候比较乱。

回到验签过程中：

  • 首先我们提供 $P’$ 和 $r’$
  • 然后计算 $k’$
  • 然后计算是否 $8sG = 8(R’ + k’ P’)$ 成立

这个式子的左边是个定值，右边可以取：

  • $R’ = s G$
  • $8 P’ = O$
    即可满足，这样我们既把不可控的 $k’$ 给摆脱了，又可以避免输入无穷远点。

然后还有一个实现上的细节（或许也不能算是细节？），就是题目数据中点 $P$ 的导出，并不是仅导出 $x$ 坐标或者 $y$ 坐标的值的。实际上，在 EdDSA 的实现中，是有“正点”和“负点”的区分的，具体可以参考 Crypto/PublicKey/ECC.py L288：虽然在模素数 $q$ 中，点的坐标值都是正的，但是由于 $q$ 是奇数，所以如果点 $P(x, y)$ 中的 $x$ 是奇数，那么点 $-P(-x, y)$ 中的 $-x$ 实际上就是 $p-x$，是偶数。把点导出的结果是同时包含了 $y$ 的值和 $x$ 的奇偶性的，这就给出了点的唯一性。

然后这个 torsion point 可能要自己去找，或者直接搜，这里利用 ed25519 和 Curve25519 （后者是 Montgomery Curve）双有理等价的性质，直接在 Curve25519 上找 torsion point：

1
2
3
4
5
6
p = 0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffed
K = GF(p)

E = EllipticCurve(GF(p), [0,486662,0,1,0])

print(factor(E.order()))

可以看到结果是 $2^3 \cdot \ell$，所以直接利用这个求就行了。求出来之后还需要走一下格式转化，代码在 Crypto/PublicKey/ECC L431 → Crypto/PublicKey/ECC L288

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
p = 0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffed
K = GF(p)

E = EllipticCurve(GF(p), [0,486662,0,1,0])

n = E.order()

while True:
    P = E.random_point()
    Q = (n // 8) * P
    if Q != E(0):
        break

print(f'{Q.order() = }')

u, v = Q.xy()
x = u/v * K(-486664).sqrt()
y = (u-1)/(u+1)

print(f'{x = }')
print(f'{y = }')

LHS = -x^2 + y^2
RHS = 1 - K(121665 / 121666) * x^2 * y^2
print(f'{LHS - RHS = }')

x, y = map(int, (x, y))
result = bytearray(y.to_bytes(32, byteorder='little'))
result[31] = ((x & 1) << 7) | result[31]
res = bytes(result)

print(f'{res = }')

在写代码的时候，我发现了一个细节上的东西：pycryptodome 初始化 ECC 密钥主要利用了 construct 方法，该方法会用 EccKey 类的实例化产生一个对象（有点像设计模式里面的工厂模式）。在 EccKey 对象的实例化中，有对 ed25519 的参数处理（可参考 Crypto/PublicKey/ECC.py L128）：

  • self._d 必须是 None
  • self._seed 长度必须是 32
1
2
3
4
5
6
7
8
9
10
11
if self._curve.id == _CurveID.ED25519:
    if self._d is not None:
        raise ValueError("Parameter d can only be used with NIST P curves")
    if len(self._seed) != 32:
        raise ValueError("Parameter seed must be 32 bytes long for Ed25519")
    seed_hash = SHA512.new(self._seed).digest()   # h
    self._prefix = seed_hash[32:]
    tmp = bytearray(seed_hash[:32])
    tmp[0] &= 0xF8
    tmp[31] = (tmp[31] & 0x7F) | 0x40
    self._d = Integer.from_bytes(tmp, byteorder='little')

也就是说，这样的设定让我们 无法通过直接指定私钥的值的方式来初始化一个 ed25519 密钥。这里我们需要事先对 pycryptodome 的实现稍加改动，使得可以直接指定私钥的值，来初始化一个 ed25519 密钥：

1
2
3
4
5
6
7
8
9
10
11
12
if self._curve.id == _CurveID.ED25519:            
    if self._d is not None:
        self._d = Integer(self._d)
    else:
        if len(self._seed) != 32:
            raise ValueError("Parameter seed must be 32 bytes long for Ed25519")
        seed_hash = SHA512.new(self._seed).digest()   # h
        self._prefix = seed_hash[32:]
        tmp = bytearray(seed_hash[:32])
        tmp[0] &= 0xF8
        tmp[31] = (tmp[31] & 0x7F) | 0x40
        self._d = Integer.from_bytes(tmp, byteorder='little')

然后解题代码如下：

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
from pwn import *

from Crypto.Math.Numbers import Integer
from Crypto.PublicKey import ECC
from Crypto.Signature import eddsa

class Gao:
    def __init__(self):
        self.conn = process(['python3', 'another.py'])
        self.messages = [
            b"Alice cracks codes in her sleep.",
            b"Alice never leaves a cipher unsolved.",
            b"No flag for those who give up too soon, says Alice.",
            b"Alice never gives up; that's why she always gets the flag.",
            b"Alice loves solving ciphers, especially when they're tricky.",
        ]
        self.ans = []
    
    def recv_known(self):
        self.conn.sendlineafter('[Q]uit\n', 'G')
        for i in range(5):
            c = self.conn.recvline().strip().decode()
            c = c.split(' : ')[1]
            a = [x.strip() for x in c.split(',')]
            self.ans.append(a)
    
    def complete_other(self):
        self.ans[1][0] = self.ans[0][0]
        for i in range(4):
            self.ans[4][i] = self.ans[0][i]

    def gao_3(self):        
        some_key = ECC.generate(curve='ed25519')
        signer = eddsa.new(some_key, 'rfc8032')
        signature = signer.sign(self.messages[3])
        
        self.ans[3][0] = some_key.public_key().export_key(format='raw').hex()
        self.ans[3][1] = signature[:32].hex()
        self.ans[3][2] = signature[32:].hex()

    def gao_2(self):
        wtf = b'\xc7\x17jp=M\xd8O\xba<\x0bv\r\x10g\x0f* S\xfa,9\xcc\xc6N\xc7\xfdw\x92\xac\x03\xfa'
        wtf = b'\xc7\x17jp=M\xd8O\xba<\x0bv\r\x10g\x0f* S\xfa,9\xcc\xc6N\xc7\xfdw\x92\xac\x03z'
        
        
        s = Integer.from_bytes(bytes.fromhex(self.ans[2][2]), 'little')
        # ed25519 = ECC._curves ['ed25519']
        some_key = ECC.construct(curve='ed25519', d=s)
        r = some_key.public_key().export_key(format='raw')
        
        self.ans[2][0] = wtf.hex()
        self.ans[2][1] = r.hex()

    def submit_ans(self):
        for i in range(5):
            self.conn.sendlineafter('[Q]uit\n', 'U')
            m = f'{i},' + ','.join(self.ans[i])
            self.conn.sendlineafter('msg:', m)
        self.conn.sendlineafter('[Q]uit\n', 'A')

    def gao(self):
        self.recv_known()
        self.complete_other()
        self.gao_3()
        self.gao_2()
        self.submit_ans()
        self.conn.interactive()

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

Hoshi (x)

题目描述

$p$ 为一个未知 256 比特素数，在 $\mathbb{Z}/p^{12}\mathbb{Z}$ 中定义椭圆曲线 $E: y^2 = x^3 + a x + b$，给定 5 个点 $P_1(x_1, y_1), P_2(x_2, y_2), \ldots, P_5(x_5, y_5)$ 以及其相应倍点 $d_1 P_1, d_2 P_2, \ldots, d_5 P_5$，保证 $1 \le d_i \le p^{11}, i = 1, 2, \ldots, 5$。需要求出这些 $d_i$，全部求出就能得到 flag

我的解答 (x)

比赛的时候，我和沛公都想到论文 The group structure of elliptic curves over Z/NZ，该论文解析了椭圆曲线论文在整数模 $N$ 的环上的点群结构。主要就是在非奇异情形（即 $q:=|E(\mathbb{F}_p)| \ne p$）下，那么

相当于可以把 $E(\mathbb{Z}/p^{e}\mathbb{Z})$ 分为两部分

  1. 投射到 $\mathbb{F}_p$ 的部分 $E(\mathbb{F}_p)$
  2. 无穷远点部分 $E^\infty$

然后就有一个结论：这个 $E^\infty$ 是一个 $p^{e}$ torsor，就是一个循环群。

然后这里是模 $p^{12}$，但是 $d_i$ 不大于 $p^{11}$，所以应该就是这篇了。

首先是解参数，这个可以参考 Sobata 相关的内容解出来，不是本题的主要难点

然后就是分别去解离散对数。继续看论文：

  • 论文中第 5 章给出了针对 $|E(\mathbb{Z}/p^{e}\mathbb{Z})| = p^{e}$ 时的同构攻击，这就需要赌 $q = |E(\mathbb{F}_p)| = p$，这个肯定概率太小了，不予考虑；
  • 论文中命题 4 也给出了当 $1 \le e \le 5$，且 $q \neq p$ 的时候，有一个良定义的群同态 $\Phi$
  • 论文中命题 2 给出了无穷远点的结构，说是 存在 一个 $f(X)$ 可以在模 $p^{10}$ 中考虑，但是好像也没给出 $f$ 的具体形式

然后就不知道怎么弄了

赛后复盘

之前在 sagemath 中，可以通过 p-adic number 的形式实现对无穷远点的兼容

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
set_random_seed(4396)

nbit = 256
l, p, n = 12, getPrime(nbit), 5
PTS,a,b = gen_curve(p, l, n)
SCV = [randint(1, p ^ (l - 1)) for _ in range(n)]
EPT = [SCV[_] * PTS[_] for _ in range(n)]

E = EllipticCurve(Zmod(p ^ l), [a, b])
E0 = EllipticCurve(Zmod(p), [a, b])
n0 = E0.order()
EQp = EllipticCurve(Qp(p, prec=12), [a, b])

P0 = PTS[0]
print(P0)
PQp = P0.change_ring(Qp(p, prec=12))
print(PQp)

P0y = P0[1]
print(f'{ZZ(P0y).digits(p) = }')
print(f'{n0 * P0 = }') # OK in 10.6
print(f'{n0 * PQp = }')

打印出来，可以观察到这里 PQp 实际上就是 P0 坐标的 $p$ 进制表示（因为是模 $p^l$ 的，所以已经没有 P.xy() 方法），然后后面也是能直接打印出 n0 * P0 的值的，貌似在 SageMath 10.6 中可以直接在 mod p^l 上运算了？我好像记得之前版本是不支持这玩意儿的，以前是直接算到无穷远点上貌似会出问题。然后就出问题：

1
2
3
4
5
6
K0 = n0 * P0
print(f'{K0 = }')

# K1 = 2 * K0
K1 = (2 * n0) * P0
print(f'{K1 = }')

直接运行 K1 = 2 * K0 是会报错的：

1
2
3
4
5
6
7
8
9
  File "/home/xxx/miniconda3/envs/sage/lib/python3.12/site-packages/sage/schemes/elliptic_curves/ell_point.py", line 340, in _add_
    pt = CRT_vectors([pt, [x1.lift(), y1.lift(), z1.lift()]], [mod, mod_1st])
         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/xxx/miniconda3/envs/sage/lib/python3.12/site-packages/sage/arith/misc.py", line 3718, in CRT_vectors
    a = CRT_basis(moduli)
        ^^^^^^^^^^^^^^^^^
  File "/home/xxx/miniconda3/envs/sage/lib/python3.12/site-packages/sage/arith/misc.py", line 3683, in CRT_basis
    raise ValueError('moduli must be coprime')
ValueError: moduli must be coprime

所以我们要么只能写成 K1 = (2 * n0) * P0，要么用 p-adic number 表示数：

1
2
3
4
KQp = n0 * PQp
print(f'{KQp = }')
KKQp = 2 * KQp
print(f'{KKQp = }')

于是我们就可以利用论文中命题 4 的映射，去解决 $e \le 5$ 的情形，也就是得出 $d \bmod p^{4}$ 的值：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
F_ = Zmod(p^(l-1))
def get_l(P):
    K = n0 * P
    return F_(ZZ(K[0]) / p) / F_(K[1])

l0 = get_l(P0)

d = 2
P1 = d * P0
l1 = get_l(P1)


print(f'{l0 % p^4 = }')
print(f'{l1 % p^4 = }')
print(f'{d * l0 % p^4 = }')
print()

print(f'{l0 % p^5 = }')
print(f'{l1 % p^5 = }')
print(f'{d * l0 % p^5 = }')
print()

当然上面这个 get_l 也可以用 p-adic number 去做。可以看到，下面模 $p^4$ 的值是能够对上的，但是模 $p^5$ 的值对不上，我和沛公比赛的时候就是卡在了这里。赛后看到 maple 做出来了，自然去问了一下：

把 mod p^4 的部分減掉然後進位
反覆做就行了

回到题目，假设我们已经求出了 $d \bmod p^4$ 的值，写成式子就是：

其中这里的 $d_0$ 是通过上述方法求出来的，$d_1$ 是需要继续去求的值。

因为无穷远点群是一个循环群，所以在实验的时候，直接把 $K$ 的 $x$ 坐标不是除以 $p$，而是除以 $p^5$ 就行了，可以看看下面这个例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def get_l(P, t):
    K = n0 * P
    F_ = Zmod(p^4)
    return F_(ZZ(K[0]) / p^t) / F_(K[1])

l0 = get_l(P0, 1)

d = 3 * p^4 + 7
P1 = d * P0
l1 = get_l(P1, 1)

Q1 = P1 - 7 * P0

l2 = get_l(Q1, 5)
print(f'{l2 = }')
print(f'{3 * l0 = }')

为什么要把用来测试的 $d$ 构造成这种形式？因为时代少年团的队长叫 🐎+7

就可以验证这个“把 $\bmod p^4$ 的部分减掉”的可行性。这样子我们就能迭代求解了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def dlog(P, Q):
    # Solve Q = d P
    l0 = get_l(P, 1)
    k = 0
    Q_ = Q
    d = 0
    while (k < l - 1):
        print(f'{k = }')
        l1 = get_l(Q_, k + 1)
        d_ = ZZ(l1 / l0)
        d += d_ * p^k
        Q_ = Q - d * P
        k += 4
    return ZZ(d % p^(l-1))

d = ZZ.random_element(p ^ (l-1))
P1 = d * P0
d_ = dlog(P0, P1)

print(f'{d = }')
print(f'{d_ = }')

当然也可以参考沛公直接用 p-adic number 的做法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
P0 = PTS[0]
PQp = P0.change_ring(Qp(p, prec=12))

def get_l(P):
    K = n0 * P
    return K[0] / K[1]

d = 3 * p^4 + 7
QQp = d * PQp

l0 = get_l(PQp)
l1 = get_l(QQp)

Q1 = QQp - 7 * PQp

l2 = get_l(Q1)
print(f'{l2 = }')
print(f'{3 * l0 = }')
print(f'{3 * get_l(p^4 * PQp) = }')

那其实上面这个是歪打正着了，其实正确的是看到原论文的命题 3，该命题直接给出了无穷远点群的结构：

如果 $P_1(X_1 : 1 : \mathrm{f}(X_1)), P_2(X_2 : 1 : \mathrm{f}(X_2)) \in E^{\infty}$，其中 $e_1 = \mathrm{v}_p(X_1), e_2 = \mathrm{v}_p(X_2)$，这里的 $\mathrm{v}_p(x)$ 就是 $x$ 的 $p$ 进赋值，那么：
$P_1 + P_2 = (X_3 : 1 : \mathrm{f}(X_3))$，其中 $X_3 \equiv X_1 + X_2 \pmod{p^{5\min\{e_1, e_2\}}}$

也就是说：

  1. 对于所有 $E^{\infty}$ 内的无穷远点，都能写成 $(X : 1 : \mathrm{f}(X))$ 的形式，其中 $X$ 中必有一个因子为 $p$，所以可以保证一开始的这个 $\mathrm{v}_p(X_1)$ 和 $\mathrm{v}_p(X_2)$ 都不小于 1，也就是上面那个同余只能在模 $p^5$ 上成立；
  2. 利用“以点 $q P$ 为生成元构成的椭圆曲线点群，上述性质在模 $p^5$ 上成立”的特性求离散对数 $Q = d P$（实际上转化成了求 $(qQ) = d (qP)$ 这个离散对数问题)，但是因为 $X_{qP}$ 中已经包含了一个 $p$，所以离散对数只能求出 $d \bmod p^4$ 的值，此时将 $d$ 写成 $d = d_0 + p^4 d_1$，已知 $d_0$，待求 $d_1$；
  3. 欲求 $d_1$ 的值，需考虑 $P’ = p^4{P}$ 和 $Q’ = Q - d_0 P$ 的离散对数问题 $Q’ = d_1 P’$（实际上去求 $qQ’ = d_1 (q P’)$ 这个离散对数问题）；
  4. 此时我们考察以点 $q P’$ 为生成元构成的椭圆曲线点群，我们会发现因为乘了个 $p^4$，加上原来因为映射到无穷远点上会产生的那个 $p$，所以我们可以保证 $\mathrm{v}_p(P’)$ 不小于 5；
  5. 回看命题 3，里面描述的那个同余能在 $ \bmod p^{25}$ 之内成立了。此时去掉 $X_{qP’}$ 中已经包含的 $p^{5}$，这次离散对数可以直接求出 $d_1 \bmod p^{20}$ 的值！

这个发现和上面的迭代求解的区别就是，之前都是用线性的速率去迭代的，利用完命题 3 之后，可以把迭代求解离散对数问题的过程改成平方的速率。

所以如果真正把命题 3 给搞懂了之后，其实就会发现命题 4 相当于是命题 3 的一个推论了

然后就是把交互脚本给搓出来了。在应用这个方法的时候，需要注意一个小细节：题目只给了点 $Q$ 的 $x$ 坐标，也就是点 $Q$ 的可能取值也有 2 个，需要先尝试一个去算离散对数 $d’$，然后验证 $Q = d’ P$ 是否成立从而决定结果是 $d = d’$ 还是 $d = p^{l-1} - d’$：

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
from pwn import *
from sage.all import *


class Gao:
    def __init__(self):
        self.conn = process(['sage', 'another.sage'])
        self.N = 5
    
    def gao_dlp_one(self, P, Q):
        # Q = d P
        p, l = self.p, self.l
        n0 = self.n0
        def get_l(P):
            K = n0 * P
            F_ = Zmod(p**4)
            return F_(ZZ(K[0]) / p) / F_(K[1])

        def get_l2(P):
            K = n0 * P
            F_ = Zmod(p**20)
            return F_(ZZ(K[0]) / p**5) / F_(K[1])

        d0 = ZZ(get_l(Q) / get_l(P))

        P1 = p**4 * P
        Q1 = Q - d0 * P

        d1 = ZZ(get_l2(Q1) / get_l2(P1))
        d_ = (d0 + p**4 * d1) % p**(l-1)
        
        # Deal with lifting
        if d_ * P == Q:
            d = d_
        else:
            d = p**(l-1) - d_
        return d
    
    def recv_points(self):
        self.P_list = []
        self.conn.sendlineafter('[Q]uit\n', 'B')
        for i in range(self.N):
            self.P_list.append((i+1, int(self.conn.recvline().split(b'=')[1])))
        
        self.Qx_list = []
        self.conn.sendlineafter('[Q]uit\n', 'E')
        for i in range(self.N):
            self.Qx_list.append(int(self.conn.recvline().split(b'=')[1]))
    
    def gao_curve(self):
        # N
        gs = []
        for i in range(self.N - 2):
            x1, y1 = self.P_list[i]
            x2, y2 = self.P_list[i+1]
            x3, y3 = self.P_list[i+2]
            A1 = x1 - x2
            B1 = (y1**2 - x1**3) - (y2**2 - x2**3)
            A2 = x2 - x3
            B2 = (y2**2 - x2**3) - (y3**2 - x3**3)
            gs.append(A1 * B2 - A2 * B1)
        g = gcd(gs)
        fac = factor(g)
        p, l = fac[-1]
        assert l == 12

        self.p, self.l = p, l
        F = Zmod(p**l)
        A = matrix(F, [[x1, 1],
                       [x2, 1]])
        B = vector(F, [y1**2 - x1**3, y2**2 - x2**3])
        a, b = A.solve_right(B)
        self.E = EllipticCurve(F, [a, b])
        self.P_list = [self.E(P) for P in self.P_list]
        self.Q_list = [self.E.lift_x(F(Qx)) for Qx in self.Qx_list]
        self.E0 = self.E.change_ring(Zmod(p))
        self.n0 = self.E0.order()
    
    def gao_dlp(self):
        self.ds = [self.gao_dlp_one(P, Q) for P, Q in zip(self.P_list, self.Q_list)]
    
    def submit_dlp(self):
        self.conn.sendlineafter('[Q]uit\n', 'S')
        for d in self.ds:
            self.conn.sendlineafter('integer:\n', str(d))
    
    def gao(self):
        self.recv_points()
        self.gao_curve()
        self.gao_dlp()
        self.submit_dlp()
        self.conn.interactive()

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

SingleRow (x)

题目描述

记 $q = 256, k = 40, v = 64$。题目的运算都在 $\mathbb{F} = GF(q) = GF(2^8)$ 下进行。

首先生成公钥和私钥：

  1. 记 $n = k + v$
  2. makecore 函数是往一个向量空间里面一直加入与其线性无关的向量，使得扩充之后的向量空间占据整个空间
  3. 用 makecore 生成一个满秩的矩阵 $M \in \mathbb{F}^{n \times n}$
  4. 生成 $k$ 个矩阵 $F_i, G_i$
    a. 生成随机 $F_i \in \mathbb{F}^{n \times n}$，其中 $F_i$ 具有分块形式：$A_i = 0^{k \times k}, B_i \in \mathbb{F}^{k \times v}, C_i \in \mathbb{F}^{v \times k}, D_i \in \mathbb{F}^{v \times v}$
    b. 如果 $\mathbb{F}$ 的 特征) 不为 2，则更新 $F_i$ 的取值为 $F_i’ = 1/2 \cdot (F_i + F_i^\top)$（因为 $\mathbb{F} = GF(2^8)$ 的特征总是 2，所以该条不会执行）
    c. 计算 $G_i = M^\top F_i M$
    d. 记录矩阵 $F_i$ 和 $G_i$
  5. 私钥为 $(M, F)$，公钥为 $G$，其中 $F$ 为若干个矩阵 $F_i$ 构成的列表，$G \in \mathbb{F}^k$ 为上述 $k$ 个 $G_i$ 构成的向量

然后是一套签名的流程。假设我们有私钥 $(M, F)$ 和二进制消息 $Z \in \{0, 1\}^{k}$：

  1. 生成 $k$ 个变量 $x_{i}, i = 0, 1, \ldots, k-1$ 的，在 $\mathbb{F}$ 上定义的多项式环
  2. 生成向量 其中 $K$ 为 $Y$ 的问号部分，问号代表 $\mathbb{F}$ 中的随机元素
  3. 计算二次型 $E_i = Y^\top F_i Y$，并抽出 $E_i$ 中 $x_0, x_1, \ldots, x_{k-1}$ 的系数，构成一行 $S_i$；遍历所有的 $i$，可以构成一个 $k \times k$ 的矩阵 $S$
  4. 抽出上面二次型 $E_i$ 的常数部分，遍历所有的 $i$，可以构成一个向量，记为 $P \in \mathbb{F}^{n}$
  5. 计算 $T = Z - P$
  6. 尝试解关于 $S’$ 的线性系统 $S S’ = T$；若能解出这样的 $S’$，则记 $V = \begin{bmatrix}S’ \\ K\end{bmatrix}$
  7. 返回 $M^{-1} V$

然后题目是一个 bit oracle：

  • 如果 msg[i] 是 1，那么返回 $M^{-1}$ 的前 $k$ 列向量张成空间中的随机一个元素
  • 如果 msg[i] 是 0，那么返回对一个长为 $k$ 的随机消息签名的结果

为了表示清楚，上面部分记号和代码中的字母有出入，请自行核对

如果能根据 oracle 返回的结果，正确判定分支，那么就能拿到 flag。

我的解答 (x)

没看。

刚查了一下 1997 比赛时候的合作文档，好像没人去看这道题，寄。

注册的时候一卡车人，到后面就剩几个老登苦苦支撑

赛后复盘

注意到上面虽然说是说了公钥和私钥，但是 公钥也是未知的……

而且光是将题目代码转述成上面文字描述，都看起来好长一坨

然后注意到可以用 flag 格式 CCTF{} 得知部分 oracle 结果的正确答案（已知信息）：

1
2
3
4
5
from Crypto.Util.number import *

flag_format = b"CCTF{}"
print(f'{bytes_to_long(flag_format) = :b}')
print(f'{bytes_to_long(flag_format).bit_count()}')

也就是有 24 组结果我们是知道的

先尝试写开一些东西，把 $M$ 写成分块矩阵

其中 $M_1 \in \mathbb{F}^{k \times n}, M_2 \in \mathbb{F}^{v \times n}$

然后密钥生成中的 $G_i$ 写开了就是

然并卵，因为我们并不知道 $G$ 的内容

然后签名中的 $E_i$ 写开了就是

所以 $P$ 的第 $i$ 个分量 $P_i = K^\top D_i K$，$T$ 的第 $i$ 个分量 $T_i = Z_i - P_i$

然后就是 $S$ 矩阵，因为 $S$ 矩阵的第 $i$ 行 $S_i^{\top}$ 是把 $x_i$ 的系数拼起来的，所以 $S_i = K^\top (C_i + B_i^\top)$

然后其实这个题面给的提示蛮明显的：假设我们记

那么当 msg[i] = 1 的时候，我们得到的是 $M_1’$ 列空间里面的向量 $R_1$，也就是 $R_1 \in \mathrm{Col}(M_1’)$；然后我们自然想到当 msg[i] = 0 的时候，我们得到的向量 $R_0$ 就应该不是 $M_1’$ 列空间里面的向量，也就是 $R_0 \notin \mathrm{Col}(M_1’)$？也就是说，这个题目绕来绕去，实际上那个列空间的生成就把真正的关键泄露到差不多了？我们魔改下代码测试一下，发现果然成立：

1
2
3
4
5
6
7
8
9
10
11
12
A, F = skey
V = span(A.inverse().columns()[:len(F)])
SIGNS = []
for i in range(len(FLAG_BITS)) :
    if FLAG_BITS[i]:
        R = vecsub(skey)
        print(f'1: {(R in V) = }')
        SIGNS.append(R)
    else:
        R = sign(skey, vector([randint(0, 1) for _ in range(m)]))
        print(f'0: {(R in V) = }')
        SIGNS.append(R)

可以观察到所有的数据都满足：

1
2
1: (R in V) = True
0: (R in V) = False

我们来证明一下这个猜想：要想证明 $R_0 \notin \mathrm{Col}(M_1’)$，可以利用 左零空间的正交性：倘若存在 $y \in \mathrm{Null}(M_1’^\top)$，即 $y^\top M_1’ = 0$，使得

那么 $R_0$ 不在列空间中。这是利用了“任何在左零空间中的向量 $y$ 都会对列空间中的向量点积为零。”这一性质。

实际上，只需要注意到将 $M$ 和 $M’$ 写成分块矩阵之后的性质：

对比就有：

特别注意到 $M_2 M_1’ = 0$，尝试令上面的 $y^\top$ 为 $M_2$，并计算

而 $K$ 是随机生成的，可以认为不为零。这样我们就用构造的方式说明了 $R_0 \notin \mathrm{Col}(M_1’)$。

既然知道了这个命题成立了，那么我们还需要根据已知的信息，构建出 $\mathrm{Col}(M_1’)$（维数为 40 的线性空间）。题目数据长度为 255，用 CCTF{} 可以提供列空间的 24 个向量，还剩 16 个向量，我们可以尝试用 RANSAC 算法：

  • 我们可以认为 flag 可见字符串部分的 0 和 1 出现概率是相当的，也就是有 1/2 的概率抽样到 1，对应 $\mathrm{Col}(M_1’)$ 中元素
  • 所以，我们还需要抽样出 16 个向量来构建完整的 $\mathrm{Col}(M_1’)$，也就是说我们有 1/65536 的概率构建成功列空间
  • 如果我们能构建成功列空间，那么可以用对应位置的向量是否属于列空间内，来推出 bit 序列
  • 如果构建正确的话，bit 序列中也应该有明显多于 40 个 1；把这个作为我们是否构建成功列空间（以及是否能成功获得 flag）的判断依据

加入多进程，这个算法应该是能成功的。但是如果不出意外的话，就要出意外了：和 maple3142 确认了一下，发现 题目数据生成的时候用的多项式和 SageMath 10.6 所用的多项式不他妈的一致！真是操了他的血吗

所以还得加个多项式的枚举，真的是没活硬整了……

代码如下：

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
from sage.all import *
from Crypto.Util.number import *
import random
import multiprocessing as mp
import time

F2 = GF(2)
P, x = PolynomialRing(F2, name='x').objgen()

irreducibles = [f for f in P.polynomials(8) if f.is_monic() and f.is_irreducible()]

with open('signatures.txt') as f:
    SIGNS_RAW = f.read().replace('^', '**')

flag_template = b'CCTF{12345678901234567890123456}'
flag_bits = list(map(int, f'{bytes_to_long(flag_template):b}'))

def worker(proc_id, col_space, other_indices, FF, SIGNS, found_flag, start_time, timeout=60):
    random.seed()
    num_tries = 0
    while True:
        if found_flag.value or (time.time() - start_time > timeout):
            break

        expanded_col_space = [x for x in col_space]
        expanded_indices = random.sample(other_indices, k=16)
        for i in expanded_indices:
            x = vector(FF, SIGNS[i])
            expanded_col_space.append(x)
        V = span(expanded_col_space)
        ans = []
        one_count = 0
        for i in range(len(flag_bits)):
            x = vector(FF, SIGNS[i])
            if x in V:
                ans.append('1')
                one_count += 1
            else:
                ans.append('0')
        if one_count > 42:
            with found_flag.get_lock():
                found_flag.value = True
            ans_int = int(''.join(ans), 2)
            flag = long_to_bytes(ans_int)
            print(f'[Proc #{proc_id}] AOLIGEI!!! {one_count = }')
            print(f'[Proc #{proc_id}] {flag = }')
            with open('44_flag.txt', 'wb') as f:
                f.write(flag)
            break

        num_tries += 1
        if proc_id == 0 and num_tries % 100 == 0:
            print(f'[Proc #0] Trying {num_tries} ...')

def main():
    for mod_poly in irreducibles:
        print(f"Trying {mod_poly = }")
        FF, z8 = GF(2**8, name='x', modulus=mod_poly).objgen()
        SIGNS = eval(SIGNS_RAW, {"z8": z8})
        col_space = []
        for i in range(len(flag_bits)):
            x = vector(FF, SIGNS[i])
            if (i < 5 * 8 - 1) or (i >= 31 * 8):
                if (flag_bits[i] == 1):
                    col_space.append(x)

        other_indices = [i for i in range(len(flag_bits))
                         if not ((i < 5 * 8 - 1) or (i >= 31 * 8)) and not (i % 8 == 7)]

        num_procs = mp.cpu_count()
        found_flag = mp.Value('b', False)
        start_time = time.time()
        procs = []
        for pid in range(num_procs):
            p = mp.Process(target=worker, args=(pid, col_space, other_indices, FF, SIGNS, found_flag, start_time, 60))
            p.start()
            procs.append(p)
        for p in procs:
            p.join()

        if found_flag.value:
            break

if __name__ == '__main__':
    main()

最后经过不懈枚举，得出的多项式和 flag 为：

1
2
3
Trying mod_poly = x^8 + x^6 + x^4 + x^3 + x^2 + x + 1
[Proc #1] AOLIGEI!!! one_count = 139
[Proc #1] flag = b'CCTF{On3_vEc7or_!n_UOV_5ch3meS!}'

坑爹啊.jpg