📌 前言

在密碼學的發展史中，RSA 是第一個同時能用於「數據加密」與「數位簽章」的非對稱加密演算法。今天我們將從 RSA 的數學基礎切入，分析其潛在的安全弱點，並透過 picoCTF / CyLab 平台上的 Mini RSA 題目，示範如何利用 Python 自動化腳本攻破配置不當的小公鑰指數（Small Exponent Attack）。

💡 RSA 演算法數學原理

RSA 的安全性建立在大整數的質因數分解困難度上（Factoring Problem）。其運作流程如下：

1. 金鑰生成（Key Generation）

1. 隨機選擇兩個大質數 p 與 q。
2. 計算模數（Modulus）：N = p × q
3. 計算歐拉函數（Euler's Totient Function）：φ(N) = (p - 1)(q - 1)
4. 選擇一個與 φ(N) 互質的公鑰指數 e（常取 e = 65537 或 e = 3）。
5. 計算私鑰指數 d，滿足模逆元關係：d × e ≡ 1 (mod φ(N))

• 公鑰 (Public Key)：(N, e)
• 私鑰 (Private Key)：(N, d)

2. 加密與解密 (Encryption & Decryption)

• 加密：將明文 M 轉為整數，計算密文 C：C ≡ M^e (mod N)
• 解密：使用私鑰 d 還原明文 M：M ≡ C^d (mod N)

🎯 漏洞原理：小公鑰指數攻擊 (Small Exponent Attack)

當公鑰指數選擇過小（例如 e = 3），且明文 M 的長度較短或未添加足夠強度的隨機填充（Padding，如 OAEP）時：

1. 如果 M^e < N，則在加密過程中根本沒有發生模數溢位（Modulo Operation）：
   C = M^e
   此時只要直接對密文 C 開 e 次方根即可還原明文：
   M = 💡(C 的 e 次方根)

2. 如果 M^e 稍微超過 N（即溢位了 k 次），其關係式可表示為：
   C = M^e - k × N => M^e = C + k × N
   只要爆破小範圍的整數 k（k = 0, 1, 2, ...），並檢查 C + k × N 是否能精準開 e 次整數方根，就能輕鬆求得明文 M。

🚩 實戰解題：Mini RSA

• 題目來源：picoCTF 2021 / CyLab Security Academy
• 題目難度：Medium
• 題目說明：題目給定了一個 values 檔案，內容包含巨大的 $N$、小公鑰指數 $e = 3$ 以及密文 $C$。

1. 自動化解題腳本 (solve_minirsa.py)

為了處理超大整數的高精度計算，我們使用 Python 的 gmpy2 模組中的 iroot 函數，配合 pycryptodome 將整數轉換回明文字串。

import gmpy2
from Crypto.Util.number import long_to_bytes
import urllib.request

# 1. 下載題目提供的數值檔案
url = "[https://challenge-files.cylabacademy.net/library/e5f3ed71ca30832720bfbed988000b07159531af4efd8bde534455cb31281df7/values](https://challenge-files.cylabacademy.net/library/e5f3ed71ca30832720bfbed988000b07159531af4efd8bde534455cb31281df7/values)"
print("[*] 正在下載 values 檔案...")
urllib.request.urlretrieve(url, "values.txt")

# 2. 解析檔案內容 (相容各類欄位格式)
data = {}
with open("values.txt", "r") as f:
    for line in f:
        line = line.strip()
        if ":" in line:
            key, val = line.split(":", 1)
            data[key.strip().lower()] = int(val.strip())

N = data['n']
e = data['e']
c = data['ciphertext (c)']

print(f"[*] 解析成功！N 長度: {N.bit_length()} bits, e: {e}")
print("[*] 開始嘗試 Small Exponent (e=3) 開幾次方根爆破...")

# 3. 爆破 k 值並進行整數開三次方根
found = False
for k in range(100000):
    val = c + k * N
    root, is_exact = gmpy2.iroot(val, e)
    
    if is_exact:
        flag_bytes = long_to_bytes(int(root))
        print(f"\n[+] 成功找到整數次方根！k = {k}")
        print(f"[🎯] 解密結果 (Flag): {flag_bytes.decode('utf-8', errors='ignore')}\n")
        found = True
        break

if not found:
    print("[-] 未在範圍內找到結果。")

2. 執行結果

在 WSL (Ubuntu) 環境下執行：

python3 solve_minirsa.py

輸出畫面：

[*] 正在下載 values 檔案...
[*] 解析成功！N 長度: 3340 bits, e: 3
[*] 開始嘗試 Small Exponent (e=3) 開幾次方根爆破...

[+] 成功找到整數次方根！k = 0
[🎯] 解密結果 (Flag): academy{e_sh0u1d_b3_lArg3r_35f26e1a}

Flag: academy{e_sh0u1d_b3_lArg3r_35f26e1a}