電子署名DSA/ECDSAの数的構造(2/2)
はじめに
概要
この記事は、前回の電子署名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を引数として指定することもできます
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$を計算するのみです。
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$と比較するという計算そのままです。
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メソッドを流用しています。
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 }
)
以下、コードの内容は特に示しませんが、鍵を生成して署名生成、署名検証を試した時どのような結果になるかを試した例です。一応、署名対象でないメッセージで検証を試すと失敗もするよ、というところも含めて、です。
** 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$を導き出せています。
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が漏洩した鍵ということです。
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にあります。
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$ のようになります。べき乗ではなくスカラー倍ですね。
以下実行結果例です。
** 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 とか )。- 点のx座標をランダムに決める
- y座標を、実装した
sqrtを使って計算する ( できない場合もある ) - できた$\omega=(x,y)$を素数乗しても都合よく$\epsilon$ ( 無限遠点 ) になってはくれないので、$\omega^r=\epsilon$ となる $r$ を求め、$r=qh$ と分解し、$\gamma=\omega^h$ とする、という手順を踏む。なお、$r$はほぼほぼ $mod~p$ の $p$ の近辺で見つかる。
- $q$ が希望の範囲に収まってない場合は$a,b$から選び直し
終わりに
ということで、前の記事の計算を実装したコードを紹介してみました。実際の暗号ではデータをどう表現するかとか、ハッシュに何を使うかとか、色々あるのですが、あくまで数値としての計算に留めています。
これで計算内容が身近に感じて頂ければ幸いです。
Author And Source
この問題について(電子署名DSA/ECDSAの数的構造(2/2)), 我々は、より多くの情報をここで見つけました https://qiita.com/angel_p_57/items/355eec5b5547ac122607著者帰属：元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Content is automatically searched and collected through network algorithms . If there is a violation . Please contact us . We will adjust (correct author information ,or delete content ) as soon as possible .