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

こんにちは、アンペンです！

今回は公開鍵暗号の王様、RSAの基礎編です。CTFの暗号カテゴリで最も登場する暗号方式であり、現実のTLS・SSH・PGPでも長年使われてきた要のアルゴリズムです。

『素因数分解の難しさ』を安全性の根拠にしているため、nが弱いと一瞬で崩れるのがCTF的に最高に楽しいポイントです。

『あんな巨大な数学が、なぜCTFでは解けるの？』——いい質問です。種明かしをすると、CTFのRSAは“わざと弱く”作られているから。本物のRSAは2048ビットという気の遠くなる桁数ですが、CTFでは『nがやけに小さい』『eが3しかない』『同じnを使い回している』といった“実装ミス”をあえて仕込んで、練習させてくれるんです。つまり解くべきは数学そのものではなく、『どんなミスが仕込まれているか』を見抜くこと。だから初心者でも、ちゃんと楽しめます。

RSAって超巨大な数学のやつでしょ？なんでCTFで解けるの？

CTFは『わざと弱いパラメータ』になっているからね。nが小さすぎる・eが小さすぎる・同じnを使い回し…そんな実装ミスをわざと作って練習させてくれるんだ。

RSAと聞くと『超巨大な数式のかたまりで、自分には無理』と身構えてしまうかもしれません。でも安心してください。RSAの“心臓部”は、たったひとつのシンプルな事実です——『2つの数を掛け算するのは簡単。でも、掛け算の答えから元の2つに戻すのは、とてつもなく難しい』。この一方通行の性質だけで、世界中の通信を守る暗号が成り立っています。今日はその仕組みと、“弱く作られたRSA”の崩し方を見ていきましょう。

RSAの仕組みをざっくり3式で

RSAは『大きな2つの素数 p, q を選んで n = p × q とする』ところから始まります。n と e の組(公開鍵)からd(秘密鍵)を作るのに p, q が必要、というのがミソ。p, q を外に出さず n だけ公開すれば、原理上 d は他人には作れません。

ここがRSAのいちばんの肝なので、もう少しかみ砕きます。p と q という2つの素数を掛けて n を作るのは、電卓で一瞬。でも、できあがった n だけを渡されて『元の p と q は何だった？』と聞かれると、桁が大きいほど絶望的に難しい。この“掛けるのは楽、割り戻すのは地獄”という非対称さこそ、RSAの安全性そのものです。逆に言えば、n さえ素因数分解できてしまえば、秘密鍵 d は芋づる式に作れて、暗号は全部開いてしまうわけです。

• 鍵生成：p, q を選び n=p×q、φ(n)=(p-1)(q-1)、d ≡ e^(-1) mod φ(n)
• 暗号化：c = m^e mod n（公開鍵 e で m を上げる）
• 復号：m = c^d mod n（秘密鍵 d で戻す）

図解：RSAの鍵と式の関係

n, e, d, p, q, φ(n) という6つの登場人物の関係さえ掴めば、後の攻撃手法はすべてこの図上で動いている話だと分かります。

登場人物が6つも出てきて頭が痛くなりますが、関係はシンプルです。公開していいのは n と e の2つだけ。p, q, φ(n), d の4つは“絶対に隠す秘密”です。そして、この秘密グループは n を素因数分解できた瞬間に、ドミノ式に全部バレてしまう。だから攻撃側の狙いはいつもひとつ——『どうにかして n を p と q に割りたい』。これから出てくる5つの攻撃も、結局はこの一点を、いろんな“弱点”から突いているだけなんです。

CTF頻出！RSA攻略5パターン

攻め方マップ

• ① factordb 照会：有名な弱いn(過去CTF出題)はDBに登録済み。まずfactordb.comに投げる
• ② Fermat法：p,qが近い場合 n=a²−b²=(a+b)(a−b) で分解。RsaCtfToolが自動でやってくれる
• ③ Low Public Exponent (e=3)：m^3 < n なら mod n の影響なし。iroot(c,3)で立方根
• ④ Common Modulus：同じ n を別のe1, e2 で使うと、ベズーの等式で gcd(e1,e2)=1 ⇒ m が復元
• ⑤ Common Factor：2つの n1, n2 が同じ p を共有 ⇒ gcd(n1, n2) = pで一発

5パターンの判別ポイントは『与えられた情報』を見るだけ。e=3が見えたら③、複数(n,c)組があれば④か⑤、と一瞬で当たりが付きます。

面白いのは、『どの攻撃を使うか』が、問題で“与えられた情報”を眺めるだけで決まってしまう点です。eが3みたいに小さければLow Exponentを疑い、同じnに対して暗号文が2つ以上配られていればCommon Modulusを疑う。料理でいえば、冷蔵庫の中身を見てメニューを決めるようなもの。RSA問題を開いたら、まず『何が渡されているか』をリストアップする——これが解答への最短ルートになります。

RsaCtfTool 1本でほぼ自動化できる

CTFのRSA問題は、RsaCtfTool(GitHub)に公開鍵PEMと暗号文を投げれば9割は自動で解けます。各種攻撃を順に試して、当たれば復号結果を吐いてくれる優れもの。

• ./RsaCtfTool.py -n <n> -e <e> --uncipher <c>
• ./RsaCtfTool.py --publickey pub.pem --uncipher c.bin
• 裏で factordb, Fermat, Wiener, Pollard などを順次試す

これに加えて、複雑な攻撃にはSageMath(数式処理系)が定番。Lattice系の応用編は#53で扱います。

『ツールが自動で解くなら、原理を学ぶ意味は？』と思うかもしれません。でも、むしろ逆です。RsaCtfToolは“なぜ解けたか”までは教えてくれないので、原理を知らないと『たまたま解けた』で終わってしまう。本番で少しひねられた問題が出たとき、手が出るかどうかは原理の理解しだいです。ツールは時短の相棒として使いつつ、『今どの弱点を突いたのか』を毎回ふり返るクセをつけましょう。

CTFでやってみよう：弱いRSAを自分で解く

ここまで“崩し方”を見てきましたが、裏返せば、そのまま“守り方”になります。CTFで頻出の敗北フラグ——nが小さい・eが小さい・nを使い回す——を、実装の段階で1つも作らないこと。それが守る側のチェックリストです。

守る側：RSAを安全に使うチェックリスト

nがちっちゃい・eがちっちゃい・nを使い回す、が全部敗北フラグなんだね。

そう。次回はRSA応用編。Wiener攻撃やCoppersmith法など、もっと数学的にエレガントな攻撃を扱うよ。

ここまでをひと言でまとめると、RSAは『nを素因数分解できれば終わり』。だから攻める側は“nの弱点”を5パターンで探し、守る側は“nを強く保つ”ことに集中する。攻守どちらも、見ているのは結局おなじ n だった——そう捉えると、ごちゃっとした攻撃名もスッキリ整理できます。

まとめ：『nが弱い5パターン』をまず疑う

今日の持ち帰りは『RSAは数学が難しいのではなく、ミスを見抜くゲーム』。本物のRSAは強固ですが、パラメータの選び方を一つ間違えるだけで一瞬で崩れます。攻める人は“渡された情報”からミスを探し、守る人は“ミスを作らない”。この視点さえあれば、次のRSA応用編もぐっと楽に読めますよ。

次回はRSA応用編、Wiener・Hastad Broadcast・Coppersmithといった、Lattice(格子)を使うエレガントな攻撃を扱います。

次に読みたい記事

参考資料