Digital Signature Algorithm (DSA)

電子署名の方法は RSA + ハッシュしか良く知らなかったので
他のもということで 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 を 2^L-1 < p < 2^L となるように選びます

• p-1 の素因数 q を 2^N-1 < q < 2^N の範囲で選びます

p は奇数なので p-1 は偶数となり自明でない素因数分解ができます
(実際には q を選んで n もランダムで選んで p = q n + 1 が素数かチェックする?)

• mod p の世界で q 乗して初めて 1 になる数 g を探します (1 < g < p)

(mod p = p で割った余りを考えろ、と読みましょう)
p は素数なので mod p の世界は有限体となり乗法群の位数は p-1
p-1 の素因数である q を位数とする元 g が存在するはずなので選びます

以上の (p, q, g) の triple が DSA のパラメータとなります

DSA の秘密鍵・公開鍵

次に秘密鍵・公開鍵を作ります、といっても簡単で

• x を 0 < x < q で選んで秘密鍵とする

• y = g^x mod p を公開鍵とする

送信者は受信者に {(p, q, g), y} というデータを渡すことになります

DSA の署名と検証

署名しましょう
平文 M のハッシュ値を z とします

• 整数 k を 0 < k < q となるように選びます (x 同様内緒にします)

• r = (g^k mod p) mod q とします
• s = k^-1 (z + x r) mod q とします

この (r, s) が署名となります
k は M 毎に選びます、同じものを再び使うことのないようにします
r と s のどちらかが 0 になってしまった場合、k を選ぶところからやり直します

というわけで、メーッセージの受信者は

• (p, q, g) と y と z = Hash(M) と (r, s) を知っていて
• x と k は知らない

という状況になります
x と k を使わずに r を表現する方法を作れれば検証方法確立です

(g^z y^r)^(s-1) mod p

を考えます. y=g^x を使えばこれは

g^{(z + x r) (s-1)} mod p

です
g^q = 1 mod p だったので g の肩は mod q の世界でした
s の定義を見てみればこの値は

g^k mod p

なので更に mod q とってやれば

((g^z y^r)^(s-1) mod p) mod q = r

となります
左辺は x も k も使わない表現で r を表わすことができました

なので、受信者は

• アルゴリズムパラメータ (p, q, g)
• 公開鍵 y
• 平文 M
• ハッシュ関数
• 署名 (r, s)

が与えられたとき、(r, s) の検証がしたければ

((g^z y^r)^(s-1) mod p) mod q = r

が成立するかどうか確認すれば良いことになります

DSA の雑感

署名を偽造する一番素直な方法は

• y = g^x となる x を求める
• ((g^z y^r)^(s-1) mod p) mod q = r となる s を求める

のどちらかでしょうか
ここで後者の場合 k は攻撃者が選んで良いので r は知ってます
どっちも計算大変だよね? というのが署名を信頼する元になっています
なので p, q が大きいことが大切になってきます

q を使う理由は、単純に mod p の世界で考えてしまうと
平方剰余の乗法性を用いて既知のデータから未知のデータが類推し易くなるから
k をランダムで選ぶと既存の平文と署名から検証可能な平文と署名が作れちゃうとか
色々と知るべきことが残っていそうなんですがとりあえず DSA の流れということで

ちなみに、未だに s の形があの形なことが納得し切れていません
積だけだと攻撃に弱そうなことは分かるんですが.....