2026.05.25

【RSA基礎編】素因数分解・小さい指数・Common Modulusの攻め方｜CTF思考フレームワーク #52

安全に生きたい編集部

広告・PRを含みます。この記事にはアフィリエイトリンクが含まれます。掲載内容は編集方針に基づいて作成していますが、価格・在庫・キャンペーン内容はリンク先で最新情報を確認してください。

RSA暗号って、銀行のサイトのHTTPSで使われてるやつ？仕組み難しそう…🔐

はい、HTTPSや署名の基本。RSAは『素因数分解の難しさ』に依存した暗号で、原理は実は数学的にシンプル。CTFでは弱い設定（小さい鍵・素数の偏り・指数の小ささ）を突く問題が定番です。

RSA暗号は、1977年に発表された公開鍵暗号の代表。HTTPS・SSH・GPG・電子署名の基礎を支えます。安全性は『大きな数の素因数分解は困難』という前提に依存。CTFでは『小さいN』『eが小さい』『同じNを複数で共有』など、弱い設定での解読が頻出問題です。

数学的な仕組みなのね…でも、設定ミスで破られるんだ。

この記事は、CTF思考フレームワーク第52回。RSA暗号の基本（鍵生成・暗号化・復号）と、CTFで頻出の解読パターン（素因数分解・小さい指数・Common Modulus・Hastad）を、初心者向けに整理します。

📖 この記事はシリーズの一部です
「CTF思考フレームワーク」 #52 / 全86記事　→　シリーズ一覧を見る →

🔐 RSAは「素因数分解の困難性」を信頼の根拠にした暗号。NとeとcからmをどうやってMod指数で復元するか、CTFでは小さなパラメータの隙を突くパズルが出題されます。

RSA暗号の典型攻撃は、N が小さくて分解できる、e が小さすぎる（e=3）、複数の暗号文（同一m・異なるN）が揃う、などのパラメータ起因の弱さがほとんどです。

難易度：★★☆（中級）

素因数分解・小さい指数・Common Modulusの攻め方を学びます🔑

RSAは「大きな合成数の素因数分解の困難性」に依存。逆に言えば、ナメた使い方をすると即崩壊🔑

この記事で出てくる言葉

先に意味を押さえておくと読みやすい用語です。

CTF: セキュリティの練習問題を解く競技。必ず許可された環境だけで試します。
脆弱性: ソフトや仕組みにある弱点。攻撃者に悪用されると不正アクセスにつながります。
暗号: 情報を第三者に読まれにくい形へ変換する技術です。

Contents

👀 観察フェーズ：まず何を見る？
🤔 仮説フェーズ：攻撃者は何を考える？
🔬 検証フェーズ：どうやって確かめる？
⚔️ 攻撃フェーズ：実際の手口
🛡️ 防御フェーズ：どう守る？
⚠️ よくある落とし穴
🧰 ツール早見表
🎓 本気で学びたい人へ
📚 もっと深く学びたい人へ
📚 次に読みたい
✍️ 学んだことを発信する
⚖️ 大事なお約束

👀 観察フェーズ：まず何を見る？

N(モジュラス)、e(公開指数)、c(暗号文)の3要素を観察！特にNとeの取り扱いがヒント🔍

まずパラメータ（N, e, c）を観察。Nのbit長、eの値、cが複数あるか、Nが共通要素を含むかをチェック。

Nのbit長（512bit以下なら現実的に分解可能）
eの値（3 / 65537が一般的、他は要警戒）
cの個数（複数c×同一m があればHastad）
N同士のGCD（共通素因数攻撃）
N = p * q で p ≒ q ならFermat
d の小ささ（Wienerの伏線）

Nが512bit以下、eが3、複数同じNで違うeを使ってる…どれもアウトのサインです👀

RSAって「Nを正しく作ること」がスタートで、ここで油断すると終わるんだね💡

🤔 仮説フェーズ：攻撃者は何を考える？

RSA基礎攻撃の典型は4パターン。

🕶️ 攻撃者は「Nを分解する」ルートを最優先で探します。FactorDB引き直し、Fermat、Pollard rho、ECM。それで割れなければ「e の小ささ」「複数暗号文の関係」「PKCS#1パディング」など、関数の使い方の弱点に視点を移します。

🔢 仮説①：素因数分解

Nが小さい(〜512bit)ならFactorDB / Yafu / msieveで因数分解できてしまう。

🌱 仮説②：低指数攻撃(e=3)

e=3で平文が小さい場合、c = m^3 mod Nがmodを跨がず単純な3乗根で解ける。

🔁 仮説③：Common Modulus

同じNで異なるe1,e2と暗号文c1,c2が手に入ると拡張ユークリッドで平文復元。

🎯 仮説④：低公開指数 with パディングなし

PKCS#1パディングなしの教科書RSAは乗算的性質で破られる。

RSAは「教科書の式」と「実装の式」が違うことを覚えておこう💡

🔬 検証フェーズ：どうやって確かめる？

RsaCtfToolを流せば既知攻撃のほぼ全部を自動試行してくれる。CTFでは最強🧪

まずFactorDB（既知Nのデータベース）に投げる。そこで割れたら一瞬で終わり。割れなければsage / sympyでpollard / fermat / ecmを試す流れ。

# FactorDBにオンライン照会
# https://factordb.com

# Pythonで小Nを分解
from sympy import factorint, gcd
N = 12345...
print(factorint(N))  # 小さければ即出る

# 共通要素：複数Nのペアワイズgcd
from math import gcd
for i, Ni in enumerate(N_list):
    for Nj in N_list[i+1:]:
        g = gcd(Ni, Nj)
        if g not in (1, Ni):
            print("Found:", g)

SageMathでfactor(N)から始めるのも基本だね💡

⚔️ 攻撃フェーズ：実際の手口

RSA基礎の崩し技トップ3。

基本攻撃：①小N分解、②Fermat（p≒q）、③共通N要素、④e=3 で m が小さい→立方根、⑤Common Modulus（同一N、異なるeで同じmを暗号化）。

# e=3 + 小m → 立方根
from gmpy2 import iroot
m, ok = iroot(c, 3)
if ok: print(m)

# Common Modulus攻撃（同一N、e1とe2が互いに素）
from sympy import gcdex
g, a, b = gcdex(e1, e2)
# m = c1^a * c2^b mod N
m = pow(c1, a, N) * pow(c2, b, N) % N

Padding付きRSA（PKCS#1 v1.5）はBleichenbacher攻撃の標的。CTFでは生RSA（textbook RSA）が多いですが、実務ではOAEPに移行しているはずです🔑

① FactorDBで一発

NをFactorDBにペースト。既に分解済みなら即答え。

② Hastad Broadcast

同じ平文を3つの異なるNでe=3暗号化されたら、CRT+3乗根で復号可。

③ Common Modulus攻撃

同じNでgcd(e1,e2)=1なら、s,t を計算してc1^s × c2^t = m mod N。

🛡️ 防御フェーズ：どう守る？

RSA安全運用の3鉄則！🛡️

RSA運用の基本：鍵長は最低2048bit、推奨3072bit以上、e=65537固定、パディングはOAEP/PSS。署名検証時に必ず公開指数とパディングをチェック。

鍵長 2048bit以上（NIST 2030年以降は3072bit）
e は 65537（小e攻撃を回避）
暗号化は RSA-OAEP、署名は RSA-PSS
署名検証時にパディングを厳密チェック
同一鍵を暗号化と署名で兼用しない
長期的にはハイブリッド（PQC）への移行計画

🔒 N >= 3072bit

NIST推奨は2048bit以上、新規なら3072〜4096bit。512bitは現代では即終わる。

🔢 e = 65537 + パディング必須

公開指数はe=65537、暗号化はOAEPパディング。署名はPSS。

🛡️ 鍵の使い回し禁止

Common Modulus等の合体攻撃を防ぐため、鍵ペアごとに独立したNを生成。

「教科書RSAは絶対使わない」。これだけ守れば現代では破られない💪

⚠️ よくある落とし穴

Textbook RSAを本番に使う（OAEPなしは平文情報が漏れる）
eを3や17にして実装を簡素化
鍵生成で乱数源が弱く、p や q が他鍵と共通
署名検証でパディングOIDを見逃す（Bleichenbacher e=3）
Common Modulusで同一NをユーザごとにeだけずらしてOK判定
d（秘密指数）を小さくしてWiener攻撃の餌食

🧰 ツール早見表

ツール	用途	備考
FactorDB	既知N検索	最初に必ず叩く
sympy.factorint	Python整数分解	~50bit以下なら即
SageMath	Coppersmith・LLL等	本格Crypto向け
RsaCtfTool	RSA脆弱性網羅	初手の自動化
Wiener Attack lib	d小・連分数攻撃	d < N^0.25 で有効