2019-04-02SHAREツイートシェアはてブLINEPocketこんにちは。電子署名~DSA署名~に続き、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\)(分数による短縮のため式の構造は違いますが、ごにょごにょすると書き換えられるようです)などがあります。楕円曲線上では足し算ができます。言われても、わけがわからないと思います。前回記事を読んでいないとわけわからないかもしれませんが、前回記事読んでると、以下の説明ならちょっとわかりやすいと思います。すると、この楕円曲線は、加法に関して「群」とみなせるどうでしょうか。やって加法を定義するねん、ということになりますが、挙げた三つの性質を満たすように、都合よく定義してやれば良いのです。Wikipedia加法は1+1のように、+の両側に1が二つと、二項演算の形になりますから、加算するために適当に二つの楕円曲線上の点を取ります。図1のP,Q図2のP,Q図3のP,Q図4のP,P(交わるではなく接する、なので重解になるため)にあたります。次に、それら二点を結ぶ直線を描いてみます。その直線がもう一箇所で楕円曲線と交わる場合がありますね。図1のR図2のQ(交わるではなく接する、なので重解になるため)図3の無限遠点(ようするに図上では交わらない)図4の無限遠点(ようするに図上では交わらない)がそうです。結合法則まず、結合法則はおk。これで群の性質1を満たせます。次に群の性質2を満たすように単位元を定義します。図3の\(P+Q=O\)図4の\(P+P=O\)となるように単位元\(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すなわちECDSAになります。先程説明した加算の定義では、「ぐるぐる循環」はまだしていません。適当な点\(G\)をとります。それらを足し算しまくってみましょう。\\\end{eqnarray}\)足しまくっていくと、いずれ\(nG=O\)となる\(n\)回目の加算になります。こんな感じで、答えがぐるぐる循環していきます。これこそが巡回群です。この\(G\)は、ベースポイントと呼ばれます。,+)\)という群が定義できました。位数また、ここでの\(n\)が、この巡回群の位数となります。前回記事では整数論的な位数の意味をご紹介しましたが、実はこっちの意味のほうがより一般化された意味となります。シンプルに「集合の元の数」と考えて問題ありません。p\)を満たす\(x\)が\(y\)に対する離散対数だ、とご紹介しましたが、今回も構造は同じです。\}\)上の任意の点\(Q\)に対して、\(Q=dG\)を満たす\(d\)が、離散対数となります。DSAの場合、\(x\)がわかると\(y\)はすぐに計算できましたが、逆は難しいものでした。\(d\)がわかると\(Q\)はすぐに計算できますが、\(Q\)がわかっても\(d\)がわからないのです。この\(Q\)が公開鍵、\(d\)が秘密鍵になります。まとめDSAの「素数の割り算の余りが周期的にぐるぐる循環していく群」を、「楕円曲線上の巡回群」に置き換えたもの、これが、ECDSAの正体です。ECDSAの安全性はDSAと同じく、「離散対数問題を多項式時間で解くアルゴリズムが存在しない」という仮定に依拠します。この仮定が正しいと考えられている間は安全だ、ということになるわけです。これにて、署名シリーズはおわります!ありがとうございました。テーマは難しいものですが、順を追った説明で、いままでわからなかったところで少しわかったポイントもあったのではないでしょうか。弊社内では緩さがありながらも、このような噛み砕いた説明で知識を共有し、共に高めあっています。新しい仲間をいつでも募集しています。