近年、楕円曲線暗号（Elliptic Curve Cryptography）は、その高い効率性と強力なセキュリティにより人気が高まっています。この記事の目的は、現在インターネット上にあるものよりも比較的分かりやすい形でこのテーマを紹介することです。
この記事では、楕円曲線とは何か、それらに対して実行できる基本的な演算、そして暗号の文脈でどのように使用できるかを説明します。記事の大部分は、誤った実装や誤った使用法に対する既知の攻撃の例で構成されています。記事全体を通して、説明を直感的で高水準な部分と、より詳細な数学的な部分に分けるようにしています。読者は、その場所で自分が興味を持った方の部分に集中し、そうでない部分は読み飛ばすことができます。
それでは、楽しくお読みください！
一般に、楕円曲線はある種の曲線です。その例として放物線があり、その方程式は $𝑦 = 𝑎𝑥^2 + 𝑏𝑥 + 𝑐$ の形をしており、次のように見えます：
暗号の文脈では、次の形の方程式を持つ楕円曲線を使用するのが通例です。
$𝑦^2 = 𝑥^3 + 𝑎𝑥 + 𝑏$
例えば、方程式 $𝑦^2 = 𝑥^3 − 3𝑥 + 3$ に対応する楕円曲線は次のように見えます：
曲線の方程式は、曲線上の点の 𝑥 座標とその 𝑦 座標の間の関係を定義します。暗号の文脈では、𝑥、𝑦、𝑎、𝑏 を整数に制限し、計算をある大きな素数を法とするものに制限します。したがって、楕円曲線の方程式は次のようになります：
$𝑦^2 = 𝑥^3 + 𝑎𝑥 + 𝑏\ \ \ \ (mod\ 𝑝)$。
これは、曲線上に有限個の点があることを意味します。数学的な言葉で言えば、この曲線は位数 𝑝 の有限体上で定義されます。その結果、すべての 𝑥 座標が必ずしも曲線上の対応する点を持つとは限りません。なぜなら、それに対応する 𝑦 座標が整数でない場合があるからです。
曲線上の点の集合は、曲線の方程式を満たす整数のペア (𝑥, 𝑦) から構成されます。これらの点に加えて、「無限遠点」と呼ばれる特別な点が定義され、𝒪 と表記されます。数学的な言葉で言えば、この点は、次のセクションで定義する加算演算に関して、曲線上の点の集合の単位元です。曲線上の点の数（点 𝒪 を含む）は「曲線の位数」と呼ばれます。
もう1つの観察として、楕円曲線は X 軸に対して対称です。つまり、点 𝑃 = (𝑥, 𝑦) が曲線上にあるならば、点 −𝑃 = (𝑥, −𝑦) も曲線上にあります。実際、これらの点は互いの「逆元」と見なされ（したがって2番目の点に −𝑃 と表記します）、それらの間の加算演算の結果は単位元 𝒪 と定義されます。
ハッセの定理と呼ばれる定理は、曲線の位数である #𝐸 の推定値を提供し、その桁は Θ(𝑝) です。より正確には：
$𝑝 + 1 − 2\sqrt𝑝 ≤ 𝐸 ≤ 𝑝 + 1 + 2\sqrt𝑝$
曲線上の2つの点が与えられたとき、それらの間の加算演算を定義でき、その結果は曲線上の3つ目の点になります。この点を幾何学的に見つけるには、与えられた2つの点の間に直線を引き、それが曲線と3つ目の点で交差するまで延長します。この点を 𝑋 軸に関して反転させ、その結果得られる点が加算の結果として定義されます。
以下は、点 𝑃 と 𝑄 が与えられたときに、点 𝑃 + 𝑄 をどのように見つけるかを示す図です：
この説明から生じる疑問は、2つの点の間に引いた直線が再び曲線と交差しない場合はどうなるのか、ということです。この場合、直線は「無限遠」で曲線と交差すると言われ、加算の結果は点 𝒪 になります。このケースは、引いた直線が垂直である場合、つまり点 𝑃 をその逆点 −𝑃 と加算しようとしている場合に発生することに注意してください：
これから2つの基本的な恒等式が導かれます。すべての点 𝑃 に対して次のことが成り立ちます：
𝑃 + 𝒪 = 𝑃
𝑃 + (−𝑃) = 𝒪
幾何学的な説明から生じるもう1つの疑問は、点をそれ自身に加算するにはどうすればよいかということです。2つの異なる点 𝑃 と 𝑄 を加算するには、それらの間に直線を引き、その延長線と曲線との交点を見るのでした。直感的には、𝑃 を固定したまま、𝑄 を 𝑃 に「どんどん近づけて」移動させるにつれて生じる直線を考え、最終的に 𝑄 が 𝑃 と重なるようにします。得られるのは、点 𝑃 において曲線にますます「接する」直線であり、𝑃 をそれ自身に加算したいときに注目するのはまさにこの直線です：
点 𝑃 をそれ自身に加算するには、点 𝑃 で曲線に接線を引き、それが曲線と2つ目の点で交差するまで延長します。この点を 𝑋 軸に関して反転させ、その結果得られる点が加算の結果として定義されます。加算の結果は 𝑃 + 𝑃 = 2𝑃 と表記するのが通例です。繰り返しになりますが、接線が曲線と2つ目の点で交差しない場合、その接線は「無限遠」で曲線と交差すると言われ、この場合の加算の結果は点 𝒪 になります。
これらの視覚的な幾何学的説明は、点の加算がどのように機能するかをうまく示し、理解を助けます。しかし、実際にはどのように計算するのでしょうか？ もちろん、数学の方程式です！
点 $𝑃 = (𝑥_𝑃, 𝑦_𝑃)$ と $𝑄 = (𝑥_𝑄, 𝑦_𝑄)$ が与えられたとき、それらの加算の結果は点 $𝑅 = (𝑥_𝑅, 𝑦_𝑅)$ であり、以下の通りです：
$𝑥_𝑅 = 𝜆^2 − 𝑥_𝑃 − 𝑥_𝑄\ \ \ \ \ \ \ \ \ (mod\ 𝑝)$
$𝑦_𝑅 = 𝜆(𝑥_𝑃 − 𝑥_𝑅) − 𝑦_𝑃\ \ \ \ (mod\ 𝑝)$
ここで 𝜆 は、2つの点が異なる場合はそれらの点を結ぶ直線の傾き、点がそれ自身に加算される場合はその点における曲線への接線の傾きと定義されます。正式には：
$\displaystyle𝜆 = \frac{𝑦_𝑃 − 𝑦_𝑄}{𝑥_𝑃 − 𝑥_𝑄}\ \ \ \ \ (mod\ 𝑝)\ \ \ ;\ \ \ 𝑖𝑓 𝑃 ≠ 𝑄$
$\displaystyle𝜆 = \frac{3{𝑥_𝑃}^2 + 𝑎}{2𝑦_𝑃}\ \ \ \ (mod\ 𝑝)\ \ \ ;\ \ \ 𝑖𝑓 𝑃 = 𝑄$
点の加算の背後にある数学的計算は、この記事の残りの部分にとって重要ではありません。そのため、点の加算を、曲線上の2つの点を受け取り、やはり曲線上にある3つ目の点を返すブラックボックスと見なすことができます。
点 𝑃 をそれ自身に加算できることを確認し、その結果の点を 2𝑃 と表記しました。この結果に再び点 𝑃 を加算すると、3𝑃 と表記される点に到達し、以下同様です。このようにして、点をそれ自身に繰り返し加算することにより、点を定数で「乗算」することを定義できます（数の乗算と同様）：
$𝑛𝑃 = 𝑃 + 𝑃 + ⋯ + 𝑃\ \ \ \ \ (n\ times)$
一見すると、点を数値 𝑛 で乗算するには、点同士の加算を 𝑛 回実行する必要があるように思えます。なぜなら、開始点が与えられたとき、「最後」の点がどこに落ちるかを事前に知ることは難しく、「一歩一歩」到達するしかないからです。𝑛 は非常に大きくなり得るため、そのような計算は非常に非効率になります。
この目的のために、Double And Add アルゴリズムがあります。これは点 𝑃 から始め、𝑛 の2進表現の各ビットについて、現在の点を 2 倍し（つまり、それ自身に加算し）、ビット値が 1 の場合に結果に加算します。このアルゴリズムの実行時複雑性は 𝑂(log 𝑛) であり、非常に大きな数による点の乗算を効率的に行うことができます。
後で使用する点の乗算の重要な性質は、すべての点 𝑃 と数値のペア 𝑎、𝑏 に対して次が成り立つことです：
$𝑏(𝑎𝑃) = (𝑏𝑎)𝑃 = (𝑎𝑏)𝑃 = 𝑎(𝑏𝑃)$
直感的には、点 𝑃 から始めて、そこから 𝑎 歩進み、点 𝑎𝑃 に到達するとします。この点から、「大きさ」𝑎 の 𝑏 歩進み、点 𝑏(𝑎𝑃) に到達します。あるいは、別のシナリオとして、点 𝑃 から始めて、そこから 𝑏 歩進み、点 𝑏𝑃 に到達したとします。この点から「大きさ」𝑏 の 𝑎 歩進み、点 𝑎(𝑏𝑃) に到達します。
どちらのシナリオでも、点 𝑃 から合計で同じ 𝑎𝑏 歩進んだことになるので、どちらのシナリオでも同じ最終点に到達します。数学的には、点を定数で乗算することは結合的です。
点 𝑃 から始めて、それを何度も何度もそれ自身に加算すると、各ステップで曲線上の何らかの新しい点に到達します。曲線上の点は有限個なので、ある段階で以前に到達した点に再び到達し、何らかのループ、つまり「円」に入ることになります。より正確には、ある段階で点 -𝑃 に到達し、次のステップで点 𝒪 に到達し、その次のステップで再び開始した点 𝑃 に到達します。
このような「円」を生成する点は、その「円」全体をそこから生成できるため、生成元（Generator）と呼ばれ、文字 𝐺 で表記するのが通例です。「円」内の点の数（点 𝒪 を含む）は「生成元 𝐺 の位数」と呼ばれ、通常 𝑛 で表されます。曲線上の各点は、ある種の「円」を形成します。数学的には、この「円」上の点の集合は巡回群です。
これから得られる興味深い性質は、点 𝐺 をその位数 𝑛 で乗算すると無限遠点が得られることです：
𝑛𝐺 = 𝒪
「ある 𝑥 について 𝑄 = 𝑥𝑃 となるような点 𝑃 と 𝑄 が与えられたとき、𝑥 を見つけることは困難である。」
言葉で言い換えると、誰かがある開始点から始めて、そこから一定の歩数進み、最終点に到達したとします。開始点と最終点が与えられたとき、その人が何歩進んだかをどうやって知ることができるでしょうか？
この質問に対する答えはそれほど直感的ではありません。なぜなら、開始点から歩を進めたときにどの点に到達するかを事前に予測することは難しいからです。素朴な解法としては、自分たちで 𝑃 から始めて、そこから1歩ずつ進み、𝑄 に到達するまで歩数を数えるというものがあります。この解法の複雑性は 𝑂(𝑥) であり、𝑥 が大きな数であることが分かっている場合、例えば 𝑥 が 256 bit である場合には実行不可能です。
この問題は楕円曲線離散対数問題（ECDLP）と呼ばれ、困難な問題です。しかし、どの程度困難なのでしょうか？
暗号の文脈では、問題の「困難さ」や「暗号システムの強度」を、Security Level と呼ばれる指標で測定するのが通例です。この指標では、最良の既知の攻撃が $𝑂(2^𝑛)$ ステップで問題を解く場合、その問題は「𝑛 ビットのセキュリティ」を持つと言われます。
現在、ECDLP問題を解く最良のアルゴリズムは、$𝑂(\sqrt n)$ の複雑性でそれを解きます。ここで 𝑛 は点 𝑃 の位数であり、Meet In The Middle攻撃を使用します。十分に大きな位数を持つ点が選択された場合、それを解くことは実行不可能であり、それがこの問題の強度となります。
例えば、256 bit の大きさの 𝑛 を選択すると、ECDLP問題のセキュリティレベルは 128 bit セキュリティになります。比較として、整数分解問題に基づくRSA暗号で同じ 128 bit セキュリティを達成するには、3072 bit の大きさの公開鍵が必要です。このことにより、楕円曲線の使用は比較的計算効率が高くなります。
これまで楕円曲線の世界への導入を見てきましたが、次に暗号の文脈でそれらを用いて何ができるかを見ていきます。ご存知の通り、暗号システムは通常、解くのが困難な「困難な問題」に基づいています。例えば、前述した数の因数分解問題を用いるRSAや、離散対数問題を用いるDiffie-Hellmanプロトコルなどです。楕円曲線上のECDLP問題に基づく暗号システムは、楕円曲線暗号（Elliptic Curve Cryptography）ファミリー、略してECCに属します。
まず、ある物語から始めましょう。あなたがパーティーにいると想像してください。部屋は人でいっぱいで、誰もが誰とでも話すことができ、誰もが全員の話を聞いています。この部屋には、これまで一度も会ったことのないアリスとボブもいます。アリスはボブが好きで、デートに誘いたいと思っています。アリスは少し恥ずかしがり屋なので、他のパーティー客に聞かれることなく、この秘密のメッセージをボブに伝えたいと思っています。アリスとボブは事前に何も打ち合わせておらず、アリスがボブに言うことはすべて、パーティーの他の客全員に聞かれてしまいます。アリスはどうやって他の誰にも聞かれずにメッセージをボブに伝えられるでしょうか？
「楕円曲線」と答えたなら、正解です！
アリスはある楕円曲線とその中の生成元を選択し、それらをボブに伝えます。具体的には、アリスはボブ（および部屋の他の全員）に、2つの曲線パラメータ 𝑎、𝑏、法 𝑝、および生成元 𝐺 を渡します。さらに、アリスは $1 ≤ 𝑑_𝐴 ≤ 𝑛 − 1$ の範囲の何らかの値 $𝑑_𝐴$ を選択します。ここで 𝑛 は 𝐺 の位数です。この値 $𝑑_𝐴$ はアリスの秘密鍵と呼ばれます。アリスは点 $𝐴 = 𝑑_𝐴𝐺$ を計算します。これはアリスの公開鍵と呼ばれ、ボブに伝えます。同様に、ボブも秘密鍵 $𝑑_𝐵$ を選択し、点 $𝐵 = 𝑑_𝐵𝐺$ を計算します。これはボブの公開鍵と呼ばれ、アリスに伝えます。
アリスはボブの公開鍵を取り、その点を自分の秘密鍵で乗算し、3つ目の点 $𝑃_𝐴 = 𝑑_𝐴𝐵$ に到達します。同様に、ボブはアリスの公開鍵を取り、それを自分の秘密鍵で乗算し、自分自身の3つ目の点 $𝑃_𝐵 = 𝑑_𝐵𝐴$ に到達します。アリスとボブが別々に到達した点を調べると、それらが同じ点であることが分かります！ この事実は、前に見た点を定数で乗算する際の結合性の性質に由来します：
$𝑃_𝐴 = 𝑑_𝐴𝐵 = 𝑑_𝐴(𝑑_𝐵𝐺) = 𝑑_𝐵(𝑑_𝐴𝐺) = 𝑑_𝐵𝐴 = 𝑃_𝐵$
この一連のプロセスの終わりに、アリスとボブは曲線上の何らかの点について合意に達することができましたが、どの段階でもどちらもその点を相手に渡しませんでした。誰もが聞いた情報は次のとおりです：𝑎、𝑏、𝑝、𝐺、𝐴、𝐵。部屋にいてこの情報を聞いている人は、この情報からアリスとボブが合意した点を見つけることはできません。
これは、部屋の中の別の人がその点を見つけたいと思った場合、𝐵 または 𝐴 を掛け合わせるために、アリスの秘密鍵かボブの秘密鍵のいずれかを知る必要があるからです。例えばアリスの秘密鍵を見つけるには、$𝐴 = 𝑑_𝐴𝐺$ に注目します。これが送信された唯一の情報であり、アリスの秘密鍵を「含んでいる」からです。𝐺 と $𝑑_𝐴𝐺$ が与えられたとき、$𝑑_𝐴$ を見つけることは、楕円曲線における離散対数問題を解くことと等価であり、前述の通りこれは困難な問題です。
この美しいプロトコルは、楕円曲線ディフィー・ヘルマン（ECDH）と呼ばれます。
私たちの物語はまだ終わっていません。アリスとボブは共有秘密の点に合意しましたが、アリスはそれでもどうしても望んでいたデートの誘いをボブにしていません。
当事者が共有秘密の点に合意した後、それを任意の暗号化方式（例えばAES）の暗号化キーとして使用し、その時点から暗号化を通じて安全に通信できます。
通常、点の 𝑥 または 𝑦 座標のいずれかを取り出して使用します。安全性を保つため、選択した値をハッシュ化し、ハッシュ結果のみを暗号化キーとして使用することが推奨されます。実際には、その値が暗号化キーとして使用するには大きすぎる場合があります。例えば、使用するハッシュ関数がSHA-1の場合、その出力長は 160 bit ですが、AES暗号化に必要なのは 128 bit だけです。そのような場合、160 のうち 128 bits のみを使用し、残りを破棄するのが通例です。
とにかく、この時点でアリスとボブは暗号化キーに合意し、それを知っているのは2人だけです。この時点から、2人は暗号化を通じて通信し、部屋で聞いている誰もが彼らの言っていることを理解することはできません。
以下はプロトコルの図です：
合意したキーを使用して、アリスはメッセージ「ねえボブ、明日の夕方コーヒーでもどう？」を暗号化し、暗号化されたメッセージをボブに渡します。ボブは自分も知っているキーでメッセージを復号します。アリスはボブが「はい」と言ってくれることを願っていますが、それはプロトコルの一部ではありません。
よく知られているディフィー・ヘルマン（DH）プロトコルでは、当事者は素数 𝑝 と、値 𝑝 に対応する群に含まれる生成元 𝑔 を公開して送信します。アリスは秘密鍵 𝑎 をランダムに生成し、自分の公開鍵 $𝐴 = 𝑔^𝑎\ \ \ \ (mod\ 𝑝)$ を公開してブロードキャストします。同様に、ボブも秘密鍵 𝑏 をランダムに生成し、自分の公開鍵 $𝐵 = 𝑔^𝑏\ \ \ \ (mod\ 𝑝)$ を公開してブロードキャストします。次にアリスはボブの公開鍵を取り、それを自分の秘密鍵で累乗し、値 $𝐾 = 𝐵^𝑎 = (𝑔^𝑏)^𝑎 =𝑔^{𝑎𝑏}\ \ \ \ (mod\ 𝑝)$ を計算します。同じように、ボブは値 $𝐾 = 𝐴^𝑏 = (𝑔^𝑎)^𝑏 =𝑔^{𝑎𝑏}\ \ \ \ (mod\ 𝑝)$ を計算します。プロセスの終わりに、アリスとボブは、それを相互に送信することなく、共通の 𝐾 値に合意することができました。
彼らの通信を傍受する攻撃者は、ブロードキャストされた値 𝑝、𝑔、𝐴、𝐵 が与えられても 𝐾 を見つけることができません。それを行うには、アリスまたはボブの秘密鍵のいずれかを見つけなければなりません。例えばアリスの秘密鍵を計算するには、𝑔 と $𝑔^𝑎\ \ \ \ (mod\ 𝑝)$ が与えられたときに 𝑎 を見つけなければならず、これは困難な問題です。この問題は離散対数問題（DLP）と呼ばれます。
DLPに基づくDHと、ECDLPに基づくECDH（基本的に同じで、ECという接頭辞が付いているだけ）との間には、非常に明確な類似性があります。両方のプロトコルにおいて、互いに通信する2つの当事者は、事前に何も打ち合わせることなく、何らかの共有秘密の値に合意できます。当事者間のメッセージを聞く人は誰でも、彼らが相互に渡す公開情報に触れることになりますが、彼らの間で共有された秘密の値に到達することはできません。### 楕円曲線の2つ目の利用法 - メッセージへの署名 話の続きをしましょう。アリスとボブはデートに出かけ、楽しい夜を一緒に過ごしたとしましょう。その翌日、アリスは「こんにちは、アリス。ボブです。昨日は一緒に楽しい時間を過ごせて、また今週末に会いたいと思っています」というメッセージを受け取ります。アリスは、そのメッセージを送ったのがボブではないと疑います。なぜなら、ボブは昨日一緒にいてとても楽しかったので、週末まで待って会おうとはせず、明日会いたいと思うはずだと彼女が知っているからです！ アリスはどうやって、そのメッセージを書いたのがボブであることを確認できるでしょうか？
「楕円曲線」と答えたなら、またしても正解です！
ECDLP問題の難しさは、メッセージへの署名にも利用できます。デートの間に、アリスとボブはある楕円曲線と、その中の生成元 𝐺 について合意しました。ボブは、ボブの秘密鍵と呼ばれる値 $𝑑_𝐵$ を生成し、ボブの公開鍵と呼ばれる点 $𝑃_𝐵 = 𝑑_𝐵𝐺$ を計算しました。ボブはアリスに自分の公開鍵を渡しました。アリスが後で受け取ったメッセージが本当に彼によって署名されたものかを検証するために使えるようにするためです。
ボブが特定のメッセージ 𝑚 に署名したいとしましょう。彼は何らかの安全なハッシュ関数を使って値 $z = hash(m)$ を計算し、その結果から、生成元 𝐺 の位数である n のビット長に等しいビット数を保持します。ボブは範囲 $1 ≤ 𝑘 ≤ 𝑛 − 1$ の乱数 𝑘 を生成します。次にボブは点 $𝑘𝐺 = (𝑥_1, 𝑦_1)$ を計算し、その 𝑥 座標を取り、$𝑟 = 𝑥1\ \ \ \ (mod\ n)$ を計算します。最後に、ボブは値 $𝑠 = 𝑘^{−1}(𝑧 + 𝑟𝑑_𝐵)$ を計算します。
メッセージ 𝑚 の署名は、計算された値 𝑟 と 𝑠 のペアとして定義されます。
アリスが特定のメッセージ 𝑚 を受信し、その署名が値 𝑟 と 𝑠 のペアで構成されているとします。アリスは、そのメッセージに署名したのが本当にボブであることを確認したいと考えます。アリスはボブと同じ方法で値 $z = hash(m)$ を計算します。次にアリスは値 $𝑢_1 = 𝑧𝑠^{−1}$ と $𝑢_2 = 𝑟𝑠^{−1}$ を計算します。最後にアリスはボブの公開鍵 $𝑃_𝐵$ を使い、点 $𝑢_1𝐺 + 𝑢_2𝑃_𝐵 = (𝑥_1, 𝑦_1)$ を計算します。$𝑟 ≡ 𝑥_1\ \ \ \ (mod\ n)$ が成り立てば、署名は有効と見なされます。これが正しい理由は、次の式が成り立つからです：
$𝑢_1𝐺 + 𝑢_2𝑃_𝐵 = 𝑧𝑠^{−1}𝐺 + 𝑟𝑠^{−1}𝑃_𝐵 = 𝑠^{−1}(𝑧𝐺 + 𝑟𝑃_𝐵) = 𝑠^{−1}(𝑧𝐺 + 𝑟𝑑_𝐵𝐺) = 𝑠^{−1}(𝑧 + 𝑟𝑑_𝐵)𝐺 = 𝑘(𝑧 + 𝑟𝑑_𝐵)^{−1}(𝑧 + 𝑟𝑑_𝐵)𝐺 = 𝑘𝐺$
署名が有効であれば、この点の 𝑥 座標は、メッセージ署名で定義されているとおり、確かに 𝑟 になります。生成元 𝐺 の位数は、文字 𝑛 で表されますが、素数である必要があることに注意してください。これは、署名アルゴリズムと検証アルゴリズムにおいて逆数を確実に計算できるようにするためです。
秘密鍵 $𝑑_𝐵$ を保持する人だけが、公開鍵 $𝑃_𝐵$ に対する有効な署名を作成できることがわかります。値 $𝑑_𝐵$ を持たない攻撃者は、署名内の $𝑃_𝐵$ に対応する値 𝑠 を計算できません。攻撃者が特定のメッセージに一致する署名を作成したい場合、ECDLP問題を解かなければなりません。すなわち、$𝐺$ と $𝑃_𝐵 = 𝑑_𝐵𝐺$ が与えられたときに秘密鍵 $𝑑_𝐵$ を見つけることであり、これは困難な問題です。
この署名プロトコルは、Elliptic Curve Digital Signature Algorithm（略してECDSA）と呼ばれます。このプロトコルは、署名されたメッセージが改変または偽造されていないことを保証し、さらに、メッセージに署名した人物が自分が作成したことを否定できないことを保証します。
事前に何も調整する必要がなかったECDHプロトコルとは異なり、ECDSAプロトコルでは、当事者があらかじめ公開鍵について合意しておかなければなりません。各当事者が、自分が保持する公開鍵が本当に通信したい相手のものであると確信できた後で初めて、そのプロトコルを使用できます。そうでなければ、各当事者が保持する公開鍵を使って署名を検証しても意味がありません。
さて、話に戻りましょう。アリスは、自分が保有する公開鍵 $𝑃_𝐵$ が確かにボブのものであると確信しています。なぜなら、デートのときにボブが彼女に明示的に渡したからです。アリスはその鍵でメッセージを検証しようとし、一致しないことを発見します。もちろんです！ 別の誰かがメッセージを作成して署名したのです。まさにアリスが疑ったとおりです。
以下はこのプロトコルの図です：
ElGamal署名プロトコルでは、当事者は大きな素数 𝑝 と生成元の数 𝑔 について合意します。署名する当事者は、秘密鍵と呼ばれる範囲 $1 ≤ 𝑑 < 𝑝 − 1$ の値 𝑑 を生成し、公開鍵と呼ばれる値 $𝑦 = 𝑔^𝑑\ \ \ \ (mod\ p)$ を計算して公開します。
特定のメッセージに署名するため、彼らは値 $z = hash(m)$ を計算し、$(p-1)$ と互いに素である範囲 $1 ≤ 𝑘 < 𝑝 − 1$ の乱数 𝑘 を生成します。彼らは $𝑟 = 𝑔^𝑘\ \ \ \ (mod\ p)$ と $𝑠 = 𝑘^{−1}(𝑧 − 𝑑𝑟)\ \ \ \ (mod\ (p-1))$ を計算します。メッセージ m の署名は、計算された値 𝑟 と 𝑠 のペアとして定義されます。
特定のメッセージ 𝑚 と、値 𝑟 と 𝑠 のペアからなるその署名を受け取った当事者は、公開鍵 𝑦 を使って、値 $𝑢_1 = 𝑟^𝑠𝑦^𝑟$ と $𝑢_2 = 𝑔^𝑧$ を計算することによって署名を検証します。$𝑢_1 = 𝑢_2$ であれば、署名は有効と見なされます。これは、𝑠 の定義により次のようになるためです：
$𝑠 = 𝑘^{−1}(𝑧 − 𝑑𝑟)$ なので、$𝑘𝑠 = 𝑧 − 𝑑𝑟$ となり、したがって $𝑧 = 𝑘𝑠 + 𝑑𝑟$ となります。よって：
$𝑢_2 = 𝑔^𝑧 = 𝑔^{𝑘𝑠+𝑑𝑟} = 𝑔^{𝑘𝑠}𝑔^{𝑑𝑟} = (𝑔^𝑘)^𝑠(𝑔^𝑑)^𝑟 = 𝑟^𝑠𝑦^𝑟 = 𝑢_1$
攻撃者は、秘密鍵 𝑑 を知らなければ、公開鍵 𝑦 に対する有効な署名を作成できません。公開鍵から秘密鍵を取得するには、攻撃者はDLP問題を解かなければならず、これは困難な問題です。
ここにも、ECDLPに基づくECDSAと、DLPに基づくElGamalの間に明確な類似点があります。どちらの場合も、当事者は事前に公開鍵を調整する必要があり、新しいメッセージに署名するたびに乱数 𝑘 を生成することが必要です。また、どちらの場合も、当事者間のメッセージを傍受する攻撃者は、署名を偽造できるような有用な情報を推測できません。
楕円曲線が、秘密の値について合意するためやメッセージへの署名のために、暗号システムでどのように使われるかを見てきました。人生のすべてのことと同様に、何かを実際に使うとなると、物事はいつも計画どおりにうまくいくとは限りません。この記事の残りの部分では、ユーザーが誤用したり、安全でない方法で実装された、ECCベースの暗号システムに対するさまざまな攻撃方法を紹介します。
当然ながら、この部分はECDHに対する攻撃とECDSAに対する攻撃に分けます。どちらの場合も、いずれかの当事者の秘密鍵を見つけたら、攻撃に「成功」したと見なし、そこで止めることにします。ECDHの場合、秘密鍵から共有秘密値と、その後それを使って暗号化されたすべての情報に到達できるため、それで十分です。ECDSAの場合、秘密鍵を使えば好きなようにメッセージに署名できるため、それで十分です。
SageMathは、無料でオープンソースの数式処理ソフトウェアです。Pythonとほぼ同じ構文で記述でき、Pythonライブラリとしても使用できます。このライブラリは楕円曲線に関連する便利な関数を実装しており、ECCの文脈で必要となる計算に非常に役立ちます。この記事の一部として、このライブラリで書かれたコードスニペットを提供します。私は、Ubuntuオペレーティングシステム、具体的にはバージョン22.04にインストールするのが最も簡単だとわかりました。インストールするには、単にコマンド sudo apt install sagemath を実行します。
コードを含むファイルを実行するには、ファイルを.sage拡張子で保存し、コマンド sage file.sage を実行します。
さらに、Pythonのインタープリタと同様に、コマンド sage を実行することでインタープリタを使用できます。また、ライブラリsage.allをインポートした.pyファイルを作成し、コマンド python3 file.py で実行することも可能です。コマンド sage でファイルを実行する場合、記号 ^ はべき乗として解釈されますが、python3 で実行する場合は、この記号はxorとして解釈されることに注意してください。
この記事では、主にSageMathの以下の関数を使用します：
E.gens() - 曲線 E の生成元を見つけるG.order() - 生成元 G の位数を計算するn*G - 生成元 G と数 n の乗算n.factor() - 数 n をその因数に分解する - この関数はペア (𝑝, 𝑒) のリストを返します。ここで 𝑝 は素因数、𝑒 はその指数、すなわち n の分解に 𝑝 が現れる回数ですcrt - 中国の剰余定理の方程式系を解くおそらく、ECDHの誤用の中で最も攻撃しやすいのは、位数 n が小さすぎる生成元を選ぶことです。
前述のように、ECDLP問題は計算量 $O(\sqrt{n})$ で解くことが可能です。𝑛 が小さすぎる場合、例えば32ビットの場合、この問題を解くことが現実的になります。この問題を解くアルゴリズムはいくつかあり、Baby-Step Giant-Step、Pollard's Rho、Pollard's Lambdaなどがあります。これらのアルゴリズムは、SageMathの助けを借りて、discrete_log 関数を使えばブラックボックスとして実行できます：```python
import random
p = random_prime(2^32)
a = random.randrange(p)
b = random.randrange(p)
E = EllipticCurve(GF(p), [a,b])
G = E.gens()[0]
n = G.order()
private_key = random.randrange(n)
A = private_key * G
found_key = G.discrete_log(A)
assert found_key * G == A
assert private_key == found_key
print("success!")
このコードスニペットでは、`𝑝` が32ビット長であるという制限の下で、曲線のパラメータをランダムに選択しています。この制限により、曲線上の点の数が $O(2^{32})$ であることが保証され、したがって曲線上の各点の位数も最大で $O(2^{32})$ となります。その後、曲線を作成し、その中から生成元を選び、ランダムな秘密鍵を生成して公開鍵を計算します。最後に、生成元と公開鍵から離散対数を計算して秘密鍵を求め、見つけた鍵が実際に正しいことを検証します。このコードは、秘密鍵を見つけるのに最大でも数秒しかかかりません。
## 生成元の位数は平滑数である
前述のとおり、生成元の位数は、生成元の点を繰り返し自身に加算してできる「円」上の点の数として定義され、`𝑛` で表されます。`𝑛` がより小さな素因数に分解できる合成数である場合、ECDLP を効率的に解くことが可能です。このような数を平滑数と呼びます。この記事の目的においては、十分な数の素因数に分解でき、それぞれの素因数が攻撃を機能させるのに十分小さな数であることを意味します。平滑数の形式的な定義はこれとは少し異なり、私たちには関係ありません。
直感的には、これは各素因数に対して個別に「攻撃」することで行われます。非常に大きな「円」を形成する生成元 `𝐺` と、`𝑃 = 𝑘𝐺` を満たす「円」上の点 `𝑃` が与えられたとします。大きな「円」は、それぞれが `𝑛` の1つの素因数のサイズを持ついくつかの小さな「円」に分解できます。各小さな「円」では、`G` と `P` を、小さな「円」内に位置し `𝑃′ = 𝑘′𝐺′` を満たす対応する別の点 `G'` および `P'` に写像できます。「円」が小さいため、問題を解いて `𝑘′` を見つけるのは比較的容易です。最後に、見つけたすべての小さな `𝑘′` を組み合わせて、元の「円」における目的の `𝑘` を得ることができます。
私が説明した処理を実行するアルゴリズムは、Pohlig-Hellman アルゴリズムと呼ばれます。その実行時複雑性は $O(\sqrt{p_{max}})$ です。ここで $p_{max}$ は `𝑛` の分解における最大の素因数です。これも当然のことであり、アルゴリズムで最も負荷が高い部分は、より小さな「円」の中で最大の「円」における ECDLP 問題を解くことだからです。たとえば、`n` が128ビットの数であり、素因数分解したときに最大の素因数が30ビットの数になる場合があります。このアルゴリズムは、問題を解く複雑性を $2^{64}$ から $2^{15}$ に削減し、実行不可能から実行可能に変えます。
幸いなことに、SageMath の `discrete_log` 関数は、その実装内でこのアルゴリズムを実行します。攻撃を実行するには、単に関数を呼び出すだけで済みます。```python
p = 183740305291166889900894879302858411333
a = 13
b = 37
E = EllipticCurve(GF(p), [a,b])
G = E(123764810000715262449972298016641419881,
144640915410606177233842123838934486566)
n = G.order()
print("number of bits in n:", n.nbits())
print("n's factors:", n.factor())
print("number of bits in n's greatest factor:", n.factor()[-1][0].nbits())
import random
private_key = random.randrange(n)
A = private_key * G
print("Calculating discrete_log...")
found_key = G.discrete_log(A)
assert found_key * G == A
assert private_key == found_key
print("success!")
このコードスニペットでは、楕円曲線とその上の生成元を定義し、その位数の素因数を出力しています。出力は次のとおりです。``` number of bits in n: 128 n's factors: 2 * 3 * 13 * 101 * 211 * 21141581 * 38581057 * 60652309 * 2234328781 number of bits in n's greatest factor: 32 Calculating discrete_log... success!
生成元の位数は128ビットですが、最大の素因数が32ビットになるように素因数分解されることがわかります。
その後、前回の攻撃と同様に、ランダムな秘密鍵を選び、そこから公開鍵を計算し、生成元と公開鍵が与えられたときに秘密鍵を計算して、それが正しいことを検証します。
攻撃は完了しましたが、「小さな」円がどのように定義されるのか、点 `𝐺` と `𝑃` を対応する点 `𝐺′` と `𝑃′` にマッピングする方法、そして小さな解をすべて大きな解に組み合わせる方法をまだ見ていません。次の攻撃もこの部分に基づいているため、ここで直感的に説明しようと思います。
位数 `3𝑥5𝑥7 = 105` の「円」があり、その生成元が `𝐺` であるとします。点 `𝐺′ = (5𝑥7)𝐺 = 35𝐺` を定義し、そこから生成される「円」を考えます。`𝐺′` から1「ステップ」進む、つまり `𝐺′` をそれ自身に加えると、元の「円」の点 `35𝐺` から35ステップ進むことになり、点 `2𝐺′ = 70𝐺` に到達します。さらに1「ステップ」進むと点 `3𝐺′ = 105𝐺 = 𝒪` に到達し、そこからもう1「ステップ」進むと点 `4𝐺′ = 35𝐺 = 𝐺′`、つまり開始点に戻ります。`G′` によって形成される「円」の位数は `3` です。これは偶然ではありません。位数 `105` の「円」では、サイズ `35` の「ステップ」をちょうど `3` 回取ることができるからです。同様に、点 `𝐺′ = (3𝑥7)𝐺 = 21𝐺` を定義することで位数 `5` の「円」を作成でき、`𝐺′ = (3𝑥5)𝐺 = 15𝐺` を定義することで位数 `5` の「円」を作成できます。
逆の見方をすると、さらに興味深くなります。元の「円」で点 `G` から `𝑛` ステップ進んで点 `𝑛𝐺` に到達したとします。小さな「円」でも点 `𝐺′` から `𝑛` ステップ進むと、`𝑛 ≡ 𝑛′ (𝑚𝑜𝑑 3)` を満たす点 `𝑛′𝐺′` に到達します。なぜこれが興味深いのでしょうか。`𝐺′` の位数は `𝐺` の位数よりもはるかに小さいため、`𝐺′` と `𝑛′𝐺′` が与えられれば、`𝑛′` を比較的簡単に見つけることができます。この計算を、「円」の位数の他の2つの素因数である `5` と `7` についても行うと、以下の値が得られます。
𝑛 ≡ $𝑛'_1$ (𝑚𝑜𝑑 3)\
𝑛 ≡ $𝑛'_2$ (𝑚𝑜𝑑 5)\
𝑛 ≡ $𝑛'_3$ (𝑚𝑜𝑑 7)
これらの3つの値から、中国剰余定理を使うことで `𝑛` を簡単に見つけることができ、元の問題を解くことができます。
## 生成元の位数がほぼスムーズ数であり、秘密鍵が小さい場合
前回の攻撃と同様に、生成元の位数が素因数分解できる曲線が得られたとします。ただし今回は、最大の素因数が大きすぎて、そのECDLPを現実的に解くことができません。たとえば、生成元の位数が `256 bit` であっても、最大の素因数が `128 bit` の場合です。
Pohlig-Hellmanアルゴリズムは、秘密鍵を見つけるために約 $O(2^{64})$ 回の操作を必要とするため、実行不可能です。
使用されている秘密鍵が比較的小さいと分かっていれば、それでも効率的に見つけることができます。
秘密鍵が `64 bit`（`256 bit` ではなく）であると仮定しましょう。公開鍵が作成されるとき、生成元に秘密鍵が掛けられ、生成元が作る「円」上のどこかの点が得られます。「円」は約 $2^{256}$ 個の点の大きさですが、この点は「最初の」$2^{64}$ 個の点のどこかに「落ちる」ことになります。秘密鍵と、より大きな値に対応する「円」上の点との間には「相互作用」はありません。
Pohlig-Hellmanアルゴリズムを実行しつつ、大きすぎる「円」を「破棄」することが可能です。ただし、残った「円」の位数の積が秘密鍵の長さ以上であることが条件です。積が少なくとも `64 bit` になる十分な数の小さな素因数が見つかった場合、対応する「円」は、前に見た攻撃と同じ攻撃を実行するのに十分です。
以前はコードを書くのが簡単でしたが、今回は自分たちで実装する必要があります。SageMathの `discrete_log` 関数は、いくつかの素因数を「破棄」したいことを知らないからです。次のコードスニペットはこれを実行します:```python
p = 88664572752015126127869404674421545790506871948117527783533589813159111825511
a = 13
b = 37
E = EllipticCurve(GF(p), [a,b])
G = E(19374976316789648652022260955836934561553454311144967863145605756652014623129,
68630819472054489323664324766002023315775509214344811025345735680440707888471)
n = G.order()
print("Number of bits in n:", n.nbits())
factors = n.factor()
print("n's factors:", factors)
PRIVATE_KEY_BIT_SIZE = 64
import random
private_key = random.randrange(2^PRIVATE_KEY_BIT_SIZE)
P = private_key * G
print("We know that the private key is", PRIVATE_KEY_BIT_SIZE, "bits long")
print("Lets find which of the factors of G's order are relevant for finding the private key")
# find factors needed such that the order is greater than the secret key size
count_factors_needed = 0
new_order = 1
for p, e in factors:
new_order *= p^e
count_factors_needed += 1
if new_order.nbits() >= PRIVATE_KEY_BIT_SIZE:
print("Found enough factors! The rest are not needed")
break
factors = factors[:count_factors_needed]
print("Considering these factors:", factors)
print("Calculating discrete log for each quotient group...")
subsolutions = []
subgroup = []
for p, e in factors:
quotient_n = (n // p ^ e)
G0 = quotient_n * G # G0's order is p^e
P0 = quotient_n * P
k = G0.discrete_log(P0)
subsolutions.append(k)
subgroup.append(p ^ e) # k the order of G0
print("Running CRT...")
found_key = crt(subsolutions, subgroup)
assert found_key * G == P
assert private_key == found_key
print("success!")
このコードスニペットでは、楕円曲線とその生成元を定義し、その位数の素因数を出力します。出力は次のとおりです。``` Number of bits in n: 256 n's factors: 2 * 3 * 29 * 2699 * 28751 * 831913766251 * 92996710252298530263979 * 84878782522781478604307230464271
生成元の位数は`256 bit`であり、いくつかの素因数に分解されます。そのうち最大の2つは`77 bit`と`107 bit`です。これらは十分に大きいため、ECDLPを解くことは非現実的です。次に、`64 bit`の秘密鍵がランダムに生成され、公開鍵が計算されます。次のステップでは、少なくとも`64 bit`の長さの位数が得られるまで、十分な数の素因数を「収集」します。出力は次のとおりです：```
We know that the private key is 64 bits long
Lets find which of the factors of G's order are relevant for finding the private key
Found enough factors! The rest are not needed
Considering these factors: [(2, 1), (3, 1), (29, 1), (2699, 1), (28751, 1), (831913766251, 1)]
It can be seen that the two largest factors are redundant, and the largest factor we are left with is 40 bit. In the next step, for each of the factors we are left with, we calculate points 𝐺′ and 𝑃′ as I explained earlier, and for each one of them we solves ECDLP. The results and the prime factors are kept in the lists subsolutions and subgroups respectively. Finally, all the results are combined using the Chinese Remainder Theorem into the private key, and we verify it is indeed correct.
楕円曲線における点加算の定義を調べると、点加算では値 𝑏 を使用せず、値 𝑎 と 𝑝 のみを使用するという興味深い性質に気付きます。これは、ある曲線上にある点を加算することが、𝑏 の値だけが異なる別の曲線でも意味を持つことを意味します。これはもちろん、点に数を掛ける場合にも当てはまります。ユーザーが相手から公開鍵として受け取った点が、実際に自分の曲線上にあることを検証しない場合、Invalid Curve Attack（無効曲線攻撃）に対して脆弱になります。
2つの当事者が何らかの楕円曲線 $E_1$ に合意したとします。攻撃者は、$𝐸_1$ と同じ 𝑎 と 𝑝 の値を持つが、𝑏 の値が異なる悪意のある曲線 $𝐸_2$ を作成できます。曲線 $𝐸_2$ 上で、攻撃者は位数が小さい点、例えば 3 の点 𝑃 を選択します。もちろん、点 𝑃 は $𝐸_1$ 上にはありません。なぜなら、$𝐸_1$ とは異なる 𝑏 の値を持つ方程式を満たすからです。攻撃者は自分の公開鍵として点 𝑃 をユーザーに送信します。ユーザーが、受け取った点が当事者間で合意した曲線 $𝐸_1$ 上に実際にあることを検証する手間を省いたとしましょう。ユーザーは攻撃者から受け取った公開鍵を取り、自分の秘密鍵と掛け合わせて、ECDH プロトコルの定義で見たように共有秘密点となる点に到達します。ユーザーの視点では、曲線 $𝐸_1$ 上で乗算演算を計算することになります。しかし、点 𝑃 は $𝐸_1$ 上にはまったくなく、$𝐸_2$ 上にあるため、ユーザーは実際には曲線 $𝐸_2$ 上で乗算演算を計算することになります。その後、ユーザーは共有秘密点を使用して攻撃者との通信を継続します。当事者が点の 𝑥 座標を AES 暗号化キーとして使用すると仮定しましょう。この場合、ユーザーは何らかのメッセージを暗号化して攻撃者に送信します。
𝑃 の位数は 3 なので、ユーザーが計算する共有点は 3 通りしかありません。攻撃者はこれらの可能な点をすべて調べ、そのうちどの点が、ユーザーが送信した暗号化メッセージを正常に復号できるキーに対応するかを見つけます。この点と開始点 𝑃 が分かれば、攻撃者はユーザーの秘密鍵を 3 で割った余りを推測できます。攻撃者はユーザーに、位数が増加する追加の悪意のある 𝑃 点、例えば 5, 7 などを送信できます。このようにして、攻撃者はユーザーの秘密鍵を小さな数で割った余りを表す値を十分に収集できます。最後に、攻撃者は前の攻撃で見たのと同じ方法で、中国剰余定理を使用してユーザーの秘密鍵を計算できます。
より直感的な説明は次のとおりです。攻撃者はユーザーに、非常に小さな「円」上の点、例えば長さ 2 の点を提供できます。ユーザーはこの「円」上を任意の歩数だけ前進し、目的地の点に到達します。攻撃者はユーザーの目的地の点を知っており、それは 2 通りのいずれかです。したがって、攻撃者はユーザーが円上で偶数歩または奇数歩のどちらを進んだかを判断できます。攻撃者はユーザーに、長さ 3, 5, 7 などの「円」上の追加の点を提供できます。攻撃者が、それぞれがユーザーの歩数に関するわずかな情報を含む、そのような因子を十分に得るまで続けます。最後に、攻撃者はこれらすべての値を組み合わせて、ユーザーが進んだ正確な歩数、つまりユーザーの秘密鍵を求めることができます。
次のコードはこの攻撃を示しています。```python from ecdsa.ecdsa import generator_128r1, curve_128r1 from Crypto.Util.number import long_to_bytes from Crypto.Util.Padding import pad, unpad from Crypto.Cipher import AES import random
curve = curve_128r1 G = generator_128r1 n = G.order() p = curve.p() a = curve.a()
private_key = random.randrange(n)
def encrypt_data(shared_point, message): if shared_point.is_zero(): x, y = 0, 0 else: x, y = shared_point.xy() key = long_to_bytes(int(x)).rjust(16, b"\x00") iv = long_to_bytes(int(y)).rjust(16, b"\x00") cipher = AES.new(key, AES.MODE_CBC, iv)
message = pad(message.encode(), 16)
return cipher.encrypt(message)
def decrypt_data(shared_point, enc_message): if shared_point.is_zero(): x, y = 0, 0 else: x, y = shared_point.xy() key = long_to_bytes(int(x)).rjust(16, b"\x00") iv = long_to_bytes(int(y)).rjust(16, b"\x00") cipher = AES.new(key, AES.MODE_CBC, iv)
decrypted = cipher.decrypt(enc_message)
return unpad(decrypted, 16)
def ECDH(A): # Send our public key to the other side # Have them reach the shared point and # Send us an encrypted message using the shared point as key
# This part takes place remotely and is unknown to the attacker
shared_point = private_key * A
message = "Inconceivable!"
return encrypt_data(shared_point, message)
def brute_force_encrypted_message(A, encrypted_message, max_order): # Returns n such that n*A matches the key used to encrypt the message for i in range(1, max_order): shared_point = i * A try: # If both padding is correct and all characters are ascii # Then it is probably the correct encryption key decrypted = decrypt_data(shared_point, encrypted_message) decrypted = decrypted.decode() return i except: continue raise Exception("Did not find a value for one of the encrypted messages")
def find_curves_with_small_subgroup(p, a, max_order): # Yield tuples of (order, point) such that the point is # on a curve with the same a & p values, but different b # and the point's order is <= max_order orders_found = set() b = 0 while True: b += 1 if b == p: # Ran out of b values break if (4a^3 + 27b^2) % p == 0: # Curve is singular continue
E = EllipticCurve(GF(p), [a, b])
for _ in range(100):
R = E.random_point()
n = R.order()
for f, e in n.factor():
if f in orders_found:
continue
if f > max_order:
break
# Create a point with order f
orders_found.add(f)
P = (n // f) * R
assert P.order() == f
yield (f, P)
subsolutions = [] subgroup = [] max_order = 10000 upto = 1 for order, A in find_curves_with_small_subgroup(p, a, max_order): upto *= order print("Found point with order", order, "so now can find keys of size up to", upto)
# Send this point as our public key and get an encrypted message from other side
encrypted_message = ECDH(A)
# Find the value n such that: private_key = n (mod order)
key_mod_order = brute_force_encrypted_message(A, encrypted_message, max_order)
# Save result to be used in CRT later
subsolutions.append(key_mod_order)
subgroup.append(order)
# Found enough values to calculate private key
if upto >= n:
break
print("Found enough values! Running CRT...") found_key = crt(subsolutions, subgroup) print("Found private key", found_key) assert private_key == found_key print("success!")
このコードスニペットでは、曲線とジェネレータが選択され、ユーザーは秘密鍵をランダムに生成し、ECDHプロトコルのすべての使用でそれを使用します。関数 `find_curves_with_small_subgroup` は、各点の位数が比較的小さく、その点が元の曲線とは `𝑏` の値だけ異なる何らかの曲線上にあるような、点と位数のペアを見つけます。コードは、十分な数のペアが見つかるまでそれらのペアを生成します。各ペアについて、公開鍵がユーザーに送信され、暗号化されたメッセージがユーザーから受信されます。
現在の位数を法としてユーザーの秘密鍵の値を求めるために、暗号化されたメッセージに対して総当たり攻撃が実行されます。これらの結果はすべて保存され、最後に中国剰余定理を使用してユーザーの秘密鍵を計算し、それが正しいことを検証します。この場合、当事者は、共有秘密点の `x` 座標を暗号化鍵とし、その `𝑦` 座標をIVとするAESで通信を行うことに同意しました。
攻撃の計算量は $𝑂(𝑛_{𝑚𝑎𝑥})$ です。ここで $𝑛_{𝑚𝑎𝑥}$ は、悪意のある点の位数の中で最大の位数です。これは、攻撃の「最も重い」部分が、小さな「円」の中の最大の「円」に対する総当たり攻撃であるためであり、攻撃者にとって幸運なことに、この値をほぼ完全に制御できます。したがって、この攻撃は計算量の点で比較的効率的です。前述のように、この場合の問題の根本は、ユーザーが受信した点が自分が作業している曲線上にさえあるかどうかを確認していないことです。さらに、ユーザーはECDHを新しく使用するたびに同じ秘密鍵を使用しており、これはあまり安全ではありません。
## 曲線が特異である場合
暗号的に安全であるために楕円曲線が満たさなければならない重要な特性の1つは、非特異であることです。非特異曲線とは、曲線の「判別式」と呼ばれる特定の値がゼロではない曲線です。これは、そのパラメータ `𝑎` と `𝑏` が次の不等式を満たすときに成立します:
$4a^3 + 27b^2 ≠ 0$
この不等式を満たさない曲線には、`singular point` と呼ばれる「問題のある」点が存在します。そのような点には、ノード (node) とカスプ (cusp) の2種類があります。ノード点は、特異点でそれ自体と交差する一種のループを持ち、その点を通って曲線に異なる2本の接線を引くことができる曲線上に存在します。
カスプ点は、曲線が「鋭く」なっている点であり、あたかも2本の線がそこから出ているかのようですが、その点における曲線の接線は1本しかありません。
<img src="https://assets.kitploit.com/production/public/readmes/48932/a40d8ce67ecb97eeabe85b52937a8935bc917b622e02168d9047200ed54feafc.png" alt="Singular Elliptic Curves" width="500">
ノード型の点では二重根が存在するため、曲線の方程式は次のように書けます:
$y^2 = (x-x_0)^2(x-x_1)\ \ \ \ (mod\ p)$
変数 $x$ を変数 $(𝑥 + 𝑥_0)$ に置き換えることで、曲線を左に「移動」させて、次の形に到達できます:
$y^2 = x^2(x+x_0-x_1)\ \ \ \ (mod\ p)$
これで、特異点は軸の原点にあります。$t = (x_0-x_1)$ の数値を使用して、曲線上の点から整数へのマッピングを作成できます。これにより、曲線上の点同士の加算演算が、数同士の乗算演算と等価になります。各点 `(𝑥, 𝑦)` に対して、数
$\frac{y+\sqrt{t}x}{y-\sqrt{t}x}$ を対応させます。特に、`𝑄 = 𝑛𝐺` であるような点のペア `𝐺` と `𝑄` に対して、$𝑞 ≡ 𝑔^𝑛\ \ \ \ (mod\ p)$ となる数 `𝑔` と `𝑞` を対応させることができ、これは「通常の」DLP問題です。このプロセスを説明するために、記事の最後の参考文献に小さな数を使った例へのリンクを追加しました。前述のマッピングでは、直線の方程式 $y+\sqrt{t}x$ と $y-\sqrt{t}x$ を使用しました。これらの直線は、（曲線を「移動」させた後に）特異点に引くことができる2本の接線に対応するものであり、これが基本的にこの攻撃が使用できる理由です。
このようなDLP問題は、前述のPohlig-Hellmanアルゴリズムを使用して効率的に解くことができます。なぜなら、このアルゴリズムは曲線上の点の代わりに整数に対しても使用できるからです。点の文脈では、このアルゴリズムはジェネレータの位数が平滑数である場合に有用であることを確認しました。曲線上の点の「円」は任意の位数を持つ可能性がありますが、素数 `𝑝` を法とする整数の体では、位数は `𝑝 − 1` です。`𝑝 − 1` が平滑数であれば、アルゴリズムはDLP問題を効率的に解き、秘密鍵 `n` を見つけます。
次のコードスニペットはこれを行います:```python
p = 102360775616927576983385464260307534406913988994641083488371841417601237589487
a = -3
b = 2
assert (4*a^3 + 27*b^2) % p == 0
Gx = 1777671135698746847568710125129424132255529153914112337834835240247819869964
Gy = 6786424314307625790108882554225666781375821855884993473586521771737454762217
Qx = 45541468695354471317248123146376609839909398850045396377931300808635064950836
Qy = 42191909885728105279718027025083923092282618497451601162405594991792376530066
x = GF(p)["x"].gen()
f = x^3 + a*x + b
roots = f.roots()
assert len(roots) == 2 # two roots, so one must be double
if roots[0][1] == 2:
double_root = roots[0][0]
single_root = roots[1][0]
else:
double_root = roots[1][0]
single_root = roots[0][0]
print("double root:", double_root)
print("single root:", single_root)
# map G and Q to the new "shifted" curve
Gx = (Gx - double_root)
Qx = (Qx - double_root)
# Transform G and Q into numbers g and q, such that q=g^n
t = double_root - single_root
t_sqrt = t.square_root()
def transform(x, y, t_sqrt):
return (y + t_sqrt * x) / (y - t_sqrt * x)
g = transform(Gx, Gy, t_sqrt)
q = transform(Qx, Qy, t_sqrt)
print("g:", g)
print("q:", q)
# Find the private key n
print("Factors of p-1:", factor(p-1))
print("Calculating discrete log for g and q...")
found_key = discrete_log(q, g)
print("Found private key:", found_key)
from Crypto.Util.number import long_to_bytes
print("The secret is:", long_to_bytes(found_key).decode())
このコードスニペットでは、楕円曲線のパラメータを定義し、それが実際に特異であることを検証します。曲線に対応する多項式の根を求め、そのうちどれが重根かを特定します。その重根を使って曲線を「移動」し、移動後の点 𝐺 と 𝑄 を得ます。次に、見つけた根から $\sqrt{t}$ を計算し、それを使って点 𝐺 と 𝑄 を数値 𝑔 と 𝑞 にマッピングします。𝑝 − 1 の素因数分解を出力して（DLP が実際に効率的に解けることを検証するため）、最後に DLP を計算し、結果を文字列として解釈します。
出力は次のとおりです： ``` double root: 1 single root: 102360775616927576983385464260307534406913988994641083488371841417601237589485 g: 79308184675041981395063385790064051127319168083579208141274962436724168376607 q: 72551144069373709737718398534799929820619379063890479978458954196900267190559 Factors of p-1: 2 * 41 * 2422091127107 * 3224683479179 * 3224849279789 * 3269304069319
今回は秘密鍵そのものにメッセージを隠しました。特異曲線であるため、SageMath では以前のように通常の方法で曲線を作成し、その上の点を定義して演算を行うことはできないことに注意してください。このコードでは、点の座標を定数変数として定義しました。点 `𝑄` を計算するために、Double And Add アルゴリズムの自作実装を使って秘密鍵と生成元を掛け合わせました。
## 曲線は超特異である
与えられた楕円曲線を法 `𝑝` とし、位数が `𝑛` の生成元を考えます。このとき、生成元に関する曲線の埋め込み次数 (Embedding Degree) は、$p^k ≡ 1\ \ \ \ (mod\ 𝑛)$ を満たす最小の数 `k` として定義されます。特定の変換により、ECDLP 問題は位数 $𝑝^𝑘$ の体における DLP 問題に帰着できます。`𝑘` の値は通常非常に大きな数（`𝑝` 自体とほぼ同程度）ですが、これが比較的小さい場合（たとえば `6` 未満）、その曲線は `supersingular`（超特異）と呼ばれ、この DLP 問題を効率的に解くことが可能になります。この攻撃は、3人の発明者（Menezes-Okamoto-Vanstone）の名前にちなんで MOV 攻撃と呼ばれます。
先ほど述べた変換は、2つの点を受け取り、複素数体上の何らかの数を返す関数です。使用できる変換としては Weil Pairing または Tate Pairing があり、これらをブラックボックスとして使用します。このような変換 `𝑇` は、任意の点のペア `𝑃`, `𝑄` に対して次の性質を満たします：
$T(mP, nQ)=T(P,Q)^{mn}$
したがって、2つの点 `𝐺` と `𝑄 = 𝑚𝐺` が与えられたとき、3つ目の点 `𝑅` をランダムに選び、次の2つの値を計算できます： \
$g = T(G, R)$ \
$q = T(Q, R)=T(mG,R)=T(G,R)^m=g^m$
ここから、位数 $p^k$ の体における `𝑔` と `𝑞` の DLP 問題を解くことができ、それによって秘密鍵 `𝑚` を見つけられます。この攻撃の背後にある数学のより詳しい説明へのリンクは、記事末尾の参考文献に含めておきました。
次のコードスニペットはこの攻撃を実行します：```python
p = 682209701131405092329016993551
a = -35
b = 98
E = EllipticCurve(GF(p), [a, b])
G = E(516365702870683577608927237052,
524474557735717484100814381066)
# Find embedding degree k
Gn = G.order()
k = 1
while p^k % Gn != 1:
k += 1
print("Found k:", k)
# Select private key, and calculate public key Q
private_key = 5072587499125503347
Q = private_key * G
# Define new curve mod p^k and the points on it
Ek = EllipticCurve(GF(p ^ k), [a, b])
Gk = Ek(G)
Qk = Ek(Q)
Rk = Ek.random_point()
# Find a point T with order d such that d divides G's order
m = Rk.order()
d = gcd(m, Gn)
Tk = (m // d) * Rk
assert Tk.order() == d
assert (Gn*Tk).is_zero() # Point INFINITY
# Using T, pair G and Q to integers g and q such that q=g^n (mod p^k)
g = Gk.weil_pairing(Tk, Gn)
q = Qk.weil_pairing(Tk, Gn)
# Alternatively:
#g = Gk.tate_pairing(Tk, Gn, k)
#q = Qk.tate_pairing(Tk, Gn, k)
# Make sure the pairing did not break anything
assert g ^ private_key == q
print("Calculating private key...")
found_key = q.log(g)
assert found_key == private_key
print("success!")
from Crypto.Util.number import long_to_bytes
print("The private key is:", long_to_bytes(found_key).decode())
このコードスニペットでは、曲線とその生成元を定義し、その埋め込み次数の値を計算します。この場合、それは 2 であるため、攻撃を実行するのが実用的です。元の曲線と同一の曲線を定義しますが、計算は法 $𝑝$ ではなく法 $𝑝^𝑘$ で行われます。2つの点 𝐺 と 𝑄 も新しい曲線上にあります。次に、位数が 𝑛 を割り切る3番目の点を見つけます。
3番目の点を使用して、点 𝐺 と 𝑄 を数値 𝑔 と 𝑞 にマッピングし、それらの離散対数を計算します。最後に、得られた結果が実際に正しいことを検証します。
出力は次のとおりです。``` Found k: 2 Calculating private key... success! The private key is: Festivus
計算の観点から言えば、今日では DLP 問題を比較的高効率に解く Index Calculus アルゴリズムが存在し、その計算量は $e^{O((log\ p^k)^{1/3}(log\ log\ p^k)^{2/3})}$ です。この式は一見恐ろしく見えるかもしれませんが、計算量が $O(\sqrt{p})=e^{O(log\ p)}$ である ECDLP アルゴリズムと比較すると、埋め込み次数（`𝑘` と表記）が確かに小さいという前提の下では、DLP 問題の方が解きやすいことが分かります。
## 異常曲線
ある曲線が、その位数（曲線上の点の数）が法 `𝑝` と正確に等しいという性質を持つ場合、その曲線は `Anomalous Curve` と呼ばれ、Smart's Attack と呼ばれる攻撃に対して脆弱です。この攻撃は `𝑝-adic numbers` を使用します。そのような数は、係数を伴う `p` の冪（正と負）の和として表現できます。形式的には、そのような数 `s` は次の形の級数です：
$s=\sum_{i = -k}^{\infty} a_{i}p^i = a_{-k}p^{-k} + \cdots + a_0 + a_1p + a_2p^2 + \cdots$
係数が $0 ≤ 𝑎_𝑖 < 𝑝$ の範囲の整数であり、級数は `𝑝` の正の冪の方向に無限に続くことができます。そのような数では、数字を左から右ではなく右から左に「見る」ため、そのような級数はある値に収束し得ます。そのような数は、私たちが慣れ親しんでいる数体系とは異なる数体系に属し、「通常の」数学的な規則とは大きく異なる振る舞いをします。このテーマだけで独立した記事が書けるほどであり、興味がある方のために、記事末の参考文献に、このテーマを比較的分かりやすく解説した動画へのリンクを掲載しました。
いずれにせよ、この攻撃では、与えられた曲線から、p-adic 数上で定義される新しい曲線が作成されます。元の曲線上の2つの点 `𝐺` と `𝑄 = 𝑚𝐺` が与えられたとき、それらを新しい曲線上の対応する点に写像します。得られた点の座標から `𝑚` を簡単に計算できます。
次のコードはこの攻撃を実行します：```python
def lift(P, E, p):
# lift point P from old curve to a new curve
Px, Py = map(ZZ, P.xy())
for point in E.lift_x(Px, all=True):
# take the matching one of the 2 points corresponding to this x on the p-adic curve
_, y = map(ZZ, point.xy())
if y % p == Py:
return point
p = 82880337306360052550952380657384418102169134986290141696988204552000561657747
a = 26413685284385555604181540288021678971301314378522544469879270355650843743231
b = 10017655579196313780863100027113686719855502076415017585743221280232958057095
E = EllipticCurve(GF(p), [a, b])
G = E(37991937053350834320678619330546903567320901767090609881924528835279022654346,
28947208718252880061735762506756351277969075978732800286053352115837132331595)
assert E.order() == p
private_key = 28153370716511608040616395150859085058202177279382452583684367923334520519740
P = private_key * G
# Lift the points to some new curve over p-adic numbers
E_adic = EllipticCurve(Qp(p), [a+p*13, b+p*37])
G = p * lift(G, E_adic, p)
P = p * lift(P, E_adic, p)
# Calculate discrete log
Gx, Gy = G.xy()
Px, Py = P.xy()
found_key = int(GF(p)((Px / Py) / (Gx / Gy)))
assert found_key == private_key
print("success!")
from Crypto.Util.number import long_to_bytes
print("The private key is:", long_to_bytes(found_key).decode())
このコードスニペットでは、元の曲線上の点を受け取り、新しい曲線上の点に対応付けるリフト関数が定義されています。次に、楕円曲線とその生成元を定義し、曲線の位数が確かに p であることを検証します。秘密鍵を選択し、対応する公開鍵を計算します。その後、攻撃を実行します。𝑝進数上の新しい曲線を定義し、リフト関数を使って元の点 𝐺 と 𝑃 を新しい曲線上の対応する点に写像し、それらを 𝑝 倍します。
各新しい点について、その 𝑥 座標と 𝑦 座標の比を計算します。この2つの値の商が、元の点のECDLP解となります。
出力は次のとおりです。``` success! The private key is: >>>>> Extraordinarily Nice <<<<<
この計算が機能する理由は、曲線上の点の数が正確に `𝑝` であるという事実に関係しています。この性質により、いくつかの写像（マッピング）を実行できます。その最後の写像は、𝑝進数上の曲線上の点を、$p^2$ を法とする数に対応付けます。この写像には、元の2点に対応する数のペアの比率が、2点の対数の結果と正確に一致するという性質があります。これらの写像はすべてブラックボックスとして扱いますが、記事の最後に関連する数学的説明への参照を追加しました。
# ECDSA 攻撃
## 署名する前にメッセージをハッシュ化しない場合
メッセージに署名するプロセスでは、まずメッセージのハッシュが計算され、そのハッシュの上位ビットが署名計算に使用されることを確認しました。ある署名生成・検証の実装で、このハッシュ化のステップが省略され、ハッシュの上位ビットを取る代わりに、メッセージからそのままビットを取ると仮定しましょう。そのような実装では、メッセージのうち署名に影響する部分はメッセージの先頭だけです。言い換えれば、メッセージとその署名がある場合、メッセージの先頭を保持して残りを変更しても、署名は有効なままです。これは本当に単純な攻撃です。
たとえば、次のメッセージを銀行に書き、ハッシュ化せずに署名したとします。```
"Please transfer 1,000$ from my account to GitHub so that they can continue hosting awesome repositories"
銀行はこのメッセージの検証に成功し、そのアクションを実行します。一部の...攻撃者...は次のメッセージを作成する可能性があります:``` "Please transfer 1,000$ from my account to GitHub and 1,000,000$ to Eli Kaski"
そして、先ほど作成した署名を使用します。この署名はこのメッセージに対しても有効で、銀行はアクションを実行します。良くないですね（まあ、誰にとってかによりますが）。
以下のコードは攻撃を示しています：```python
from ecdsa import SigningKey, NIST256p
signing_key = SigningKey.generate(NIST256p)
verifying_key = signing_key.verifying_key
class MyHash:
def __init__(self, data):
self.data = data
def digest(self):
return self.data
# Sign the message and verify the signature
message = "Please transfer 1,000$ to GitHub"
signature = signing_key.sign(message.encode(), hashfunc=MyHash)
assert verifying_key.verify(signature, message.encode(), hashfunc=MyHash)
# Construct an evil message and verify the original message's signature is valid for it as well
evil_message = "Please transfer 1,000$ to GitHub and 1,000,000$ to Eli Kaski"
assert verifying_key.verify(signature, evil_message.encode(), hashfunc=MyHash)
print("success!")
このコードスニペットでは、ライブラリ ecdsa が既知の曲線とともに使用されています。ここでは、ハッシュ関数を実装するはずのクラスを定義していますが、このクラスは実際にはハッシュ化を行わず、メッセージをそのまま残します。そのため、メッセージに署名する際、そのハッシュからではなく、元のメッセージの最初のビットだけが使用されます。その後、メッセージは署名され、検証は成功します。次に悪意のあるメッセージが作成され、コードは元のメッセージの署名が悪意のあるメッセージにも一致することを検証します。
このようなシナリオでは、独自の新しい署名を生成するための秘密鍵を入手していない可能性もありますが、1つの署名が与えられれば、同じプレフィックスで始まる限り、好きなだけ多くのメッセージに署名することができます。
𝑘 値を使用するメッセージ署名プロセスの一環として、ユーザーは 𝑘 の値をランダムに生成し、それを使用してメッセージに署名する必要があります。異なる署名では異なる 𝑘 値を使用することが非常に重要です。そうしないと、ユーザーが再生成せずに同じ値 𝑘 を使用して署名した2つのメッセージが与えられた場合、攻撃者はユーザーの秘密鍵を計算できる可能性があります。
前述のように、メッセージ署名中にユーザーは $r=x_1\ \ \ \ (mod\ p)$ および $s=k^{-1}(z+rd_A)$ を公開送信します。ユーザーが $𝑧_1$ と $𝑧_2$ に対応する2つの異なるメッセージに署名し、$𝑟, 𝑠_1$ と $𝑟, 𝑠_2$ の2組の値を公開送信した、つまりこれら2つの署名で同じ 𝑘 値を使用したと仮定します。ここで次が成り立ちます:
$s_1-s_2=k^{-1}(z_1+rd_A)-k^{-1}(z_2+rd_A)=k^{-1}(z_1+rd_A-z_2-rd_A)=k^{-1}(z_1-z_2)$
これにより、攻撃者は次を計算して 𝑘 の値を見つけることができます:
$\displaystyle k=\frac {z_1-z_2}{s_1-s_2}$
攻撃者が 𝑘 を見つけた後、いずれかの署名からユーザーの秘密鍵を計算できます。ここで次が成り立ちます:
$r^{-1}(ks-z)=r^{-1}(kk^{-1}(z+rd_A)-z)=r^{-1}(z+rd_A-z)=r^{-1}rd_A=d_A$
メッセージとその署名の 𝑟, 𝑠, 𝑧 の値と、攻撃者が見つけた 𝑘 の値が与えられると、攻撃者は $d_A=r^{-1}(ks-z)$ を計算できます。この時点から、攻撃者は秘密鍵を取得したユーザーに代わって、任意のメッセージに署名できます。
次のコードスニペットはこの攻撃を実行します:```python from ecdsa.ecdsa import curve_256, generator_256, Public_key, Private_key from Crypto.Util.number import bytes_to_long, long_to_bytes from hashlib import sha256 import random
curve = curve_256 generator = generator_256 n = generator.order()
secret_key = 6743529130774090927928101169617481154782309 public_key = Public_key(generator, generator * secret_key) private_key = Private_key(public_key, secret_key)
k = random.randrange(curve.p()) message1 = "Life is like a box of chocolates." message2 = "You never know what you're gonna get." z1 = bytes_to_long(sha256(message1.encode()).digest()) z2 = bytes_to_long(sha256(message2.encode()).digest())
signature1 = private_key.sign(z1, k) signature2 = private_key.sign(z2, k)
found_k = (z1 - z2) * inverse_mod(signature1.s - signature2.s, n) % n assert k == found_k
found_key = inverse_mod(signature1.r, n) * (found_k * signature1.s - z1) % n assert found_key == secret_key print("success!") print("The secret is:", long_to_bytes(found_key).decode())
このコードスニペットでは、ライブラリ`ecdsa`と既知の曲線を使用しています。秘密鍵を定義し、それを使って2つのメッセージに署名します。`𝑘`の値はランダムに生成されますが、2つの署名に対して同じ値のままです。2つのメッセージとその署名が与えられたとき、コードは前述の計算を実行して`𝑘`を求めます。最後に、見つけた`𝑘`の値を使って、前述のとおり秘密鍵を計算します。出力は次のとおりです。```
Success!
The secret is: Mistakes were made
興味深いことに、この攻撃は実際に2010年に使用されました。ソニーがPlayStationコンソールソフトウェアの署名メカニズムを安全でない方法で実装したときです。ソニーは署名に𝑘の静的な値を使用していたため、攻撃者は上記の計算を使用してソニーの秘密鍵を取得できました。これにより、任意のコードに署名し、PlayStationにそれを実行させることが可能になりました。後にこの能力は、コンソールに海賊版および非公式ゲームをインストールするために使用されました。
k 値を安全でない方法で生成するユーザーが𝑘を十分にランダムでない方法で選択した場合、秘密鍵が見つかる可能性があります。例えば、攻撃者が𝑘が非常に小さい値の範囲にあることを知っている場合、または𝑘の一部のバイトを知っている場合、単一の署名済みメッセージがあれば、単純なブルートフォースによってユーザーの秘密鍵を見つけることが可能です。攻撃者は、正しい値に到達して秘密鍵を取得するまで、前の攻撃で見た計算を異なる𝑘の値に対して実行します。
この問題を克服するために、ユーザーはランダムに何らかの値を生成し、そのハッシュを何らかのハッシュ関数で計算し、その結果を𝑘として使用することがあります。この方法は問題を引き起こす可能性があります。例えば、生成元の位数𝑛が256 bitであり、選択されたハッシュ関数がSHA-1であるとします。この関数の出力は160 bitの数値です。法𝑛の計算では、𝑘の値の先頭に96個のゼロが含まれることが知られており、𝑘は比較的小さい数値であることを意味します。このような状況では、𝑘の値はbiased（偏っている）と言われ、同じ秘密鍵で署名された複数のメッセージが与えられた場合、秘密鍵を見つけることができます。
この攻撃は、Lattice（格子）と呼ばれる代数構造に基づいています。直感的には、格子は𝑚次元空間内のベクトルの集合と考えることができ、整数係数を持つ「基底」ベクトルの線形結合として表現できます。数学的には、$\{b_1,\dots,b_d\}$ が $ℝ^𝑚$ 上の基底ベクトルである場合、それらに対応する格子は $L=$ $\{\sum_{i=1}^d a_ib_i\mid a_i \in Z\}$ です。この構造には既知の問題があります：格子の基底が与えられたとき、その格子内に存在する最短ベクトルを見つけるという問題です。この文脈では、直感的に言えば、「短いベクトル」とは、要素ができるだけゼロに近いベクトルです。この問題は最短ベクトル問題（SVP）と呼ばれ、NP困難であると考えられています。類似しているがより簡単な問題を解くアルゴリズムがあります。それは、何らかの短いベクトル、すなわち格子内の最短ベクトルに比較的「近い」ベクトルを見つける問題です。この問題は最近ベクトル問題（CVP）と呼ばれ、それを解くアルゴリズムの1つがLenstra-Lenstra-Lovász（LLL）アルゴリズムです。この攻撃では、このアルゴリズムをブラックボックスとして使用します。
𝑑個の署名済みメッセージが与えられると、ベクトル $(𝑘_1, \dots , 𝑘_𝑑)$ を含む格子を構築できます。このベクトルの各要素は、1つの署名に対応する𝑘の値です。LLLアルゴリズムは、この格子内の最短ベクトルへの近似を見つけます。𝑘の値は小さいことが知られているため、アルゴリズムが見つけた短いベクトルが少なくとも1つの正しいk要素を含む確率は高くなります。正しい𝑘が見つかれば、前の攻撃で見たように秘密鍵を計算できます。
この格子を構築するには、その基底ベクトルを定義する必要があります。この記事の最後の参考文献に、これらの基底ベクトルがどのように定義されるかを説明する記事へのリンクを含めました。技術的には、格子の基底ベクトルは行列として表現でき、その各行が1つの基底ベクトルの要素で構成されます。LLLアルゴリズムの精度を向上させるには、この行列に、𝑘の値の期待されるサイズと𝑘と𝑛の比率に関する情報を含む2つの列を追加することをお勧めします。この改善点は、添付した参考文献でも説明されています。次のコードスニペットは、この攻撃を示しています：```python
from ecdsa.ecdsa import curve_256, generator_256, Public_key, Private_key
from Crypto.Util.number import bytes_to_long, long_to_bytes
from hashlib import sha1
import random
def build_matrix(signatures, bias, q): # M matrix should be: """ [ B 0 m'1 m'2 m'2 ... m'n 0 B/q r'1 r'2 r'3 ... r'n 0 0 0 0 q * I 0 0 ] where: m' = s^-1 * m r' = s^-1 * r """
# Construct the first 2 rows of M:
row1 = [bias, 0]
row2 = [0, bias / q]
for m, r, s in signatures:
row1.append((inverse_mod(s, q) * m) % q)
row2.append((inverse_mod(s, q) * r) % q)
top_rows = Matrix(QQ, [row1, row2])
# Construct the q*I block along with 2 columns of zeros
zero_cols = zero_matrix(QQ, len(signatures), 2)
qI = q * identity_matrix(QQ, len(signatures))
bottom_rows = block_matrix([[zero_cols, qI]])
# Combine all rows into one matrix
M = top_rows.stack(bottom_rows)
return M
def find_private_key(L, signatures, public_key): # Check if any valid k was found in L generator = public_key.generator q = generator.order() for row in L.rows(): for i in range(len(signatures)): m,r,s = signatures[i] # Skip the first two vector components we used to improve LLL possible_k = row[i+2] # LLL might have swapped the sign of the found short vectors for k in [possible_k, -possible_k]: d = inverse_mod(r,q)(ks-m) % q if d*generator == public_key.point: return d
curve = curve_256 generator = generator_256 q = int(generator_256.order())
secret_key = 1793056234309773077862125006843383726029262764680727851636 public_key = Public_key(generator, generator * secret_key) private_key = Private_key(public_key, secret_key)
messages_to_sign = [ "And then I go and spoil it all", "By saying somethin' stupid like", "I love you" ]
signatures = [] for message in messages_to_sign: message_hash = bytes_to_long(sha1(message.encode()).digest()) k = bytes_to_long(sha1(long_to_bytes(random.randrange(q))).digest()) signature = private_key.sign(message_hash, k) signatures.append((message_hash, signature.r, signature.s))
bias = 2^160 M = build_matrix(signatures, bias, q)
L = M.LLL()
found_key = find_private_key(L, signatures, public_key) assert found_key == secret_key print("success!") print("The secret is:", long_to_bytes(found_key).decode())
このコードスニペットでは、標準曲線が使用され、秘密鍵が選択され、そこから対応する公開鍵が計算されます。3つのメッセージが作成され、SHA-1ハッシュ関数の結果である3つのランダムな `k` 値で署名されます。次に、記事で説明したようにラティスの基底に対応する行列を作成し、その行列に対してLLLアルゴリズムを実行します。その後、結果の行列の行を調べ、いずれかの行に正しい `𝑘` の値が見つかるかどうかを確認します。
このチェックは、前回の攻撃で見たように、候補となる `𝑘` から秘密鍵を計算し、得られた鍵が実際に正しいかどうかを確認することで実行されます。最後に、見つかった秘密鍵が確かに正しいことを確認します。出力は次のとおりです。```
success!
The secret is: I am Jack's broken heart
この攻撃の複雑さはLLLアルゴリズムの複雑さと同じであり、$O(d^6\ \log^3B)$ です。ここで 𝐵 は 𝑘 のバイアスの長さ（この場合は $2^{160}$）を示し、𝑑 は署名済みメッセージの数（この場合は3）を示します。攻撃を実行するために必要な署名済みメッセージの最小数はいくらかという疑問が生じます。その答えは $\displaystyle d=O(\frac {\log n}{\log n-\log B})$ です。ここで 𝑛 は生成元の位数であり、𝐵 はバイアスです。この説明は、この記事の最後に添付した参考文献の2番目のリンクに記載されています。
実際には、この攻撃の変種は、𝑘 の上位ビットが既知である場合や、𝑘 の任意のビットだけが既知である場合にも実行できます。この攻撃は、1ビットだけの値が既知である場合や、1ビットだけの値が50%を超える確率で既知である場合でも実行できます。しかしもちろん、これらの場合、攻撃を実行するにははるかに多くの署名済みメッセージが必要です。
署名検証のプロセスでは、署名者が値のペア 𝑟 と 𝑠 を検証者に送信することを確認しました。例えば、HTTPSプロトコルを実装するブラウザでは、この値のペアを証明書で送信するのが一般的であり、証明書には署名者が使用した曲線に関するデータも含まれる場合があります。検証者は、証明書内の曲線データが事前に合意された曲線と一致することを確認する必要があります。一致しない場合、問題が発生する可能性があります。
ある曲線において、アリスが秘密鍵 $d_A$ とそれに対応する公開鍵 $𝑃_𝐴$ を持っているとします。つまり、この曲線の生成元 𝐺 に対して $𝑃_𝐴 = 𝑑_𝐴𝐺$ が成り立ちます。秘密鍵 $𝑑_𝐴$ を用いて、アリスはECDSAプロトコルの定義で見たように自分のメッセージに署名できます。署名を検証する側がユーザーから生成元 𝐺 も受け取り、ユーザーから受け取った生成元が本当に合意された生成元であることを検証しないと仮定します。攻撃者は、アリスの公開鍵である点 $𝐺^′ = 𝑃_𝐴$ を生成元として送信できます。攻撃者は「偽の」秘密鍵として値 $𝑑_𝐴^′ = 1$ を選びます。したがって、$𝑃_𝐴 = 𝑑_𝐴^′𝐺^′$ が成り立つことは明らかです。これは、攻撃者がアリスの公開鍵に対応する秘密鍵を持っていることを「証明」できることを意味します。したがって、攻撃者は任意のメッセージを作成し、通常の方法で $𝑑_𝐴^′$ を用いて値のペア 𝑟 と 𝑠 を計算でき、結果として得られる署名は検証に成功します。
直感的には、署名検証のプロセスにおいて、署名者は自分が公開鍵の「所有者」であることを証明します。公開鍵は曲線上の「目的地」の点です。これは、開始点から目的地の点に到達するために何歩進むべきかを知っているのは署名者だけだからです。検証者がユーザーから受け取った開始点が本当の開始点であることを検証しない場合、攻撃者は開始点が目的地の点であり、そこから進む歩数がゼロであると決めることができます。署名検証の他のすべての部分は同じままであり、署名は検証に成功します。この攻撃はCurveballと呼ばれます。
この攻撃は、追加の値を使用して一般化できます。攻撃者はある値 𝑥 を選択し、$𝐺^′ = 𝑥𝑃_𝐴$ を計算します。偽の秘密鍵は $𝑑'_𝐴 = 𝑥^{−1}\ \ \ \ (mod\ n)$ になります。すると、$𝑑'_𝐴𝐺^′ = 𝑥^{−1}𝑥𝑃_𝐴 = 𝑃_𝐴$ が成り立つことは明らかです。
次のコードはこの攻撃を示しています。```python from ecdsa.ecdsa import generator_256 from Crypto.Util.number import bytes_to_long from hashlib import sha256 import random
def hash_message(message): return bytes_to_long(sha256(message.encode()).digest())
def verify(public_key, G, message, r, s): n = G.order() if r < 1 or r > n - 1 or s < 1 or s > n-1: return False hash = hash_message(message) u1 = (hash * inverse_mod(s, n)) % n u2 = (r * inverse_mod(s, n)) % n P = u1 * G + u2 * public_key return P.x() % n == r
def sign(private_key, G, message): n = G.order() k = random.randrange(n) hash = hash_message(message)
r = (k * G).x() % n
s = inverse_mod(k, n) * (hash + r * private_key) % n
return r, s
G = generator_256 n = G.order() private_key = random.randrange(n) public_key = private_key * G
message = "Let me be the one that shines with you" r, s = sign(private_key, G, message) assert verify(public_key, G, message, r, s)
x = random.randrange(n) fake_G = x * public_key fake_private_key = inverse_mod(x, n) assert fake_private_key != private_key assert fake_G != G
evil_message = "Where did I go wrong?" r, s = sign(fake_private_key, fake_G, evil_message) assert verify(public_key, fake_G, evil_message, r, s)
このコードスニペットでは、既知のジェネレータ、秘密鍵、公開鍵を選択します。メッセージに署名し、それが正常に検証されることを確認します。次に、元の公開鍵の両方に一致する偽の秘密鍵と偽のジェネレータを作成します。悪意のあるメッセージが偽の鍵で署名され、最後に偽の署名が元の公開鍵で正常に検証されます。このコードの問題は、検証アルゴリズムがジェネレータ `𝐺` が公開鍵と一致することを検証しないことです。この攻撃ではユーザーの秘密鍵を見つけることはできませんでしたが、攻撃者は署名検証の誤った実装を悪用して、正常に検証される署名を作成できます。ただし、攻撃者は、署名検証の正しい実装で実際に正常に検証される「本物の」署名を作成することはできません。
興味深いことに、これは Windows CryptoAPI アーキテクチャに存在した実際の脆弱性です。証明書の署名を検証する関数では、曲線のパラメータが証明書自体に含まれている場合、それらのパラメータの検証が不十分でした。特に、ジェネレータが公開鍵に対応するジェネレータであるかどうかのチェックはありませんでした。攻撃者は、信頼できる認証局によって署名されたように見えるため、信頼されていると見なされる偽の証明書を作成できました。これは、証明書に悪意のある曲線フィールドを追加し、前述の方法でジェネレータを選択することによって行われました。この脆弱性は NSA によって発見され、2020 年に修正され、CVE-2020-0601 の番号が割り当てられました。
# 結論
## ECDH 攻撃の概要
| 問題の種類 | 問題 | 攻撃 | 攻撃の仕組み | 攻撃の複雑さ |
| ------------- | ------------- | ------------- | ------------- | ------------- |
| 安全でないジェネレータを持つ曲線の選択 | ジェネレータ `n` の位数が小さすぎる | Baby-Step Giant-Step | 中間一致 | $𝑂(\sqrt n)$ |
| 安全でないジェネレータを持つ曲線の選択 | ジェネレータ `n` の位数が平滑数である | Pohlig-Hellman | `𝑛` を素因数に分解し、それぞれを個別に攻撃し、中国剰余定理を用いて結果を組み合わせる | $O(\sqrt{p_{max}})$。ここで $p_{max}$ は `𝑛` の分解における最大の素因数 |
| 安全でないジェネレータを持つ曲線の選択 + 安全でない秘密鍵の選択 | ジェネレータ `n` の位数がほぼ平滑数であり、秘密鍵が小さい | Improved Pohlig-Hellman | `𝑛` を素因数に分解し、大きすぎる因数を破棄し、それぞれを個別に攻撃し、中国剰余定理を用いて結果を組み合わせる | $O(\sqrt{p_{max}})$。ここで $p_{max}$ は `𝑛` の分解における最大の素因数 |
| ECDH の誤った実装 | 点が曲線上にあることを検証しない | Invalid Curve Attack | 悪意のある曲線上の位数の小さい点を公開鍵として送信し、それぞれを個別に攻撃し、中国剰余定理を用いて結果を組み合わせる | $𝑂(𝑛_{𝑚𝑎𝑥})$。ここで $𝑛_{𝑚𝑎𝑥}$ は悪意のある点の位数の中で最大の位数 |
| 曲線パラメータの安全でない選択 | 曲線が特異である | ECDLP の DLP への帰着 | 点の加算を整数の乗算に変換する方法で点を数値にマッピングする | $O(\sqrt{p_{max}})$。ここで $p_{max}$ は $(p-1)$ の分解における最大の素因数 |
| 曲線パラメータの安全でない選択 | 曲線が超特異である | ECDLP の DLP への帰着 | 点の加算を整数の乗算に変換する方法で点を数値にマッピングする | $e^{O((log\ p^k)^{1/3}(log\ log\ p^k)^{2/3})}$。ここで `k` はジェネレータに関する埋め込み次数 |
| 曲線パラメータの安全でない選択 | 曲線が異常である | Smart 攻撃 | 曲線上の点から `p-adic` 数上の曲線上の点への、そして整数へ戻る一連の写像 | $O(1)$ |
## ECDSA 攻撃の概要
| 問題の種類 | 問題 | 攻撃 | 攻撃の仕組み | 攻撃の複雑さ |
| ------------- | ------------- | ------------- | ------------- | ------------- |
| 署名と検証の誤った実装 | 署名する前にメッセージをハッシュ化しない | 署名済みメッセージが与えられたとき、同じ署名に対応する追加のメッセージを偽造する | メッセージのプレフィックスをそのまま保持し、残りの部分を変更する | $O(1)$ |
| 署名アルゴリズムの誤った使用 | 異なる署名で同じ `k` の値を再利用する | ユーザーの秘密鍵を見つける | `k` の値を見つけ、それからユーザーの秘密鍵を計算する | $O(1)$ |
| 署名アルゴリズムの誤った使用 | `k` の値を安全でない方法で生成する | 複数の署名済みメッセージが与えられたとき、ユーザーの秘密鍵を見つける | 問題を格子内の短いベクトルを見つける問題に帰着させ、`k` の値を見つけ、それからユーザーの秘密鍵を計算する | $O(d^6\ \log^3B)$。ここで `B` は `k` のバイアス、`d`d は署名済みメッセージの数 |
| 検証の誤った実装 | ジェネレータが有効であることを検証しない | 正常に検証される署名の偽造 (Curveball) | 別のユーザーの公開鍵に対応する偽のジェネレータと秘密鍵を選択する | $O(1)$ |
## これらの攻撃に対する防御
ECDH では、プロトコルの開始時に両当事者が曲線について合意する必要があることに注意してください。ユーザーが攻撃者と通信しており、攻撃者が曲線パラメータを提供する側である場合、攻撃者は安全でないパラメータを提供できます。その結果、攻撃者はユーザーの秘密鍵を取得できます。ユーザーが常に同じ秘密鍵を使用する場合、攻撃者はそのユーザーと他の任意のユーザーとの間のすべての会話を復号化できます。そのため、信頼できない場合、馴染みのないユーザーに曲線パラメータを提供させないことが非常に重要です。さらに、外部のユーザーから受信したすべての点が、合意した曲線上に実際にあることを確認する必要があります。そしてもちろん、選択した曲線自体が、これまでに見てきた既知の攻撃のいずれかに対して脆弱でないことを確認する必要があります。また、ECDH プロトコルを使用するたびに新しい秘密鍵を使用することをお勧めします。
同様に、ECDSA では、署名アルゴリズムと検証アルゴリズムを適切に実装するように注意する必要があります。メッセージのハッシュ化と、プロトコルを使用するたびの `𝑘` 値のランダムかつ安全な生成を省略しないでください。そしてもちろん、署名検証では、ジェネレータをユーザーから受け取った場合は、それが以前に合意されたものであることを確認してください。
## 参考文献
- この記事では、Christof 著の書籍 Understanding Cryptography のグラフ図を使用しました。
paar:\
https://gnanavelrec.wordpress.com/wp-content/uploads/2019/06/2.understanding-cryptography-by-christof-paar-.pdf
- 暗号学的楕円曲線がどのように見えるかを示すサイト:\
https://graui.de/code/elliptic2/
- 楕円曲線における加算演算と乗算演算の詳細な解説:\
https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication
- 楕円曲線と点の加算の入門に関する講義 - Christof Paar 著:\
https://www.youtube.com/watch?v=vnpZXJL6QCQ
- ジェネレータ、ECDLP、問題の難しさ、ECDH、Double And Add に関する講義 - Christof Paar 著:\
https://www.youtube.com/watch?v=zTt4gvuQ6sY
- さまざまな暗号化アルゴリズムのセキュリティレベルの解説:\
https://en.wikipedia.org/wiki/Security_level
- ECDH の解説:\
https://en.wikipedia.org/wiki/Elliptic-curve_Diffie%E2%80%93Hellman
- ECDSA の解説:\
https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm
- ElGamal による署名の解説:\
https://en.wikipedia.org/wiki/ElGamal_signature_scheme
- 中国剰余定理の解説:\
https://en.wikipedia.org/wiki/Chinese_remainder_theorem
- 特異曲線の判別式と、それが重根を持つという事実との関係の解説:\
https://www.quora.com/For-an-elliptic-curve-in-the-form-Y-2-X-3+AX+B-why-is-4A-3+27B-2-neq-0-the-condition-for-non-singularity
- 特異曲線における点と数の間の写像の、小さな数による例:\
https://crypto.stackexchange.com/questions/61302/how-to-solve-this-ecdlp/61434#61434
- 𝑝 進数の解説:\
https://en.wikipedia.org/wiki/P-adic_number \
https://www.youtube.com/watch?v=3gyHKCDq1YA
- MOV 攻撃の背後にある数学の解説:\
https://risencrypto.github.io/WeilMOV/
- Smart 攻撃の背後にある数学の解説(かなり複雑です。警告しておきます):\
https://wstein.org/edu/2010/414/projects/novotney.pdf \
http://www.monnerat.info/publications/anomalous.pdf
- 格子ベースの攻撃と LLL アルゴリズムの解説:\
https://forum.vac.dev/t/lattice-attacks-on-ecdsa/136 \
\
この攻撃は、Joachim Breitner と Nadia Heninger による論文のパート 4 に基づいています:\
https://eprint.iacr.org/2019/023.pdf
- CVP 問題の解説:\
https://en.wikipedia.org/wiki/Lattice_problem#Closest_vector_problem_(CVP)
- LLL アルゴリズムの解説:\
https://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm