Digital Signature Algorithm
ハッシュ関数を H {\displaystyle H} 、署名したいメッセージを m {\displaystyle m} とする。
0 < k < q {\displaystyle 0<k<q} なる k {\displaystyle k} をメッセージごとにランダムに決定する。
r = ( g k mod p ) mod q {\displaystyle r=\left(g^{k}{\bmod {\,}}p\right){\bmod {\,}}q} を計算する
もし r = 0 {\displaystyle r=0} である場合には k {\displaystyle k} を選択し直す。
s = k − 1 ( H ( m ) + x r ) mod q {\displaystyle s=k^{-1}\left(H\left(m\right)+xr\right){\bmod {\,}}q} を計算する。
もし s = 0 {\displaystyle s=0} である場合には k {\displaystyle k} を選択し直す。
( r , s ) {\displaystyle \left(r,s\right)} が m {\displaystyle m} に対する署名となる。
最初の2段階がメッセージごとの鍵を生成するステップである。冪剰余の計算が署名操作において最も計算量の多い過程であり、メッセージのハッシュを求める前に計算される。 k − 1 mod q {\displaystyle k^{-1}{\bmod {\,}}q} が次いで計算量の多い過程であり、拡張されたユークリッドの互除法あるいは k q − 2 mod q {\displaystyle k^{q-2}{\bmod {\,}}q} としてフェルマーの小定理を用いて計算されることがある。
g k ≡ g H ( m ) w g x r w ≡ g H ( m ) w y r w ≡ g u 1 y u 2 ( mod p ) {\displaystyle {\begin{aligned}g^{k}&\equiv g^{H(m)w}g^{xrw}\\&\equiv g^{H(m)w}y^{rw}\\&\equiv g^{u1}y^{u2}{\pmod {p}}\end{aligned}}}
最終的に、DSAの正当性は以下に示される。
r = ( g k mod p ) mod q = ( g u 1 y u 2 mod p ) mod q = v {\displaystyle {\begin{aligned}r&=(g^{k}{\bmod {\,}}p){\bmod {\,}}q\\&=(g^{u1}y^{u2}{\bmod {\,}}p){\bmod {\,}}q\\&=v\end{aligned}}}