文章总结： 本文详细分析BCTF2016自定义RSA变体题目，指出其无法抵抗已知明文攻击。作者利用扩展欧几里得算法从已知明文密文对中成功恢复密钥k并解密flag。文章深入讲解了模运算原理，提供完整攻击脚本与防御建议，极具教学价值。 综合评分： 96 文章分类： CTF,漏洞分析

---

BCTF 2016 Special RSA – 从零开始的完整解题分析

原创

破镜安全

破镜安全

2025年12月24日 08:00 四川

BCTF 2016 Special RSA – 从零开始的完整解题分析

前言

本文将详细分析一道来自 BCTF 2016 的密码学题目 Special RSA。这道题目涉及一个自定义的 RSA 变体加密算法，通过分析其加密机制的漏洞，我们可以从已知的明文-密文对中恢复出密钥，进而解密出 flag。

本文将从零开始，一步一步地分析题目、寻找突破点、推导数学原理、编写攻击脚本，最终成功解密 flag。即使你是密码学新手，也能通过本文理解整个攻击过程。

题目初探

题目给了我们什么

下载题目附件后，我们得到以下文件：

special_rsa.py    # 加密和解密程序源代码
msg.txt          # 一段明文消息
msg.enc          # msg.txt 的加密结果
flag.enc         # 加密的 flag（我们的目标）

题目的目标很明确：我们需要想办法解密 flag.enc 来获得 flag。

第一步：阅读源代码

打开 special_rsa.py，我们首先看到一个很大的数字 N：

N = 23927411014020695772934916764953661641310148480977056645255098192491740356525240675906285700516357578929940114553700976167969964364149615226568689224228028461686617293534115788779955597877965044570493457567420874741357186596425753667455266870402154552439899664446413632716747644854897551940777512522044907132864905644212655387223302410896871080751768224091760934209917984213585513510597619708797688705876805464880105797829380326559399723048092175492203894468752718008631464599810632513162129223356467602508095356584405555329096159917957389834381018137378015593755767450675441331998683799788355179363368220408879117131

这是一个 618 位的十进制数字，在整个加密系统中扮演”模数”的角色。

接下来是几个工具函数：

def egcd(a, b):
    # 扩展欧几里得算法
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    # 计算 a 在模 m 下的乘法逆元
    g, x, y = egcd(a, m)
    assert g == 1
    return x % m

def pad_even(x):
    # 确保十六进制字符串长度为偶数
    return ('', '0')[len(x)%2] + x

这些是数学辅助函数，我们稍后会详细解释它们的作用。

关键：加密函数

现在来看最关键的加密函数：

def encrypt(ms, k):
    out = []
    for i in range(0, len(ms), 256):
        m = ms[i:i+256]
        m = int(m.encode('hex'), 16)
        r = random_r()
        r_s = pad_even(format(r, 'x')).decode('hex')
&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;assert&nbsp;m < N
&nbsp; &nbsp; &nbsp; &nbsp; c = (pow(k, r, N) * m) % N
&nbsp; &nbsp; &nbsp; &nbsp; c_s = pad_even(format(c,&nbsp;'x')).decode('hex')
&nbsp; &nbsp; &nbsp; &nbsp; out.append((r_s, c_s))
&nbsp; &nbsp;&nbsp;return&nbsp;msgpack.packb(out)

让我们逐行分析这个加密函数在做什么：

1. 分块处理：for i in range(0, len(ms), 256) – 将明文每 256 字节分成一块
2. 转换为整数：m = int(m.encode('hex'), 16) – 把每块的字节转换成一个大整数
3. 生成随机数：r = random_r() – 为每一块生成一个随机数
4. 核心加密公式：c = (pow(k, r, N) * m) % N

第 4 步是整个加密算法的核心，用数学符号表示就是：

c ≡ k^r * m (mod N)

其中：

• c 是密文
• k 是密钥（secret key）
• r 是随机数
• m 是明文
• N 是公开的大数

1. 输出：每一块加密后输出一对 (r, c)，即随机数和密文

解密函数

再看看解密函数：

def decrypt(c, k):
    out = ''
    for r_s, c_s in msgpack.unpackb(c):
        r = int(r_s.encode('hex'), 16)
        c = int(c_s.encode('hex'), 16)
        k_inv = modinv(k, N)
        out += pad_even(format(pow(k_inv, r, N) * c % N, 'x')).decode('hex')
    return out

解密的核心公式是：

m = pow(k_inv, r, N) * c % N

其中 k_inv 是 k 的模逆元，即满足 k * k_inv ≡ 1 (mod N) 的数。

用数学符号表示：

m ≡ k^(-r) * c (mod N)

理解加密和解密的数学原理

为什么这样能解密呢？让我们验证一下：

加密：c ≡ k^r * m (mod N)
解密：m' ≡ k^(-r) * c (mod N)

把加密公式代入解密公式：

m' ≡ k^(-r) * (k^r * m) (mod N)
m' ≡ k^(-r) * k^r * m (mod N)
m' ≡ k^0 * m (mod N)
m' ≡ 1 * m (mod N)
m' ≡ m (mod N)

所以解密能够正确还原明文。

初步思考

到这里，我们已经理解了加密算法的工作原理。现在的问题是：

题目给了我们 msg.txt（明文）和 msg.enc（密文），以及 flag.enc（加密的flag）。我们需要找到密钥 k，才能解密 flag.enc。

但是，程序里并没有给出 k 的值，k 应该在 from key import k 这个导入语句中，但我们没有 key.py 文件。

所以，我们的任务就是：从已知的明文-密文对中恢复出密钥 k。

第二步：提取和分析已知信息

查看明文内容

首先看看 msg.txt 的内容：

ARM, originally Acorn RISC Machine, later Advanced RISC Machine, is a family
of reduced instruction set computing (RISC) architectures for computer
processors, configured for various environments. British company ARM Holdings
develops the architecture and licenses it to other companies, who design their
own products that implement one of those architectures—including
systems-on-chips (SoC) that incorporate memory, interfaces, radios, etc.

这是一段关于 ARM 架构的介绍文字，共 446 字节。

编写数据提取脚本

为了分析加密数据，我们需要编写一个脚本来提取 msg.enc 中的信息：

import msgpack

N = 23927411014020695772934916764953661641310148480977056645255098192491740356525240675906285700516357578929940114553700976167969964364149615226568689224228028461686617293534115788779955597877965044570493457567420874741357186596425753667455266870402154552439899664446413632716747644854897551940777512522044907132864905644212655387223302410896871080751768224091760934209917984213585513510597619708797688705876805464880105797829380326559399723048092175492203894468752718008631464599810632513162129223356467602508095356584405555329096159917957389834381018137378015593755767450675441331998683799788355179363368220408879117131

# 读取明文
with open('msg.txt', 'rb') as f:
    msg = f.read()

# 读取密文
with open('msg.enc', 'rb') as f:
    enc_data = msgpack.unpackb(f.read(), raw=True)

print(f"明文长度: {len(msg)} 字节")
print(f"加密块数量: {len(enc_data)} 块")
print()

# 分析每个加密块
for i, (r_s, c_s) in enumerate(enc_data):
    r = int(r_s.hex(), 16)
    c = int(c_s.hex(), 16)
    m_bytes = msg[i*256:(i+1)*256]
    m = int(m_bytes.hex(), 16)

    print(f"块 {i+1}:")
    print(f"  随机数 r{i+1} = {r}")
    print(f"  明文   m{i+1} = {m}")
    print(f"  密文   c{i+1} = {c}")
    print()

运行这个脚本，我们得到：

明文长度: 446 字节
加密块数量: 2 块

块 1:
  随机数 r1 = 1290067619162043036042711764185954751683881359633161616676...
  明文   m1 = 8246074182642091125578311828374843698994233243811347691229...
  密文   c1 = 1454899738089726523977888482538130110996551898966180809068...

块 2:
  随机数 r2 = 7718975159402389617924543100113967512280131630286624078102...
  明文   m2 = 1557505145385852175310846206372375098638609306776394831661...
  密文   c2 = 1279394279511003831972453187556869350746932717608595416403...

分析结果

从输出可以看到：

1. 明文被分成了 2 个块
2. 对于每一块，我们都知道：

• 随机数 r（因为加密时输出了它）
• 明文 m（因为我们有 msg.txt）
• 密文 c（从 msg.enc 中读取）

用数学方程表示，我们有：

块1: c1 ≡ k^r1 * m1 (mod N)
块2: c2 ≡ k^r2 * m2 (mod N)

其中，c1, r1, m1, c2, r2, m2, N 都是已知的，只有 k 是未知的。

这是两个关于 k 的方程！能不能从这两个方程中求解出 k 呢？

第三步：寻找攻击突破点

问题分析

我们有两个方程：

c1 ≡ k^r1 * m1 (mod N)
c2 ≡ k^r2 * m2 (mod N)

如果直接求解 k，会遇到一个问题：这是关于 k 的指数方程，k 在指数的底数位置，而 r1 和 r2 是巨大的数字（155位），直接求解非常困难。

变换方程

让我们尝试变换一下方程。由第一个方程：

c1 ≡ k^r1 * m1 (mod N)

两边同时乘以 m1 的逆元（假设它存在）：

c1 * m1^(-1) ≡ k^r1 (mod N)

即：

k^r1 ≡ c1 * m1^(-1) (mod N)

同理，由第二个方程：

k^r2 ≡ c2 * m2^(-1) (mod N)

现在方程变成了：

k^r1 ≡ c1 * m1^(-1) (mod N)  ... (方程1)
k^r2 ≡ c2 * m2^(-1) (mod N)  ... (方程2)

等等右边都是已知数了，但左边 k 还在指数位置。我们需要想办法把 k 从指数上”拉下来”。

关键突破：扩展欧几里得定理

这里要用到一个重要的数学定理：扩展欧几里得定理（Extended Euclidean Algorithm）。

欧几里得定理说的是：对于任意两个整数 a 和 b，一定存在最大公约数 gcd(a, b)。

扩展欧几里得定理进一步告诉我们：对于任意整数 a 和 b，一定存在整数 x 和 y，使得：

a * x + b * y = gcd(a, b)

在我们的问题中，如果我们对 r1 和 r2 应用扩展欧几里得定理，就能找到整数 a 和 b，使得：

a * r1 + b * r2 = gcd(r1, r2)

如果幸运的话，gcd(r1, r2) = 1（r1 和 r2 互质），那么：

a * r1 + b * r2 = 1

这个定理如何帮助我们？

现在我们有：

k^r1 ≡ c1 * m1^(-1) (mod N)  ... (方程1)
k^r2 ≡ c2 * m2^(-1) (mod N)  ... (方程2)
a * r1 + b * r2 = 1           ... (方程3)

接下来是巧妙的一步：

将方程1的两边同时取 a 次方：

(k^r1)^a ≡ (c1 * m1^(-1))^a (mod N)

简化左边：

k^(r1*a) ≡ (c1 * m1^(-1))^a (mod N)  ... (方程4)

将方程2的两边同时取 b 次方：

(k^r2)^b ≡ (c2 * m2^(-1))^b (mod N)
k^(r2*b) ≡ (c2 * m2^(-1))^b (mod N)  ... (方程5)

现在，将方程4和方程5相乘：

k^(r1*a) * k^(r2*b) ≡ (c1 * m1^(-1))^a * (c2 * m2^(-1))^b (mod N)

利用指数法则 x^a * x^b = x^(a+b)：

k^(r1*a + r2*b) ≡ (c1 * m1^(-1))^a * (c2 * m2^(-1))^b (mod N)

根据方程3，我们知道 a * r1 + b * r2 = 1，所以：

k^1 ≡ (c1 * m1^(-1))^a * (c2 * m2^(-1))^b (mod N)

即：

k ≡ (c1 * m1^(-1))^a * (c2 * m2^(-1))^b (mod N)

太好了！我们成功地得到了 k 的计算公式，而且右边全部都是已知量！

第四步：实现攻击脚本

编写完整的攻击脚本

现在我们有了理论基础，可以编写脚本来恢复密钥了：

import msgpack

N = 23927411014020695772934916764953661641310148480977056645255098192491740356525240675906285700516357578929940114553700976167969964364149615226568689224228028461686617293534115788779955597877965044570493457567420874741357186596425753667455266870402154552439899664446413632716747644854897551940777512522044907132864905644212655387223302410896871080751768224091760934209917984213585513510597619708797688705876805464880105797829380326559399723048092175492203894468752718008631464599810632513162129223356467602508095356584405555329096159917957389834381018137378015593755767450675441331998683799788355179363368220408879117131

def egcd(a, b):
    """扩展欧几里得算法（迭代版本）"""
    x0, x1, y0, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

def modinv(a, m):
    """计算 a 在模 m 下的乘法逆元"""
    return pow(a, -1, m)

# 读取明文
with open('msg.txt', 'rb') as f:
    msg = f.read()

# 读取密文
with open('msg.enc', 'rb') as f:
    enc_data = msgpack.unpackb(f.read(), raw=True)

# 提取块1的数据
r1 = int(enc_data[0][0].hex(), 16)
c1 = int(enc_data[0][1].hex(), 16)
m1 = int(msg[0:256].hex(), 16)

# 提取块2的数据
r2 = int(enc_data[1][0].hex(), 16)
c2 = int(enc_data[1][1].hex(), 16)
m2 = int(msg[256:512].hex(), 16)

print("="*80)
print("开始恢复密钥")
print("="*80)
print()

# 步骤1: 使用扩展欧几里得算法求解 a, b
print("[步骤1] 使用扩展欧几里得算法")
gcd, a, b = egcd(r1, r2)
print(f"gcd(r1, r2) = {gcd}")
print(f"找到的 a = {a}")
print(f"找到的 b = {b}")
print(f"验证: a*r1 + b*r2 = {a*r1 + b*r2}")
print()

if gcd != 1:
    print("警告: gcd 不等于 1，需要特殊处理")
    exit(1)

# 步骤2: 计算 m1 和 m2 的模逆
print("[步骤2] 计算模逆元")
m1_inv = modinv(m1, N)
m2_inv = modinv(m2, N)
print("m1 的模逆元已计算")
print("m2 的模逆元已计算")
print()

# 步骤3: 计算密钥 k
print("[步骤3] 计算密钥 k")
print("使用公式: k = (c1 * m1^(-1))^a * (c2 * m2^(-1))^b mod N")
k = (pow(c1 * m1_inv % N, a, N) * pow(c2 * m2_inv % N, b, N)) % N
print("密钥计算完成!")
print()
print(f"k = {k}")
print()

# 步骤4: 验证密钥
print("[步骤4] 验证密钥")
verify1 = (pow(k, r1, N) * m1) % N
verify2 = (pow(k, r2, N) * m2) % N

print(f"块1验证: (k^r1 * m1) mod N == c1? {verify1 == c1}")
print(f"块2验证: (k^r2 * m2) mod N == c2? {verify2 == c2}")
print()

if verify1 == c1 and verify2 == c2:
    print("密钥验证成功!")
else:
    print("密钥验证失败!")
    exit(1)

# 保存密钥
with open('recovered_key.txt', 'w') as f:
    f.write(str(k))
print("密钥已保存到 recovered_key.txt")

运行结果

运行这个脚本，我们得到：

================================================================================
开始恢复密钥
================================================================================

[步骤1] 使用扩展欧几里得算法
gcd(r1, r2) = 1
找到的 a = 458416794751376378007159637833614257020119680526925844122814899920948185532435074923534471162466683056571856608579849049108886177843500000915882029948452
找到的 b = -766149198275939187831083761021244664144859791039598872343747262504169838575201881093683645353747566413865606036907836666018865368882798147957510637712665
验证: a*r1 + b*r2 = 1

[步骤2] 计算模逆元
m1 的模逆元已计算
m2 的模逆元已计算

[步骤3] 计算密钥 k
使用公式: k = (c1 * m1^(-1))^a * (c2 * m2^(-1))^b mod N
密钥计算完成!

k = 175971776542095822590595405274258668271271366360140578776612582276966567082080372980811310146217399585938214712928761559525614866113821551467842221588432676885027725038849513527080849158072296957428701767142294778752742980766436072183367444762212399986777124093501619273513421803177347181063254421492621011961

[步骤4] 验证密钥
块1验证: (k^r1 * m1) mod N == c1? True
块2验证: (k^r2 * m2) mod N == c2? True

密钥验证成功!
密钥已保存到 recovered_key.txt

太好了！我们成功恢复了密钥，并且通过验证确认密钥是正确的。

第五步：解密 flag

编写解密脚本

现在有了密钥 k，我们就可以解密 flag.enc 了：

import msgpack

N = 23927411014020695772934916764953661641310148480977056645255098192491740356525240675906285700516357578929940114553700976167969964364149615226568689224228028461686617293534115788779955597877965044570493457567420874741357186596425753667455266870402154552439899664446413632716747644854897551940777512522044907132864905644212655387223302410896871080751768224091760934209917984213585513510597619708797688705876805464880105797829380326559399723048092175492203894468752718008631464599810632513162129223356467602508095356584405555329096159917957389834381018137378015593755767450675441331998683799788355179363368220408879117131

# 恢复的密钥
k = 175971776542095822590595405274258668271271366360140578776612582276966567082080372980811310146217399585938214712928761559525614866113821551467842221588432676885027725038849513527080849158072296957428701767142294778752742980766436072183367444762212399986777124093501619273513421803177347181063254421492621011961

def modinv(a, m):
    return pow(a, -1, m)

def pad_even(x):
    return ('', '0')[len(x)%2] + x

def decrypt(c, k):
    """解密函数"""
    out = ''
    for r_s, c_s in msgpack.unpackb(c, raw=True):
        r = int(r_s.hex(), 16)
        c = int(c_s.hex(), 16)
        k_inv = modinv(k, N)
        m_int = pow(k_inv, r, N) * c % N
        m_hex = pad_even(format(m_int, 'x'))
        out += bytes.fromhex(m_hex).decode('utf-8', errors='ignore')
    return out

# 读取 flag 密文
with open('flag.enc', 'rb') as f:
    flag_enc = f.read()

# 解密
print("正在解密 flag...")
flag = decrypt(flag_enc, k)

print("="*80)
print("Flag:")
print("="*80)
print(flag)
print("="*80)

# 保存结果
with open('flag_decrypted.txt', 'w') as f:
    f.write(flag)
print()
print("Flag 已保存到 flag_decrypted.txt")

运行结果

正在解密 flag...
================================================================================
Flag:
================================================================================
BCTF{q0000000000b3333333333-ju57-w0n-pwn20wn!!!!!!!!!!!!}
================================================================================

Flag 已保存到 flag_decrypted.txt

成功了！我们得到了 flag：BCTF{q0000000000b3333333333-ju57-w0n-pwn20wn!!!!!!!!!!!!}

核心知识点深度解析

通过这道题，我们学到了很多重要的密码学和数学知识。让我们深入理解这些核心概念。

1. 模运算（Modular Arithmetic）

模运算是密码学的基础。a mod n 表示 a 除以 n 的余数。

例如：

• 17 mod 5 = 2（因为 17 = 5 × 3 + 2）
• 100 mod 7 = 2（因为 100 = 7 × 14 + 2）

在密码学中，我们经常使用同余符号 ≡：

a ≡ b (mod n)

表示 a 和 b 在模 n 下同余，即 a mod n = b mod n。

模运算的重要性质：

1. 加法：(a + b) mod n = ((a mod n) + (b mod n)) mod n
2. 乘法：(a * b) mod n = ((a mod n) * (b mod n)) mod n
3. 幂运算：(a^b) mod n 可以高效计算（快速幂算法）

2. 模逆元（Modular Inverse）

在普通算术中，a 的倒数是 1/a，满足 a * (1/a) = 1。

在模运算中，a 的模逆元是一个数 b，满足：

a * b ≡ 1 (mod n)

我们记作 b = a^(-1) mod n。

模逆元存在的条件：

a 在模 n 下有逆元，当且仅当 gcd(a, n) = 1（a 和 n 互质）。

例子：

求 3 在模 7 下的逆元：

• 尝试：3 × 1 = 3 ≡ 3 (mod 7)
• 尝试：3 × 2 = 6 ≡ 6 (mod 7)
• 尝试：3 × 3 = 9 ≡ 2 (mod 7)
• 尝试：3 × 4 = 12 ≡ 5 (mod 7)
• 尝试：3 × 5 = 15 ≡ 1 (mod 7) ✓

所以 3 在模 7 下的逆元是 5。

Python 中计算模逆元：

Python 3.8+ 提供了简便方法：

inv = pow(a, -1, n)  # 计算 a 在模 n 下的逆元

3. 扩展欧几里得算法（Extended Euclidean Algorithm）

欧几里得算法用于求两个数的最大公约数（GCD）：

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

扩展欧几里得算法不仅求 GCD，还找到系数 x 和 y，使得：

a * x + b * y = gcd(a, b)

这个算法在密码学中非常重要，因为它可以：

1. 计算模逆元
2. 解线性同余方程
3. 本题中的密钥恢复

算法实现（迭代版本）：

def egcd(a, b):
    x0, x1, y0, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0  # 返回 (gcd, x, y)

例子：

求 gcd(35, 15) 以及满足 35x + 15y = gcd(35, 15) 的 x, y：

gcd, x, y = egcd(35, 15)
# 结果: gcd = 5, x = 1, y = -2
# 验证: 35 * 1 + 15 * (-2) = 35 - 30 = 5 ✓

4. 为什么这个加密系统不安全？

这个加密系统的致命弱点在于：它无法抵抗已知明文攻击（Known Plaintext Attack）。

已知明文攻击是指攻击者同时拥有一些明文和对应的密文。

在这个系统中：

• 每个明文-密文对都给出一个关于密钥 k 的方程：c ≡ k^r * m (mod N)
• 有两个这样的方程，结合扩展欧几里得定理，就能直接求出 k

标准 RSA 为什么安全？

标准 RSA 的加密公式是：

c ≡ m^e (mod N)

其中 N = p × q（两个大素数的乘积），e 是公开指数。

即使知道明文 m 和密文 c，攻击者也无法直接求出私钥 d，因为：

1. 求 d 需要知道 φ(N) = (p-1)(q-1)
2. 求 φ(N) 需要分解 N = p × q
3. 分解大数是困难的（基于大数分解难题）

而本题的系统：

• 密钥 k 直接出现在加密公式中
• 没有基于困难数学问题的保护
• 容易受到已知明文攻击

5. 模幂运算的性质

本题的攻击利用了模幂运算的一个重要性质：

(a^x)^y ≡ a^(xy) (mod n)
a^x * a^y ≡ a^(x+y) (mod n)

我们利用这个性质，通过组合 k^r1 和 k^r2，构造出 k^1 = k：

k^(a*r1) * k^(b*r2) = k^(a*r1 + b*r2) = k^1 = k

这是一个巧妙的数学技巧，将指数上的线性组合转化为底数上的求解。

攻击流程总结

让我们回顾整个攻击流程：

1. 分析源代码，理解加密算法
   ↓
2. 识别已知信息：明文 m1, m2，密文 c1, c2，随机数 r1, r2，模数 N
   ↓
3. 建立数学方程：c1 ≡ k^r1 * m1 (mod N), c2 ≡ k^r2 * m2 (mod N)
   ↓
4. 变形方程：k^r1 ≡ c1/m1 (mod N), k^r2 ≡ c2/m2 (mod N)
   ↓
5. 应用扩展欧几里得定理：找到 a, b 使得 a*r1 + b*r2 = 1
   ↓
6. 推导密钥公式：k ≡ (c1/m1)^a * (c2/m2)^b (mod N)
   ↓
7. 计算模逆元：m1^(-1), m2^(-1)
   ↓
8. 计算密钥：k = (c1 * m1^(-1))^a * (c2 * m2^(-1))^b mod N
   ↓
9. 验证密钥：检查 k^r1 * m1 ≡ c1 (mod N) 和 k^r2 * m2 ≡ c2 (mod N)
   ↓
10. 使用密钥解密 flag.enc 得到 flag

防御措施和改进建议

如果要设计一个安全的加密系统，应该：

1. 使用经过验证的标准算法

• 不要自己发明加密算法
• 使用 AES、RSA、ECC 等标准算法

1. 确保系统能抵抗已知明文攻击

• 即使攻击者知道部分明文-密文对，也无法恢复密钥

1. 基于困难数学问题

• RSA：基于大数分解
• ECC：基于离散对数问题
• 本题系统：没有困难问题保护

1. 添加随机化和填充

• 相同明文加密后应得到不同密文
• 使用 OAEP、PKCS#7 等标准填充方案

1. 实施消息认证

• 添加 MAC 或数字签名
• 防止密文被篡改

学习建议

通过这道题，密码学初学者可以学到：

数学基础：

• 模运算的性质和应用
• 欧几里得算法和扩展欧几里得算法
• 模逆元的概念和计算
• 数论在密码学中的应用

密码学概念：

• 加密和解密的数学原理
• 已知明文攻击
• 为什么自定义加密算法通常不安全
• RSA 变体的安全性分析

编程能力：

• Python 大整数运算
• 密码学库的使用（msgpack）
• 算法实现和验证

学习路径建议：

1. 打好数学基础

• 学习数论基础（模运算、同余、互质等）
• 理解欧几里得算法
• 掌握费马小定理、欧拉定理

1. 了解标准密码算法

• 学习 RSA 的完整原理
• 理解为什么 RSA 安全
• 学习 AES、DES 等对称加密

1. 实践 CTF 题目

• 从简单的密码学题目开始
• 逐步提高难度
• 学习常见的攻击方法

1. 阅读密码学书籍

• 《An Introduction to Mathematical Cryptography》
• 《Applied Cryptography》
• 《Serious Cryptography》

总结

本题通过一个自定义的 RSA 变体加密算法，展示了密码学设计中的一个重要教训：不要自己发明加密算法。

我们成功利用已知明文攻击，通过扩展欧几里得定理，从两个明文-密文对中恢复出了密钥，进而解密出 flag。

整个攻击过程体现了密码分析的典型思路：

1. 理解系统的工作原理
2. 识别已知和未知信息
3. 建立数学模型
4. 寻找数学工具（扩展欧几里得定理）
5. 推导攻击方法
6. 编写脚本实现
7. 验证结果

希望通过本文的详细讲解，你能够理解整个攻击过程，掌握相关的数学知识，并在今后的 CTF 比赛和密码学学习中有所收获。

最终答案：BCTF{q0000000000b3333333333-ju57-w0n-pwn20wn!!!!!!!!!!!!}

---

免责声明：

本文所载程序、技术方法仅面向合法合规的安全研究与教学场景，旨在提升网络安全防护能力，具有明确的技术研究属性。

任何单位或个人未经授权，将本文内容用于攻击、破坏等非法用途的，由此引发的全部法律责任、民事赔偿及连带责任，均由行为人独立承担，本站不承担任何连带责任。

本站内容均为技术交流与知识分享目的发布，若存在版权侵权或其他异议，请通过邮件联系处理，具体联系方式可点击页面上方的联系我。

本文转载自：破镜安全 破镜安全《BCTF 2016 Special RSA – 从零开始的完整解题分析》