楕円曲線でデジタル署名を実装する


今回は楕円曲線でデジタル署名を実装したいと思います。
楕円曲線に関する記事をいくつか書きました。
これらの記事で作成したプログラムを使用します。

楕円曲線上の点を演算するサンプルを作成しました
楕円曲線暗号で鍵共有を検証しました

署名のアルゴリズム


プログラムを書く前に署名のアルゴリズムを簡単にまとめておきます。

楕円曲線DSAでは以下のようにして署名を作成します。
こちらをアリスとして、アリスの秘密鍵をaとします。
ちなみにベースポイントGとお互いの公開鍵(アリス:aG, ボブ:bG)は知っています。

  1. 乱数 r を生成して rG を計算する
  2. メッセージmのハッシュ値 h を求める。ビットコインではハッシュ関数にsha-256使われていようです。
  3. Gの位数を N としてNを法としたときのrの逆数を求め、これを r^-1 とする
  4. (h+rGのx)*r^-1%nを計算してこれを s とする
  5. m、rG、sをボブに送信する

検証のアルゴリズム


次は署名の検証です。

以下のような流れで検証します。
こちらはボブで。

  1. アリスからm、rG、sを受け取る
  2. mからハッシュ値を求めこれを h とする
  3. Nを法とするsの逆数を s^-1 とする
  4. (h*s^-1%N)*G+(x*s^-1%N)*aGを計算し、rGと比較する(xを比較する)

実装する


上でまとめたアルゴリズムを参考に実装します。


実行結果です。


x座標の値が一致していれば署名の検証が成功したということです。

ビットコインではこの署名と検証がコインの支払いに使われています。
今回は楕円曲線にCurve P-192を使いましたが、ビットコインではsecp256k1が使われています。
楕円曲線暗号に少し触れたことで、仮想通貨を勉強するうえで一つ壁を乗り越えたかなと思います。

“楕円曲線でデジタル署名を実装する” に1件のコメントがあります

  1. rGはどこからきたのかというご指摘をいただき、一部修正しました。
    恐らく「署名のアルゴリズム」の5番にあるrGのことかと思います。
    ご指摘ありがとうございました。

    修正箇所は「署名のアルゴリズム」とソースコードです。

    「乱数 k を生成して kG を計算する」

    「乱数 r を生成して rG を計算する」

    「Gの位数を N としてNを法としたときのkの逆数を求め、これを k^-1 とする」

    「Gの位数を N としてNを法としたときのrの逆数を求め、これを r^-1 とする」

    「(h+kGのx)*k^-1%nを計算してこれを s とする」

    「(h+rGのx)*r^-1%nを計算してこれを s とする」

    「m、kG、sをボブに送信する」

    「m、rG、sをボブに送信する」

    k という文字を rに変えたのですがなぜ k を使っていたのかはよく覚えてないんですよね。

コメントは停止中です。