2026.05.25

【RSA応用編】Wiener・Hastad Broadcast・Coppersmithで殴る｜CTF思考フレームワーク #53

安全に生きたい編集部

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

RSA応用って、もっと複雑な攻撃があるの？🎯

あります。Wiener攻撃（dが小さいケース）、Hastad’s Broadcast攻撃（複数公開鍵で同じ平文）、Coppersmith攻撃（部分既知平文）――現代暗号研究の成果が CTF 問題として出題されます。数学が深いほど面白い分野です。

RSA応用攻撃には、Wiener Attack（d < N^0.25 のとき連分数で d を復元）、Hastad’s Broadcast Attack（小さい e と複数 N で中国剰余定理）、Coppersmith Attack（LLL格子簡約で部分既知平文から復元）など、高度な手法があります。Sage/Python ライブラリで実装可能。

格子簡約とか、数学が本格的になってきた…

この記事は、CTF思考フレームワーク第53回。RSA応用攻撃（Wiener・Hastad・Coppersmith・Common Modulus・Boneh-Durfee）の数学的背景と、Sage/Pythonでの実装、CTF典型問題のパターンを整理します。

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

🧮 RSA応用編は格子・連分数・近似解の世界。Wiener、Hastad Broadcast、Coppersmith。数学の道具箱を増やすほど、Cryptoカテゴリの「ちょっと特殊なRSA」を一網打尽にできます。

RSAは「条件付きで穴がある」暗号。dが小さい、eが小さくmが小さい、平文の上位ビットが既知、N同士に関連がある——どれも特定の数学テクで殴れます。

難易度：★★★（上級）

Wiener・Hastad Broadcast・Coppersmithの攻め方を学びます🧮

RSA応用攻撃は「特殊条件で成り立つ高度な数学」。CTFの本格暗号問題はここから🧮

この記事で出てくる言葉

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

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

Contents

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

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

攻略のヒントは「dが小さい」「平文の一部が既知」「同じ平文を複数Nで暗号化」などの条件!🔍

パラメータ観察：基礎編で割れなかったRSAは、d/e の比、複数暗号文の関係、平文に既知部分があるか、Nの構造（pとqの近さや特殊形）を見直します。

d < N^0.25 → Wiener攻撃
同一m、異なるN3つ（e=3） → Hastad Broadcast
平文の高ビットが既知 → Coppersmith / Stereotyped Message
p高ビット既知 → Coppersmith Factorization
N = p*q で p, q が特殊形（p = 2*q+1等）
パディングなし署名と暗号化兼用 → 既存攻撃多数

d < N^0.25ならWiener、高位ビット既知ならCoppersmith、同平文×複数NならHastad Broadcastです👀

応用攻撃は「数学的特殊条件」を見抜けるかが勝負だね💡

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

RSA応用の典型は4方向。

🕶️ 出題者は「現実の実装ミス」を再現します。鍵生成時に強度設定を間違えてdが小さい、eを下げて高速化したらHastadに当たる、平文に既知prefix（”FLAG{“）が含まれる、など。攻撃側はSageのsmall_roots一発で済むことも多いです。

🎯 仮説①：Wiener攻撃

秘密指数dがN^0.25未満だと連分数展開でdを復元可能。

📐 仮説②：Coppersmith

Nの素因数の高位ビットが一部既知、または平文の高位ビット既知でLLLにより復元。

📡 仮説③：Hastad Broadcast

同じ平文をe=3で3つの異なるNで暗号化されると中国剰余定理で復元。

🤖 仮説④：Boneh-Durfee

Wienerの拡張でd < N^0.292まで対応可能。

CTFでは「N、e、dの関係」と「与えられた追加情報」から手筋を選ぶんだね💡

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

SageMathのsmall_roots()でCoppersmithが書ける。RsaCtfToolにも組込み済み🧪

攻撃のほとんどはSageMathのsmall_roots（Coppersmithを内部で実行）かWienerの連分数。ライブラリ（RsaCtfTool）も豊富で、まず自動化してから理解を深めるのが効率的。

# Sage: Coppersmith で平文の上位ビット既知
R. = PolynomialRing(Zmod(N))
f = (m_high * 2^k + x)^e - c
roots = f.small_roots(X=2^k, beta=1.0, epsilon=0.05)
print(roots)

# Wiener attack（連分数）
from Crypto.Util.number import inverse
# e/N の連分数収束分母から d を試す

これらの攻撃は数学を理解しないと使いこなせないから、教科書とCTF両輪で学ぶのが良いね📚

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

RSA応用攻撃の使いどころトップ3。

応用攻撃：①Wiener（dが小さい）、②Hastad Broadcast（同一m・異なるN・小e）、③Coppersmith Stereotyped（平文一部既知）、④Franklin-Reiter（線形関係のある2平文）、⑤Boneh-Durfee（Wiener拡張）。

# Hastad Broadcast: e=3, 同一m, 3組(N,c)
from sympy.ntheory.modular import crt
N_list = [N1, N2, N3]
c_list = [c1, c2, c3]
x, _ = crt(N_list, c_list)
from gmpy2 import iroot
m, ok = iroot(x, 3)
if ok: print(m)

実務での悪夢：CIスクリプトで鍵生成スクリプトの引数を間違え、社内全サーバが共通N要素を持っていた、なんて事例も。鍵生成は枯れた関数を使う以外の選択肢なしです🚫

① 小d攻撃(Wiener)

実装ミスで秘密指数が極端に小さいとWiener一発。古い暗号製品で実例あり。

② 部分既知Coppersmith

平文構造の一部が既知(例: flag{...})で未知部分が小さいと復元可。

③ Broadcast Hastad

同じメッセージを多くの相手にe=3で配信するシステムは即破られる。

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

RSA応用攻撃を防ぐ3鉄則！🛡️

応用攻撃の根本対策は「ちゃんとした鍵生成・パディング・OS提供のCrypto APIを使う」。自作実装はほぼ常にどこかで穴をあけます。

鍵生成はOS/標準ライブラリのみ（OpenSSL / libsodium等）
RSA-OAEP / PSSを必ず使い、textbookは絶対避ける
同一m・異なるN・小eを許す設計を回避（パディングで自動回避）
d 小化・e 小化を性能チューニング目的で行わない
CryptoライブラリのCVE追跡（HeartbleedやROBOTのような事例）
長期的にPQC移行（Kyber / Dilithium等）の準備

🔢 d は十分大きく

dを小さく取る最適化は絶対NG。CRT-RSAでも各p-1,q-1関連の指数は十分な大きさを確保。

🧂 必ずランダムパディング

OAEP/PSSのような確率的パディング。同じ平文でも毎回異なる暗号文になり、Broadcast/Coppersmithが効かない。

🔁 鍵ペアの独立生成

マルチユーザーで同じe・近接Nを生成しない。Fermat攻撃やROCAも避けられる。

「特殊条件を作らない」が応用攻撃対策の本質💪

⚠️ よくある落とし穴

自作RSAでパディングを省略して教科書のまま実装
マルチユーザシステムでN生成が乱数源弱く、共通要素が出る
eを3や17にして高速化、Hastad/Coppersmithの餌食
平文に固定prefix（”USER:” 等）を付けて、Stereotyped前提を満たす
Sage / SageMathの環境構築を諦めて手動でCoppersmith再実装ミス
PQC移行計画を後回しにして暗号資産が長期間Harvest-Now-Decrypt-Later対象に

🧰 ツール早見表

ツール	用途	備考
SageMath	Coppersmith・LLL	応用RSAの主戦場
RsaCtfTool	既知攻撃の自動試行	初手の網羅自動化
gmpy2	高速整数演算	Pythonから使う
Crypto.Util.number	inverse・gcd等	PyCryptodome
cocks2.sage / coppersmith.sage	CTF常備レシピ	GitHubで多数公開