Digital Signature Algorithm
適切な暗号学的ハッシュ関数 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 mod p なる g を求める。もし g が1となる場合には h を選択し直す。h = 2がよく用いられる。
パラメータ (p, q, g) は他者との間で共有される。
DSAの署名スキームは、検証者が常に純正の署名を受け入れるという意味では正当である。それは以下のように証明される。
g = h mod p であるとき、フェルマーの小定理より g ≡ h ≡ 1 (mod p) が導かれる。g > 1 かつ q が素数であるから、g は次数 q でなければならない。
署名者は次式を計算する。
s = k − 1 ( H ( m ) + x r ) mod q {\displaystyle s=k^{-1}(H(m)+xr){\bmod {\,}}q}
ゆえに
k ≡ H ( m ) s − 1 + x r s − 1 ≡ H ( m ) w + x r w ( mod q ) {\displaystyle {\begin{aligned}k&\equiv H(m)s^{-1}+xrs^{-1}\\&\equiv H(m)w+xrw{\pmod {q}}\end{aligned}}}
g は次数 q (mod p) であるから