こんにちは。
前々回
前回
に続き、ECDSA署名をご紹介します。ブロックチェーンに使われているため、これの説明をするべく、前々回から続いてきました。ついにこの電子署名シリーズはいったん終わります。笑
前記事に
DSAとECDSAの関係はなんなのかと先にいうと、DSAに使っている群に、楕円曲線上の巡回群を使っているものこそがECDSA、ということになります。
と書いておいたことを、今一度掘り返しておきます。つまりECDSAはDSAの応用です。
これを念頭に置いて、進めていきます。
楕円曲線
実数\(a,b\)を用いて、
\(y^2=x^3+ax+b\)と表される曲線のことを楕円曲線といいます。
代表的なものでは、Bitcoinに使われているsecp256k1
\(y^2=x^3+7\)TendermintやNEMなどいろんなところで使われているed25519
\(-x^2+y^2=1-\frac{121665}{121666}x^2y^2\)（分数による短縮のため式の構造は違いますが、ごにょごにょすると書き換えられるようです）
などがあります。
楕円曲線上の加算
楕円曲線上では足し算ができます。
といきなり言われても、わけがわからないと思います。私もそうでした。
が、前回記事を読んでいないとわけわからないかもしれませんが、前回記事読んでると、以下の説明ならちょっとわかりやすいと思います。
- 楕円曲線を点の集合とみなし、
- その集合の中でこれらを満たす加法を定義
- 結合法則
- 単位元
- 逆元
- そうすると、この楕円曲線は、加法に関して「群」とみなせる
どうでしょうか。
じゃあどうやって加法を定義するねん、ということになりますが、挙げた三つの性質を満たすように、都合よく定義してやれば良いのです。
加法は1+1のように、+の両側に1が二つと、二項演算の形になりますから、加算するために適当に二つの楕円曲線上の点を取ります。
- 図1のP,Q
- 図2のP,Q
- 図3のP,Q
- 図4のP,P（交わるではなく接する、なので重解になるため）
にあたります。
次に、それら二点を結ぶ直線を描いてみます。図のとおりですね。そして、その直線がもう一箇所で楕円曲線と交わる場合がありますね。
- 図1のR
- 図2のQ（交わるではなく接する、なので重解になるため）
- 図3の無限遠点（ようするに図上では交わらない）
- 図4の無限遠点（ようするに図上では交わらない）
がそうです。
結合法則
まず、結合法則はおｋ。と決めておきましょう。これで群の性質1を満たせます。
単位元
次に群の性質2を満たすように単位元を定義します。単位元をOとして、
- 図3の\(P+Q=O\)
- 図4の\(P+P=O\)
となるように単位元\(O\)を定義しましょう。
ウィキペディア曰く
射影平面で考えると、すべての滑らかな三次曲線上の群構造を定義することができる。射影平面上、楕円曲線がヴァイエルシュトラスの標準形 によりあらわされるとき、そのような三次曲線は斉次座標（英語版） [0 : 1 : 0] である無限遠点 O を持ち、群の単位元となる。
楕円曲線 – Wikipedia
とのことなので、ちゃんと理由があるようです。
こうやって定義する方法以外に、図3や4みたいに無限遠点が出てきた場合にどうすればいいかわからないからこうする、といっても正直問題ないと思います。
逆元
最後に、逆元を定義して、群にしてあげましょう。
\(P+(-P)=O\)となるような\(-P\)を定義すればよいわけです。図3と単位元の定義に戻りましょう。\(P+Q=O\)となっていますね。てことは、あとは簡単。
\(P+(-P)=O\)と、図3での\(P+Q=O\)より、図3では\(-P=Q\)となります。ようするに、図上で、x軸を挟んで反対側の点を逆元とする、とすればよいわけです。
楕円曲線はx軸を挟んで対称なので、これで完璧です。
要約
まとめると、
楕円曲線上の二点の加算は、それらを結んだ直線と楕円曲線とのもう一つの交点のx軸挟んだ反対側になる（なければ無限遠点）。
ということになります。
図1,2,3,4で確認してみてください。この定義で群の性質を満たしていることがわかります。
DSAの応用
前回記事のとおり、DSAでは素数の割り算の余りが周期的にぐるぐる循環していく群を使って、離散対数を定義していました。
この「素数の割り算の余りが周期的にぐるぐる循環していく群」を、「楕円曲線上の点の集合と、そこに加法を定義した、ぐるぐる循環していく群」に置き換えると、それが楕円曲線DSAすなわちECDSAになります。
しかし、先程説明した加算の定義では、「ぐるぐる循環」はまだしていません。そこで、楕円曲線上の点という集合の中に部分集合をとり、その部分集合で「巡回群」を定義します。
巡回群
楕円曲線上に、適当な点\(G\)をとります。それらを足し算しまくってみましょう。
\(\begin{eqnarray} \\
G+G &=&2G \\
2G+G &=&3G \\
3G+G &=&4G \\
& \vdots & \\
(n-1)G+G &=& nG=O \\
nG+G &=&O+G=G \\
G+G &=&2G \\
2G+G &=&3G \\
\end{eqnarray}
\)
足しまくっていくと、いずれ\(nG=O\)となる\(n\)回目の加算になります。
と、こんな感じで、答えがぐるぐる循環していきます。
これこそが巡回群です。この\(G\)は、ベースポイントと呼ばれます。
\((\{G,2G,3G,…,O \} ,+)\)という群が定義できました。位数
また、ここでの\(n\)が、この巡回群の位数となります。
前回記事では整数論的な位数の意味をご紹介しましたが、実はこっちの意味のほうがより一般化された意味となります。
シンプルに「集合の元の数」と考えて問題ありません。前回記事の位数の意味は、「余りがぐるぐる循環する集合の元の数」を、具体的に言った意味だということになります。
離散対数
前回記事では、 \(y \equiv g^x \bmod p\)を満たす\(x\)が\(y\)に対する離散対数だ、とご紹介しましたが、今回も構造は同じです。
\(\{ G,2G,3G,…,O \}\)上の任意の点\(Q\)に対して、\(Q=dG\)を満たす\(d\)が、離散対数となります。DSAの場合、\(x\)がわかると\(y\)はすぐに計算できましたが、逆は難しいものでした。それと同じです。
\(d\)がわかると\(Q\)はすぐに計算できますが、\(Q\)がわかっても\(d\)がわからないのです。この\(Q\)が公開鍵、\(d\)が秘密鍵になります。
まとめ
DSAの「素数の割り算の余りが周期的にぐるぐる循環していく群」を、「楕円曲線上の巡回群」に置き換えたもの、これが、ECDSAの正体です。
ECDSAの安全性はDSAと同じく、「離散対数問題を多項式時間で解くアルゴリズムが存在しない」という仮定に依拠します。
この仮定が正しいと考えられている間は安全だ、ということになるわけです。
これにて、署名シリーズはおわります！ありがとうございました。
いかがでしたか。
テーマは難しいものですが、順を追った説明で、いままでわからなかったところで少しわかったポイントもあったのではないでしょうか。
