LoginSignup
9
8

More than 5 years have passed since last update.

@angel_p_57

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

Posted at

はじめに

概要

この記事は、前回の電子署名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$から選び直し

終わりに

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

9
8
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
9
8