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）。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" mod "p" および "g" mod "p" の効率的な計算法が存在する。冪乗#効率的な演算法を参照のこと。
ハッシュ関数を formula_1、署名したいメッセージを formula_2 とする。
最初の2段階がメッセージごとの鍵を生成するステップである。冪剰余の計算が署名操作において最も計算量の多い過程であり、メッセージのハッシュを求める前に計算される。formula_13 が次いで計算量の多い過程であり、拡張されたユークリッドの互除法あるいは formula_14 としてフェルマーの小定理を用いて計算されることがある。
メッセージ formula_2 と署名 formula_11 の検証は以下のように行われる。
DSAはElGamal署名の改良版であり、類似している。
DSAの署名スキームは、検証者が常に純正の署名を受け入れるという意味では正当である。それは以下のように証明される。
"g" = "h" mod "p" であるとき、フェルマーの小定理より "g" ≡ "h" ≡ 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をサポートしているライブラリは以下のものがある。