離散対数問題を安全性の根拠にするデジタル署名。
DSA の元になった方式。

---

署名者 A と検証者 B の間のやり取りを考える。

1. 素数 $p$ と、$\mathbb{F}_{p}^{\times}$ の生成元 $g$ を固定し、A と B で共有する

$$g\in\mathbb{F}_{p}^{\times}$$

2. A は秘密鍵 $x\in\{1,\dots,p-2\}$ を決め、公開鍵 $y$ を共有する

$$y\equiv g^{x}\pmod p$$

3. A はメッセージ $m$ に署名 $(r,s)$ を作り、B に送る

$$\begin{aligned} k&\in\{1,\dots,p-2\},\quad \gcd(k,p-1)=1, \\ r&\equiv g^{k}\pmod p, \\ s&\equiv k^{-1}(H(m)-xr)\pmod {p-1} \end{aligned}$$

4. B は $(r,s)$ を検証する

$$g^{H(m)}\equiv y^{r}r^{s}\pmod p$$

これが成り立つなら正しい署名