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日の特許（）によってカバーされている。この特許は「ワシントンD.C.に所在する、商務長官に代表されるアメリカ合衆国」に提供され、NISTが全世界にロイヤリティフリーで開放した。Claus P. Schnorrは、DSAは彼の特許（、失効済み）によってカバーされていると主張したが、この主張に対しては異議が唱えられている。
鍵生成.
鍵生成は2つのフェイズに分けられる。1つ目は他者と共有されるパラメータの選択であり、2つ目は公開鍵および秘密鍵の生成である。
パラメータ生成.
パラメータ ("p", "q", "g") は他者との間で共有される。
鍵ペアの生成.
パラメータ ("p", "q", "g") を基に鍵ペアを生成する。
冪剰余 "h"("p"–1)/"q" mod "p" および "gx" mod "p" の効率的な計算法が存在する。冪乗#効率的な演算法を参照のこと。
署名.
ハッシュ関数を formula_1、署名したいメッセージを formula_2 とする。
最初の2段階がメッセージごとの鍵を生成するステップである。冪剰余の計算が署名操作において最も計算量の多い過程であり、メッセージのハッシュを求める前に計算される。formula_13 が次いで計算量の多い過程であり、拡張されたユークリッドの互除法あるいは formula_14 としてフェルマーの小定理を用いて計算されることがある。
検証.
メッセージ formula_2 と署名 formula_11 の検証は以下のように行われる。
DSAはElGamal署名の改良版であり、類似している。
アルゴリズムの正当性.
DSAの署名スキームは、検証者が常に純正の署名を受け入れるという意味では正当である。それは以下のように証明される。
"g" = "h"("p" − 1)/"q" mod "p" であるとき、フェルマーの小定理より "gq" ≡ "h""p" − 1 ≡ 1 (mod "p") が導かれる。"g" > 1 かつ "q" が素数であるから、"g" は次数 "q" でなければならない。
署名者は次式を計算する。
ゆえに
"g" は次数 "q" (mod p) であるから
最終的に、DSAの正当性は以下に示される。
ランダム値の選択方法と安全性.
DSAにとって、署名の際のランダム値 "k" のエントロピー、機密性、唯一性は決定的に重要である。これら3つのうちの1つが破られることは、攻撃者に対して秘密鍵そのものが明かされることと等しい。"k" として同じ値を二度用いること（"k" を秘密にしていたとしても）、予測可能な値を用いること、複数の署名に対するそれぞれの "k" が数ビットであっても漏洩することは、DSAを破るには十分である。
2010年12月、"fail0verflow" と名乗るグループが、ソニーがPlayStation 3のソフトウェア署名に用いていた楕円曲線DSAの秘密鍵の回復に成功したと発表した。これは、ソニーが署名ごとに新しいランダムな "k" を用いていなかったためである。
この問題は、RFC 6979にあるように、秘密鍵とメッセージハッシュから決定論的に "k" を導くことで回避できる。これにより、"k" がそれぞれの "H(m)" に対して異なることと、秘密鍵 "x" を知らない攻撃者にとって予測不能であることが保証される。
実装ライブラリ.
DSAをサポートしているライブラリは以下のものがある。