DSA

multiplicative_order 安全素数 r,sからy=g^xをもとめる

pはmultiplicative order p-1が p-1 = tqとあらわされる素数（いわゆる安全素数）

鍵

署名

  • k \leftarrow \lbrack 1, q-1 \rbrack

  • r = g^k \mod p

  • s = k^{-1}(h + xr) \mod q

(r, s)が署名

検証

  • g^{hs^{-1}}y^{rs^{-1}} \equiv g^{s^{-1}(h + rx)} \mod p を計算し、 r と等しいことを確かめる

  • g の肩の位数は q なので g^{s^{-1}(h + rx) \mod q} \equiv g^k \mod p が成り立つ

r,sからy=gxをもとめる

  • g^{hs^{-1}}y^{rs^{-1}} \equiv g^k = r なので

  • g^{hs^{-1}}r \equiv y^{rs^{-1}} だし

  • (g^{hs^{-1}}r)^{r^{-1}s} = y

  • 当然ここの r^{-1}s は \mod q でのはなし