離散対数問題を安全性の根拠にするデジタル署名。

---

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

1. 素数 $p,q$ と $g\in\mathbb{F}_{p}$ を固定し、A と B で共有する

$$q\mid p-1,\quad g^{q}\equiv 1\bmod{p}$$

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

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

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

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

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

$$\begin{aligned} w&\equiv s^{-1}\pmod q \\ u_1&\equiv H(m)w\pmod q \\ u_2&\equiv rw\pmod q \\ v&=(g^{u_1}y^{u_2}\bmod p)\bmod q \end{aligned}$$

$v=r$ なら正しい署名

---

• 🧠DSAを完全に理解する