nemの楕円曲線暗号を基礎から学んでみる(数式)-その3 楕円曲線離散対数問題

nemの楕円曲線暗号を基礎から学んでみるシリーズ

nemの楕円曲線暗号を基礎から学んでみる(数式)-その2 スカラー倍算の高速化の続きです。

次はいよいよ、楕円曲線暗号の解読が実質的に、ほとんど不可能な理由を考えていきましょう。

前回まで、素体\(\mathbb{F}_p\)上の楕円曲線の有理点の集合で、適当にベースポイント\(P\)を選びスカラー倍算を計算するのは、比較的簡単であることを学びました。

計算の分野では問題の難しさは、その問題が入力に対し、どれぐらいの時間で解けるかを目安に考えることが多いです。特に、ある入力の長さ\(n\)に対して平均でどれぐらい時間がかかるかとか、最悪どれぐらいかかるかなんかを考えたりします。ここでいう簡単とか難しいと言うのは、そういう意味です。

つまり、実質的に不可能とは、現在用いられているコンピュータの性能を以て問題に取り組んでも、入力の長さが大きい場合などは、現実的な時間(せいぜい数年)では解けないことを意味します。

 

ここでは今までとは逆に、点\(Q\)が点\(P\)の何倍になっているのかを求める問題を考えます。これは、楕円曲線離散対数問題と呼ばれます。

この問題に対する解法ですぐに思いつくのは、総当たり法です。

しかし、その1の\(p=5\)の場合など、点位数が小さい場合はいいですが、NEMのTechnical Referenceを見てみれば、

「曲線上の巡回群\(G\)に対応するベースポイントを\(B\)とします。この群は、\(q=2^{252}-27742317777372353535851937790883648493\)個の元を持ちます。」

とあります。CPUのクロック周波数は\(5GHz\)程度ですから、一秒に\(5\times10^{9}\)回命令を回せます。本当は命令と言うと語弊がありますが、ここでは無視しましょう。シングルコアを想定して、楕円曲線離散対数問題の正解が、\(d=2^{200}\)のところにあった場合を考えます。一年は\(3\times 10^7\)程度ですから、

\[{2^{200}}/{5\times 10^9}/{(3\times 10^7)}\simeq 10^{43}年\]

かかってしまいます。ベースポイントの位数を\(l\)とすれば、かかる時間は最悪の場合、最悪計算量\(O(l)\)(\(l\)に比例する程度の時間)になります。

(逆に今まで考えてきた掛け算の場合は、\(100\times P=(64+32+4)\times P\)のような計算ができますから、比較的簡単です。つまり、もとの問題の計算時間の\(log\)程度で抑えることができます。)

ちょっと現実的ではありません。もうちょっと簡単に暗号を打ち破る方法はないのでしょうか。

 

Baby-step Giant-step法

楕円曲線離散対数問題\(Q=d\times P\)に対し、ベースポイント\(P\)の位数\(l\)を用いて、\(m=[\sqrt{l}]\) ([]はガウス記号)とします。このとき、\(d=sm+t\)(\(s\)は\(d\)を\(m\)で割った商\(,t\)は\(d\)を\(m\)で割ったあまり)とします。

\(R=m\times P\)として、

\[Q=d\times P=(sm+t)\times P=s\times R+t\times P\]

となるから、\(s,t\)は以下を満たします。

\[Q-t\times P=s\times R\]

そこで、

\(\{Q-t\times P|t\in \mathbb{N},0\leq t\leq m-1\}\),

\(\{s\times R|s\in \mathbb{N},0\leq s\leq m-1\}\)

のデータベースをあらかじめ計算し、この中で互いに同じものがあれば、それは答えになります。

 

しかしこれでも、計算量は\(O(\sqrt{l})\)です。

ちなみに、\(y=log(x),y=x,y=\sqrt{x}\)のグラフはこんな感じです。

 

\(l\)がさらに大きいところだと、コイツらの差はアホみたいに大きくなります。それぐらい、計算量のオーダーは大事だと言うことです。

 

さらに、\(\rho\)法と言う、よりすぐれたアルゴリズムがあります。最近の、大きなサイズの離散対数問題を突破した手法に関しては、全てこの方法が用いられています。

楕円曲線離散対数問題\(Q=d\times P\)に対し、何らかの方法(実際にはランダム)で

\[s\times P+t\times Q=s^\prime \times P+t^\prime \times Q\]

となる、互いに異なる\(s,s^\prime,t,t^\prime\)が見つかったとします。

すると、

\[(t-t^\prime)\times Q=(s^\prime-s)\times P\]

よって、\(\frac{s^\prime-s}{t-t^\prime }\)(ベースポイント\(P\)の点位数\(l\)の\(mod(l)\)での除算)が答えになります。

\(i\)番目にランダムに選ばれた点を\(R_i=s_i\times P+t_i\times Q\)とすると、このような点同士をいかに早く見つけるかが問題です。この特別な点どうしを、コリジョンペアと言います。

ランダムな点を効率的に求めるためには、つぎの\(R\)として、以下の\(f(R)\)を用います。

\[f(R)=R+M_i(ここで、i=x(R)mod4)\]

ただし、\(M_0,M_1,M_2,M_3\)はあらかじめランダムにとった点であり、\(x(R)\)は\(R\)の\(x\)座標です。

 

この\(4\)という数字は、大規模な問題の場合はランダム性の向上のため\(20\)などの大きな数にします。

これは、線形合同法と言う基本的な乱数生成法で、C言語のrandは線形合同法を用いています。ちなみに、pythonはメルセンヌツイスタです。

 

この\(rho\)法を用いた攻撃は、誕生日攻撃と呼ばれます。

点の集合から2つの点をランダムに選んで試すのと、

クラスから2人同じ誕生日の人を選んでくるのが、同じ構造を持っているからです。

詳細は省きますが、誕生日攻撃において、\(50\%\)の確率で攻撃が成功する試行回数は\(O(\sqrt{N})\)であることが、それほど難しくない数理的解析から分かります。これはBaby-step Giant-step法と同じですが、ある方法を用いることで保存すべき情報が減らせるから、こちらの方が優れているとされています。

このように、暗号の生成(スカラー倍算)に比べ、楕円曲線離散対数問題を解くのにメチャクチャ時間がかかる(少なくとも、それよりいいアルゴリズムが見つかっていない)ため、楕円曲線暗号の安全性が保障されています。

ちなみに、量子計算機を用いた楕円曲線離散対数問題の効率的な解法はすでに知られているようで、これが最近ニュースでよく見る暗号の問題かと、やっと納得に至りました。