楕円曲線暗号(Elliptic Curve Cryptography)について思い出すお

ECIESの記事で、楕円曲線暗号について取り上げましたがRSAに比べて聞き慣れなかったり、 聞いたことがあっても楕円曲線がどのようなものか難しくてよくわからないって人もいるのではないでしょうか。 私も数年前の大学の講義を思い出しつつおさらいしてみようと思います。

まず、楕円と楕円曲線は違うものです。字面が似ているから楕円を思い浮かべた人もいるかもしれませんので 最初に言っておきます。大事なことなので2回言います。楕円と楕円曲線は違います。

さて、ECIESの説明の中では、計算機上の楕円曲線暗号の実装の説明が主たる目的であったので 「楕円曲線上の離散対数問題を利用した楕円曲線暗号」と説明しましたが、これだけで楕円曲線暗号を理解できたら苦労はないでしょう。

社内からも、ECIESの記事が難しいという声が聞こえてくるのでもう少し概念的な話をしたいと思います。

楕円曲線とは

まず、「楕円と楕円曲線は違うものだ」というところから話を始めましたが、では「楕円曲線とは何か?」という問に答えることから始めたいと思います。

楕円曲線とは以下の様な数式を満たす曲線のことです。

$$ y^2 = x^3 + ax +b $$

数式だけではわかりにくいので、実数上のイメージしやすい楕円曲線の一例を絵で書くとこんな感じです。

images

\( a \)と\( b \)の2つのパラメータ次第では、他の形にもなりますが、 代表的な例として覚えておくとよいでしょう。

離散対数問題

次に離散対数問題について説明します。

ある素数\( p \)が与えられた時に、

$$ g^i = a \;\;\; (a, g \in Z \pmod{p}) $$

を満たす\( i \)を見つける問題を離散対数問題といいます。

\( g \)と\( i \)がわかっている時に\( a \)を求めることは容易なのに対して、 \( a \)と\( g \)から\( i \)を求めることが困難であることを利用して暗号として利用されています。

また、集合\( Z \pmod{p} \)のことを有限体と呼びます。 有限体は、集合に含まれる元(わかりやすくいうと各要素)の間で四則演算を定義することができ、 またその四則演算が閉じているような有限の集合のことです。 有理数同士の和、差、積、商が有理数となるようなときに、「四則演算が閉じている」といいます。

楕円曲線上の離散対数問題

楕円曲線と離散対数問題についてなんとなく理解できたところで、「楕円曲線上の離散対数問題」について話します。

楕円曲線離散対数問題とは、

\( p > 3 \)を素数とし、有限体\( \mathbb{F}_p \) 上の楕円曲線

$$ \ E: \;\;\; y^2 = x^3 + ax +b \;\;\; ( a,b \in \mathbb{F}_p) $$

とするとき、\( E ( \mathbb{F}p ) \ni S, T \) (楕円曲線の点\(S = (xS, yS) \)と\( T = (xT , y_T ) \))が \( T = dS \)を満たす整数\( d \)を見つける問題のことです。

Elliptic Curve Discrete Logarithm Problemの頭文字をとって楕円曲線離散対数問題をECDLPと呼びます。 この楕円曲線離散対数問題こそが楕円曲線暗号のことです。

楕円曲線暗号と楕円曲線離散対数問題の計算困難性

楕円曲線離散対数問題の説明で登場した\( T \)と\( S \)と\( d \)の関係から、 \( T \)と\( S \)がわかっている時に\( d \)を求めることが大変難しいのに対して、 \( d \)と\( S \)から\( T \)を求めることは極めて簡単に行えることに着目して 楕円曲線離散対数問題を暗号として利用しています。

しかし、この問題が暗号に使えるくらい計算困難性があり、またRSAに比べて少ない計算量や鍵長でも 同じくらいの暗号強度があるということを理解することは難しいと思います。

それでは、楕円曲線暗号を解読することにどの程度の計算困難性があるのかもう少し調べてみましょう。

ECC Challengeという取り組みが、まさに楕円曲線暗号を実際に攻撃する取り組みとしては有名です。 ECC Challengeでは、2002年に109ビットの楕円曲線離散対数問題が解読されています。

この際には、約10,000台の計算機を用い、549日を書けて解読したそうです。 10年前の計算機ですが途方も無いリソースを必要したことがわかります。

ECC challenge以外でも、2009年に112ビットの楕円曲線離散対数問題を200台のPlayStation 3を用いて半年かけて解読されています。

現在、楕円曲線暗号として使われている224ビットや256ビットの楕円曲線離散対数問題の解読は、 109ビットや112ビットに比べて遥かに困難であるため楕円曲線暗号の安全性が担保されています。

楕円曲線や楕円曲線離散対数問題を理解することで少しでも楕円曲線暗号を知るきっかけになれれば幸いです。