【楕円曲線・近代暗号編】ECDH・ECDSA・Smart’s Attackの世界｜CTF思考フレームワーク #57

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

今回は暗号章の最終回、楕円曲線暗号(ECC)。ECDH/ECDSAをはじめ、近代暗号で広く採用されている方式の入門+CTF頻出攻撃をまとめます。

ECCという略称はなじみが薄いかもしれませんが、実はあなたのスマホやブラウザ、BitcoinやメッセージアプリのE2E暗号化まで、いまや“近代暗号の主役”です。RSAという大ベテランがいるのに、なぜ新顔が主役を奪ったのか。キーワードは『軽さ』。同じ強さなら、ECCはRSAよりずっと短い鍵で済み、計算も速い。電池やCPUに限りがあるスマホ・IoT時代に、ぴったりだったわけです。

RSAより楕円曲線がいいって聞くけど、何が違うの？

同じ強度なら鍵が短い・計算が速い。RSA-3072 ≒ ECC-256 くらいのコスパ。ただし曲線選択ミスで簡単に崩れる落とし穴もあるんだ。

『楕円曲線』なんて聞くと、数学アレルギーが疼くかもしれません。でも大丈夫、中身のイメージはとてもシンプルです。曲線の上を“決まった規則でジャンプして進む”ゲームだと思ってください。スタート地点も、ジャンプの仕方も、ゴール地点も全部公開。なのに『何回ジャンプしたか』だけは誰にも分からない——この“回数の秘密”が、そのまま秘密鍵になります。今日はその仕組みと、つまずきやすい落とし穴を見ていきましょう。

楕円曲線って何？(超ざっくり)

楕円曲線は y² = x³ + ax + b という方程式を満たす点の集まり。ここに『点同士の足し算』というルールを定義することで、有限の世界での『離散対数問題』を構成します。整数の掛け算より遥かに効率的に、同等の安全性を実現できるのが特徴です。

ここでひっかかりやすいのが『点同士の足し算』という言葉。普通の足し算とは違い、これは“曲線の上で定義された独自ルールの操作”です。2つの点を通る直線を引いて、曲線とぶつかる3つ目の点を見つけて…という幾何学的な手続きなのですが、細かい計算は道具がやってくれるので心配いりません。大事なのは『点と点を“足す”と、また曲線上の別の点になる』というルールがある、という一点だけ押さえればOKです。

図解：ECC vs RSA の鍵長対比

同じ攻撃耐性で必要な鍵長を比べると、ECCの軽量さがよく分かります。モバイル端末・IoT・TLS高速化の主役になっている理由です。

なぜ短い鍵で同じ強さが出るのでしょう。ざっくり言うと、楕円曲線の“ジャンプの迷路”を逆にたどる方法が、素因数分解よりもさらに見つかっていないからです。攻撃の近道が少ないぶん、小さい鍵でも十分な安全を保てる。RSA-3072とECC-256がほぼ同じ強度、というのはその表れです。鍵が短いと保存も通信も署名も軽くなるので、回線やバッテリーにやさしい——これがモバイル時代にECCが選ばれた理由なんです。

ECDH と ECDSA の超要約

では、この“ジャンプの秘密”を、実際の通信でどう役立てるのか。代表が2つあります。鍵交換の『ECDH』と、署名の『ECDSA』。どちらも『P = k·G（Gをk回ジャンプした点がP）』という同じ土台の上に立っています。難しそうに見えても、骨組みは“ジャンプ回数を秘密にする”という一点。そう思って次の要約を読むと、すっと入ってきますよ。

• ECDH(鍵交換)：Alice が a, Bob が b を秘密に持ち、公開鍵 A=a·G / B=b·G を交換 → 共有鍵 a·B = b·A = ab·G
• ECDSA(署名)：乱数 k、署名 r=(k·G).x mod n、s=(hash+r·d)/k mod n。鍵 d, 公開鍵 P で検証可能
• EdDSA(Ed25519):k を決定的に生成、より安全。Curve25519上で動く

ECDHの面白さは『一度も秘密を送り合っていないのに、二人だけの共通の鍵ができる』ところ。たとえるなら、AliceとBobが別々のバケツに自分だけの絵の具を混ぜ、公開の場で交換し合い、最後にもう一度それぞれ自分の絵の具を足すと——不思議と二人だけが同じ色になる。外から見ている人は、交換された“途中の色”からは最終的な色を逆算できない。これが鍵交換の魔法で、楕円曲線はその“絵の具”を効率よく扱う仕組みなんです。

ここからは“崩し方”です。といっても、楕円曲線そのものが弱いわけではありません。崩れるのはたいてい『変な曲線を選んだ』『実装でうっかりした』とき。つまり攻撃の大半は、数学の正面突破ではなく、“選択ミス・実装ミス”を突くものなんです。

CTF頻出 3攻撃

曲線選択ミス・実装ミスを突く

• Smart’s Attack：曲線位数=素数pと一致(anomalous curve)→離散対数が線形で解ける
• MOV/Frey-Rück Attack：埋め込み次数が小さい曲線→有限体の離散対数に帰着(易化)
• ECDSAのk再利用：2つの署名で同じkを使うと d = (s1·h2 − s2·h1)/(r·(s1−s2)) で秘密鍵 d が即座に求まる
• Invalid Curve Attack：不正な曲線上の点を投げて小位数部分群に押し込み、秘密鍵をビット単位で漏らさせる

『k再利用』はSony PS3鍵漏洩の原因として有名。標準実装(libsodium/ECC libraries)に任せれば回避できます。

中でも『k再利用』には、有名な実例があります。かつてSony PS3が、本来“毎回変えるべき使い捨ての乱数k”を固定してしまい、署名2つを突き合わせるだけで秘密鍵が丸ごと抜かれた事件です。署名のたびにkを必ず作り直す——たったこれだけのことを怠ると、屋台骨ごと崩れてしまう。逆に言えば、kを決定的かつ安全に作るEd25519を使えば、この罠は最初から踏みようがないんです。

CTFでやってみよう：k再利用で秘密鍵を抜く

ここまでの落とし穴を見れば、守り方は自然と見えてきます。楕円曲線は『道具選びが9割』。曲線も実装も、世界中の専門家に検証され尽くした“ド定番”を選ぶ。それだけで、今回の攻撃はほぼ出番を失います。

守る側：『標準曲線+標準実装』で完封

Ed25519使っとけば概ね安心ってこと？

そう。これで暗号章は完結。次回からは新章Pwn編。x86アセンブリと関数呼び出し規約から始めるよ。

これで暗号章は完結です。古典暗号から始まり、RSA、AES、ハッシュ、そして楕円曲線まで——通底していたのは『アルゴリズム自体より、使い方とパラメータで強さが決まる』という一点でした。楕円曲線も同じで、本体は超強力。あとは“正しい曲線を、正しいライブラリで”使うだけなんです。

まとめ：『短い鍵・速い計算・標準曲線』

今日の持ち帰りは『ECCは強い。崩れるのは、たいてい選び方のせい』。短い鍵で軽くて速い、現代のスタンダードです。だからこそ自作に走らず、Curve25519やEd25519のような“枯れた定番”に乗る。その一歩が、いちばん確実な守りになります。お疲れさまでした、これで暗号章は卒業です。

次回からはPwn編。x86/x64アセンブリと関数呼び出し規約を整理します。

次に読みたい記事

参考資料