Digital Signature Algorithm

Digital Signature Algorithm(デジタル シグネチャー アルゴリズム、DSA)は、デジタル署名のための連邦情報処理標準である。1991年8月にアメリカ国立標準技術研究所 (NIST) によってDigital Signature Standard (DSS) での利用を目的として提唱され、1993年にFIPS 186として標準化された。2013年までに4度の改訂を経ている(1996年:FIPS 186-1、2000年:FIPS 186-2、2009年:FIPS 186-3、2013年:FIPS 186-4)。FIPS 186-5では、DSAは新たにデジタル署名を行うことには推奨されないが、標準策定以前に行われた署名の検証には引き続き利用可能とされる。DSAはElGamal署名の改良版の一つであり、それと同様に離散対数問題の困難性に基づく電子署名方式である。

DSAは、かつてNSAに勤めていたDavid W. Kravitzによる1991年7月26日の特許(アメリカ合衆国特許第 5,231,668号)によってカバーされている。この特許は「ワシントンD.C.に所在する、商務長官に代表されるアメリカ合衆国」に提供され、NISTが全世界にロイヤリティフリーで開放した。Claus P. Schnorrは、DSAは彼の特許(アメリカ合衆国特許第 4,995,082号、失効済み)によってカバーされていると主張したが、この主張に対しては異議が唱えられている。

鍵生成

鍵生成は2つのフェイズに分けられる。1つ目は他者と共有されるパラメータの選択であり、2つ目は公開鍵および秘密鍵の生成である。

パラメータ生成

  • 適切な暗号学的ハッシュ関数 H を選択する。当初のDSSでは H はSHA-1であったが、FIPS 186-4ではSHA-2も選択可能となった。ハッシュの出力値は鍵ペアのサイズに切り詰められる。
  • 鍵長 L および N を決定する。これらが主に暗号強度に影響する。当初のDSSでは、L は512から1024の間の64の倍数であった。NIST 800-57においては、L を2048あるいは3072とすることで、2010年あるいは2030年まで安全が保たれると推奨された。FIPS 186-3では、L と N の組み合わせは (1024, 160)、(2048, 224)、(2048, 256)、(3072, 256) の4つと規定された。
  • N ビットの素数 q を選択する。N はハッシュの出力長以下でなければならない。
  • p–1 が q の倍数となるような L ビットの素数法 p を選択する。
  • 1 < h < p−1 なる h に対して g = h(p–1)/q mod p なる g を求める。もし g が1となる場合には h を選択し直す(h の初期値としては 2がよく用いられる)。フェルマーの小定理より gq ≡ hp − 1 ≡ 1 (mod p) が導かれる。g > 1 かつ q が素数であるから、g は有限体 の乗法群(位数 p-1) の位数 q の元である(つまり 0 < a < q である任意の整数 a について、ga ≢ 1 (mod p)である)。

鍵ペアの生成

パラメータ (p, q, g) を基に鍵ペアを生成する。

  • 0 < x < q なる x をランダムに選択する。
  • y = gx mod p を計算する。x と y の対応は1対1であり、x から y を計算することは比較的容易だが、y から x を計算することは実質的に不可能(離散対数問題)である。つまり x と y の対応は一方向性関数になっている。
  • 公開鍵は (p, q, g, y)、秘密鍵は x である。

冪剰余 h(p–1)/q mod p および gx mod p の効率的な計算法が存在する。冪乗#効率的な演算法を参照のこと。

パラメータ (p, q, g, y) は他者との間で共有される。例えば、公開鍵基盤(PKI)を用いる場合は、これらは認証局(CA) において署名者の情報と関連付けられて公開される。

署名

ハッシュ関数を 、署名したいメッセージを とする。

最初の2段階がメッセージごとの鍵を生成するステップである。冪剰余の計算が署名操作において最も計算量の多い過程であり、メッセージのハッシュを求める前に計算される。 が次いで計算量の多い過程であり、拡張されたユークリッドの互除法あるいは としてフェルマーの小定理を用いて計算されることがある。

検証

メッセージ と署名 の検証は以下のように行われる。

DSAはElGamal署名の改良版であり、類似している。

アルゴリズムの正当性

DSAの署名スキームは、検証者が常に純正の署名を受け入れるという意味では正当である。それは以下のように証明される。

署名者は次式を計算する。

ゆえに

前述のように gq ≡ 1 (mod p) であるから

最終的に、DSAの正当性は以下に示される。

ランダム値の選択方法と安全性

DSAにとって、署名の際のランダム値 k のエントロピー、機密性、唯一性は決定的に重要である。これら3つのうちの1つが破られることは、攻撃者に対して秘密鍵そのものが明かされることと等しい。k として同じ値を二度用いること(k を秘密にしていたとしても)、予測可能な値を用いること、複数の署名に対するそれぞれの k が数ビットであっても漏洩することは、DSAを破るには十分である。

によって秘密鍵 x の値 を計算可能になる。

であるから、上の2式の差を取ると xr の項が相殺されてしまい、

となり、k の値が計算可能になる。k の値が分かれば上述のように秘密鍵 x の値も計算可能になる。

2010年12月、fail0verflow と名乗るグループが、ソニーがPlayStation 3のソフトウェア署名に用いていた楕円曲線DSAの秘密鍵の回復に成功したと発表した。これは、ソニーが署名ごとに新しいランダムな k を用いていなかったためである。

唯一性の問題は、RFC 6979にあるように、秘密鍵 x とメッセージハッシュ H(m) から決定論的に k を導くことで回避できる。これにより、k がそれぞれの H(m) に対して異なることと、秘密鍵 x を知らない攻撃者にとって予測不能であることが保証される。

実装ライブラリ

DSAをサポートしているライブラリは以下のものがある。

関連項目