这次 hard 分类的题目难道是碳基生物能整出来的活儿？？？

Chochol

题目描述

题目基于 ECC：

128bit 素数 $p$ 和 $q$ 均满足 $p \equiv q \equiv 3 \pmod{4}$，$a$ 取随机，$b = 0$。

$E_p$ 和 $E_q$ 分别是 $E$ 在 $GF(p)$ 和 $GF(q)$ 下的情形。

生成元 $G_p$ 和 $G_q$ 的横坐标均为 2024。(MAN！)

然后有一个未知的 $s$，$H_p = s G_p$，$H_q = s G_q$

题目对明文的加密采用 RSA：

已知 $G_p, H_p, G_q, H_q, c$，求 $m$

我的解答

首先是求出 $a, p, q$ 这三个值。以 $p$ 为例，将 $G_p(x_1, y_1)$ 和 $H_p(x_2, y_2)$ 代入椭圆曲线方程：

可以消去 $a$：$(y_1^2 - x_1^3) x_2 - (y_2^2 - x_2^3) x_1 = 0$

注意到这些运算都是在模 $p$ 意义下进行的，所以上面这个等式的实际含义就是 $p$ 要整除左边那一坨。类似地，$q$ 也要整除由 $G_q$ 和 $H_q$ 产生的那一坨。

所以就是要把这两坨进行分解，分解出一个 128bit 的素因子出来，就是对应的 $p$ 或者 $q$。

结果这个分解没有那么简单，我们都只知道用 yafu 硬挂，结果套娃用 cado-nfs 一下子就跑出来了，我的发：

1
2
3
p = 243678574849421895808521345944938402807
q = 278451262698064898668334196027031252819
a = 127671661251150651301269745259748083900

然后就是求那个 ECDLP，先简单看一下阶：

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
Gp = (2024, 77522466419731346352388161327659294096)
Hp = (187001239996895215821259450553198409012, 158495938026527642884038157170741730943)
Gq = (2024, 92609909821520263487623088269239797003)
Hq = (191534442430060308634251661645421139195, 102273233384427938890774177710170123915)
c  = 15084463560924811262750235394027264639346464192638172940901706702947534963652

def kkp_modulus(G, H):
    x1, y1 = G
    x2, y2 = H
    ps = x2 * (y1^2 - x1^3) - x1 * (y2^2 - x2^3)
    return ps

ps = kkp_modulus(Gp, Hp)
qs = kkp_modulus(Gq, Hq)

def kkp_a(G, p):
    x, y = G
    return (y^2 - x^3) * inverse_mod(x, p)

a_p = kkp_a(Gp, p)
a_q = kkp_a(Gq, q)
a = crt([a_p, a_q], [p, q])
print(f'{a = }')

p = 243678574849421895808521345944938402807
q = 278451262698064898668334196027031252819
a = 127671661251150651301269745259748083900


Ep = EllipticCurve(Zmod(p), [a, 0])
Eq = EllipticCurve(Zmod(q), [a, 0])

Gp, Hp = map(Ep, (Gp, Hp))
Gq, Hq = map(Eq, (Gq, Hq))

print(f'{Gp.order() = }')
print(f'{Ep.order() = }')
print(f'{p = }')
print(f'{Gq.order() = }')
print(f'{Eq.order() = }')
print(f'{q = }')

然后发现这两根曲线的阶都是素数的值加上一，感觉是跟这个曲线的形式有关。

那还说啥呢，MOV attack 直接一把梭吧：

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
p = 243678574849421895808521345944938402807
a = 127671661251150651301269745259748083900
b = 0

k = 2

F1 = GF(p)
E1 = EllipticCurve(F1, [a, b])
F2 = GF(p^k, 'w')
phi = Hom(F1, F2)(F1.gen().minpoly().roots(F2)[0][0])
E2 = EllipticCurve(F2, [a, b])

P1 = E1(2024, 77522466419731346352388161327659294096)
R1 = E1(187001239996895215821259450553198409012, 158495938026527642884038157170741730943)

n = P1.order()

P2 = E2(phi(P1.xy()[0]), phi(P1.xy()[1]))
R2 = E2(phi(R1.xy()[0]), phi(R1.xy()[1]))

cn1 = E2.gens()[0].order()
coeff = ZZ(cn1 // n)

while True:
    Q = coeff * E2.random_point()
    if (Q.order() == n):
        break

alpha = P2.weil_pairing(Q, n)
beta = R2.weil_pairing(Q, n)
d = beta.log(alpha)

print(d)

求出离散对数之后，RSA 解密，需要注意 $e$ 和 $p-1$（$q-1$）不互素，且最大公约数为 2：

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

p = 243678574849421895808521345944938402807
q = 278451262698064898668334196027031252819
s = 172134561985710786674839705035313724070

c  = 15084463560924811262750235394027264639346464192638172940901706702947534963652

def decrypt(p, e, c):
    g = gcd(e, p-1)
    d = inverse_mod(e // g, p-1)
    m0 = pow(c, d, p)
    print(m0)
    print(g)
    m = Zmod(p)(m0).nth_root(g, all=True)
    print(m)
    assert pow(m[0], e, p) == c
    return m

mp = decrypt(p, s, c)
mq = decrypt(q, s, c)
for mpi, mqi in itertools.product(mp, mq):
    m = crt([ZZ(mpi), ZZ(mqi)], [p, q])
    msg = long_to_bytes(int(m))
    print(msg)

得到 flag 为：

1
CCTF{m1X!n9__3cC__&_R54_!}

关于为什么这样生成的曲线的阶满足 $\#E(\mathrm{F}_p) = p + 1$，可以看看 这篇 paper 的 3.2 节，之后也能看到类似的生成方法就不用验证也能一眼丁真（

Imen

题目描述

给定 $GL(p, k)$ 中的 $n$ 个矩阵 $A_1, A_2, \ldots, A_n$，这些矩阵的行列式均非零，每个元素 $x$ 均满足 $0 \le x \le B$，其中 $k, B$ 均较小。

生成 $i_1, i_2, \ldots, i_n$ 为 $1, 2, \ldots, n$ 的一个排列，并且计算

已知 $A_1, A_2, \ldots, A_n, M$，求排列 $i_1, i_2, \ldots, i_n$。

我的解答

题目背景详见 这篇 paper。

其实这个问题就是上面那篇 paper 的 intuition，可以直接用他的那个 decompose algorithm 来解就行了。注意到他在第 4 页中的第 3 段中定义了矩阵之间的小于号比较。

可以看看他那个第 5 页最末尾的 Example 1 来辅助理解。

所以只需要实现以下他的这个 decompose algorithm 就行了。

因为当时是先做的也是关于这个背景的另一道题 Jonon，所以就直接对着 Jonon 的求解代码改一改就出来了。

注意到在这个问题里面，模数 $p$ 是未知的。这里介绍两个解决方法：

  1. 随机生成一个大素数 $p$：假设能 decompose 的话，成功 decompose 的情形和 $p$ 的具体取值无关；
  2. 直接不管，在 $\mathbb{Q}$ 上去求逆去做。成功 decompose 的情形肯定能算出所有元素都是 $\mathbb{Z}$ 内的。

在实现的时候我选用了方法 2。貌似在他这个情境下面，decompose algorithm 不是时时刻刻都能 work 的，可能需要拼人品。然后是因为这个求解代码是根据 Jonon 的求解代码改的，所以第一层会采用一个枚举的操作，保证第一层 decompose 不会挂。代码如下： 

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


class Gao:
    def __init__(self):
        self.conn = remote('00.cr.yp.toc.tf', '31117')
    
    def decompose(self, A, index_list, M):
        if len(A) == 0:
            return None
        elif len(A) == 1:
            if M != A[0]:
                return None
            else:
                return [index_list[0]]
        else:
            for i, Ai in enumerate(A):
                M_ = Ai^-1 * M
                try:
                    MZ = M.change_ring(ZZ).list()
                    MZ_ = M_.change_ring(ZZ).list()
                    if (all(MZi_ < MZi for MZi, MZi_ in zip(MZ, MZ_))):
                        A_ = A[:i] + A[i+1:]
                        index_list_ = index_list[:i] + index_list[i+1:]
                        res = self.decompose(A_, index_list_, M_)
                        if res:
                            return [index_list[i]] + res
                        else:
                            return None
                except:
                    continue
            else:
                return None

    def decrypt(self, As, M):
        T = M
        # CAONIMA, exceed
        index_list = list(range(len(As)))
        for i, Ai in enumerate(As):
            A_ = As[:i] + As[i+1:]
            index_list_ = index_list[:i] + index_list[i+1:]
            T_ = Ai^-1 * T
            S = self.decompose(A_, index_list_, T_)
            if S:
                return [i] + S
        else:
            return None

    def get_matrices(self, k, l):
        self.conn.sendlineafter('[Q]uit', 'G')
        matrices = []
        for i in range(l):
            mat = []
            for i in range(k):
                self.conn.recvuntil(b'[')
                row = self.conn.recvuntil(b']')[:-1].decode().split()
                mat.append(list(map(int, row)))
            matrices.append(matrix(ZZ, mat))
        return matrices

    def get_product(self, k):
        self.conn.sendlineafter('[Q]uit', 'P')
        product = []
        self.conn.recvuntil(b'M = ')
        for i in range(k):
            self.conn.recvuntil(b'[')
            row = self.conn.recvuntil(b']')[:-1].decode().split()
            product.append(list(map(int, row)))
        return matrix(ZZ, product)

    def submit_answer(self, ans):
        self.conn.sendlineafter('[Q]uit', 'S')
        msg = ','.join(map(str, ans))
        self.conn.sendline(msg)

    def gao_1(self, k, l):
        As = self.get_matrices(k, l)
        M = self.get_product(k)
        ans = self.decrypt(As, M)
        if ans:
            self.submit_answer(ans)
            return True
        else:
            return False
    
    def gao(self):
        nbit, step = 128, 12
        for level in range(step):
            print(f'{level = }')
            k, l, B = 3, 12 + level, 14 + (level + 1)
            if not self.gao_1(k, l):
                self.conn.close()
                return False
        self.conn.interactive()

if __name__ == '__main__':
    while True:
        g = Gao()
        g.gao()
  • 感觉 get_matrices 方法的接受矩阵过程还有优化的空间（一次收完慢慢切）
  • 成功率貌似有丶感人，可以考虑土味多进程挂机

获取 flag 为：

1
CCTF{c4N_y0U_3fF1c!En7lY_rEc0v3Re_tH3_0rD3R_of_M4tR1x_PrODuC7S?}

这里也给出随机生成一个大素数 $p$ 的代码实现：

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


class Gao:
    def __init__(self):
        self.conn = remote('00.cr.yp.toc.tf', '31117')
    
    def decompose(self, A, index_list, M):
        if len(A) == 0:
            return None
        elif len(A) == 1:
            if M != A[0]:
                return None
            else:
                return [index_list[0]]
        else:
            for i, Ai in enumerate(A):
                M_ = Ai^-1 * M
                MZ = M.change_ring(ZZ).list()
                MZ_ = M_.change_ring(ZZ).list()
                if (all(MZi_ < MZi for MZi, MZi_ in zip(MZ, MZ_))):
                    A_ = A[:i] + A[i+1:]
                    index_list_ = index_list[:i] + index_list[i+1:]
                    res = self.decompose(A_, index_list_, M_)
                    if res:
                        return [index_list[i]] + res
                    else:
                        return None
            else:
                return None

    def decrypt(self, As, M):
        T = M
        # CAONIMA, exceed
        index_list = list(range(len(As)))
        for i, Ai in enumerate(As):
            A_ = As[:i] + As[i+1:]
            index_list_ = index_list[:i] + index_list[i+1:]
            T_ = Ai^-1 * T
            S = self.decompose(A_, index_list_, T_)
            if S:
                return [i] + S
        else:
            return None

    def get_matrices(self, k, l):
        self.conn.sendlineafter('[Q]uit', 'G')
        matrices = []
        for i in range(l):
            mat = []
            for i in range(k):
                self.conn.recvuntil(b'[')
                row = self.conn.recvuntil(b']')[:-1].decode().split()
                mat.append(list(map(int, row)))
            matrices.append(matrix(ZZ, mat))
        return matrices

    def get_product(self, k):
        self.conn.sendlineafter('[Q]uit', 'P')
        product = []
        self.conn.recvuntil(b'M = ')
        for i in range(k):
            self.conn.recvuntil(b'[')
            row = self.conn.recvuntil(b']')[:-1].decode().split()
            product.append(list(map(int, row)))
        return matrix(ZZ, product)

    def submit_answer(self, ans):
        self.conn.sendlineafter('[Q]uit', 'S')
        msg = ','.join(map(str, ans))
        self.conn.sendline(msg)

    def gao_1(self, k, l, B):
        p_l = (k * l) ** B * 2^5
        p = random_prime(2*p_l, proof=False, lbound=p_l)
        Zp = Zmod(p)
        As = self.get_matrices(k, l)
        M = self.get_product(k)
        As = [Ai.change_ring(Zp) for Ai in As]
        M = M.change_ring(Zp)
        ans = self.decrypt(As, M)
        if ans:
            self.submit_answer(ans)
            return True
        else:
            return False
    
    def gao(self):
        nbit, step = 128, 12
        for level in range(step):
            print(f'{level = }')
            k, l, B = 3, 12 + level, 14 + (level + 1)
            if not self.gao_1(k, l, B):
                self.conn.close()
                return False
        self.conn.interactive()

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

也是存在失败率的

Latifa

题目描述

记明文为 $m$，题目设计了一个加密算法：

其中参数 $b, g$ 未知。

给定 $S$，求 $m$。

我的解答

首先分子中的 $b$ 可以提出来。

然后就是求和式

也就是

然后还有就是注意到 $m$ 是个比较大的数。记上式为 $f(m)$。

因为当时只需要把题目解出来就行了，所以直接去看了 $g$ 为比较小值的时候，上式的值：

  • $g=2$ 的时候： $f(m)=1/6 + m/2$
  • $g=3$ 的时候： $f(m)=1/4 + m/2$
  • $g=4$ 的时候： $f(m)=3/10 + m/2$

找灵感的代码如下：

1
2
3
4
5
6
7
8
9
10
from tqdm import trange

g = 4

s = 0
m = 12345
for i in trange(m):
    s += n(1 / (g^((2*i-m)/m) + 1), prec=12345)

print(20 * s)

所以就可以认为 $S \approx bm/2$，也就是说，$m \mid 2S$。

所以也就是说把 $2S$ 的所有因数拿出来看一下，看看符不符合消息的格式。

然后注意，因为消息是可打印字符串，所以最后一个 byte 的值是小于 128 的，也就是 $m$ 的素因数分解中，2 的幂次至多为 6。

这里之前做题的时候有点狗屎运了，没注意到题目是把 CCTF{} 的包裹都丢掉了，就以为 $m$ 一定以 } 结尾，为奇数（实际上不是这样的）。结果他的消息也正好是奇数，瞎猫碰上死耗子了算是。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from Crypto.Util.number import *
import itertools
from tqdm import tqdm

pi = [3, 5, 379, 39719, 8959787, 891059823255825019255461632769683]
ai = [1, 1 + 11954, 1, 1, 1, 1]

ri = [range(aii+1) for aii in ai]
for ai_ in tqdm(itertools.product(*ri)):
    m = 1
    for p, a in zip(pi, ai_):
        m *= p**a
    msg_ = long_to_bytes(m)
    if all(32 <= x < 128 for x in msg_):
        print('AOLIGEI!!!')
        print(msg_)

解得 flag 为：

1
CCTF{h4Lf_7UrN_5ym3Try!}

然后我们来求一下那个和式。

因为 $m$ 较大，所以可以用积分

估计和式的值。作换元 $x = um$，有

再作换元 $v = 2 u - 1$，有

然后问题就转换为求定积分

的值。

求这个定积分对于大学生来说小菜一碟，但是对于我这种工友来说还是需要花点心思

考虑不定积分

首先直接求这个被积函数的积分有丶困难，所以我们想办法要在分母中凑出一个 $g^x$ 来，这样就可以配凑出分母的形式来。分母出 $g^x$ 的方式很简单：

然后再想办法塞到微分算子里面去：

回到原问题，当 $g$ 大的时候，我们前面待求的定积分也就是

所以有 $I \approx m/2$，也就是我们前面通过验证 $g$ 较小的时候得出的结论。

但是那个直接算求和式得到的常数项还是不知道是哪里来的

再试了多几组，发现

虽然还是不知道常数项怎么出来的，很烦