利用者:Roget/試訳/DSA

The Digital Signature Algorithm (DSA) is a United States Federal Government standard or FIPS for digital signatures. It was proposed by the National Institute of Standards and Technology (NIST) in August 1991 for use in their Digital Signature Standard (DSS), specified in FIPS 186 [1], adopted in 1993. A minor revision was issued in 1996 as FIPS 186-1 [2], and the standard was expanded further in 2000 as FIPS 186-2 [3].

'DSAは電子署名に関するアメリカ連邦政府の標準規格 (Federal Information Processing Standards (FIPS))である。 NISTによって1991年8月に提案され FIPS 186 [4] として指定され、1993年採用された。 1996年、FIPS 186-1 [5]として改訂され、2000年にはFIPS 186-2として拡張された[6]。

DSA is covered by アメリカ合衆国特許第 5,231,668号, filed July 26, 1991, and attributed to David W. Kravitz, a former NSA employee. This patent was given to "The United States of America as represented by the Secretary of Commerce, Washington, D.C." and the NIST has made this patent available world-wide royalty-free. [7] Dr. Claus P. Schnorr claims that his アメリカ合衆国特許第 4,995,082号 covers DSA; this claim is disputed (see minutes of the Sept. 94 meeting of the Computer System Security and Privacy Advisory Board).

DSAはアメリカ合衆国特許第 5,231,668号となっており、

暗号方式

鍵生成

（セットアップアルゴリズムと呼んではダメなのか...）

鍵生成アルゴリズムは2段階に分かれる。 第1段階ではシステムのユーザ間で共有されるパラメータを決定する。

• 暗号学的なハッシュ関数Hを選ぶ。
  • 元の定義では、HはSHAである。しかし、実際にはSHA系のより強いとハッシュ関数が使われている。既に作られている鍵ペアで古いハッシュ関数を用いている場合、互換性を考えて、新規に選ばれたハッシュ関数のハッシュ値は切り詰められることがある。
• 鍵長Lを選ぶ。
  • 鍵の暗号学的な強さは主にこのパラメータに依存する。元の定義では、Lは512から1024の間の64の倍数と定められている。FIPS-186-2, change notice 1 では、Lは常に1024になっている。NIST 800-57は、2010年から2030年まで安全性を保ちたい場合には、Lの長さを2048または3072とするよう推奨している。 (同時により長いハッシュ関数とqを用いることが必要である。) また、draft FIPS 186-3ではより長い鍵長Lや長いハッシュ関数を用いることも可能である。
• Hの出力長と同じビット数の素数qを選ぶ。
• p-1がqの倍数となるLビットの素数pを選ぶ。
• 法pの下で乗法の位数がqとなる数gを選ぶ。
  • 1 < h < p-1となる適当なhについて、g = h^(p-1)/q mod pとして結果が1でなければ採用するとしても良い。使いやすいgを取るためにh=2がよく使われる。
• システムのユーザ間で(p, q, g)が共有パラメータとして用いられる。

第2段階では、各ユーザの鍵を生成する。

• 0 < x < qからランダムにxを選ぶ。
• y = g^x mod pを計算する。
• 公開鍵は (p, q, g, y)。秘密鍵はx。

FIPS 186-3 (草稿は[8]を参照のこと) ではSHA-224/256/384/512がハッシュ関数として用いられ、qは224または256ビットとなる。また、Lは2048または3072ビットとなる。

h^a mod pやg^x mod pを計算する効率の良いアルゴリズムが存在する。

署名生成

署名したい平文をmとする。

• ランダムなkを 0 < k < qから選ぶ。
• r = (g^k mod p) mod qを計算する。
• s = (k^-1 (H(m)+x*r)) mod qを計算する。
• r=0またはs=0ならやり直し。
• (r, s)を署名として出力する。

ユークリッドの互除法#拡張された互除法を用いて、k^-1 mod qを計算できる。

検証

平文をm, 署名を(r, s)とする。

• 0 < r < q かつ 0 < s < qでない場合、拒否する。
• w = s^-1 mod qを計算する。
• u1 = H(m)*w mod qを計算する。
• u2 = r*w mod qを計算する。
• v = (g^u1*y^u2 mod p) mod qを計算する。
• v = rならば受理、そうでないなら拒否する。

DSAはElGamal署名と類似点が多い。

完全性

正当な署名者が正しく署名を作れば検証を必ず通るという意味でDSAは完全である。

まずg = h^(p-1)/q mod pなので、フェルマーの小定理よりg^q ≡ h^p-1 ≡ 1 (mod p)である。 また、g > 1とqが素数であることから、gの位数はqである。

署名者は

$s=k^{-1}(H(m)+xr)\mod {q}.$

とsを計算している。

${\begin{matrix}k&\equiv &H(m)s^{-1}+xrs^{-1}\\&\equiv &H(m)w+xrw{\pmod {q}}.\\\end{matrix}}$

gの位数はqであるから、

${\begin{matrix}g^{k}&\equiv &g^{H(m)w}g^{xrw}\\&\equiv &g^{H(m)w}y^{rw}\\&\equiv &g^{u1}y^{u2}{\pmod {p}}\\\end{matrix}}$

となる。 最後に、

$r=(g^{k}\mod p)\mod q=(g^{u1}y^{u2}\mod p)\mod q=v.$

より完全性が示せた。

参照

• ElGamal署名
• Elliptic Curve DSA

外部リンク

• FIPS-186, DSA仕様書, the first version of the official DSA specification.
• FIPS-186, change notice No.1, DSA仕様書の変更点, the first change notice to the first version of the specification.
• FIPS-186-1, DSA仕様書改訂版, the first revision to the official DSA specification.
• FIPS-186-2, DSA仕様書改訂版2版 (2版における変更点も含む), the second revision to the official DSA specification (including the first change notice to this revision).
• FIPS-186-3, DSA仕様書改訂版3版草稿, draft for the third revision to the official DSA specification.
• Recommendation for Key Management -- Part 1: general, NIST Special Publication 800-57, p. 62–63