bitcoin において使われているのは楕円曲線暗号で、この楕円曲線暗号を使った署名(ECDSA)が bitcoin の一つの柱になっています。ようやくですがこのあたりの署名について少しずつ少しずつ理解が進んできたので、忘れる前にその理解を書き残しておこうと思います。

楕円曲線の基本

暗号界隈における楕円曲線というのは、素数 $p$ を法として $y^{2} = x^{3} + ax + b$ という式で表されます。 $a, b, p$ は曲線のパラメータであって、このパラメータに応じて無数の曲線が定義されることになります。

楕円曲線上の和

楕円曲線上の点の集合には加算(和)が定義できます。

$P_{A} (x_{A}, y_{A})$ と $P_{B}(x_{B},y_{B})$ の和 $P_{A}+P_{B}$ は、2 点 $P_{A}$ と $P_{B}$ を通る直線と楕円曲線との交点 $Q$ に関し、 $y$ 座標の符号を逆にした点として定義されます。

これ、図なしで説明すると何がなにやら分からないと思うんですが、以下のエントリの「楕円曲線上の加算」なんかが分かりやすいかと思います。

これら楕円曲線上の点の集合と上記で定義される「和」について、特定の点 $G$ に着目し $2G, 3G, 4G, \cdots$ と計算していくと、最終的には無限遠点 $O$ に辿りつきます。

ここで、 $\langle G \rangle={G, 2G, 3G, \cdots, O}$ と定義すると、 $\langle G \rangle$ は、いわゆるwikipedia:有限アーベル群を構成します。このとき、単位元は無限遠点 $O$ になります。ここでいう $G$ が、生成元、あるいはベースポイントといわれるヤツですね。(ref: wikipedia:群の生成系)

bitcoin で使われる楕円曲線

楕円曲線は無数にありますが、bitcoin で使われる曲線は secp256k1 として明確な定義があります。

secp256k1 では、素数 $p$ は $p=2^{256}-2^{32}-977$ として定義されます。また、曲線は $a=0, b=7$ というパラメータを持ちます。つまりは $y^{2}=x^{3}+y$ という式で定義される曲線が、bitcoin で使われる楕円曲線です。

楕円曲線には当然のように $G$ を生成元とする有限アーベル群が構成できますが、この生成元 $G$ として何を使うかも secp256k1 は規定していて、その点は

$x$ 座標: 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
$y$ 座標: 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8

(※16進数表記) になります。

ECDSA: Elliptic Curve Digital Signature Algorithm

Bitcoin における公開鍵暗号は、楕円曲線上の生成元 $G$ と $e$ に対し、 $P=eG$ は簡単に計算できるけれど、 $e=P/G$ は容易に計算できないという wikipedia:離散対数問題を基礎にしています。ここで、 $P$ が楕円暗号における公開鍵、 $e$ が秘密鍵に該当します。

bitcoin における電子署名は以下のように計算されます。

前提

秘密鍵 $e$ に対し、点 P を $eG$ として定義する。つまり、 $P=eG$
署名する側はランダムな値 $k$ を取得し、点 $R=kG$ とする。この点 $R$ の $x$ 座標を $r$ とする。

署名計算

まず認めなければならないのは、 $uG+vP=R$ なる $u \ne 0, v \ne 0$ を見つける問題は離散対数問題であるということです。なぜか。

まず、この式を変形すると、 $P=\frac{k-u}{v}G=eG$ つまり $e=\frac{k-u}{v}$ になります。つまり、 $uG+vP=R$ なる $u \ne 0, v \ne 0$ が簡単に求められるということは、容易に離散対数問題が解けるということになってしまいます。

逆に言うと、秘密鍵 $e$ を知っている者 (署名者) でなければ、 $uG+vP=R$ を成立させるような $u \ne 0, v \ne 0$ は分からない、ということです。

ここまでの議論で、 $uG+vP=R$ なる $u \ne 0, v \ne 0$ を求められることを示せれば、秘密鍵を持っているということを示せそうです。ただ、ここで我々は電子署名の議論をしているのですから、秘密鍵を持っているということだけでなく、「正しいメッセージ」を送っている、ということを示したい。

そのため、メッセージ全体のハッシュ値を $z$ 、新しい変数 $s$ を導入し、 $u=\frac{z}{s}, v=\frac{r}{s}$ と置いてみましょう。実は、ここで導入されるハッシュ値 $z$ と $r, s$ があれば、受信側で署名の検証を行うことができます。

まず、先程から何度も記載している式 $uG+vP=R=kG$ に $P=eG$ を代入してみましょう。結果、 $uG+veG=kG$ です。ここで両辺から $G$ を除けば、 $u+ve=k=\frac{z}{s}+\frac{re}{s}$ が成立します。これを $s$ について解くと、 $s=\frac{z+re}{k}$ になります。