CPCTF - 1、0、7 Writeup¶

题目信息¶

比赛: CPCTF
题目: 1、0、7
类别: Crypto / RSA
难度: 简单
附件/URL: 107107_b38e4b4bcd49c22b496049abb867695331cdc0f7542dd59288b3597e1b8e4119.txt
附件链接: 下载附件 · 仓库位置
Flag格式: CPCTF{...}
状态: 已解

Flag¶

CPCTF{N_1s_34sy_70_bRe4k_873b4982a}

解题过程¶

1. 初始侦察/文件识别¶

附件里直接给出了 RSA 公钥参数和密文：

N=111...111000...000777...777
e=65537
c=24843637357401882323446973756028112485787496266605121365114610100704976130139741775294278368083885062198910614947919701406960107347354136102083123762522563111468269091870174521712246171376836840432255040039220296948193266921702699341919800731671378599220251932387731543800016339125706640050863673217753733950003925236014913643596976803633793469056544830856356906877796834342590774214214984186572346186348406049348500029472048880777893019592044554103952675917537653629499365661200893824071688347597515583518961750064206790440539820055665939394772896875086157476469036827442358013160609933570806379028553689444972004391787853021463769839240033616969091368964549902197048529690707775841641688773013075774663922475980270327652933542

\(e = 65537\) 是最常见的 RSA 公钥指数。
真正可疑的是 N：它不是看起来随机的模数，而是十进制下非常整齐的拼接数。
把 N 的十进制连续数字块统计一下，很快就能看到：

1 重复 317 次
0 重复 95 次
7 重复 317 次

2. 关键突破点一：把十进制拼接写成代数式¶

设：

\[ k = 317,\qquad t = 95,\qquad R_k = \frac{10^k - 1}{9} \]

其中 \(R_k\) 表示由 \(k\) 个 1 组成的 repunit。

那么低位的 777...777 可以写成：

\[ 777\ldots777 = 7R_k \]

整个模数 \(N\) 就是：

\[ N = R_k \cdot 10^{t+k} + 7R_k \]

提出公共因子 \(R_k\)：

\[ N = R_k \left(10^{t+k} + 7\right) \]

代入本题的长度参数以后：

\[ N = \frac{10^{317} - 1}{9} \cdot \left(10^{412} + 7\right) \]

所以两个因子直接出来了：

\[ p = \frac{10^{317} - 1}{9},\qquad q = 10^{412} + 7 \]

3. 关键突破点二：恢复私钥并解密¶

一旦 \(N\) 被分解，后续可以直接交给 RsaCtfTool 做私钥恢复与解密。
先按“关键突破点一”的结构化推导（即把 N 写成 \(R_k(10^{t+k}+7)\)）得到：

\[ p = \frac{10^{317} - 1}{9},\qquad q = 10^{412} + 7 \]

再使用 RsaCtfTool 解密（这里直接传入 p/q/e/c）：

python3 ~/.local/bin/RsaCtfTool \
  -p 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 \
  -q 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000007 \
  -e 65537 \
  --decrypt 24843637357401882323446973756028112485787496266605121365114610100704976130139741775294278368083885062198910614947919701406960107347354136102083123762522563111468269091870174521712246171376836840432255040039220296948193266921702699341919800731671378599220251932387731543800016339125706640050863673217753733950003925236014913643596976803633793469056544830856356906877796834342590774214214984186572346186348406049348500029472048880777893019592044554103952675917537653629499365661200893824071688347597515583518961750064206790440539820055665939394772896875086157476469036827442358013160609933570806379028553689444972004391787853021463769839240033616969091368964549902197048529690707775841641688773013075774663922475980270327652933542

输出中的 utf-8 即：

CPCTF{N_1s_34sy_70_bRe4k_873b4982a}

也可以走纯数学流程，自己计算：

\[ \varphi = (p - 1)(q - 1) \]

\[ d \equiv e^{-1} \pmod{\varphi} \]

\[ m \equiv c^d \pmod{N} \]

把 m 再转回字节串即可拿到明文。
实战里可以额外做两步自检：
assert p * q == N
用 sympy.isprime() 或其他素性测试确认 p、q 没问题

4. 获取 Flag¶

解密结果就是：

CPCTF{N_1s_34sy_70_bRe4k_873b4982a}

攻击链/解题流程总结¶

识别 RSA 参数 -> 观察 \(N\) 的十进制结构是 \(1^k 0^t 7^k\) -> 将 \(N\) 代数化为 repunit 公因子乘积 -> 直接分解 \(N\) -> 计算 \(d\) -> RSA 解密 -> Flag

漏洞分析 / 机制分析¶

根因¶

RSA 模数 \(N\) 被构造成了一个带明显十进制规律的数：

\[ N = 111\ldots111000\ldots000777\ldots777 \]

由于首尾重复块长度相同，且尾部数字块正好是前部 repunit 的 7 倍，所以可以直接提出公共因子：

\[ N = R_k \cdot 10^{t+k} + 7R_k \]

\[ N = R_k \left(10^{t+k} + 7\right) \]

这样一来，RSA 赖以成立的“分解 \(N = pq\) 很困难”这个前提就直接失效了。

影响¶

攻击者不需要通用大整数分解算法，也不需要外部因数分解平台。
只要看懂这个十进制结构，就能瞬间得到 p 和 q，再恢复私钥解出密文。

修复建议（适用于漏洞类题目）¶

p 和 q 必须来自安全随机数生成器，而不是人为拼接或带明显模式的整数。
生成 RSA 密钥后，应做基本健康检查，避免：
明显结构化因子
共享因子
低熵、可预测的构造方式

知识点¶

RSA 分解后解密的标准流程
Repunit：\(111\ldots111 = \frac{10^k - 1}{9}\)
十进制拼接数的代数化表示
结构化 RSA 模数往往比随机模数更容易被拆解

知识点常见问题解答（可选）

为什么 111...111000...000777...777 能一眼拆出来？

因为它不是“随机大整数”，而是“高位块 + 若干个 0 + 低位块”的十进制拼接。
只要前后块长度相同，并且低位块是高位 repunit 的整数倍，就能把整个数写成：

\[ R_k \cdot 10^{\mathrm{offset}} + \mathrm{multiplier} \cdot R_k \]

\[ = R_k \left(10^{\mathrm{offset}} + \mathrm{multiplier}\right) \]

本题里 \(\mathrm{multiplier} = 7\)，所以直接得到：

\[ p = \frac{10^{317} - 1}{9},\qquad q = 10^{412} + 7 \]

使用的工具¶

RsaCtfTool — 读取参数并解密（本篇主流程）
Python 3 — 读取附件、统计数字块并构造因子
Go 1.25+ — 使用 math/big 纯标准库复现同一条解题链
SymPy（可选）— 如需额外验证，可用 isprime() 检查质性
yafu（可选） — 若遇到“仅给 n 需做通用整数分解”的 RSA 题型，可先分解再交给 RsaCtfTool
RsaCtfTool 安装与常用命令参考：RsaCtfTool 上手使用指南
yafu 安装与常用命令参考：yafu 上手使用指南

脚本归档¶

Go：CPCTF_1_0_7.go
Python：CPCTF_1_0_7.py
说明：两个版本都会直接读取归档后的附件，并自动根据 N 的十进制结构构造因子与私钥。

from itertools import groupby
from pathlib import Path
import re

raw = Path("CTF_Writeups/files/1、0、7/107107_b38e4b4bcd49c22b496049abb867695331cdc0f7542dd59288b3597e1b8e4119.txt").read_text()
N = int(re.search(r"N=(\d+)", raw).group(1))
e = int(re.search(r"e=(\d+)", raw).group(1))
c = int(re.search(r"c=(\d+)", raw).group(1))

groups = [(digit, len(list(chunk))) for digit, chunk in groupby(str(N))]
assert groups == [("1", 317), ("0", 95), ("7", 317)]

k = groups[0][1]
shift = groups[1][1] + groups[2][1]
p = (10**k - 1) // 9
q = 10**shift + 7

assert p * q == N

phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
m = pow(c, d, N)

print(m.to_bytes((m.bit_length() + 7) // 8, "big").decode())

命令行提取关键数据（无 GUI）¶

# 统计 N 的连续数字块
python -c "from pathlib import Path; import re,itertools; s=Path('CTF_Writeups/files/1、0、7/107107_b38e4b4bcd49c22b496049abb867695331cdc0f7542dd59288b3597e1b8e4119.txt').read_text(); N=re.search(r'N=(\d+)',s).group(1); print(len(N)); print([(k,len(list(g))) for k,g in itertools.groupby(N)])"

# Python 版复现
python CTF_Writeups/scripts_python/CPCTF_1_0_7.py

# Go 版复现
go run CTF_Writeups/scripts_go/CPCTF_1_0_7.go

推荐工具与优化解题流程¶

这题的关键不在“硬分解”，而在于看出 N 的十进制规律并把它写成可直接拆分的代数式。

工具对比总结¶

工具	适用阶段	本题耗时	优点	缺点
Python	参数解析、公式验证、RSA 解密	< 1 秒	原生大整数支持好，复现成本低	需要自己写少量脚本
Go	参数解析、公式验证、RSA 解密	< 1 秒	纯标准库，适合长期归档	`math/big` 写法比 Python 稍长
SymPy	素性测试	< 1 秒	`isprime()` 使用方便	本题不是必须，只是额外验证
yafu / 通用分解工具	尝试分解 N	不推荐（本题）	可用于一般 RSA 分解场景	本题重点是结构化代数分解，不是通用硬分解

工具 A（推荐首选）¶

安装：Python 3
详细步骤：
读取附件中的 N、e、c
统计 \(N\) 的连续数字块，确认是 \(1^{317} 0^{95} 7^{317}\)
构造 \(p=\frac{10^{317}-1}{9}\) 和 \(q=10^{412}+7\)
计算 \(d\) 并解密 \(c\)
优势：推导过程短、可读性高、完全离线可复现

工具 B（可选）¶

安装：pip install sympy
详细步骤：
使用 sympy.isprime(p) 和 sympy.isprime(q) 检查因子是否为质数
使用 assert p*q == N 检查分解是否正确
优势：可以快速确认分解出的两个因子满足 RSA 质因子条件

工具 C（推荐归档版）¶

安装：Go 1.25+
详细步骤：
读取归档附件并解析 N、e、c
用分组或正则确认 \(N\) 的结构是 \(1^k 0^t 7^k\)
使用 math/big 构造 \(p=\frac{10^k-1}{9}\) 和 \(q=10^{t+k}+7\)
计算 d 并解密出明文
优势：纯标准库，无第三方依赖，适合长期归档

CPCTF - 1、0、7 Writeup¶

题目信息¶

Flag¶

解题过程¶

1. 初始侦察/文件识别¶

2. 关键突破点一：把十进制拼接写成代数式¶

3. 关键突破点二：恢复私钥并解密¶

4. 获取 Flag¶

攻击链/解题流程总结¶

漏洞分析 / 机制分析¶

根因¶

影响¶

修复建议（适用于漏洞类题目）¶

知识点¶

使用的工具¶

脚本归档¶

命令行提取关键数据（无 GUI）¶

推荐工具与优化解题流程¶

工具对比总结¶

推荐流程¶

工具 A（推荐首选）¶

工具 B（可选）¶

工具 C（推荐归档版）¶

评论