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

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

楕円曲線暗号をプログラムしたらこうなった

楕円曲線上の点を演算するサンプルを作成しました

楕円曲線暗号Diffie-Hellman鍵交換を検証する

楕円曲線暗号で鍵共有を検証しました

署名のアルゴリズム

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

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

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

検証のアルゴリズム

次は署名の検証です。

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

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

実装する

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

import ecc._
import scala.math._
import scala.util.Random
import java.security.MessageDigest
object ECCDSA {
  def main(args: Array[String]) {
    //  Curve P-192
    val prime = BigInt("6277101735386680763835789423207666416083908700390324961279")
    val N = BigInt("6277101735386680763835789423176059013767194773182842284081")
    val a = new FiniteField(BigInt("6277101735386680763835789423207666416083908700390324961276"),prime)
    val b = new FiniteField(BigInt("2455155546008943817740293915197451784769108058161191238065"),prime)
    val x = new FiniteField(BigInt("602046282375688656758213480587526111916698976636884684818"),prime)
    val y = new FiniteField(BigInt("174050332293622031404857552280219410364023488927386650641"),prime)
    var G = new ECPoint(x,y,a,b)

    // アリスの秘密鍵
    val priA = BigInt(123456789)
    val aG = G*priA

    // 乱数rとして使用
    val r = BigInt(987654321)
    val rG = G*r

    val m = "hello world"
    val h = BigInt(
              1,
              MessageDigest.getInstance("SHA-256").digest(
                  MessageDigest.getInstance("SHA-256").digest(m.getBytes("UTF-8"))
              )
            )

    val r_inv = r.modPow(N-2,N)
    val s = (h+priA*(rG.x.num))*r_inv%N
    println("Signing--------------------------------------")
    println("x: "+rG.x.num+" y: "+rG.y.num)

    val h2 = BigInt(
              1,
              MessageDigest.getInstance("SHA-256").digest(
                  MessageDigest.getInstance("SHA-256").digest(m.getBytes("UTF-8"))
              )
            )
    val s_inv = s.modPow(N-2,N)
    val res = G*( h2*s_inv%N )+aG*( rG.x.num*s_inv%N )
    println("Verifying-----------------------------------")

    println("x: "+res.x.num+" y: "+res.y.num)
    println("Result "+ (res.x.num==rG.x.num) )

  }
}

import ecc._

import scala.math._

import scala.util.Random

import java.security.MessageDigest

object ECCDSA {

def main(args: Array[String]) {

// Curve P-192

val prime = BigInt("6277101735386680763835789423207666416083908700390324961279")

val N = BigInt("6277101735386680763835789423176059013767194773182842284081")

val a = new FiniteField(BigInt("6277101735386680763835789423207666416083908700390324961276"),prime)

val b = new FiniteField(BigInt("2455155546008943817740293915197451784769108058161191238065"),prime)

val x = new FiniteField(BigInt("602046282375688656758213480587526111916698976636884684818"),prime)

val y = new FiniteField(BigInt("174050332293622031404857552280219410364023488927386650641"),prime)

var G = new ECPoint(x,y,a,b)

// アリスの秘密鍵

val priA = BigInt(123456789)

val aG = G*priA

// 乱数rとして使用

val r = BigInt(987654321)

val rG = G*r

val m = "hello world"

val h = BigInt(

MessageDigest.getInstance("SHA-256").digest(

MessageDigest.getInstance("SHA-256").digest(m.getBytes("UTF-8"))

)

val r_inv = r.modPow(N-2,N)

val s = (h+priA*(rG.x.num))*r_inv%N

println("Signing--------------------------------------")

println("x: "+rG.x.num+" y: "+rG.y.num)

val h2 = BigInt(

MessageDigest.getInstance("SHA-256").digest(

MessageDigest.getInstance("SHA-256").digest(m.getBytes("UTF-8"))

)

val s_inv = s.modPow(N-2,N)

val res = G*( h2*s_inv%N )+aG*( rG.x.num*s_inv%N )

println("Verifying-----------------------------------")

println("x: "+res.x.num+" y: "+res.y.num)

println("Result "+ (res.x.num==rG.x.num) )

}

実行結果です。

Signing--------------------------------------
x: 2288499831435877701733209893715223990745122713620980414676 y: 4806876787794843079498911981144347330866905652071595735787
Verifying-----------------------------------
x: 2288499831435877701733209893715223990745122713620980414676 y: 4806876787794843079498911981144347330866905652071595735787
Result true

Signing--------------------------------------

x: 2288499831435877701733209893715223990745122713620980414676 y: 4806876787794843079498911981144347330866905652071595735787

Verifying-----------------------------------

x: 2288499831435877701733209893715223990745122713620980414676 y: 4806876787794843079498911981144347330866905652071595735787

Result true

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

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

euniclus 8:11 PM2019年11月14日返信

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 を使っていたのかはよく覚えてないんですよね。