_ [sec]OpenSSL 開発者のブログからも ECC について抜粋

「ここはどうなってんの？」と思ったことが、ギリギリ理解できる程度の分かりやすさで書かれている気がしたので、無断で一部だけ訳してみる。

(略) しかし楕円曲線は単に方程式を満たす点の集まりというだけでなく、ちょっとした工夫で群を作れる構造だ。(群というのは数学用語)

群であるためには四つの条件を満たす必要がある。二つの要素を足してできた第三の要素も群の要素であること。すべての要素において (a + b) + c = a + (b + c) が真であること。ゼロ要素が存在して a + 0 = a であること。そして最後に、すべての要素に負の要素が存在して a + -a = 0 であること。(訳注: Wikipedia を見ると、このことを「閉じていて、結合法則を満たし、単位元があり、逆元がある」と言うらしい)

足し算をうまく定義すれば、楕円曲線上の点はこの構造を持つ。さらに、その足し算の法則はグラフ的に素敵な定義になっている (略)

(略)

このように足し算を定義したわけだが、ゼロ要素はちょっと工夫が要る。まず、負の要素とは、その点から X 軸に対称な点であると定義する。要素とその負の要素を足すとゼロ要素になるわけだから、その二点を足すとどうなるのかについて考えよう。一点から対称な点に線を引くと、垂直な線になる。曲線に交わる点を探さなければいけないが、方程式の y² という項から、この曲線が x に対して二つの解しか持たないことは明らかだ。この直線は曲線と交わってくれない！

ここでゼロ要素が出てくる。それは無限遠点といって、無限に遠い特別な点である。つまり垂直な線はそこまで行くことになる。そして無限遠点はあらゆる点の真上にあるわけだから、ゼロ要素を点に足すと、まず対称な点で曲線と交わり、その対称な点つまり元の場所に戻ってくるわけだ。

というわけで、こんなコブみたいなグラフで、群ができてしまうのだ！ だからどうしたって？ えっと、足し算があれば掛け算も定義できる (繰り返し足せばいい)。そうすれば、曲線とその上の点 (基点といって G で表す) を決めれば点の自然数倍を計算できる。しかし計算結果の点を見ても、それが基点の何倍なのかを遡って計算することは現実的に不可能なのだ。これは一方向関数だ。

これが暗号にどう役立つのか理解できるように、長年の友アリスとボブが登場してくれる。二人は人の多い部屋に立っていて、秘密の話をしたいと思っているが、場所がない。嬉しいことに、アリスもボブも、標準的な公知の楕円曲線と基点を知っている。それぞれが乱数を思い浮かべて、基点をその数だけ倍にする。

アリスの乱数を a として、ボブのを b としよう。二人は基点の a 倍と b 倍、つまり aG と bG を互いに教える (ということは、全員に公表するわけだ)。アリスは a と bG を知り、それをさらに掛けて abG を知る。ボブは b と aG を知り、掛けて baG を知る。abG = baG なので、二人は共通の、秘密の鍵を手に入れることになる。まわりの人たちは aG と bG しか知ることができず、割り算で a や b を出すこともできないので、その秘密の abG を計算することは不可能だ。

(これが楕円曲線の Diffie-Hellman 鍵交換である。)

実装

(略: 変換について)

群の下敷きになっている体

上で楕円曲線を定義したとき、点の集合については話題にしたが、点を定義していなかった。さて、平面上の一点は (x,y) で表すことができるが、x と y というのは何か？ 数学の授業であれば ℜ つまり実数の集合、の中の要素ということになる。しかしコンピュータで実数は遅かったり近似値だったりする。単なる近似値では、群の法則がすぐに崩壊してしまう。

それで、暗号で利用する際には、有限体というものを使う。(体というのも群と同じく数学用語だ。) 今回の場合、有限体は素数を法とした剰余のことだ。(位数の同じ有限体はすべて可換なので本当はそこは重要ではないのだが。)

ここからは加速することにしよう。有限体の説明はしない。一気に実装の工夫に飛びこもう。ここまでやったんだから上出来だ！

まず、異なる二つの構造を使っていることを覚えておくのが大切だ。楕円曲線群があり、その上の点を足したり倍にしたりする。そして、その下に有限体がある。群で演算をするにあたっては、その下にある有限体の要素でいろいろな演算をしなければいけない。たとえば群の足し算をヤコビアン変換の下でおこなう公式がある。そこにはコストが有限体の言葉で書かれている: 11 回の掛け算と 5 回の自乗。

我々 (訳注: OpenSSL 開発者) の仕事は、こうした群と体の演算を素早く一定の時間でおこなうことだ。「一定の時間」というのが重要！ AES や RSA に対するタイミング攻撃の力を見よ！

(略: Limb schedules)

素数

曲線を実装するとき通常は自分で素数を選ぶ必要はない。NIST によって (FIPS 186-3 で) 定義されている標準的な素数と、知名度の劣る (curve25519 のような) 素数がある。(以下略)