楕円曲線でデジタル署名を実装する
今回は楕円曲線でデジタル署名を実装したいと思います。
楕円曲線に関する記事をいくつか書きました。
これらの記事で作成したプログラムを使用します。
署名のアルゴリズム
プログラムを書く前に署名のアルゴリズムを簡単にまとめておきます。
楕円曲線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を比較する)
実装する
上でまとめたアルゴリズムを参考に実装します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
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) ) } } |
実行結果です。
|
1 2 3 4 5 6 |
Signing-------------------------------------- x: 2288499831435877701733209893715223990745122713620980414676 y: 4806876787794843079498911981144347330866905652071595735787 Verifying----------------------------------- x: 2288499831435877701733209893715223990745122713620980414676 y: 4806876787794843079498911981144347330866905652071595735787 Result true |
x座標の値が一致していれば署名の検証が成功したということです。
ビットコインではこの署名と検証がコインの支払いに使われています。
今回は楕円曲線にCurve P-192を使いましたが、ビットコインではsecp256k1が使われています。
楕円曲線暗号に少し触れたことで、仮想通貨を勉強するうえで一つ壁を乗り越えたかなと思います。
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 を使っていたのかはよく覚えてないんですよね。