はじめに

概要

この記事は、前回の電子署名DSA/ECDSAの数的構造(1/2)の続きです。

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

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

コードの構成

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

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

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

DSAの実装

DSAEngineクラス

では、まず最初に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を引数として指定することもできます

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$を計算するのみです。

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$と比較するという計算そのままです。

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が該当します。

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

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

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 }
)

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

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$を導き出せています。

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が漏洩した鍵ということです。

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が該当します。

やってることは上のDSAのデモと同じなのですが、計算に使用する群を楕円曲線ベースのものに変えています。楕円曲線の演算の実装はfg_ec.rbにあります。

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を組んで、次のパラメータを探し出しました。

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

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

以下実行結果例です。

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$から選び直し

終わりに

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