CryptoCTF 2024 hard 分类 团队解题 writeup 之二

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

O7R

题目描述

题目基于 RSA 和七！段！数！码！管！

题目给出了 $p, q, n, n^2$ 的七段数码管的 损坏形式，以及密文 $c$ 的七段数码管形式，其中一个数的七段数码管的损坏形式被定义为：这个七段数码管的每一位数都会以 50%的概率，某一段数码管本来要亮的，结果没亮了，如下就是一个数位 7 损坏了一个数码管的例子：

 xxxx        xxxx
o    x      o    o
o    x      o    o
o    x      o    o
 oooo    ->  oooo 
o    x      o    x
o    x      o    x
o    x      o    x
 oooo        oooo

题目没说 $e$ 是多少（可能要靠猜，譬如 $e=65537$），求明文 $m$。

我的解答

当时比赛的时候，我没看这道题，未央、三顺七、苏氨酸当时还就被这个男的女的折磨，多捞哦！

这尼玛是碳基生物整得出的活儿？

首先得把他那个七段数码管切成数，至少转换成七段数码管的某个表示，譬如长度为 7 的 01 串。

我们先约定一下这七段数码管的编号：

 0000 
3    4
3    4
3    4
 1111 
5    6
5    6
5    6
 2222 

然后就是把 PDF 转换成图片，这里随便找一个 网站 转换一下

然后就是抠图的过程，这里可以搞个蒙版去对一下抠的对不对，看看行不行，如果不行的话得继续调，譬如这样就得继续看看

这是因为，数字与数字间的距离 不能 直接用两个相邻的数来得到，应该用最左和最有的距离减去，再除以中间间隔的数的个数，这样得到的距离才不会受到累计误差的影响。

import numpy as np
import cv2
import pickle

PAGE_HEIGHT = 3508
SEGMENT_WIDTH = 5
SEGMENT_HEIGHT = 20
INTER_SEGMENT_WIDTH = (1954 - 691) / 39.
INTER_SEGMENT_HEIGHT = (2505 - 1198) / 15.
NUM_COLORS = 3

def extract_segments(a, x0, y0, nrows=4, ncols=40):
    b = a.copy()

    seven_segments_buffer = []
    all_segments = []
    def draw(block):
        block[:] = [255, 0, 0]
    def add_buffer(block):
        seven_segments_buffer.append(int(block.sum() < 0.5 * 255 * NUM_COLORS * SEGMENT_WIDTH * SEGMENT_HEIGHT)) 
    is_draw = True
    for i in range(nrows):
        for j in range(ncols):
            seven_segments_buffer = []
            xi = int(x0 + i * INTER_SEGMENT_HEIGHT)
            yi = int(y0 + j * INTER_SEGMENT_WIDTH)
            seven_segments = [
                b[xi:xi+SEGMENT_WIDTH,
                  yi+SEGMENT_WIDTH:yi+SEGMENT_WIDTH+SEGMENT_HEIGHT], # 0
                b[xi+SEGMENT_WIDTH+SEGMENT_HEIGHT:xi+2*SEGMENT_WIDTH+SEGMENT_HEIGHT,
                  yi+SEGMENT_WIDTH:yi+SEGMENT_WIDTH+SEGMENT_HEIGHT], # 1
                b[xi+2*SEGMENT_WIDTH+2*SEGMENT_HEIGHT:xi+3*SEGMENT_WIDTH+2*SEGMENT_HEIGHT,
                  yi+SEGMENT_WIDTH:yi+SEGMENT_WIDTH+SEGMENT_HEIGHT], # 2
                b[xi+SEGMENT_WIDTH:xi+SEGMENT_WIDTH+SEGMENT_HEIGHT,
                  yi:yi+SEGMENT_WIDTH], # 3
                b[xi+SEGMENT_WIDTH:xi+SEGMENT_WIDTH+SEGMENT_HEIGHT,
                  yi+SEGMENT_WIDTH+SEGMENT_HEIGHT:yi+2*SEGMENT_WIDTH+SEGMENT_HEIGHT], # 4
                b[xi+2*SEGMENT_WIDTH+SEGMENT_HEIGHT:xi+2*SEGMENT_WIDTH+2*SEGMENT_HEIGHT,
                  yi:yi+SEGMENT_WIDTH], # 5
                b[xi+2*SEGMENT_WIDTH+SEGMENT_HEIGHT:xi+2*SEGMENT_WIDTH+2*SEGMENT_HEIGHT,
                  yi+SEGMENT_WIDTH+SEGMENT_HEIGHT:yi+2*SEGMENT_WIDTH+SEGMENT_HEIGHT], # 6
            ]
            list(map(add_buffer, seven_segments))
            if is_draw:
                list(map(draw, seven_segments))
            all_segments.append(seven_segments_buffer)
    if is_draw:
        b = cv2.cvtColor(b, cv2.COLOR_RGB2BGR)
        cv2.imwrite(f'kkp_{x0}_{y0}.png', b)
    while len(all_segments) > 0 and sum(all_segments[-1]) == 0:
        all_segments = all_segments[:-1]
    return all_segments
  
raw_images = []
for i in range(4):
    a = cv2.imread(f'O7R.pdf-image-00{i+1}.png', cv2.IMREAD_COLOR)
    a = cv2.cvtColor(a, cv2.COLOR_BGR2RGB)
    raw_images.append(a)
a = np.concatenate(raw_images, axis=0)
p_segments = extract_segments(a, PAGE_HEIGHT+2422, 666)
q_segments = extract_segments(a, PAGE_HEIGHT+2854, 666)
n_segments = extract_segments(a, PAGE_HEIGHT*2+417, 669, 8)
n2_segments = extract_segments(a, PAGE_HEIGHT*2+1198, 682, 16)
c_segments = extract_segments(a, PAGE_HEIGHT*3+367, 664, 8)
with open('segments.pickle', 'wb') as f:
    pickle.dump({
        'p': p_segments,
        'q': q_segments,
        'n': n_segments,
        'n2': n2_segments,
        'c': c_segments,
    }, f)

这样就得到了一个阶段性的结果。

然后我们将十个数字的硬编码写出来，并且用模 $10^k$，不断增加 $k$ 的手法来求解，恢复出 $p$ 和 $q$。注意：

• $p, q, n, n^2$ 的七段数码管表示是 有损坏的
• $c$ 的七段数码管表示是 无损坏的

有损坏可以描述为，这些数每一段长度为 7 的 01 串表示和正常的数位的长度为 7 的 01 串表示相比：

• 不会 出现 (1, 0) 的情况；
• 可能 出现 (0, 1) 的情况；且如果出现了这种情况，至多出现一次

得到 $c$，以及求解 $p$ 和 $q$ 的代码如下：

import pickle
import itertools

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

p_segments = segments['p']
q_segments = segments['q']
n_segments = segments['n']
n2_segments = segments['n2']
c_segments = segments['c']

digit_segments = [
    [1, 0, 1, 1, 1, 1, 1],
    [0, 0, 0, 0, 1, 0, 1],
    [1, 1, 1, 0, 1, 1, 0],
    [1, 1, 1, 0, 1, 0, 1],
    [0, 1, 0, 1, 1, 0, 1],
    [1, 1, 1, 1, 0, 0, 1],
    [1, 1, 1, 1, 0, 1, 1],
    [1, 0, 0, 0, 1, 0, 1],
    [1, 1, 1, 1, 1, 1, 1],
    [1, 1, 1, 1, 1, 0, 1]
]

def compare(seg1, seg2):
    lt = sum(x < y for x, y in zip(seg1, seg2))
    eq = sum(x == y for x, y in zip(seg1, seg2))
    gt = sum(x > y for x, y in zip(seg1, seg2))
    return lt, eq, gt

def find_possible_digit(seg, corrupt=True):
    possible_lt_gt = {(0, 0), (1, 0)} if corrupt else {(0, 0)}
    result = []
    for i, i_seg in enumerate(digit_segments):
        lt, eq, gt = compare(seg, i_seg)
        if (lt, gt) in possible_lt_gt:
            result.append(i)
    return result

def get_c():
    result = []
    for c_segment in c_segments:
        result.append(str(find_possible_digit(c_segment, False)[0]))
    return int(''.join(result))

c = get_c()
print(f'{c = }')

def solve_pq():
    cur_sol = [(0, 0)]
    M = 1
    for i in range(len(p_segments)):
        # print(f'{i = }, {len(cur_sol) = }')
        nxt_index = -(i+1)
        nxt_p_segment, nxt_q_segment, nxt_n_segment, nxt_n2_segment = map(
            lambda segments: segments[nxt_index],
            (p_segments, q_segments, n_segments, n2_segments))
        nxt_ps, nxt_qs, nxt_ns, nxt_n2s = map(
            find_possible_digit,
            (nxt_p_segment, nxt_q_segment, nxt_n_segment, nxt_n2_segment)
        )
        nxt_sol = []
        nxt_ns, nxt_n2s = map(set, (nxt_ns, nxt_n2s))
        for cur_p, cur_q in cur_sol:
            for nxt_ph, nxt_qh in itertools.product(nxt_ps, nxt_qs):
                nxt_p = nxt_ph * M + cur_p
                nxt_q = nxt_qh * M + cur_q
                nxt_n = nxt_p * nxt_q % (10 * M)
                nxt_nh = nxt_n // M
                nxt_n2 = nxt_n * nxt_n % (10 * M)
                nxt_n2h = nxt_n2 // M
                if nxt_nh in nxt_ns and nxt_n2h in nxt_n2s:
                    nxt_sol.append((nxt_p, nxt_q))
        M *= 10
        cur_sol = nxt_sol
    print(cur_sol)

solve_pq()

然后就猜 $e=65537$ 并套用 RSA 解密：

from Crypto.Util.number import *

p = 7326673976775677403615902952775786009780696864351810113969520603559523530618382637866632341958388570488543071638027072634087397361132795284727648994814597
q = 7075605374343310393660736847187727587911784641033429799366923429044581810690842608691612098700666156539827395662425799607464237168537039463467940973806709

c = 3562663791006368034141977288433903435480729754256243271724528203580472770993094486280368310543613382256743525891807443983661459665243901555404810179525594817342115941001759547407703653781422057871347356603203075709275979343680289210665741824992476238299997444201948575831891922291318008008982215564064059476

e = 65537
d = inverse(e, (p-1)*(q-1))
m = pow(c, d, p*q)
print(long_to_bytes(m))

得到 flag 为：

CCTF{5eVEn_S39Men7_RSA_w!Th_k3Y_rEc0v3Ry!!!}

其实感觉……还好？YeYe5 拿了一血，哟西

Solmaz

题目描述

题目基于 ECC。

先生成 4 个 32bit 素数 $p_1, p_2, p_3, p_4$，$p=4(p_1p_2p_3p_4)^2+1$。

然后就是生成椭圆曲线 $E_{p}: y^2 = x^3 + c x$，并且该椭圆曲线的阶为 $p-1$。

生成椭圆曲线上两个点 $P, Q$ 满足 $Q = m P$，已知这两个点 $P, Q$，求 $m$

我的解答

和 Chochol 一样，我们 不知道 素数 $p$。

所以我们还是需要将两个点的坐标代回曲线式联立，并消去 $c$，得到一个数，然后 $p$ 就是这个数的素因子。

P = 
Q = 

x1, y1 = P
x2, y2 = Q
kp = y1**2 * x2 - x1**3 * x2 - x1 * y2**2 + x1*x2**3
print(f'{kp = }')

然后因为已知 $p-1$ 的素因子小于 $2^{32}$，所以直接使用 Pollard’s p-1 并挂机即可。

一开始想着把 Pollard’s p-1 的 python 实现直接喂给 ChatGPT，让它生成用 GMP 写的 C++代码，但是好像出了点问题……

总之做法应该是这样的，多线程（多进程）应该占不到什么便宜，毕竟 Pollard’s p-1 要一路乘方。

先给出套娃的 python 实现，总之他在比赛的时候挂出来了：

import _thread
from gmpy2 import gcd, powmod, next_prime
import time

DONE = None
def check(n, a, pi, lfn):
    global DONE
    d = gcd(a-1, n)
    log = '[Debug - %s] pi = %d\ta = %d\t d = %d' % (time.asctime(time.localtime(time.time())), pi, a, d)
    if d == n:
        print('Bias so large!')
        DONE = False
        return
    if d > 1 and d < n:
        print('Done:')
        DONE = d  # assert BIAS is large enough, so omit lock
        log += '\n[Done] d = %d' % d
    print(log)
    if lfn != None:
        with open(lfn, 'a') as lf:
            lf.write(log + '\n')
    return

def pollard(n, a=1997, pi=2, B=4294967296, lfn=None, BIAS=100000):
    global DONE
    counter = 0
    while pi < B:
        counter += 1
        a = powmod(a, pi**2, n)
        if counter == BIAS:
            #if DONE != None:
            #    break
            counter = 0
            _thread.start_new_thread(check, (n, a, pi, lfn, ) )
        pi = next_prime(pi)
    print(a)
    return DONE

n = 55454940004513276799611588380059302189664933020838413515384708243928267219228512844352832003082349090934777517286737687281070260517892560156083453894086877367076953177914949876201881341274104406095268673060476748059522884381040212
print(pollard(n, lfn='1.log', BIAS=1000000))

这个代码是用一个线程去做乘方，另一个线程去做，但是这样的话，跟 python 的 GIL 配合得不是很好（等 python 3.13 吧）。在石卡库的机器上只用 1h 就能出结果来，但是我的机器就要挂得比较久，神奇。

总之一通挂之后，得到素数 $p$ 的值为

30126567747372029007183424263223733382328264316268541293679065617875255137317

然后因为 $p-1=4(p_1p_2p_3p_4)^2$，可以直接套 Pohlig-Hellman 解：

from Crypto.Util.number import *
p = 30126567747372029007183424263223733382328264316268541293679065617875255137317
P = 
Q = 
x, y = P

c = ZZ((y^2 - x^3) * inverse_mod(x, p) % p)
EC = EllipticCurve(Zmod(p), [c, 0])
P, Q = map(EC, (P, Q))

m = P.discrete_log(Q)
print(long_to_bytes(int(m)))

得到 flag 为：

CCTF{3cC_d1ViSibil!7Y}

---

赛后反思

其实之前居然又 TMD 有丶忘记 Pollard’s p-1 是怎么玩的去了。

其实原理也就是利用

$$p \mid g^{p-1}-1 = g^{4 (p_1p_2p_3p_4)^2} - 1$$

已知 $p_1, p_2, p_3, p_4$ 均为 32bit 素数，所以指数那里把所有的 32bit 素数乘起来，也会有：

$$p \mid g^{p-1}-1 = g^{4 P^2} - 1$$

其中

$$P = \prod_{32-\mathrm{bit} \; p}{p}$$

然后：

• 我一开始在实现的时候是把 $2 \sim 2^{32}$ 的所有整数乘起来
• 后来发现只需要把 $2^{31} \sim 2^{32}$ 的所有整数乘起来
• 后来发现只需要把 $2^{31} \sim 2^{32}$ 的所有奇数乘起来
• 后来发现用 next_prime 会更快
• 当然因为 C++实现 next_prime 也需要一些工夫（至少实现求 $2^16$ 以内素数的线性筛，这个对大学生来说信手拈来，但是对工地狗来说汗流浃背），所以直接打表 100 以内的素数进行判断，就已经能加快很多了
• 最终耗时 51min 就能跑完算法

C++代码如下：

#include <gmp.h>
#include <gmpxx.h>
#include <bits/stdc++.h>

unsigned long next_p(const unsigned long x) {
    std::vector<int> primes = { 3,  5,  7, 11, 13, 17, 19, 23, 29, 31,
                               37, 41, 43, 47, 53, 59, 61, 67, 71, 73,
                               79, 83, 89, 97};
    unsigned long long t;
    for (t = x + 2; ; t += 2) {
        bool is_prime = true;
        for (auto p : primes) {
            if (t % p == 0) {
                is_prime = false;
                break;
            }
        }
        if (is_prime) {
            break;
        }
    }
    return t;
}

mpz_class pollards(const mpz_class &n, const unsigned long long L, const unsigned long R) {
    mpz_class cur = 16; // 2^4
    mpz_class gcd_result;
    auto start = std::chrono::high_resolution_clock::now();
    unsigned cnt = 0;
    for (unsigned long i = L; i < R; i = next_p(i)) {
        if ((cnt & 0xFFFFF) == 0) {
            std::cout << "Trying #" << cnt << ", i = " << i << std::endl;
            auto end = std::chrono::high_resolution_clock::now();
            auto duration = std::chrono::duration_cast<std::chrono::seconds>(end - start);
            auto minutes = std::chrono::duration_cast<std::chrono::minutes>(duration);
            auto seconds = duration - minutes;
            std::cout << "Elapsed time: " << minutes.count() << " min " << seconds.count() << " s" << std::endl;
        }
        cnt += 1;
        mpz_powm_ui(cur.get_mpz_t(), cur.get_mpz_t(), i * i, n.get_mpz_t());
    }
    // Equivalent to tst = gcd(cur - 1, n)
    mpz_class cur_minus_one = cur - 1;
    mpz_gcd(gcd_result.get_mpz_t(), cur_minus_one.get_mpz_t(), n.get_mpz_t());
    
    if (gcd_result != 1) {
        return gcd_result;
    }
    
    return 0; // Return 0 to indicate failure
}

int main() {
    mpz_class n("55454940004513276799611588380059302189664933020838413515384708243928267219228512844352832003082349090934777517286737687281070260517892560156083453894086877367076953177914949876201881341274104406095268673060476748059522884381040212");
    n /= 13;

    std::cout << "n = " << n << std::endl;

    unsigned long L = (1LL << 31) + 1;
    unsigned long R = 1LL << 32;
    mpz_class p = pollards(n, L, R);

    if (p == 0) {
        std::cout << "No factor found." << std::endl;
    } else {
        std::cout << "p = " << p << std::endl;
    }

    return 0;
}

// g++ -O3 -o pollard pollard.cpp -lgmp -lgmpxx 

阶为 $p-1$ 其实也可以套 MOV attack：

def get_embedding_degree(q, n, max_k):
    """
    Returns the embedding degree k of an elliptic curve.
    Note: strictly speaking this function computes the Tate-embedding degree of a curve.
    In almost all cases, the Tate-embedding degree is the same as the Weil-embedding degree (also just called the "embedding degree").
    More information: Maas M., "Pairing-Based Cryptography" (Section 5.2)
    :param q: the order of the curve base ring
    :param n: the order of the base point
    :param max_k: the maximum value of embedding degree to try
    :return: the embedding degree k, or None if it was not found
    """
    for k in range(1, max_k + 1):
        if q ** k % n == 1:
            return k

    return None

def attack(P, R, max_k=6, max_tries=10):
    """
    Solves the discrete logarithm problem using the MOV attack.
    More information: Harasawa R. et al., "Comparing the MOV and FR Reductions in Elliptic Curve Cryptography" (Section 2)
    :param P: the base point
    :param R: the point multiplication result
    :param max_k: the maximum value of embedding degree to try (default: 6)
    :param max_tries: the maximum amount of times to try to find l (default: 10)
    :return: l such that l * P == R, or None if l was not found
    """
    E = P.curve()
    q = E.base_ring().order()
    n = P.order()
    assert gcd(n, q) == 1, "GCD of base point order and curve base ring order should be 1."

    print("Calculating embedding degree...")
    k = get_embedding_degree(q, n, max_k)
    if k is None:
        return None

    print(f"Found embedding degree {k}")
    Ek = E.base_extend(GF(q ** k))
    Pk = Ek(P)
    Rk = Ek(R)
    for i in range(max_tries):
        Q_ = Ek.random_point()
        m = Q_.order()
        d = gcd(m, n)
        Q = (m // d) * Q_
        if Q.order() != n:
            continue

        if (alpha := Pk.weil_pairing(Q, n)) == 1:
            continue

        beta = Rk.weil_pairing(Q, n)
        print(f"Computing {beta}.log({alpha})...")
        l = beta.log(alpha)
        return int(l)

    return None

from Crypto.Util.number import *
p = 
P = 
Q = 
x, y = P

c = ZZ((y^2 - x^3) * inverse_mod(x, p) % p)
EC = EllipticCurve(Zmod(p), [c, 0])
P, Q = map(EC, (P, Q))

m = attack(P, Q)
print(long_to_bytes(int(m)))

Tesvir

题目描述

题目先将明文 $m$ 表示成 bit 表示形式（01 串），然后重排成 24 个 bit 一行的矩阵，这 24 个 bit 会在以右边追加 0 的形式被扩充为 223 个 bit，右边的右边还会加上（m 中 0 的个数）那么多个 1。

举个栗子：

01000001010011110100110
-> append to 223
0100000101001111010011000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011111111111111
-> m.count('1') = 10
0100000101001111010011000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011111111111111

这个明文矩阵记为 $\mathbf{M}$。

参数生成 记 $\mathbb{F} = GF(223^{24}), q = 223^{24} - 1$。

• 生成一个系数在 $GF(223)$ 中的不可约、首一多项式 $f$，并把 $f$ 的系数转到 $\mathbb{F}$ 中
• 生成 $F$ 中的生成元 $g$
• $t$ 为 $f$ 的一个根
• 生成 $\{1, 2, \ldots, 223\}$ 的一个排列 $r$

公钥生成

• 生成整数 $d$ 满足 $1 < d < q$
• 生成 $\{1, 2, \ldots, 223\}$ 的一个排列 $p$，其中 $p_{i}$ 为这个排列 $p$ 的第 $i$ 个元素
• 计算 $b_{i}$ 为 $t + r_{p_{i}} - 1$ 对 $g$ 的离散对数
• 计算 $c_i = (b_i + d) \bmod q$
• 公钥为 $c_1, c_2, \ldots, c_{223}$

加密算法

记 $\vec{c} = \begin{bmatrix}c_1 & c_2 & \ldots & c_{233}\end{bmatrix}^\top$，则有

$$C = \left(\mathbf{M}^{\top}\vec{c}\right) \bmod q$$

已知密文 $C$，公钥 $\vec{c}$ 以及排列 $r$，求明文 $\mathbf{M}$

我的解答

其实看到前面一大摞，都感觉比较抽象，

直接看到最后的加密算法就好，已知公钥和密文，求明文。

他写成了矩阵的形式，我们直接把每行的运算拆开来看，就是一个 01 背包。

所以直接套格就行了。

注意到因为有一个补 1 的过程，所以我们可以枚举右边 1 的个数，只对前 24 个 bit 求解。

然后还有一点就是补 1 的过程之后，有 24 个 1，所以我们还能得到前面未知数求和的一个约束式。

枚举 $t=1, 2, \ldots, 24$，记 $C’ = C - \sum_{k=1}^{t}c_{224-t} + k q$（枚举，注意到 $0 \le k < 24$，可以把这个 $k$ 放进去，但是没必要），最后格也就变成这样：

$$\begin{bmatrix}m_1 & m_2 & \ldots & m_{24} & 1\end{bmatrix}\begin{bmatrix}1 & 0 & \ldots & 0 & 0 & 1 & c_1 \\ 0 & 1 & \ldots & 0 & 0 & 1 & c_1 \\ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\ 0 & 0 & \ldots & 1 & 0 & 1 & c_{24} \\ 0 & 0 & \ldots & 0 & 1 & t-24 & -C'\end{bmatrix} = \begin{bmatrix}m_1 & m_2 & \ldots & m_{24} & 1 & 0 & 0\end{bmatrix}$$

求解代码：

from Crypto.Util.number import *
from tqdm import trange

with open('output_updated.txt') as f:
    exec(f.read())

n = 24
q = 223^24 - 1
msg_ = b''
for C in enc:
    C_ = C
    for t in trange(1, n):
        C_ -= pubkey[-t]
        for C__ in range(C_, C_ + n * q, q):
            L = [[0 for j in range(n+3)] for i in range(n+1)]
            for i in range(n):
                L[i][i] = 1
                L[i][n+1] = 1
                L[i][n+2] = pubkey[i]
            L[n][n] = 1
            L[n][n+1] = t - 24
            L[n][n+2] = -C__
            L = matrix(ZZ, L)
            for vline in L.LLL():
                if vline[n] < 0:
                    vline = -vline
                if vline[n] == 1:
                    if all(x in {0, 1} for x in vline[:n]):
                        print('AOLIGEI!!!')
                        msg = ''.join(map(str, vline[:n].list()))
                        msg = long_to_bytes(int(msg, 2))
                        print(msg)
                        msg_ += msg
                        break
            else:
                continue
            break
        else:
            continue
        break
    else:
        raise Exception(f'GG {C = }')

print(msg_)

'''
real    5m21.739s
user    5m10.547s
sys     0m10.987s
'''

其实把 $q$ 放进格还是有必要的，实测可以快很多：

from Crypto.Util.number import *
from tqdm import trange

with open('output_updated.txt') as f:
    exec(f.read())

n = 24
q = 223^24 - 1
msg_ = b''
for C in enc:
    C_ = C
    for t in trange(1, n):
        C_ -= pubkey[-t]
        L = [[0 for j in range(n+3)] for i in range(n+2)]
        for i in range(n):
            L[i][i] = 1
            L[i][n+1] = 1
            L[i][n+2] = pubkey[i]
        L[n][n] = 1
        L[n][n+1] = t - 24
        L[n][n+2] = -C_
        L[n+1][n+2] = q
        L = matrix(ZZ, L)
        for vline in L.LLL():
            if vline[n] < 0:
                vline = -vline
            if vline[n] == 1:
                if all(x in {0, 1} for x in vline[:n]):
                    print('AOLIGEI!!!')
                    msg = ''.join(map(str, vline[:n].list()))
                    msg = long_to_bytes(int(msg, 2))
                    print(msg)
                    msg_ += msg
                    break
        else:
            continue
        break
    else:
        raise Exception(f'GG {C = }')

print(msg_)

'''
real    0m19.861s
user    0m18.883s
sys     0m0.809s
'''

解得

CCTF{9j_h0W_dO_yUo_5oLvE_tH!s_m1X3D_5eMi_H4rD_T4Sk!!!?

然后石卡库就尬在这里不会做了，因为结尾不是 }，当时我就破罐子破摔，在结尾再加一个 }，结果一交就过了，WTF？？？

所以 flag 就是

CCTF{9j_h0W_dO_yUo_5oLvE_tH!s_m1X3D_5eMi_H4rD_T4Sk!!!?}

---

赛后复盘

检查一下：

>>> f"{ord('}'):08b}"
'01111101'
>>> f"{ord('?'):08b}"
'00111111'

然后再检查一下这两个位置对应的 pubkey 是不是同余

with open('output_updated.txt') as f:
    exec(f.read())

n = 24
q = 223^24 - 1

print((pubkey[17] - pubkey[22]) % q)

结果输出的不是 0。这放 flag 的在搞飞机呢？

---

老子他妈的不懂什么是格！！老子他妈的只知道暴力！！！

事实上，这题暴力也可以解。

因为 $n=24$，也就是明文矩阵 $\mathbf{M}$ 的一行只有 24bit 的信息，也就是 3byte 的信息，所以可以枚举 3byte 的可打印字符，然后构建一个对应前 24bit 部分和到 3byte 消息的映射。

最后直接尝试将密文减去末尾（补 1 的那一部分的）部分和，并拿着这个值到映射里面反查出消息的内容即可。

代码如下：

from Crypto.Util.number import *
from tqdm import tqdm
import itertools
import string

with open('output_updated.txt') as f:
    exec(f.read())

n = 24
q = 223^24 - 1
msg_ = b''

# Partial sum
last_partial_sum = [0]
for i in range(1, n):
    last_partial_sum.append(last_partial_sum[-1] + pubkey[-i])
sum2msg = {}
for mi in tqdm(itertools.product(string.printable, repeat=n // 8)):
    mi = ''.join(mi)
    mi_ = bytes_to_long(mi.encode())
    a = [int(x, 2) for x in f'{mi_:0{n}b}']
    c1 = sum(ai * pi for ai, pi in zip(a, pubkey)) % q
    sum2msg[c1] = mi

msg_ = ''
for C in enc:
    for t in range(n // 8, n):
        C_ = (C - last_partial_sum[t]) % q
        if C_ in sum2msg:
            msg_ += sum2msg[C_]
            break
    else:
        raise Exception(f"GG {C = }")

print(msg_)

其实这个暴力的速度还蛮快，而且比较无脑，爽。