Digital Signature Algorithm

デジタル署名アルゴリズム（DSA）とは

デジタル署名アルゴリズム（DSA）は、デジタル署名を行うための連邦情報処理標準（FIPS）の一つです。1991年8月にアメリカ国立標準技術研究所（NIST）によって提唱され、1993年にFIPS 186として標準化されました。その後、2013年までに4度の改訂が行われています。FIPS 186-5では、DSAは新規のデジタル署名には推奨されていませんが、過去に作成された署名の検証には引き続き利用可能です。

DSAは、ElGamal署名の改良版であり、離散対数問題の困難性に基づいた電子署名方式です。このアルゴリズムは、かつてNSAに勤務していたDavid W. Kravitzによって特許取得されましたが、NISTを通じて全世界にロイヤリティフリーで開放されています。

DSAの仕組み

DSAは、以下の3つの主要な段階で構成されています。

1. 鍵生成：署名者ごとに公開鍵と秘密鍵のペアを作成します。
2. 署名：メッセージに対するデジタル署名を生成します。
3. 検証：署名の正当性を検証します。

鍵生成

鍵生成は、以下の2つのフェーズに分かれます。

1. パラメータ生成：公開鍵と秘密鍵の生成に必要な共通パラメータを生成します。
2. 鍵ペア生成：共通パラメータに基づき、公開鍵と秘密鍵を生成します。

パラメータ生成

1. ハッシュ関数 H の選択：適切な暗号学的ハッシュ関数を選択します。初期のDSSではSHA-1が使用されていましたが、FIPS 186-4ではSHA-2も選択可能になりました。ハッシュの出力値は、鍵ペアのサイズに合わせられます。
2. 鍵長 L と N の決定：鍵長LとNを決定します。これらは主に暗号強度に影響します。FIPS 186-3では、LとNの組み合わせは、(1024, 160)、(2048, 224)、(2048, 256)、(3072, 256) の4つと規定されています。
3. Nビットの素数 q の選択：Nビットの素数qを選択します。Nはハッシュの出力長以下でなければなりません。
4. p - 1 が q の倍数となるような L ビットの素数法 p の選択：p-1がqの倍数となるようなLビットの素数法pを選択します。
5. g の計算：1 < h < p-1 なる h に対して、g = h^(p-1)/q mod p を計算します。もしgが1になる場合はhを選択し直します。これによりgは有限体の乗法群の位数qの元となります。

鍵ペアの生成

1. 秘密鍵 x の選択：0 < x < q なる乱数 x を秘密鍵として選択します。
2. 公開鍵 y の計算：y = g^x mod p を計算します。xからyの計算は容易ですが、yからxの計算は困難です。
3. 鍵ペアの完成：公開鍵は(p, q, g, y)、秘密鍵はxとなります。

署名

メッセージ m に対する署名生成は、以下の手順で行います。

1. ランダム値 k の選択：0 < k < q なるランダムな整数 k をメッセージごとに選択します。
2. r の計算：r = (g^k mod p) mod q を計算します。もし r = 0 なら、k を選択し直します。
3. s の計算：s = k^(-1) (H(m) + xr) mod q を計算します。もし s = 0 なら、k を選択し直します。
4. 署名の完成：署名は(r, s)となります。

検証

メッセージ m と署名 (r, s) の検証は、以下の手順で行います。

1. rとsの範囲の確認：0 < r < q かつ 0 < s < q を満たさない場合、署名を拒否します。
2. w の計算：w = s^(-1) mod q を計算します。
3. u1 の計算：u1 = H(m) w mod q を計算します。
4. u2 の計算：u2 = r w mod q を計算します。
5. v の計算：v = ((g^u1 y^u2) mod p) mod q を計算します。
6. 検証：v = r であれば、署名は正当なものとして受け入れます。

DSAの正当性

DSAの署名スキームは、検証者が常に正しい署名を受け入れるという意味で正当です。これは、署名生成と検証の手順から証明されます。

ランダム値 k の重要性

DSAでは、署名時のランダム値 k の選択が極めて重要です。k のエントロピー、機密性、唯一性のいずれかが損なわれると、秘密鍵が漏洩する可能性があります。

エントロピー：k のランダムさの偏りが少ないほど、エントロピーが高くなります。常に同じ k を使うと、エントロピーは最小になり、セキュリティが著しく低下します。
機密性：k は秘密に保つ必要があり、外部に漏洩すると秘密鍵が計算される可能性があります。
唯一性：同じ署名者が同じ k を用いて複数のメッセージに署名してはなりません。同じ k を使うと、攻撃者は署名を偽造できる可能性があります。

これらの問題を回避するために、RFC 6979で定義されているように、秘密鍵 x とメッセージハッシュ H(m) から決定論的に k を導く方法が推奨されています。

実装ライブラリ

DSAをサポートしているライブラリは多数あります。

Botan
Bouncy Castle
cryptlib
Crypto++
libcrypt
libsodium
Nettle
OpenSSL
wolfSSL
GnuTLS

関連項目

楕円曲線DSA（ECDSA）
ElGamal署名
合同式

外部リンク

FIPS PUB 186-4: Digital Signature Standard (DSS)
* Recommendation for Key Management -- Part 1: general, NIST Special Publication 800-57

もう一度検索