ACTF2026 • Misay's blog

🫡官方repo wp https://github.com/team-s2/ACTF-2026 ↗

inverse_pow#

I’m tired of watching people insta-gib the proof-of-work with their 128-core machines. So why not inverse it?

赛题提供了一个go写的ELF 逆向后是一个PoW 协议基本如下

生成一个 1 到 99999999 之间的随机数 $m$ 要求计算一个 $n$ 满足在60秒内计算 $2^n$ 要求 $2^n$ 的高len(m)位恰好是 $m$ 即

str(2**n)[:len(str(m))] == str(m)

题目情景可以理解为找 $n$ 满足

m \cdot 10^t \le 2^n < (m+1) \cdot 10^t

其中 $t$ 是根据数量级来确定的整数取对数

\log_{10} m + t \le n\log_{10}2 < \log_{10}(m+1) + t

我们不难理解

对于一个整数如果把它写成科学计数法的形式

m=c\times 10^{k-1}

它的 $c$ 部分的”小数”会决定它的前缀

对于LHS/RHS的大数我们全部集中于它的小数部分设十进制总长度为 $k$ 那么可以把问题全部限制在 $[\;0,1\;)$ 的区间小数

\frac{m}{10^{k-1}} \le \{2^n\}< \frac{m+1}{10^{k-1}}

回代取对数

\log_{10}\left(\frac{m}{10^{k-1}}\right) \le \log_{10}(c) < \log_{10}\left(\frac{m+1}{10^{k-1}}\right)

记为

L\le \{n\theta\}\lt U

其中 $\theta=\log_{10}2$ 作为每轮的步长

为什么要转化到小数？

就前缀而言我们其实不是很关注其他无关的后续尾部位数化为小数的视角理解可以认为是存在 1后的”截断”

可以认为 $n$ 作为轮转步数而 $\theta$ 作为无理数 $n$ 的增加会导致 $n\theta$ 不重复的分布在 $[0,1)$ 之内我们简记

\{n\theta\}=x\theta-y

$x$ 就是要找的值 $y$ 表示多”转”了多少圈

从 $y=0$ 开始先讨论是否存在整数 $x$

\frac{L}{\theta} \le x < \frac{U}{\theta}

如果存在直接返回 $x$

否则需要找到 $x$ 满足

\frac{y + L}{\theta} \le x < \frac{y + U}{\theta}

求 $x$ 和求 $y$ 没有本质区别以 $y$ 为主元

x\theta - U < y \le x\theta - L

注意我们前面的操作手法都是 只讨论必要的小数给无关的整数截断

两侧除去 $\theta$ 给共同的整数 $x$ 截断即化归为等价问题

x - \frac{U}{\theta} < \frac{y}{\theta} \le x - \frac{L}{\theta}

截断掉 $x$ 只需分析

L' \le \left\{y \cdot \left\{\frac{1}{\theta}\right\}\right\} < U'

后续按照一样的思路定义新的 $x_0$ $y_0$ 来递归求解即可

Pandora#

These mathematical structures are noisy and chaotic enough, so hiding my numbers here must be safe, right?

FLAG = b"actf{redacted}"
while (p:=random_prime(2**512))%4 != 3:
    continue
q = random_prime(2**512)
K = QuadraticField(-p, 'w')
R = RealField(2333)
ΔΚ, Δq = -p, -p*q**2
OK = K.maximal_order()
Oq = K.order([1, (Δq+q*K.gen())/2])

token = os.urandom(45)
α = OK.ideal(int(token[:30].hex(),16)+\
             int(token[30:].hex(),16)*K.gen())

a, b, c = list(α.quadratic_form())
A, B = a, b*q%(2*a)
if B >= a: B -= 2*a
h = Oq.ideal([A, (-B + q*K.gen())/2]).quadratic_form()
ζ = list(h.reduced_form())[:2]; ζ[0] >>= 360
λ = f"{R(-Δq).sqrt():.470f}".split('.')[1]

if bytes.fromhex(input(f"{ζ, λ}\n[token]: ")) == token:
    print("^_^ >🚩", FLAG)

python

先看给了什么

ζ = list(h.reduced_form())[:2]; ζ[0] >>= 360

$\zeta$ 涉及 $h$ 而 $h$ 由下列代码定义

h = Oq.ideal([A, (-B + q*K.gen())/2]).quadratic_form()

python

我们需要分析三个变量 A B K

A由a决定而
$a = x^2 + py^2$
B的定义为
$B \equiv bq \pmod{2a}$
K.gen() 由前文对K的定义严格为
$K = \mathbb{Q}(\sqrt{-p})$

随后在定义的Oq环上由A B 定义一个二次型并且约化后告诉你系数 $a_r$ 的高位和完整的 $b_r$

λ = f"{R(-Δq).sqrt():.470f}".split('.')[1]

python

相当于提供

\lambda=q\sqrt{p}

的高精度小数位数

因为它的高位被精准的截断了我们可以写 $\sqrt{D} = T + \lambda$ 等式两边平方

D = (T + \lambda)^2 = T^2 + 2T\lambda + \lambda^2

D-T^2=2T\lambda+\lambda^2

也就是 $2T\lambda + \lambda^2 \approx \text{某个整数}$

这是个高精度的Integral Diophantine approximation ↗

令 $Q = 10^{470}$ 把小数转化为整数方便做格

$D = \left(T + \frac{L}{Q}\right)^2 = T^2 + \frac{2TL}{Q} + \frac{L^2}{Q^2}$

即

$D \cdot Q^2 = T^2 Q^2 + 2TLQ + L^2$

所以说 $2TLQ + L^2$ 必须得是 $Q^2$ 的整数倍也就是一定存在线性关系

$n \cdot Q^2 + T \cdot (2LQ) + 1 \cdot L^2 = 0$

做

$B = \begin{pmatrix} Q^2 & 0 & 0 \\ 2LQ & Q & 0 \\ L^2 & 0 & Q \cdot X \end{pmatrix}$

有

$\begin{pmatrix}n,T,1\end{pmatrix} \cdot B = \Big( nQ^2 + 2TLQ + L^2, \quad T \cdot Q, \quad QX \Big)$

$X$ 取很大的量来固定目标向量第三位只能取1 提取第一位接近0的向量即可恢复 $T$ 从而恢复 $D$

解出 $D$ 之后拷打LLM 给出了如下性质

在类群密码学中，任何一个二元二次型 $h = [a, b, c]$ 必须满足其判别式恒等于系统参数 $\Delta_q$

这里 $\zeta$ 给出的虽然是约化后的二次型但是仍然满足 $b_r^2 - 4a_r c_r = -D$ 把已知的都移到一边我们有 $a_r c_r = \frac{b_r^2 + D}{4} = K$ 这里给我们 $a_r$ 的高位可以写 $a_r = A_h \cdot 2^{360} + u$ 问题转化为经典的已知因子的高位要进行分解

赛中尝试了朴素的small_roots会直接OOM 于是进行了如下优化

$a \le \lfloor\sqrt{K}\rfloor$
$A_{base} = A_{high} \cdot 2^{360} + \text{center}$ 把上界从 $2^{360}$ 压到 $2^{359}$

然后根据论文中的Howgrave-Graham ↗ 的构造搓了一个 $49\times49$ 格来恢复 $a_r$ 再恢复 $c_r$

恢复 $[a_r,b_r,c_r]$ 后目标是恢复高斯约化前的 $[a,b,c]$ 但是赛中发现 $a = x^2 + py^2 \approx 2^{512} \cdot (2^{120})^2 = 2^{752}$

$D = pq^2 \approx 2^{512} \cdot (2^{512})^2 = 2^{1536}$ $C \approx \frac{D}{4a} \approx \frac{2^{1536}}{2^{754}} \approx 2^{782}$

而 if B >= a: B -= 2*a 已经保证了 $|B| \le a \le C$ 也就是说这里的 reduced_form() 实际上没有对系数进行处理

现在梳理一下我们已知 $D=pq^2$ $a = x^2 + py^2$ $B\equiv bq\mod 2a$ 需要解 $x\;y$

接着拷打LLM得到了在当前整环 $\mathcal{O}_K$ 下的代数结构

二次型判别式的关系满足
$b^2\equiv -p \mod a$
同乘
$b^2y^2\equiv -py^2 \equiv x^2-a\equiv x^2\mod a$
故而
$(by-x)(by+x)\equiv 0 \mod a$
取
$by+x=ma\tag{0}$

而由于 $B\equiv bq\mod 2a$ 故而 $B = bq - 2an\tag{1}$

因为我们是已知 $B$ 的关于 $b$ 的系数只差一个 $q$ 来对齐我们构造

qby+qx=qma

y(B+2na)+qx=qma\rightarrow yB+qx=(2ny-qm)a=ka

这一步最大的帮助就是帮我们给 $a$ $B$ 之间建立了从模转化到线性的代数关系

回看二次型 $h$ 有

h(X,Y)=aX^2+BXY+CY^2

而我们一定有 $B^2-4aC=-D$ 给 $C$ 消掉即 $C = \frac{B^2+D}{4a}$

代回去

h=\frac{4a^2X^2+4aBXY+B^2Y^2+DY^2}{4a}

而我们又有 $yB+qx=ka\tag{2}$ 平方一下 $k^2a^2=y^2B^2+2xyqB+q^2x^2$

这个二次型其实是存在这样的构造的我们先令 $X=k$ 看看会怎么样

h(k,Y_0)=\frac{4a^2k^2+4akBY_0+B^2Y_0^2+DY_0^2}{4a}

后两项关注 $B_0^2Y_0^2$ 这个4也不难配平取 $Y_0=-2y$

h(k,-2y)= \frac{4a^2k^2-8axykB+4B^2y^2+4Dy^2}{4a}=\frac{(ak-By)^2+Dy^2}{a}

3式让我们可以消去 $ak-By=qx$ 而 $D=pq^2$ 所以说

h(k,-2y)=\frac{q^2x^2+pq^2y^2}{a}=\frac{q^2(x^2+py^2)}{a}=q^2

在我们已知二次多项式关系 $h(k,-2y)=q^2$ 后由于我们还知道 $q^2$ 的倍数 $D$ 在shift中加入 $D$ 即按照 $g(X,Y) = h(X,Y)^i \cdot D^{m-i}$ 的shift思路造格可以成功规约出满足 $h_0(k,-2y)=0$ 的系数多项式它长这样 $h_0(X,Y) = c_0 Y^{12} + c_1 X Y^{11} + c_2 X^2 Y^{10} + \dots + c_{12} X^{12} = 0$ 变形成 $c_0 + c_1 \left(\frac{X}{Y}\right) + c_2 \left(\frac{X}{Y}\right)^2 + \dots + c_{12} \left(\frac{X}{Y}\right)^{12} = 0$ 解出有理根 $\frac{k}{-2y}$ 展开成分数解出 $y\;k$ 可以算 $qx=yB-ka$ 然后gcd解 $q$ 算 $x$

ArrAnge in Asceding#

From Bubble Sort to Quick Sort, the pursuit of order has always defined humanity.

chal

import tenseal.sealapi as sealapi
import tenseal as ts, random, base64 as b64
FLAG = "actf{redacted}"

ctx = ts.context_from(open("ctx.secret", "rb").read())
ctxdata = ctx.seal_context().data
Base = random.sample(range(512),128)
Chaos = ts.ckks_vector(ctx, Base)

print(b64.b64encode(Chaos.serialize()).decode())
open("ct.bin", 'wb').write(b64.b64decode(input("😶‍🌫️ :")))
(Crystal:=sealapi.Ciphertext()).load(ctxdata, "ct.bin")

decryptor = sealapi.Decryptor(ctxdata, ctx.secret_key().data)
decryptor.decrypt(Crystal, answer:=sealapi.Plaintext())

encoder = sealapi.CKKSEncoder(ctxdata)
answer = list(encoder.decode_double(answer))[:128]
if all(round(i) == sorted(Base).index(j) for i,j in zip(answer, Base)):
    print("^_^ >🚩", FLAG)

python

setup

import tenseal as ts

ctx = ts.context(
    ts.SCHEME_TYPE.CKKS,
    32768,
    coeff_mod_bit_sizes=[50]+[40]*12+[50]
)
ctx.global_scale = 2**40

secret_bytes = ctx.serialize(save_secret_key=True)
public_bytes = ctx.serialize(save_secret_key=False)
open("ctx.secret", "wb").write(secret_bytes)
open("ctx.public", "wb").write(public_bytes)

ctx.generate_galois_keys()
ctx.galois_keys().data.save("galois.key")

python

https://arxiv.org/pdf/2412.15126 ↗

远端生成 $Base = [x_0,x_1,\dots,x_{127}]$ 并给出CKKS加密后的密文要求得到这128个项的大小索引加密后重新发回去得到flag 附件给了CKKS的公钥和Galois旋转密钥

CKKS属于FHE的一种能够支持不解密的情况下对于密文进行计算等价于直接计算明文

所以初步策略是直接对于密文进行计算让明文解密后的结果直截等于需要的rank数组

这里引入一个指示函数 $I(x_i, x_j) = \frac{\operatorname{sgn}(x_i - x_j) + 1}{2}$

有 $Rank[a]=\sum I(x_a,x_i)$

但是CKKS只支持加法乘法关于 sgn这种跃迁函数需要用多项式方法进行拟合拷打LLM后给出了一个能够使用的思路

参考 https://ieeexplore.ieee.org/document/9517029 ↗ 先用chebshev进行拟合再在7~8层加入minimax函数

进行复合多项式的拟合把符号函数的结果拓展到1与-1

这一步能解决排序精度问题但是开销非常大相当于每次比较都需要shift 127次远端会断连

再参考 https://eprint.iacr.org/2025/198 ↗ 利用已有的galois密钥给base向量拓展到行列矩阵

直观上我们简写一下这两个矩阵长什么样

$VR=\begin{pmatrix}x_0&x_1&\cdots&x_{127}\\x_0&x_1&\cdots&x_{127}\\\vdots &\vdots&&\vdots\\x_0&x_1&\cdots&x_{127}\\\end{pmatrix}$

$VC=\begin{pmatrix}x_0&x_0&\cdots&x_{0}\\x_1&x_1&\cdots&x_{1}\\\vdots &\vdots&&\vdots\\x_{127}&x_{127}&\cdots&x_{127}\\\end{pmatrix}$

做差复杂度是O(1)

$D=\begin{pmatrix}0&x_1-x_0&\cdots&x_{127}-x_0\\x_0-x_1&0&\cdots&x_{127}-x_1\\\vdots&\vdots&&\vdots\\x_0-x_{127}&x_1-x_{127}&\cdots&0\end{pmatrix}$

然后调用多项式工具拟合符号函数再直接进行计算即可

*OhMyCaptcha#

I’ve designed a group verification mechanism, let’s try.

task

from Crypto.Util.number import *
from Crypto.Cipher import AES
import random, subprocess, os, signal, re
from secret import FLAG

assert re.fullmatch(rb'ACTF\{.{41}\}', FLAG)
valid_mobile = lambda num: [s:=str(num), len(s) == 11 and s[0] == '1'][1] and isPrime(num)
prod = lambda x: 1 if not x else x[0]*prod(x[1:])

class SandboxService:
    def __init__(self, p, q):
        self.n = p * q
        self.e = 5
    
    def encrypt(self, msg):
        return pow(bytes_to_long(msg), self.e, self.n)
    
    def run(self, template):
        output = subprocess.run(
            ['python3', '-c', template],
            stdin=subprocess.DEVNULL, stdout=subprocess.PIPE, stderr=subprocess.STDOUT, timeout=1,
        ).stdout
        return long_to_bytes(self.encrypt(output.strip()))

class OhMyCaptcha:
    def __init__(self):
        self.code = ''.join(random.sample("0123456789", 10))
        self.pn = None

    def verify(self, message):
        return 0 <= message < prod(self.pn) and all(str(message % p) in self.code for p in self.pn)

    def start(self):
        print("Are you human? ")
        self.pn = list(set(map(int, input("Enter phone numbers to get a group verification code: ").split())))
        assert all(valid_mobile(p) for p in self.pn) and 0 < len(self.pn) < 66
        print(f"[Azure Assassin Alliance] {self.code} is your group verification code, valid for 1 minute.")
        signal.alarm(60)

    def serve(self):
        sandbox = SandboxService(getPrime(0x137), getPrime(0x137))
        print("n =", sandbox.n)
        key, nonce = [os.urandom(8).hex() for _ in ":)"]
        cipher = AES.new(key.encode(), AES.MODE_CTR, nonce=bytes.fromhex(nonce)).encrypt(FLAG).hex()
        for _ in "AAA🤩":
            message = int(input('> '))
            template = f"key = {key!r}\ncipher_with_key_{key}_{nonce} = {cipher!r}\nprint(eval({long_to_bytes(message)}))"
            if self.verify(message):
                print(sandbox.run(template).hex())
            else:
                print("Verification failed.")

if __name__ == "__main__":
    OHC = OhMyCaptcha()
    OHC.start()
    OHC.serve()

python

先提一下预期解

SandBoxService提供了一个沙箱来运行template的模板而其中的 eval运行执行 message 再把沙箱的输出进行RSA加密这里的指数比较小

sandbox的构造#

template中的eval允许读已有的信息可以构造message分别为 key dir()[-2][-16:] 给AES的key 与nonce 读出来这里二者大概是128字节而5次幂下截断大概在124字节稍微爆破一下模数的倍数就可以给二者成功恢复

此时还剩两次机会

随后传eval(dir()[-2]) 可以得到 cipher RSA加密的结果不难想到有相关明文攻击的机会即 Franklin-Riether-Attack 那么接下来只需要构造一个payload 能够让沙箱输出 f(cipher)的值即可先 dir()[-2] 获取cipher的变量名再 globals()[dir()[-2]] 得到取值最后字符串拼接一下 globals()[dir()[-2]] + 'a'

=== OhMyCaptcha 极短 Payload 测试沙箱 ===
[环境信息] 模拟 Key: c8c4ea2ecdc7a718
[环境信息] 模拟 Nonce: 21df4e7d0ed43209
[环境信息] 模拟 Cipher: 728f425d770f597c836f1529739d5e766c073de999c71f683b8a0aa4e1629aeb5090a0fcdebbc8af2f6d55a0595b62
输入你的 payload 字符串 (例如: key, dir(), globals())，输入 exit 退出。

Payload > dir()[-2][16:32]
--------------------------------------------------
[*] 正在执行 Payload: dir()[-2][16:32]
[*] Payload 长度: 16 bytes

[+] 原始沙箱输出 (Raw): b'c8c4ea2ecdc7a718'
[+] 字符串解码 (Decoded): c8c4ea2ecdc7a718

[*] 最终输出长度: 16 bytes
[~] 长度适中 (16-18 bytes)：会发生轻微模回绕，可利用 k-Brute Force (爆破 k) 恢复。
--------------------------------------------------
Payload > dir()[-2][-16:]
--------------------------------------------------
[*] 正在执行 Payload: dir()[-2][-16:]
[*] Payload 长度: 15 bytes

[+] 原始沙箱输出 (Raw): b'21df4e7d0ed43209'
[+] 字符串解码 (Decoded): 21df4e7d0ed43209

[*] 最终输出长度: 16 bytes
[~] 长度适中 (16-18 bytes)：会发生轻微模回绕，可利用 k-Brute Force (爆破 k) 恢复。
--------------------------------------------------
Payload > eval(dir()[-2])
--------------------------------------------------
[*] 正在执行 Payload: eval(dir()[-2])
[*] Payload 长度: 15 bytes

[+] 原始沙箱输出 (Raw): b'728f425d770f597c836f1529739d5e766c073de999c71f683b8a0aa4e1629aeb5090a0fcdebbc8af2f6d55a0595b62'
[+] 字符串解码 (Decoded): 728f425d770f597c836f1529739d5e766c073de999c71f683b8a0aa4e1629aeb5090a0fcdebbc8af2f6d55a0595b62

[*] 最终输出长度: 94 bytes
[!] 长度过长 (> 18 bytes)：需要使用 Coppersmith (small_roots) 截断分析，或考虑继续缩短输出！
--------------------------------------------------
Payload > globals()[dir()[-2]] + 'a'
--------------------------------------------------
[*] 正在执行 Payload: globals()[dir()[-2]] + 'a'
[*] Payload 长度: 26 bytes

[+] 原始沙箱输出 (Raw): b'728f425d770f597c836f1529739d5e766c073de999c71f683b8a0aa4e1629aeb5090a0fcdebbc8af2f6d55a0595b62a'
[+] 字符串解码 (Decoded): 728f425d770f597c836f1529739d5e766c073de999c71f683b8a0aa4e1629aeb5090a0fcdebbc8af2f6d55a0595b62a

[*] 最终输出长度: 95 bytes
[!] 长度过长 (> 18 bytes)：需要使用 Coppersmith (small_roots) 截断分析，或考虑继续缩短输出！
--------------------------------------------------
Payload > eval(dir()[-2])*2
--------------------------------------------------
[*] 正在执行 Payload: eval(dir()[-2])*2
[*] Payload 长度: 17 bytes

[+] 原始沙箱输出 (Raw): b'728f425d770f597c836f1529739d5e766c073de999c71f683b8a0aa4e1629aeb5090a0fcdebbc8af2f6d55a0595b62728f425d770f597c836f1529739d5e766c073de999c71f683b8a0aa4e1629aeb5090a0fcdebbc8af2f6d55a0595b62'
[+] 字符串解码 (Decoded): 728f425d770f597c836f1529739d5e766c073de999c71f683b8a0aa4e1629aeb5090a0fcdebbc8af2f6d55a0595b62728f425d770f597c836f1529739d5e766c073de999c71f683b8a0aa4e1629aeb5090a0fcdebbc8af2f6d55a0595b62

[*] 最终输出长度: 188 bytes
[!] 长度过长 (> 18 bytes)：需要使用 Coppersmith (small_roots) 截断分析，或考虑继续缩短输出！
--------------------------------------------------
Payload >

bash

后续搜索的时候 key实在太短导致m太小换成了 dir()[-2][16:32]

最后使用的是

key — dir()[-2][16:32]
nonce — dir()[-2][-16:]
cipher — eval(dir()[-2])
f(cipher) — eval(dir()[-2])*2

pn的搜索构造#

上述payload在末尾增加 # 后再在末尾增加各种乱码也不会引起问题同时注意到虽然pn是公共的但是题目给了我们code 和时间我们完全可以

搜索找10~16组可用的 pn 这一步非常简单素数长度OK即可
得到code后再针对key nonce cipher f(cihper) 当场搜索suffix即可

这里就可以转化为一个背包格问题来求解

我们的message可以看成

m_i=known_i+\sum255^i\times char_i

只需满足

m_i \equiv \text{codeSubStr} \mod pn_i

这里应该是存在一个背包格的转化的毕竟suffix 转化回来只会影响低位但当前还没发现一个稳定的规约成功suffix的思路如果想要赛中优化可以参照

字串从 $0\quad1\quad\cdots\quad9$ 拓展到2位比如 $12\quad34\quad\cdots\quad89$ 这样空间会更足

后续对着官方wp分析还是发现比较大的思路差距了

这里我们搜索的实际上是后缀的字节本质还是几十的相对大数字，而赛题的关键是

x\equiv r_i\mod p_i

其中 $r_i$ 是10以内的小量这也就意味着

如果我们能先确定 $p_i$ 再把这个细微的偏移给求出来那也一样的可以恢复我们的 $x$

所有放在模数上的问题我们都不太喜欢但是如果先确定 $p$ 那就转化为了去规约一个 $0\sim9$ 的量我们还可以中心化令

u_i=r_i-5\in\{-5\sim4\}

规约这里的 $u_i$ 并不难

再说回命令本身当我们先确定了 $n=64$ 组 $p_i$ 后格的规模和维度基本就被固定在64附近此时前缀相对而言长度没有那么敏感，规约效率也高了很多，同时当payload的长度上升反而能给我们的 $x$ 提供更大的宽度容错区间

处理数据与格#

构造四次message 前两次拿下 key nonce 后续拿下 cipher f(cipher)

前2者是16字节稍微爆破即可完全恢复而cipher是94字节再知道 RSA加密结果后相当于

m^5\equiv c_1\mod n

(2m)^5\equiv c_2\mod n

我们很容易计算出来 $m\mod n$ 接下来就需要分析因为AES加密的结果实际上是全部为hex的字串考虑继续使用背包格求解可以针对 a-z0-9 来进行稍微的移位和缩放规约到待求小量均是 $[-4,4]$ 的格中但是这个格的复杂度还是相当大的目前没有调出来如果想参考类似的求法可以看看 AliyunCTF2026-Griffin-Rec师傅的手法 ↗ 这道题是uuid格但是对于hex的处理还是值得参照的

个人的相关经验和积累还是太少了… 面对这道题赛中折腾了很长一段时间的eval短命令读取…

嗯感谢wuy4n师傅提供的相关脚本这里贴一个格的构造

def solve(p, c, k=60):
    table = string.hexdigits.lower()
    proj = {"0" : (0, -4), "1" : (0, -3), "2" : (0, -2), "3" : (0, -1),
        "4" : (0, 0), "5" : (0, 1),  "6" : (0, 2),  "7" : (0, 3),
        "8" : (0, 4),  "9" : (0, 5),  "a" : (1, -3),  "b" : (1, -2),
        "c" : (1, -1),  "d" : (1, 0),  "e" : (1, 1),   "f" : (1, 2)}

    a, b = 48, 52
    for key in proj.keys():
        x, y = proj[key]
        assert a * x + y + b == ord(key)

    P = PolynomialRing(Zmod(p), [f"x{i}" for i in range(k * 2)])
    vars = P.gens()
    xs = vars[:k]
    ys = vars[k:]

    f = sum([(a * xs[i] + ys[i] + b) * 256**(k - 1 - i) for i in range(k)]) - c
    coeffs = f.coefficients()

    C1 = 4
    C2 = 2**32
    M = matrix(ZZ, k * 2 + 2, k * 2 + 2)
    for i in range(k):
        M[i, i] = C1
        M[i + k, i + k] = 1

    M[2 * k, 2 * k] = C1

    for i in range(k * 2 + 1):
        M[i, -1] = int(coeffs[i]) * C2

    M[-1, -1] = p * C2

    M = M.LLL()
    t1 = time.time()
    M = blaster(M, block_size=63, bkz_tour=10)
    t2 = time.time()
    print("time: ", t2 - t1)
    for row in M:
        if check(row):
            print("Found row:", row)
            for i in row:
                if i<0:
                    row = -row
                    break
                elif i>0:
                    break
            plain = ""
            for i in range(k):
                plain += chr(a * row[i] // C1 + row[i + k] + b)
            print("Plaintext:", plain)
            return plain
    return None

这里预期使用的是256来进行balance

f = sum([(a * xs[i] + ys[i] + b) * 256**(k - 1 - i) for i in range(k)]) - c

结合仿射对如下式子做背包格

C=\sum_{i=0}^{k-1}(52+48x_i+y_i)\,256^{k-1-i}

亦可尝试改为 $16$ 来进行balance 取得相对更加可控的格规模

对于hex的字符令

\operatorname{ord}(s_j) = 16H_j + L_j

$s_i$ 若是数字： $H_j=3,\quad L_j\in{0,\dots,9}$
$s_i$ 若是字母： $H_j=6,\quad L_j\in{1,\dots,6}$

可以转化为

\operatorname{ord}(s_j) =16\cdot 3\frac{u_j+12}{8} + (4+v_j)

\operatorname{ord}(s_j)=6u_j + v_j + 76

其中

u_j \in \{-4,4\}

对应的

L_j = 4 + v_j\quad v_j \approx [-4,5]

背包格相对应转化为

C=\sum_{i=0}^{k-1}(12+3u_i)\,16^{2k-1-2i} + \sum_{i=0}^{k-1}(4+v_i)\,16^{2k-2-2i}

demo

  def solve(p, c, k=60):
      n, dim = p, 2 * k
      w = 2**32
      powers_hi = [2 * k - 1 - 2 * i for i in range(k)]
      powers_lo = [2 * k - 2 - 2 * i for i in range(k)]

      const = sum(12 * 16**powers_hi[i] + 4 * 16**powers_lo[i] for i in range(k))
      c0 = (ZZ(c) - ZZ(const)) % ZZ(n)

      M = matrix(ZZ, dim + 2, dim + 2)

      for i in range(dim):
          M[i, i] = 8 if i % 2 == 0 else 1

      M[dim, :] = matrix(1, dim + 2, [-12, -4] * k + [4] + [-(c0 * inverse_mod(3, n) % n) * w])

      coeff_col = []
      inv3 = inverse_mod(3, n)
      for i in range(k):
          coeff_col.append((16**powers_hi[i]) * w % n)          # u_i 对应 high nibble
          coeff_col.append((16**powers_lo[i] * inv3) * w % n)   # v_i 对应 low nibble
      M[:dim, dim + 1] = matrix(dim, 1, [ZZ(x) for x in coeff_col])

      M[dim + 1, dim + 1] = n * w
      
      t1 = time.time()
      M = M.BKZ(block_size = 30)
#     M = blaster(M, block_size=63, bkz_tour=10)
      t2 = time.time()
      print("time:", t2 - t1)

      def decode_row(row):
          msg = []
          for idx in range(0, 2 * k, 2):
              u = ZZ(row[idx])
              v = ZZ(row[idx + 1])

              if u not in (-4, 4):
                  return None

              H = 3 * ((u + 12) // 8)   # 3 or 6
              L = v + 4

              if H not in (3, 6):
                  return None
              if not (0 <= L <= 15):
                  return None

              ch = (H << 4) + L
              if not (0 <= ch <= 255):
                  return None
              msg.append(chr(int(ch)))

          s = "".join(msg)
          if all(ch in "0123456789abcdef" for ch in s):
              return s
          return None

      cands = []
      for row in M:
          s = decode_row(row)
          if s is not None:
              print("Found candidate:", s)
              cands.append(s)

      return cands

再简要说一下非预期可以直接通过

help('secret')

bash

来读取FLAG 虽然flag的长度相当大但是可以多次重连获得多组 $n$ 结合已有的 $FLAG^5\mod n_i$ 合并起来打CRT直接恢复 FLAG 😶‍🌫️