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

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

今回はRSA応用編。Wiener攻撃・Hastad Broadcast攻撃・Coppersmith法といった、数学的に少しエレガントな攻撃を扱います。共通点は『パラメータの極端さ』を突くこと。

『基礎編で出てこなかったけどCTFで頻出』を埋める回。SageMathを覚えると一気に世界が広がります。

ここで発想を切り替えましょう。基礎編の攻撃は“正面突破”——nを力ずくで割る方法でした。でも応用編は“からめ手”です。『dを節約して小さくした』『同じ手紙を複数の相手に同じ方式で送った』『平文の中身がほとんど分かっている』——こうした“運用上のうっかり”さえあれば、nがどれだけ巨大でも関係なく崩せる。狙うのは数の壁ではなく、人間が作りこんだ隙、というわけです。

nが2048bitでも、別の弱さがあれば崩せるの？

うん。dが小さすぎる(Wiener)・同じ平文を複数公開鍵に送る(Hastad)・平文の一部が既知(Coppersmith)──こんな条件があると、nがどれだけ大きくても破れるんだ。

基礎編では『nを素因数分解できれば勝ち』でした。でも、nが2048ビットもあると素因数分解は事実上不可能。じゃあお手上げかというと——そうではありません。錠そのものは頑丈でも、鍵の“作り方”がずさんなら、そこから崩せるんです。今回の3つの攻撃は、まさに『鍵やパラメータの偏り』という別の隙を突く手口。nの大きさとは別の弱点を狙う、という発想の転換がテーマです。

3つの応用攻撃の使いどころ

応用攻撃は『どの情報が与えられているか』で選びます。問題文を見た瞬間に当たりが付くようになるとCTFが楽しいです。

図解：攻撃選択マトリクス

『eが異常に大きい→Wiener』『同じmが複数のnへ→Hastad』『平文の一部が分かっている→Coppersmith』というのが大まかな指針です。

3つを一言ずつ整理しておきましょう。Wienerは『鍵dをケチって小さくしすぎた』スキを突く攻撃。Hastadは『同じ中身を、弱い設定で何人にも送った』スキを突く攻撃。Coppersmithは『答えがほとんど分かっていて、あと少しだけ未知』なときに、その“あと少し”を数学で埋める攻撃です。共通するのは、どれも“ちょっとした油断”を、数学のテコでこじ開けているという点なんです。

Wiener攻撃：dが小さい時の連分数攻め

RSAは d を大きく取るのが普通ですが、運用都合でd < N^(1/4)のような小さい値を選ぶと、e/n の連分数展開から d が復元されてしまいます。

なぜdが小さいと危険なのでしょう。RSAでは、dを小さくすると、ペアになるeが逆に巨大になります。つまり『eがやけに大きい』のは、裏で『dが小さい』ことの目印なんです。そしてdが小さいと、e/nという分数を“連分数”という形でほどいていく途中に、ぽろっとdが顔を出してしまう。計算を速くしようとdを節約した結果、鍵そのものが漏れる——“近道は罠”の典型例ですね。

• 判別ポイント：e が n と同じくらい大きい(普通は e=65537 で済むので異常)
• 解法：e/n の連分数を展開、各収束分数 k/d を試す
• 進化版：Boneh-Durfee攻撃(d < N^0.292 まで対応・Lattice利用)

Hastad Broadcast：同じ平文を複数公開鍵に送る

同じ平文 m を、e=3 の3つの異なる公開鍵 (n1,n2,n3) に同時送信した場合、中国剰余定理(CRT)で m^3 mod (n1·n2·n3) が復元できます。3つのnの積より m^3 が小さければ立方根で m が出ます。

ここが直感に反して怖いところ。中身を秘密にしたいのに、『同じ手紙を、弱い設定（e=3）で3人に送った』だけで、盗聴者は鍵を一切知らないまま中身を復元できてしまうんです。1通だけなら立方根が大きすぎて解けないのに、3通そろうと“中国剰余定理”というパズルのピースが噛み合って、急に解けてしまう。だから『パディングを付けて毎回違う暗号文にする』ことが、こんなにも大事になるわけです。

• 判別ポイント：e=3 が小さく、3つ以上のn,cの組がある
• 解法：CRT で m^3 mod ΠN を求め、整数論理で立方根
• パディングなしの古いRSAで起きる典型攻撃

Coppersmith法：『平文の一部が既知』を突く

Coppersmith法は、『mod nで小さい根を見つける』ためのLattice技法。RSAでは『定型文(Stereotyped Message)の一部が既知』『pの上位ビット既知』などのケースで活躍します。

『平文の一部が既知』——これがなぜ致命傷になるのか、ピンと来ないかもしれません。たとえば暗号文の中身が『Password: ????』のように、形式は分かっていて末尾だけ未知、というケース。普通なら未知部分を総当たりするしかありませんが、Coppersmith法を使うと、その“未知のかたまり”を1つの変数として、Latticeという数学のふるいで一気に絞り込めるんです。『少しだけ知っている』が『全部分かる』に化ける——これが格子攻撃の恐ろしさです。

• Stereotyped Message：“Password: ____” のように一部既知 → 未知部分を変数化して根を探す
• Partial Key Exposure：p, q の一部ビットが漏れた → 残りを復元
• Short Pad：同じ平文を2回違うパディングで暗号化 → 平文ごと復元
• 定番実装：defund/coppersmith (SageMath用)

CTFでやってみよう：Wienerを自分の手で動かす

では守る側へ。3つの攻撃はバラバラに見えて、防御の急所は実は重なっています。『dをケチらない』『毎回ランダムなパディングを付ける』『標準ライブラリに任せる』——この数点を守るだけで、今回の攻撃はまとめて封じられます。

守る側：応用攻撃を封じる4つの実装規律

RSAって奥が深いね…そして『独自実装はやめろ』に毎回行き着く。

その通り。次回はもう一つの大物、AESの入門編。ECB/CBC/Padding Oracleを扱うよ。

ここまでをひと言でまとめると、応用攻撃は『nの大きさではなく、パラメータの偏りを突く』。だから守る側の合言葉は“極端を作らない”です。dも、パディングも、平文の出し方も、すべて“ふつう・標準・ランダム”に寄せておけば、これらのエレガントな攻撃は出番を失います。

まとめ：『パラメータの偏り』を突く3攻撃

今日の持ち帰りは『頑丈な錠でも、鍵の作り方しだいで台無しになる』。RSAは正しく使えば極めて強い暗号ですが、最適化や手抜きで“偏り”を作った瞬間、数学の刃が入る隙が生まれます。攻める人は偏りを探し、守る人は偏りを消す。この一点で、応用編の攻撃はすべて見通せます。

次回はAES入門編、ECB・CBC・パディングオラクルの基本攻撃を扱います。対称鍵暗号の世界へ。

次に読みたい記事

参考資料