ACTF-2026

2026-05-24/更新于 2026-07-15

OhMyCaptcha

源码及解读

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 水平需要锻炼一下了。

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:])

首先规定 flag 长度：assert re.fullmatch(rb"ACTF\{.{41}\}", FLAG)，加上前后缀之后整体是 47 字节，376bits。结合后文的 CTR 加密，密文长度 cipher 同样是 47 字节。

接着是 lambda 定义的 valid_mobile 函数，这个写法是真难懂。对于传入的变量 num，要求 str(num) 长度为 11 且以 1 开头，且 num 是质数。为什么使用海象运算符 :=？因为 lambda 函数内不允许直接赋值。s := str(num) 把 str(num) 提取了出来，[...][1] 取这个校验的的布尔变量，再结合后面的素数校验，最终返回一个布尔变量。对于 := 的使用，举个例子：

s = input("Input: ")
while s != "quit":
    print(f"Your input is {s}")
    s = input("Input: ")

这段代码实现的是校验输入，只要输入的不是 quit，就一直循环。使用 := 之后，可以写成：

1 2	`while (s := input("Input: ")) != "quit": print(f"Your input is {s}")`

海象运算符可以用于循环体内依然需要使用校验中变量的情况。

还有一句 lambda 实现的 prod，作用是列表内元素求总积。

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()))

SandboxService 类内置了 RSA 加密方法和命令执行方法。需要注意的是这里的 e = 5，属于小加密指数。run 方法对于传入的 template，把它拼接到 python3 -c 后面（即当作命令语句执行），报错和真正的输出一起进入 stdout。最终输出是被 RSA 加密后的回显转成的字节串。

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
        )

OhMyCaptcha 类的 code 是把 0-9 十个数字随机打乱后的结果。random.sample(seq, k) 的作用是从序列里 无重复 地随机抽取 k 个元素，返回列表。verify 方法要求传入的 message 满足两个条件：

$0 \leq m e s s a g e < \prod p_{i}$
对于每个 pi，message % pi 的值转成字符串必须是 code 的子串。前面说过 code 是由 0-9 随机打乱得到的，而长度大于 1 的子串又不可预测，故这个条件几乎等价于 $m e s s s a g e mod p_{i} \in {0, 1, \dots, 9}$

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)

调用了之前的 valid_mobile 函数对每一个传入的手机号进行校验，且限制传入的数量必须在 1 到 65 之间。

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.")

载入沙箱，生成两个 311 位的素数进行 RSA，接着随机生成了 8 字节的 key, nonce，并初始化了 CTR 实例 cipher 用于对 FLAG 加密。for _ in "AAA🤩" 相当于重复四次，执行：

接收输入的 message，并将其转为整数。
如果 int(message) 通过了 verify 的校验，就先把变量 key 和 cipher_with_key_{key}_{nonce} 两个变量赋值为真实的 key 和 cipher，最后把 message 转字节串后用 eval 执行，回显用 RSA 加密后返回。

回显作为 RSA 明文 m，其对应的密文满足 $c = m^{5} (\mod n)$ 。n 的长度是 622bits，m 的长度需要低于 622/5 = 124bits，也即 15 字节，才能够通过 c 直接开五次根来获得回显内容，这严格限制了 message 的构造。

分析_part1

对于输入的每一个手机号，它们的位数范围都固定在 33-34bits，大小差异是几乎可以忽略不计的，重点还是提交手机号的数目。我们把这个问题放一放，先决定如何构造 message。

message 需要满足两个条件，分别是数学上的和代码上的。回顾一下：

message 的长度不能超过手机号的乘积，且模以手机号得到的结果在 0-9 之间。
经过 long_to_bytes() 转换后的 message 需要有意义，能被 eval() 执行，且能把解密需要的变量通过 print() 带出来。

源码中的 print(eval({long_to_bytes(message)})) 使得我们可以只传入变量名，print() 语句会包裹我们传入的内容。解密需要 key, nonce, cipher，缺一不可。由于 key 被直白地赋值了，所以我们可以先从它入手。根据代码条件，我们构造 message = key。

为了满足数学条件，message 不可避免地会和原始 command 有出入。假如垃圾字节出现在末尾，我们可以在原始 command 之后添加注释符，即 key#，使得末尾的垃圾字节被注释掉，从而被 eval() 函数忽略，最终同时满足数学条件和代码条件。由此，其它三条 Payload 可以写成 [*vars()][8]#、vars()#、vars()[[*vars()][8]]#（或者根据非预期解，直接传 [*open('secret.py')]#）。因此，message 的大致结构就是 $m_{h i g h} + m_{l o w}$ ，且 $m_{h i g h}$ 的低位补 0。把余数 0-9 记为 $a_{i}$ ，手机号记为 $p_{i}$ ，手机号数目记为 $n$ ，约束方程满足下面的形式：

\begin{matrix} m_{h i g h} + m_{l o w} \equiv a_{1} (\mod p_{1}) \\ m_{h i g h} + m_{l o w} \equiv a_{2} (\mod p_{2}) \\ ⋮ \\ m_{h i g h} + m_{l o w} \equiv a_{n} (\mod p_{n}) \end{matrix}

其中 $m_{h i g h}$ 已知， $p_{i}$ 由于大小差异可以忽略不计，可以批量生成，所以也已知。这里有一个陷阱。由于 $a_{i} \in {0, 1, \dots, 9}$ ，我们可能会想：为什么不直接固定 $a_{i} = 1$ ，直接用标准 CRT 求 message？

根据数学条件 $m e s s a g e < \prod p_{i}$ 和 crt() 函数本身，无论是实际得到的解还是 verify() 校验的要求，message 都小于 p 的总积。因此，若要在这种情况下求解 $m e s s a g e \equiv 1 (\mod p_{i})$ ，原本的通解 $1 + k \cdot \prod p_{i}$ 中的 $k$ 只能取 0，得到 $m e s s a g e = 1$ ，显然是错的，所以 $(a_{1}, a_{2}, \dots, a_{n})$ 可以看作未知。

事到如今，这个模方程组虽然和普通的同余方程组形式相近，但 CRT 已经不能解决这类问题。因此，我们只能回归 CRT 底层的实现原理。之前写过，如果设 $M = \prod p_{i}, M_{i} = \frac{M}{p_{i}}, N_{i}$ 是 $M_{i}$ 在模 $p_{i}$ 下的逆元（即 $M_{i} N_{i} \equiv 1 (\mod p_{i})$ ）。根据 CRT，message 可以写成：

m e s s a g e = (\sum_{i = 1}^{n} a_{i} M_{i} N_{i}) mod M

化成普通方程：

m e s s a g e = \sum_{i = 1}^{n} a_{i} M_{i} N_{i} - K \cdot M

其中 $K$ 为整数商，保证 $0 \leq m e s s a g e < M$ 。代入 $m e s s a g e = m_{h i g h} + m_{l o w}$ 后移项：

m_{l o w} = \sum_{i = 1}^{n} a_{i} M_{i} N_{i} - 1 \cdot m_{h i g h} - K \cdot M

其中 $a_{i}, K, m_{l o w}$ 未知，且我们希望 $a_{i}, m_{l o w}$ 极小。对于这种情况，我们可以使用 LLL 进行格基约简，并希望得到的目标向量中包含 $(a_{1}, a_{2}, \dots, a_{n}, m_{l o w})$ 。

对于 $m_{h i g h}$ 前的系数 1，虽然它已知，但我们希望它维持原状，不参与整体的大小平衡，所以也把它加入目标向量。对于 $K$ ，虽然它未知，但是它的大小没有任何要求，且它是调节整体大小的杠杆，所以不能加入目标向量。至此，我们的目标向量定为 $R = (a_{1}, a_{2}, \dots, a_{n}, 1, m_{l o w})$ 。由于 $a_{i} \in {0, 1, \dots, 9}$ ，参考背包密码，我们希望 $a_{i}$ 提供的范数更小且尽量均匀，所以设 $b_{i} = a_{i} - 4$ ，得到 $b_{i} \in {- 4, - 3, \dots, 5}$ 。为了平衡前几项和 $m_{l o w}$ 的大小比例，我们还要加入权重 $C$ 用于调平，最终得到 $R = (b_{1} C, b_{2} C, \dots, b_{n} C, C, m_{l o w})$ 。

将 $a_{i}$ 变为 $b_{i}$ 后，等式变为：

m_{l o w} = b_{1} (M_{1} N_{1}) + \dots + b_{n} (M_{n} N_{n}) + [\sum_{i = 1}^{n} 4 (M_{i} N_{i}) - m_{h i g h}] + K \cdot M

记 $C_{n e w} = 4 \sum_{i = 1}^{n} (M_{i} N_{i}) - m_{h i g h}$ ，二者融合成了全新的常数项。我们依然希望常数项前的系数为 1，所以目标向量不用改动。根据新等式，初始向量需要加入 $b_{i}, K$ 两个未知系数项，外加一个用于控制 $C_{n e w}$ 的常量系数 $1$ ，即初始向量 $V = (b_{1}, b_{2}, \dots, b_{n}, 1, K)$ 。

至此，我们就可以构造格基矩阵了。对于 $m_{l o w}$ ，参照初始向量，格基矩阵的最右一列是 $(M_{1} N_{1}, M_{2} N_{2}, \dots, M_{n} N_{n}, C_{n e w}, M)^{T}$ 。依次构建，最终得到：

L = [\begin{matrix} C & 0 & \dots & 0 & 0 & M_{1} N_{1} \\ 0 & C & \dots & 0 & 0 & M_{2} N_{2} \\ ⋮ & ⋮ & ⋱ & 0 & 0 & ⋮ \\ 0 & 0 & 0 & C & 0 & M_{n} N_{n} \\ 0 & 0 & 0 & 0 & C & C_{new} \\ 0 & 0 & 0 & 0 & 0 & M \end{matrix}]

其中左上角是 $C \cdot I_{n + 1}$ 。作者的 exp 在 command 之后额外拼接了一个随机字符，又对常系数 1 加了一个扰动系数 scale。应该是技巧性的东西吧，一次跑不出就更新一下 random byte 和 scale，直到找到常系数那一列固定为 -scale * C，且 $a_{i}$ 在 $(0, 9)$ 内的 $m_{l o w}$ ，最终把四个 command 对应的低位全部跑出来。

回到一开始的问题：要传入多少个手机号？

先看 Payload 的长度，最长的 vars()[[*vars()][8]]# 在 20 字节左右。每个素数 36bits，如果用 5 个，它们的乘积大小有 22.5 字节，看起来可以。但是对于 $m_{l o w}$ ，对它的约简是几乎不可能的。来算一下概率：

假设传入 $n$ 个数字，message 的长度上界为 $2^{36 n}$ 。满足余数在 $[0, 9]$ 的数字组合有 $10^{n}$ 种。 $m_{h i g h}$ 的高位被确定了，大概占用了 $2^{160}$ bits。在所有 160 位的数字中，能正好以这 160bits 开头的概率是 $1 / 2^{160}$ 。因此在 $2^{36 n}$ 的空间内，大概有 $10^{n} \times (1 / 2^{160})$ 个解。整体解的数量是 $2^{3.32 n - 160}$ 个。当 $3.32 n - 160 < 0$ ，即 $n < 48$ 时，无论怎么约简都不可能得到解。既然要求这么苛刻，不如就直接传满得了。

至此，我们可以开始写第一部分的 EXP，目的是生成素数和寻找 $m_{l o w}$ 。

EXP_part1

from Crypto.Util.number import *
import random
import os

# 预备执行的命令，拼接在 message 高位
COMMANDS = [b"key", b"[*vars()][8]", b"vars()", b"vars()[[*vars()][8]]"]


# 生成 size 个符合要求的素数
def genPrimes(size):
    valid_mobile = lambda message: [s := str(message), len(s) == 11 and s[0] == "1"][1]
    ls = []
    for i in range(size):
        while True:
            p = getPrime(35)
            if valid_mobile(p):
                ls.append(p)
                break
    return ls


def LLL_CRT(p_list, command, scale):
    prod = lambda x: 1 if not x else x[0] * prod(x[1:])
    M = prod(p_list)

    # 格基最后一列上方的系数，即 Mi*Ni
    coeffs = []
    for p in p_list:
        coeff = pow(M // p, -1, p) * (M // p) % M
        coeffs.append(coeff)

    # 对于每一批素数，随机扰动 15 次，看能否得到结果，不能得到就换一批素数
    for _ in range(15):
        # 命令 + '#' + 1 个随机字节
        prefix = command + b"#" + os.urandom(1)
        # m_low 的长度
        length = len(long_to_bytes(M)) - 1 - len(prefix)
        # 补低位 0 后的 prefix
        prefix_shift = bytes_to_long(prefix + b"\x00" * length)
        # 改进后的常系数 C_new
        C_new = (4 * sum(coeffs) - prefix_shift) % M
        # 原本应该是 2**(8*length-2)，这里是作者的经验配平
        C = 2 ** (8 * length) * 4

        L = matrix(len(p_list) + 2, len(p_list) + 2)
        for r in range(len(p_list)):
            L[r, r] = C
            L[r, len(p_list) + 1] = coeffs[r]
        L[len(p_list), len(p_list)] = -scale * C
        L[len(p_list), len(p_list) + 1] = C_new
        L[len(p_list) + 1, len(p_list) + 1] = M

        L = L.LLL()

        for row in L:
            # 如果原本的常系数 1 (row [-2]) 没有被改变，留下来继续筛选
            if row[-2] == -scale * C:
                pass
            # 如果只是向量反了，也留下来
            elif row[-2] == scale * C:
                row = -row
            # 其它情况直接舍弃
            else:
                continue

            # 把 b_i*C 中的 C 剥离，作为列表存储
            bi_list = [b // C for b in row[:-2]]
            # 组装最终的大整数 message
            message = (prefix_shift + row[-1]) % M
            # +4 后的真实余数列表
            actual_rem = [b + 4 for b in bi_list]

            # a_i 在 0-9 内，且高位保留了 command
            if all(r in range(0, 10) for r in actual_rem) and long_to_bytes(
                message
            ).startswith(command):
                try:
                    # 模拟沙箱环境
                    key = 123
                    eval(long_to_bytes(message))
                except Exception as e:
                    # 报错说明构造不成功
                    continue
                return message

    return None


# 不断尝试，直到搜索出符合条件的 message
i = 0
messages = []

while True:
    i += 1
    p_list = genPrimes(64)
    print(f"生成第 {i} 批素数")

    # 先测试最长的一条命令
    command = COMMANDS[-1]
    message = LLL_CRT(p_list, command, random.choice([4, 8, 12, 16]))

    if message is not None:
        print(f"成功找到命令 {command} 的 message")
        messages.append(message)
        break

# 逆序遍历剩余的三条命令
for command in COMMANDS[:-1][::-1]:
    j = 0
    while True:
        j += 1
        message = LLL_CRT(p_list, command, random.choice([4, 8, 12, 16]))

        if message is not None:
            print(f"成功找到命令 {command} 的 message")
            messages.append(message)
            break

with open("messages.txt", "w") as f:
    f.write("p_list: " + " ".join(map(str, p_list)) + "\n")
    f.write("messages: " + " ".join(map(str, messages[::-1])) + "\n")

print("over!")

分析_part2

预期解

跟 part1 相比，part2 就简单了。根据作者的思路构造 Payload 之后，可以通过简单的爆破和 copper 拿到各数据：

key：得到密文 $c_{1} \equiv (k e y)^{5} (\mod n)$ 。由于 key 只有 128bits，五次方后是 640bits，而模数 n 也不过 622bits。溢出截断了，但可以爆破。所以只需要枚举 $K \in (0, 2^{18})$ 就能得到 key。
[*vars()][8]：提取字符串 cipher_with_key_{key}_{nonce}，即得到密文 $c_{2} \equiv (p r e f i x + k e y + i n f i x + n o n c e)^{5}$ ，其中 prefix 是 cipher_with_key_，infix 是 _，只有末尾的 nonce 是未知的。构造 $f (x) = (m_{h i g h} + x)^{5} - c_{2} \equiv 0 (\mod n)$ ，copper 即可（可以先爆破几位，节省时间）
var() 和 vars()[[*vars()][8]]：前者返回的是字典字符串，后者返回的是 ciper 本身。FLAG 是 47 字节，它的 hex 形式是 94 字节（752bits）。作者这里在本地构造了一个 template(key, nonce) 函数，用于在本地复刻用 var() 得到的字典字符串（cipher 位置用 b'\x00' * 94 占位，即 "{'__name__': ..., 'cipher_with_key_...': '\x00\x00...\x00'}"）。若把 cipher 看作 $x$ ，那么字典字符串就是 $a x + b$ （其中 $a = 256^{2}$ ，因为后面的 '} 两个字节把 cipher 顶到前面了； $b$ 是 bytes_to_long(dict_high)）。于是我们就得到关于 $x$ 的方程：
$r_{4} = x^{5} (\mod n), r_{3} \equiv (a x + b)^{5} (\mod n)$
打 Franklin-Reiter 攻击就能得到 $c i p h e r mod n$ ，这里 cipher 大概被截断了 130bits。
格约简拿回 cipher，最后 CTR 解密拿 flag。

非预期解

想到 $e = 5$ ，可以进行小指数加密广播攻击。直接把 command 构造成 [*open('secret.py')]，只用四次机会中的一轮，得到 $n, c$ 后结束交互。重复连接靶机，让 $n$ 重新生成，这样就能得到多组不同的 $n, c$ 。由于 flag 不是以 hex 形式存储的，只有单单 47 字节（376bits），对于 622bits 的 $n$ 来说是没有被截断的。根据 $c = m^{e} (\mod n)$ ，重复连接五次靶机，根据 CRT 获得特解。计算 $m = X^{1 / 5}$ 就能直接复原 flag。

EXP_part2

这里只写非预期解的解法吧，主要练一下 pwntools 的使用

from Crypto.Util.number import *
from pwn import *

# 高位为 [*open('secret.py')]# 的 int(message)
message = 
phone_number = 

n_list = []
c_list = []

context.log_level = "debug"
HOST, POST = 

for i in range(5):
    io = remote(HOST, POST)

    # 传手机号
    io.recvuntil(b"code: ")
    io.sendline(phone_number.encode())
    # 接收模数 n
    io.recvuntil(b"n = ")
    n = int(io.recvline().strip())
    n_list.append(n)
    # 发送 message
    io.recvuntil(b"> ")
    io.sendline(str(message).encode())
    # 获取密文
    c_hex = io.recvline().strip().decode()
    c = int(c_hex, 16)
    c_list.append(c)

    io.close()

# sage
from Crypto.Util.number import *

n_list = []
c_list = []

m_5 = crt(c_list, n_list)
m = gmpy2.iroot(m_5, 5)[0]

print(long_to_bytes(m).decode())

作者还是太有水平了呀 orz

inverse_pow

源码及解读

package main

import (
	"bufio"
	"crypto/rand"
	"fmt"
	"math/big"
	"os"
	"strconv"
	"strings"
	"time"
)

func main() {
	m, err := rand.Int(rand.Reader, big.NewInt(1e8-1))
	if err != nil {
		fmt.Println("Error: ", err)
		os.Exit(2)
	}
	m = m.Add(m, big.NewInt(1))

	fmt.Printf("m = %d\n", m)
	fmt.Print("n = ")

	go func() {
		time.Sleep(60 * time.Second)
		fmt.Println("TimeOut")
		os.Exit(1)
	}() // change second based on server

	reader := bufio.NewReader(os.Stdin)
	input, _ := reader.ReadString('\n')

	n, err := strconv.Atoi(strings.TrimSpace(input))
	if err != nil {
		fmt.Println("Error: ", err)
		os.Exit(2)
	}

	power := new(big.Int).Exp(big.NewInt(2), big.NewInt(int64(n)), nil)
	powerStr := power.String()

	mStr := m.String()

	if strings.HasPrefix(powerStr, mStr) {
		fmt.Printf("Verified\n")
		os.Exit(0)
	} else {
		fmt.Printf("Failed\n")
		os.Exit(1)
	}
}

其实挺阴的，很看运气

程序首先生成一个范围在 $[1, 10^{8} - 1]$ 之间的随机整数 $m$ ，打印出来并等待选手输入数字 $n$ ，且启动计时器。输入之后，程序会计算 $2^{n}$ ，并将计算结果转为十进制的字符串，检查字符串是否以 $m$ 开头。如果满足验证且用时未到 60s，程序打印 Verified。相反，无论是超时或验证失败，程序都会退出。

分析

要求 $2^{n}$ 的头部数字是 $m$ ，等价于 $2^{n} = m \times 10^{k} + l o w$ 。写成不等式：

m \times 10^{k} \leq 2^{n} \leq (m + 1) \times 10^{k}

取以 10 为底的对数并化简：

\log_{10} (m) + k \leq \log_{10} (2) \times n \leq \log_{10} (m + 1) + k

拿左边的 $\log_{10} (m) + k$ 举例。记 $\log_{10} (m)$ 的整数部分和小数部分为 $a, b$ ，那么原数可以写成 $b + (a + k)$ ，即整数加小数形式。取指数后，由于 $1 < b < 10$ ， $\log_{10} (m)$ 就变成了天然的科学计数法形式 $b \times 10^{a + k}$ 。由此可见，影响开头的只有取对后的小数部分。因此对于每个 $m$ ，我们只需要验证 $(n \times \log_{10} 2) mod 1$ 是否落在 $\log_{10} (m mod 10)$ 和 $\log_{10} ((m + 1) mod 10)$ 之间即可。

EXP

单次交互的 exp

from math import log10

def getNum(m: int):
    length = len(str(m))
    divisor = 10 ** (length - 1)
    m_low, m_high = m / divisor, (m + 1) / divisor
    target_low, target_high = log10(m_low), log10(m_high)
    log2 = log10(2)

    n = 1
    while True:
        frac_part = (n * log2) % 1
        if target_low <= frac_part < target_high:
            return n
        n += 1


# 主程序逻辑
from pwn import *

context.log_level = "debug"
HOST, PORT = 
io = remote(HOST, PORT)

# 接收 m
io.recvuntil(b"m = ")
m = int(io.recvline().strip())
# 发送 n
n = getNum(m)
io.recvuntil(b"n = ")
io.sendline(str(n).encode())

print(io.recvline().decode())