密码挑战 - 真·Beginner Writeup by AI

题目信息

• 题目来源: 攻防世界
• 题目类型: Crypto (密码学)

题目描述

题目给出了以下约束条件：

assert(len(open('flag.txt', 'rb').read()) <= 50)
assert(str(int.from_bytes(open('flag.txt', 'rb').read(), byteorder='big') << 10000).endswith('1002773875431658367671665822006771085816631054109509173556585546508965236428620487083647585179992085437922318783218149808537210712780660412301729655917441546549321914516504576'))

题意分析

1. flag 的长度不超过 50 字节
2. 将 flag 转换为大端序的整数后，左移 10000 位（相当于乘以 $2^{10000}$）
3. 结果的十进制表示以给定的长数字结尾

考点分析

本题主要考察以下知识点：

1. 数论基础: 模运算、同余方程
2. 中国剩余定理: 利用 $10^n=2^n\times 5^n$ 分解模数
3. 模逆元计算: 在模 $5^n$ 下求 $2^{10000}$ 的逆元
4. 字节转换: 整数与字节之间的相互转换

解题思路

核心观察

设 flag 对应的整数为 $x$，则有：
$$x\times 2^{10000}\equiv \text{target}(\mathrm{mod}10^n)$$

其中 $n$ 是 target 的位数。

关键步骤

1. 分解模数: $10^n=2^n\times 5^n$
2. 简化问题: 由于 $\gcd (2^{10000},5^n)=1$，我们可以在模 $5^n$ 下求解
3. 求逆元: 计算 $(2^{10000}{)}^{-1}(\mathrm{mod}{5}^n)$
4. 求解 x: $x\equiv \text{target}\times (2^{10000}{)}^{-1}(\mathrm{mod}{5}^n)$
5. 验证范围: 检查解是否小于 $256^{50}$（flag 长度限制）
6. 转换 flag: 将整数转换为字节串

详细步骤

步骤 1: 建立数学模型

给定末尾数字：

target = '1002773875431658367671665822006771085816631054109509173556585546508965236428620487083647585179992085437922318783218149808537210712780660412301729655917441546549321914516504576'

我们需要找到 $x$ 使得：
$$x\times 2^{10000}\equiv \text{target}(\mathrm{mod}10^n)$$

步骤 2: 在模 $5^n$ 下求解

由于 $\gcd (2^{10000},5^n)=1$，存在逆元：

$$2^{10000}\times (2^{10000}{)}^{-1}\equiv 1(\mathrm{mod}{5}^n)$$

因此：
$$x\equiv \text{target}\times (2^{10000}{)}^{-1}(\mathrm{mod}{5}^n)$$

步骤 3: 实现求解算法

使用 Python 的 pow() 函数高效计算：

• pow(2, 10000, mod_5n) 计算 $2^{10000}(\mathrm{mod}{5}^n)$
• pow(a, -1, m) 计算 $a$ 在模 $m$ 下的逆元

步骤 4: 验证并转换

检查得到的 $x$ 是否满足：

• $x<256^{50}$（flag 长度限制）
• $x\times 2^{10000}$ 的末尾确实是 target

完整代码

from Crypto.Util.number import long_to_bytes

# 给定的末尾数字
target = '1002773875431658367671665822006771085816631054109509173556585546508965236428620487083647585179992085437922318783218149808537210712780660412301729655917441546549321914516504576'

# 计算 target 的位数
n = len(target)
target_int = int(target)

# 我们需要解方程：x * 2^10000 ≡ target (mod 10^n)
# 由于 10^n = 2^n * 5^n，且 2^10000 含有大量因子 2
# 我们可以先 mod 5^n，因为 gcd(2^10000, 5^n) = 1

mod_5n = 5**n

# 计算 2^10000 mod 5^n
pow2_mod_5n = pow(2, 10000, mod_5n)

# 计算 pow2_mod_5n 在 mod 5^n 下的逆元
pow2_inv = pow(pow2_mod_5n, -1, mod_5n)

# 计算 x mod 5^n
x_mod_5n = (target_int * pow2_inv) % mod_5n

print(f"x mod 5^n = {x_mod_5n}")
print(f"256^50 = {256**50}")
print(f"x_mod_5n < 256^50: {x_mod_5n < 256**50}")

# 尝试将 x_mod_5n 转换为字节
try:
    flag_bytes = long_to_bytes(x_mod_5n)
    print(f"Flag bytes: {flag_bytes}")
    print(f"Flag length: {len(flag_bytes)}")
    
    # 验证
    if len(flag_bytes) <= 50:
        x_verify = int.from_bytes(flag_bytes, byteorder='big')
        result = str(x_verify << 10000)
        if result.endswith(target):
            print(f"\n✓ 验证成功！")
            print(f"Flag: {flag_bytes.decode('utf-8', errors='ignore')}")
        else:
            print("\n✗ 验证失败")
    else:
        print("\n✗ Flag 长度超过 50")
except Exception as e:
    print(f"错误：{e}")

总结

本题是一道典型的数论应用题，主要考察：

1. 数学建模能力: 将位移操作转化为乘法运算，将"末尾数字"转化为同余方程
2. 数论知识: 理解模运算、逆元、中国剩余定理的应用
3. 编程实现: 利用 Python 的大数运算和 Crypto 库完成求解

关键技巧

• 利用 $\gcd (2^{10000},5^n)=1$ 简化问题
• 使用 pow(a, -1, m) 快速计算模逆元
• 注意 flag 长度限制用于验证解的正确性

易错点

1. 未注意到可以在模 $5^n$ 下单独求解
2. 忽略了 flag 长度限制的验证作用
3. 字节序选择错误（应使用大端序）

---

附录：用户原始提问

该题目是攻防世界中 Ctypto 类型的题目，信息如下：
题目：密码挑战 - 真·Beginner

请根据现有文件内容，输出一份解题的 writeup，格式为 md 文件。