他のもということで DSA について調べてみました
電子署名アルゴリズムの 1 つ DSA は Digital Signature Algorithm の略
例えば NIST の FIPS 186 で文章化されています
FIPS 186-2 では鍵長は 1024bit で使うハッシュ関数は SHA-1 としていますが
暗号の 2010 年問題というやつで SHA-1 や鍵長に限界が感ぜられているので
FIPS 186-3 がまだ草案ですが鍵長は 3072bit までで SHA-2 が使えるようになる予定です
DSA のパラメータ
DSA ではアルゴリズムにパラメータが指定されます鍵長を L bit、ハッシュ値の長さを N bit とします
ハッシュ関数はハッシュ値として N bit なものを出力するとします
- 大きな素数 p を 2L-1 < p < 2L となるように選びます
- p-1 の素因数 q を 2N-1 < q < 2N の範囲で選びます
(実際には q を選んで n もランダムで選んで p = q n + 1 が素数かチェックする?)
- mod p の世界で q 乗して初めて 1 になる数 g を探します (1 < g < p)
p は素数なので mod p の世界は有限体となり乗法群の位数は p-1
p-1 の素因数である q を位数とする元 g が存在するはずなので選びます
以上の (p, q, g) の triple が DSA のパラメータとなります
DSA の秘密鍵・公開鍵
次に秘密鍵・公開鍵を作ります、といっても簡単で- x を 0 < x < q で選んで秘密鍵とする
- y = gx mod p を公開鍵とする
DSA の署名と検証
署名しましょう平文 M のハッシュ値を z とします
- 整数 k を 0 < k < q となるように選びます (x 同様内緒にします)
- r = (gk mod p) mod q とします
- s = k-1 (z + x r) mod q とします
k は M 毎に選びます、同じものを再び使うことのないようにします
r と s のどちらかが 0 になってしまった場合、k を選ぶところからやり直します
というわけで、メーッセージの受信者は
- (p, q, g) と y と z = Hash(M) と (r, s) を知っていて
- x と k は知らない
x と k を使わずに r を表現する方法を作れれば検証方法確立です
(gz yr)(s-1) mod pを考えます. y=gx を使えばこれは
g(z + x r) (s-1) mod pです
gq = 1 mod p だったので g の肩は mod q の世界でした
s の定義を見てみればこの値は
gk mod pなので更に mod q とってやれば
((gz yr)(s-1) mod p) mod q = rとなります
左辺は x も k も使わない表現で r を表わすことができました
なので、受信者は
- アルゴリズムパラメータ (p, q, g)
- 公開鍵 y
- 平文 M
- ハッシュ関数
- 署名 (r, s)
((gz yr)(s-1) mod p) mod q = rが成立するかどうか確認すれば良いことになります
DSA の雑感
署名を偽造する一番素直な方法は- y = gx となる x を求める
- ((gz yr)(s-1) mod p) mod q = r となる s を求める
ここで後者の場合 k は攻撃者が選んで良いので r は知ってます
どっちも計算大変だよね? というのが署名を信頼する元になっています
なので p, q が大きいことが大切になってきます
q を使う理由は、単純に mod p の世界で考えてしまうと
平方剰余の乗法性を用いて既知のデータから未知のデータが類推し易くなるから
k をランダムで選ぶと既存の平文と署名から検証可能な平文と署名が作れちゃうとか
色々と知るべきことが残っていそうなんですがとりあえず DSA の流れということで
ちなみに、未だに s の形があの形なことが納得し切れていません
積だけだと攻撃に弱そうなことは分かるんですが.....