Ameba Ownd

アプリで簡単、無料ホームページ作成

ハッタリからはじめよ - bluff driven -

ECDSAデジタル署名の仕組み

2018.09.04 11:15

Mastering Bitcoinにデジタル署名の仕組みが詳しく書いてなかったので、備忘録と内容補完のためにまとめます。

暗号学的ハッシュ関数についての用語


ECDSAの用途


ECDSA（Elliptic Curve Digital Signature Algorithm：楕円曲線デジタル署名アルゴリズム）は、楕円曲線を使った公開鍵暗号です。


ECDSAによってもたらされる機能は主に

の3つです。


暗号鍵の生成は、秘密鍵から公開鍵の作成に使われており、これは「少しだけ易しいMastering Bitcoin第4章」で概要を説明しました。


電子署名はトランザクションについて「トランザクション作成者が本当にインプットに入れられているUTXOの所有者かどうか」「途中でデータが改竄されていないかどうか」を検証するために使われます。


bitcoinでは新規トランザクションを作成したノードは、そのトランザクションを他のノードに伝搬し、それがマイナーによってブロックに取り込まれることでトランザクションがブロックチェーンに刻まれるのでした。

しかし、作成したトランザクションデータをただ伝搬した場合、悪意のあるノードやマイナーが「送金額」や「送金先アドレス(outputに入れるlocking script)」を簡単に改竄できてしまいます。


全てのノードは新規トランザクションを生成する際に、トランザクションデータのunlocking scriptの中に"自身の秘密鍵から生成したECDSAデジタル署名(r, sという2つの値)"を入れ込んで、Bitcoinネットワークに伝搬することでこれを解決します。


これによって、秘密鍵を持たない主体がトランザクションデータを改ざんした場合にはこの署名との辻褄が合わなくなるため、伝搬してきた新規トランザクションを受け取ったノードは、そのトランザクションデータが途中で改竄されていないかどうかを確認することが可能になるのです。

各ノードは独立したトランザクション検証の際にこの署名を確認し、もし改ざんされているトランザクションだった場合には、そのトランザクションを拒否する(少しだけ易しいMastering Bitcoin 第8章前半 (2)-①参照)ので、改竄されたトランザクションがブロックチェーンに刻まれることはなくなります。


ECDSAが上記の機能を提供する仕組みについて見て行く前に、まずは楕円曲線暗号を理解して行きます。

楕円曲線暗号とは

楕円曲線は、上記の画像のような形をした

のような方程式で表される図形です。


この楕円曲線上では、通常の足し算とは違う特殊な足し算が定義されています。


楕円曲線上の2点P, Qが存在したとき、P + Qは以下のように定義される


楕円曲線上ではこのような手順で足し算が行われます。

掛け算は足し算で表せるので、以下のようにGという点をn回足したもの、すなわち上記の手順をn回行ったものがnGになります。

そしてこのような計算は実数集合でだけではなく、素数pで割った余りの集合でも可能です。

実数集合の中では、 20 - 15 = 5 ですが、

素数pで割った余りの集合の中(剰余系)では、p = 3だとすると

20 -15 = 2 (mod 3)

になります。(全部の計算に mod p をつけると思えばいいです)


この「剰余系の中での楕円曲線のスカラー倍算」は

nG = Aとなるとき

nとGからAを求めることは簡単ですが、

AとGからnを求めることは現実的には不可能(これは楕円曲線上の離散対数問題と呼ばれる)という性質を持つ不可逆関数であることから、

Gを固定点として、nを秘密鍵、Aを公開鍵とする公開鍵暗号に利用されています。


Bitcoinでは、楕円曲線のスカラー倍算による公開鍵暗号に

で表される secp256k1という楕円曲線が用いられており、

基準点Gは

(x, y) =(55066263022277343669578718895168534326250603453777594175500187360389116729240, 32670510020758816978083085130507043184471273380659243275938904335757337482424)


剰余系の素数 p は

 2256－232－29－28－27－26－24－1 ＝ 11579208923731619542357098500868790785326998466564056403945758400790883467166334671663


Gの位数 n は 115792089237316195423570985008687907852837564279074904382605163141518161494337


に設定されています。


このように設定された楕円曲線のパラメータの上で、


①位数n以下の乱数を発生させ、秘密鍵とする

②秘密鍵 * G の計算をする

③その結果たどり着いた点を公開鍵とする


というようなイメージで秘密鍵と公開鍵が生成されているのです。


これによって「秘密鍵から公開鍵は簡単に生成できるが、公開鍵から秘密鍵を求めることはできない」という仕組みが作られています。

ECDSAデジタル署名の署名方法


楕円曲線暗号についてざっくり理解できたところで、ECDSAによるデジタル署名の仕組みについて見て行きます。


Bitcoinのネットワークで用いられている楕円曲線のパラメータを

とし、

とします。


新規トランザクションを生成したノードは、以下の手順でデジタル署名r, sを導出します。


1. まず、電子署名用に新しく乱数(位数n以下じゃないと3ができない)を生成します。この乱数を電子署名用の一時的な秘密鍵TprivKeyと呼ぶ事にします。

2. 作成したトランザクションデータをハッシュ関数に通し、トランザクションの要約値(ダイジェスト、ハッシュ値)から「位数nの桁数(bit長)分」取り出したものを求めます。これをTransactionHashとします。

3. 楕円曲線secp256k1上の点　TprivKey * G = (x, y)を求めます。(楕円曲線暗号を使って一時的な秘密鍵TprivKeyから一時的な公開鍵(x, y)を求めます)

4. r = x とします。

ここで行なっている操作は楕円曲線暗号を用いたハッシュ化なので「rからTprivkeyを求めることは不可能」であるのがポイントです。

5. 以下の式からsを求めます。

4よりTprivKeyを知ることは不可能なので、sからprivKeyを求めることも不可能です。

(デジタル署名r, sからは秘密鍵はわからないということ)


こうして求めたs, rの値をデジタル署名としてトランザクションデータのunlocking script の中に含めて、Bitcoinネットワークに伝搬するのです。

ECDSAデジタル署名の検証


前節で見たような手順で作成された デジタル署名(r, sの値)をunlocking scriptに含む新規トランザクションデータがBitcoinネットワークに伝搬されたとします。


このデータを受け取ったノードは「独立したトランザクション検証」を行い、このトランザクションデータをあらゆる基準でチェックします。

その基準の一つとして、「unlocking scriptがインプットに入れられているUTXOのlocking script を解除できるか」という項目があり、この時にECDSAデジタル署名が有効かどうかから「このトランザクションの作成者がインプットに入れられたUTXOの持ち主かどうかの確認」「トランザクションデータの中身が途中で改竄されていないかの確認」をします。


具体的には、以下の式を計算することでデジタル署名の検証は行われます。

伝搬して来たトランザクションデータの検証で、unlocking scriptとlocking scriptを同時に実行する際に、以下の図のように、デジタル署名r, sをこの式に代入していき、 Q を求めます。


この時、「緑色のTransactionHash(送られて来たトランザクションデータをハッシュ化したもの)は、このノードに届いた時点でのトランザクションデータのハッシュ」であり、「水色のpubKeyは、このトランザクションにinputされているUTXOのlocking scriptにある宛先公開鍵」です。

Qを求めるために計算していくと、以下の画像のようになりますね。

この計算過程を見ても分かるように、


①

「"このノードに届いた時点でのトランザクションデータのハッシュ"である緑色のTransactionHash」と「"sの値が作成された時、つまりこのトランザクションデータが作成された時点のトランザクションデータのハッシュ"である赤のTransactionHash」が等しい


かつ


②

「"このトランザクションにinputされているUTXOの所有者の秘密鍵"である水色privKey」と「"このトランザクションの作成者の秘密鍵"である赤色privKey」が等しい


場合には、

このQの値が「 TprivKey * G 」になります。


送られて来たそもそもの値である r は、「 TprivKey * G 」によって導き出された点の x座標 でした。

すなわち、「 計算したQの x座標部分 が 伝搬されて来た r の値と同じ 」であれば、上記の①②が成り立つため、「このトランザクションにinputされているUTXOの所有者は間違いなくトランザクションの作成者である」「トランザクションデータの中身は途中で改竄されていない」ということが検証できるというわけです。


ここで最も重要な点は、トランザクションの検証者は「トランザクションが有効であるかどうか」の判断に「Qを計算してその結果がrと一致するかしないか」という情報のみしか使用しない(計算してみた結果がどうなったかを見るだけである)ため、「トランザクションの検証者はQを計算する過程でprivKeyを知る必要はない(知ることはできない)」という点です。

ECDSAデジタル署名のエンコーディング


以上で見て来たように、デジタル署名の値 s, r によってデータが全く変更されていないことが証明できるのでした。


これらの値はもちろんコンピュータのメモリ上で、バイナリデータ(コンピュータが理解できる0,1データ)に変換されているわけですが、この変換の処理がOSやCPUなどの種類によって異なってしまう場合があります。


そうなるとデジタル署名による検証がができなくなってしまうので、デジタル署名に限ってはASN.1という共通の方法でエンコードするようにします。

ECDSAデジタル署名生成の際の注意点


ECDSAデジタル署名をする際に、注意するべきポイントがあります。


ECDSAデジタル署名では、署名をする(s, rを生成する)時に「乱数であるTprivKey」を生成するところから始まっていましたが、この乱数は絶対に同じものを二度使用することがあってあってはいけません。


この理由は、もし別のトランザクションに同じTprivKeyが使われていた場合、

上記のrの導出式より、rが二回のトランザクション伝搬で同じになります。


二回のトランザクションの伝搬がそれぞれ

Transaction data 1 と r と s1

Transaction data 2 と r と s2

だったとしましょう。


これを受け取る悪意のあるノードがもし「二回のトランザクションはTprivKeyも r も同じ」であることを知っていれば、

TransactionHash1とTransactionHash2はそれぞれ送られて来たTransaction dataから導出でき、s1とs2も送られて来て手元にある値なので、TprivKeyが導かれます。

であるので、これらの情報から秘密鍵privKeyが漏洩してしまうことになってしまいます。



このような理由からデジタル署名のための一時的な秘密鍵(乱数)を生成するときは、常に暗号学的に安全な乱数生成器から生成するようにするべきです。


しかし、スペックの低いモバイルデバイスなどには質の悪い乱数生成器が搭載されていることもあり、それを使って乱数を生成することで、TprivKeyが衝突してしまうことがあるため、注意が必要です。

<References>