_ [sec]わか(った気にな)る楕円曲線暗号のメモ

なるほど、と思った点をメモ。抄訳にならないよう注意しながら。

http://arstechnica.com/security/2013/10/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/

まず、公開鍵暗号には良い一方向関数 (RSA では累乗) が必要。「良い」というのは、一方向と逆方向との計算の難しさの差が大きいこと。累乗の場合、かけ算は簡単で、因数分解は大変だから、良い、はずだった。

http://ja.wikipedia.org/wiki/%E7%B4%A0%E5%9B%A0%E6%95%B0%E5%88%86%E8%A7%A3#.E7.B4.A0.E5.9B.A0.E6.95.B0.E5.88.86.E8.A7.A3.E3.82.A2.E3.83.AB.E3.82.B4.E3.83.AA.E3.82.BA.E3.83.A0

しかし、素因数分解の計算量を減らすアルゴリズムが発見されている。大きい数ほど効果が大きいので、鍵のビット数が増えるほど前述の意味で「良く」ないことになる。やばい。4、5 年で RSA + DH は崩壊するという学者もいて、Stamo さんというらしいが私とは関係ない。

そこで楕円曲線暗号ですよ。

http://ja.wikipedia.org/wiki/%E6%A5%95%E5%86%86%E6%9B%B2%E7%B7%9A#.E8.AA.AC.E6.98.8E

楕円曲線は楕円ではなく、吸盤とか、てるてる坊主みたいなグラフ。

http://ja.wikipedia.org/wiki/%E6%A5%95%E5%86%86%E6%9B%B2%E7%B7%9A%E6%9A%97%E5%8F%B7#.E6.A5.95.E5.86.86.E6.9B.B2.E7.B7.9A.E4.B8.8A.E3.81.AE.E5.8A.A0.E7.AE.97

このグラフは上下で対称、かつ直線と最大 3 点で交わる。グラフ上の 2 点の加算 (Ars の記事では "dot" という演算) を、「その 2 点を通る直線がグラフと交わる別の 1 点を上下反転した点を求めること」と定義する (ひとつの点の「倍」は、グラフの接線を伸ばしていってグラフと交わる点を上下反転した点)。

言葉にするとよくわからんので Ars の 2 ページ目 のアニメを参照。じつによくわかる。A + B = C のあとで、A + C = D, A + D = E まで順に図示してくれている。

これが累乗に似てる。A×A=B, A×B=C, A×C=D ... って計算するのと同じ感じ。そして A の n 倍を計算するのは簡単だけど、出てきた D なり E なりを見て「これは A の n 倍だ！」と言うのが難しいところも同じ。だから、一方向関数としての出来が「良い」ことになる。30 年近くたってもなお計算を簡単にする方法がひとつもないのもポイント。

http://ja.wikipedia.org/wiki/%E6%A5%95%E5%86%86%E6%9B%B2%E7%B7%9A#.E6.95.B4.E6.95.B0.E7.82.B9

グラフの整数点だけを選び、適当な素数を法として剰余を取ると、Ars の 2 ページ目のさらに後半にあるアニメのように、一見ランダムな点々になる (ただし上下で対称) けど、加算や n 倍は同じ要領でできる。

http://www.maitou.gr.jp/rsa/rsa11.php

RSA ではふたつの素数の積を法として、元の数を pub 乗すると暗号化、それを priv 乗すると復号だった。

http://d.hatena.ne.jp/Grenouille/20110624/1308891491

ECC では、でかい素数をそのまま法とする。さらに、楕円曲線の関数と、その上にある公開点 p もシステムとして決めておく……のかな？ そして、その点 p を乱数 priv の回数だけ倍したものを公開鍵とする。Ars の記事ではそれをどうするか書いてなかったけど、ぐぐったら上の Grenouille さんの記事があった。単純に相手の公開鍵に自分の秘密の乱数 priv をかけると共通鍵 (p × 相手の priv × 自分の priv) ができるのか。(そして、掛け算は簡単だけど割り算が難しいので、盗聴者が両方の公開鍵を入手しても割れないということかな。いや、そもそも「両方の公開鍵を掛け算する」ことがナンセンスなのか。)

だから、RSA は速度を気にしなければ DH や共通鍵なんて不要なのに対して、ECC は必ず共通鍵が出てくるということか。じゃあ理解を優先するなら RSA の説明は省いても良かったんじゃないかという気がする。それより DH の説明をして、それと比較しつつ ECC の実装を説明したほうが良かったんじゃ……？ まあいいか。

利点

基本的には前から言われているとおり。 228bit の RSA 鍵を破るのはスプーン一杯の水を沸かす程度のエネルギーでできるけど、228bit の ECC 鍵は地球上の水すべてを沸かすエネルギーが必要。計算量が前より少ないから前より速くて安全、という話ではなく (もちろんそれもあるけど)、今はそれよりむしろモバイル機器に使えていいよね、という視点らしい。

問題点

まずは Dual_EC_DRBG が問題になってるらしい。NSA がバックドアを仕掛けているんじゃないかとか、そういうあれ。だからと言って楕円曲線自体が弱いっていうのではなく、乱数とか仕様策定といった副次的なところに弱点があるかもしれないということか。現在の実装はほとんどが NIST/NSA の支持するものらしい。だから djb とかの作った曲線でやれば？ という話になるけど、そしたらまた普及まで何年も必要じゃないか、と。4〜5 年で RSA がダメになるんじゃないの？ 間に合わないじゃん、と。

あと特許は前から言われてるとおり。だけど、さいきんは解決しつつあるという感じなのかな。

そして RSA と比べて特に弱いのは RNG への依存らしい。Android で Bitcoin の保護がだめになったりしたらしい。