電子署名DSA/ECDSAの数的構造(2/2)

# はじめに
## 概要
この記事は、前回の[電子署名DSA/ECDSAの数的構造(1/2)](/angel_p_57/items/f2350f2ba729dc2c1d2e)の続きです。

記事に書いた数式を実際に計算するRubyのコードをデモとして組んでみました。

ただし、実際に暗号ライブラリを作る意図ではないので、あくまで計算内容を実現しただけで、暗号処理に使えるわけではありませんから、ご注意ください。

## コードの構成
コード一式は以下のgithubリポジトリにあります。
https://github.com/angel-p57/qiita-sample/tree/master/dsa

それぞれの内容は次の通りです。

* [base.rb](https://github.com/angel-p57/qiita-sample/tree/master/dsa/base.rb) … $GF(p)$の計算等、基本部分のライブラリ
* [fg_m.rb](https://github.com/angel-p57/qiita-sample/tree/master/dsa/fg_m.rb), [fg_ec.rb](https://github.com/angel-p57/qiita-sample/tree/master/dsa/fg_ec.rb) … 有限群の実装、前者が mod p での乗算の群、後者が$GF(p)$での楕円曲線
* [dsa.rb](https://github.com/angel-p57/qiita-sample/tree/master/dsa/dsa.rb) … DSAの実装
* [test_dsa_m.rb](https://github.com/angel-p57/qiita-sample/tree/master/dsa/test_dsa_m.rb), [test_dsa_ec.rb](https://github.com/angel-p57/qiita-sample/tree/master/dsa/test_dsa_ec.rb) … 対応する有限群を使ったDSAのデモ
* [search_ec_gamma.rb](https://github.com/angel-p57/qiita-sample/tree/master/dsa/search_ec_gamma.rb) … 楕円曲線でのパラメータの探索スクリプト

# DSAの実装
## DSAEngineクラス

では、まず最初に[dsa.rb](https://github.com/angel-p57/qiita-sample/blob/master/dsa/dsa.rb)で実装した、DSAの処理を行うDSAEngineクラスです。

用意したメソッドは、コンストラクタ`initialize`、鍵ペア生成の`create_key_pair`、署名作成の`make_signature`、署名検証の`verify_signature`です。

なお、随所に出てくる$GF(q)$の演算は`base.rb`で定義しています。なので、DSAの処理上は単なる四則演算に見えるようになっています。

### コンストラクタ initialize  
ここでは、$\gamma,q,f_z,f_p$ の4パラメータを受け取り、各処理を行うためのオブジェクトを生成します。
※デバッグ制御用の`debug_enable`というパラメータも設けていますが。

$q$ からは、$GF(q)$のクラスオブジェクトを生成し、各計算で使用します。これはインスタンス変数`@gfq`にクラスを保持します。

群$G$の情報は、$\gamma$のクラス情報としてとれる想定です。この群は演算$\circ$として `*`、べき乗として `**`、単位元としてクラスメソッド `epsilon`を必要とします。なお、$\gamma^q=\epsilon$であることのチェックもコンストラクタで行っています。

関数である$f_z,f_p$にはラムダ関数を指定します。これらの関数の値を$GF(q)$の要素とするようコンストラクタでラップし、インスタンス変数`@fz`,`@fp`に保持します。

### 鍵ペア生成 create_key_pair
単純に、乱数として`x`を生成し、$\chi=\gamma^x$を計算し、ペアを返す実装です。

乱数としては、$GF(q)$のクラスで定義したものを使っています ( Ruby標準の`rand`を$1\sim q-1$の範囲に限定しただけのものです )。本来はパターンが読まれないように乱数のソースには気を遣うべきところですが、これは単なるデモですので。なお、乱数を生成する代わりに、固定の`x`を引数として指定することもできます

```ruby:create_key_pair実装
    def create_key_pair(rval=nil)
      x = rval||@gfq.rand
      chi = @gamma**x
      #(略)
      [x,chi]
    end
```

### 署名生成 make_signature
メッセージ`msg`と、前項で生成した署名鍵 ( 秘密鍵 ) `x`を用いて署名を生成する処理です。
処理中に出てくる乱数`k`は前項と同様、$GF(q)$のクラスで実装した単純な乱数です。なおこれも、引数で固定値を指定できるようにしています。

処理としては単純に$r=f_p(\gamma^k),~s=(f_z(m)+x\times r)/k$を計算するのみです。

```ruby:make_signature実装
    def make_signature(msg,x,rval=nil)
      z = @fz[msg]
      k = rval||@gfq.rand
      omega=@gamma**k
      r = @fp[omega]
      s = (z+x*r)/k
      #(略)
      [r,s]
    end
```

### 署名検証
メッセージ`msg`と、署名`(r,s)`を、前々項で作成した検証鍵 ( 公開鍵 ) $\chi$を用いて検証する処理です。成功か否かを真偽値で返します。

$u_1=f_z(m)/s,~u_2=r/s,~r'=f_p(\gamma^{u_1}\circ \chi^{u_2})$ によって$r'$を計算し、$r$と比較するという計算そのままです。

```ruby:verify_signature実装
    def verify_signature(msg,r,s,chi)
      z = @fz[msg]
      u1 = z/s
      u2 = r/s
      omega=@gamma**u1*chi**u2
      rd = @fp[omega]
      #(略)
      rd==r
    end
```

## デモ実行
続いて、`dsa.rb`を組み込んだ簡単なデモです。

### 素のDSAのデモ
ファイルとしては[`test_dsa_m.rb`](https://github.com/angel-p57/qiita-sample/blob/master/dsa/test_dsa_m.rb)が該当します。

適当に決めたパラメータですが、$\gamma=2937, q=679733$に対して $\gamma^q=1~mod~464937373$ という mod 464937373 の世界 ( 乗法群 ) を使ったDSAです。
群の定義は[`fg_m.rb`](https://github.com/angel-p57/qiita-sample/blob/master/dsa/fg_m.rb)にあるのですが、単に`base.rb`で定義した$GF(p)$を流用しているだけだったりします。

なお、$f_z$としては、実際のDSAではSHA系のハッシュを取るところ、簡単に済ますため、Rubyの標準の`hash`メソッドを流用しています。

```ruby:test_dsa_m.rbより抜粋
require "./dsa.rb"
require "./fg_m.rb"

# DSA parameters
p_=464937373
q=679733
mydsa=MyExample::DSAEngine.new(
  MyExample::FiniteGroup::Multiplicative.generate(p_).new(2937),
  q,
  fz=->msg{ msg.hash },
  fp=->gelem{ gelem.to_i }
)
```

以下、コードの内容は特に示しませんが、鍵を生成して署名生成、署名検証を試した時どのような結果になるかを試した例です。一応、署名対象でないメッセージで検証を試すと失敗もするよ、というところも含めて、です。

```text:test_dsa_m.rb実行結果(前半)
  ** debug: initialize
    DSA engine initialized with;
    gamma=2937, q=679733

  ** debug: create_key_pair
    created private key x: 627577,
            public key chi=gamma**x: 386307865

  ** debug: make_signature
    hash of msg ( hoge ) is 646295
    random value k=562151 selected, and gamma**k=355073861
    signature (r,s)=(253235,599429)

verify the signature with a same message:
  ** debug: verify_signature
    hash of msg ( hoge ) is 646295
    signature (r,s)=(253235,599429)
    calculated u1=357490,u2=58969
    gamma**u1*chi**u2=355073861
    now r(derived)=253235, which matches r

verify O.K.

next, verify the signature with another message:
  ** debug: verify_signature
    hash of msg ( uge ) is 304801
    signature (r,s)=(253235,599429)
    calculated u1=401662,u2=58969
    gamma**u1*chi**u2=196659218
    now r(derived)=216381, which does not match r

verify N.G.
```

処理の後半では、署名作成時の$k$を固定して得られた2つの署名から、署名鍵 ( 秘密鍵 ) $x$ が漏洩しますよ、というデモも行っています。
実際に、前半のデバッグメッセージにある$x=627577$を導き出せています。

```text:test_dsa_m.rb実行結果(後半)
what if fixed k used?
suppose a same k=477876 used for two messages
signature for 'hoge' = (259846,150166)
signature for 'uge' = (259846,409188)
calculated k=477876, and the private key x=627577 leaks!
```

コードとしての該当部分は次の通りです。`kd`が固定された$k$、`xd`が漏洩した鍵ということです。

```ruby:test_dsa_m.rb鍵漏洩デモ部分
r1,s1=mydsa.make_signature("hoge",x,k)
r2,s2=mydsa.make_signature("uge",x,k)
#(略)
kd=(mydsa.gfq.new(fz["hoge"])-fz["uge"])/(s1-s2)
xd=(kd*s1-fz["hoge"])/r1
```

### ECDSAのデモ
ファイルとしては[`test_dsa_ec.rb`](https://github.com/angel-p57/qiita-sample/blob/master/dsa/test_dsa_ec.rb)が該当します。

やってることは上のDSAのデモと同じなのですが、計算に使用する群を楕円曲線ベースのものに変えています。楕円曲線の演算の実装は[`fg_ec.rb`](https://github.com/angel-p57/qiita-sample/blob/master/dsa/fg_ec.rb)にあります。

```ruby:test_dsa_ec.rbより抜粋
require "./dsa.rb"
require "./fg_ec.rb"

# DSA parameters
p_,a,b=89334649,54079150, 64993959
q=1624057
EC=MyExample::FiniteGroup::EllipticCurve.generate(MyExample::GaloisField.generate(p_),a,b)
mydsa=MyExample::DSAEngine.new(
  EC.element(81994458,7695874),
  q,
  fz=->msg{ msg.hash },
  fp=->gelem{ gelem.x.to_i }
)
```

流石に楕円曲線のパラメータや$\gamma$をノリで決めるわけには行かないので、mod 89334649 の所だけ固定して、そこそこ大きめの$q$になるようなパラメータ$a,b$と$\gamma$を探すスクリプト[`search_ec_gamma.rb`](https://github.com/angel-p57/qiita-sample/blob/master/dsa/ec_search_gamma.rb)を組んで、次のパラメータを探し出しました。

* 楕円曲線: $y^2\equiv x^3+54079150x+64993959~mod~89334649$
* 基準点 ( ベースカーブ ): $\gamma=(81994458,7695874)~~(\gamma^{1624057}=\epsilon)$  
  ※$\epsilon$は楕円曲線における無限遠点

なお、一般に楕円曲線の表現としては $G=(81994458,7695874)~~, 1624057G=O$ のようになります。べき乗ではなくスカラー倍ですね。

以下実行結果例です。

```text:test_dsa_ec.rb実行結果
  ** debug: initialize
    DSA engine initialized with;
    gamma=(81994458,7695874), q=1624057

  ** debug: create_key_pair
    created private key x: 877911,
            public key chi=gamma**x: (3033960,9439161)

  ** debug: make_signature
    hash of msg ( hoge ) is 422031
    random value k=1254193 selected, and gamma**k=(85611511,2988242)
    signature (r,s)=(1160547,541224)

verify the signature with a same message:
  ** debug: verify_signature
    hash of msg ( hoge ) is 422031
    signature (r,s)=(1160547,541224)
    calculated u1=540876,u2=530903
    gamma**u1*chi**u2=(85611511,2988242)
    now r(derived)=1160547, which matches r

verify O.K.

next, verify the signature with another message:
  ** debug: verify_signature
    hash of msg ( uge ) is 611475
    signature (r,s)=(1160547,541224)
    calculated u1=311610,u2=530903
    gamma**u1*chi**u2=(60682849,203046)
    now r(derived)=592740, which does not match r

verify N.G.

what if fixed k used?
suppose a same k=963009 used for two messages
signature for 'hoge' = (1268855,756660)
signature for 'uge' = (1268855,12419)
calculated k=963009, and the private key x=877911 leaks!
```

# その他補足
その他、細かい実装については実際にコードを見て頂いた方が早いと思うのですが、何点か補足を。

* $GF(p)$での除算、逆数について ( `base.rb` )  
  他の演算はただmod pを取るだけで良いのですが、除算だけは逆数を計算して掛け算という形をとります。その逆数の計算のために、`MyExample::Util.egcd`というユークリッドの互除法の拡張版を使用しています。
* 有限群のべき乗 ( `base.rb` )  
  演算$\circ$さえ決まってしまえばべき乗は同じように計算できるので、`MyExample::FiniteGroup::Common`というモジュールで、演算`**`として共通化しています。なお$\circ$に対応するのは`*`としています。
* 楕円曲線のパラメータの探索 ( `search_ec_gamma.rb` )  
  基本ランダムに値を作っているのですが、$\gamma$については以下のようにしています。実際に使われる楕円曲線の場合は、適切なパラメータが予め計算されて公開され、その組み合わせに名前が付けられています ( nistp256 とか )。
    1. 点のx座標をランダムに決める
    2. y座標を、実装した`sqrt`を使って計算する ( できない場合もある )
    3. できた$\omega=(x,y)$を素数乗しても都合よく$\epsilon$ ( 無限遠点 ) になってはくれないので、$\omega^r=\epsilon$ となる $r$ を求め、$r=qh$ と分解し、$\gamma=\omega^h$ とする、という手順を踏む。なお、$r$はほぼほぼ $mod~p$ の $p$ の近辺で見つかる。
    4. $q$ が希望の範囲に収まってない場合は$a,b$から選び直し

# 終わりに
ということで、前の記事の計算を実装したコードを紹介してみました。実際の暗号ではデータをどう表現するかとか、ハッシュに何を使うかとか、色々あるのですが、あくまで数値としての計算に留めています。
これで計算内容が身近に感じて頂ければ幸いです。