DSAを完全に理解します。

# DSAの概要

署名者 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$ なら正しい署名

# $\bmod p$ と $\bmod q$ の2つを考えている理由

$\bmod p$ の上にあるのは公開情報である $y,g$ のみで、ほかは全て $\bmod q$ の上で考えている。

大雑把には、

• 安全性のために公開情報は大きな値で ($\bmod p$ で) 扱う
• 通信量軽減のために署名は小さな値で ($\bmod q$ で) 扱う

ということらしい。

---

もう少し構造的には、$q$ は「指数側の世界」のサイズ。

秘密鍵 $x$ や nonce $k$ は $g$ の指数として使われるため、$\langle g\rangle$ の位数である $q$ を法として考えればよい。

一方で、実際の公開値 $y=g^{x}$ や $g^{k}$ は $\mathbb{F}_{p}^{\times}$ の元として計算される。

# 検証の整合性を見る

1. $(r,s)$ は公開鍵 $y$ に対応する秘密鍵で作られた $\Longrightarrow v=r$ (必要性)
2. 秘密鍵を知らずに $v=r$ となる $(r,s)$ を作るのは難しい (擬似的な十分性)

が必要。

# 1を確かめる

$s$ の定義から、$\mathbb{F}_{q}$ において、

$$\begin{align*} k=&s^{-1}(H(m)+xr)\\ =&wH(m)+wxr\\ =&u_{1}+u_{2}x \end{align*}$$

が成り立ち、したがって

$$\begin{align*} v=&(g^{u_{1}}y^{u_{2}}\bmod p)\bmod q\\ =&(g^{u_{1}+u_{2}x}\bmod p)\bmod q\\ =&(g^{k}\bmod p)\bmod q\\ =& r \end{align*}$$

# 2について

これは色々な根拠が複合的に為すもの。この続きで頑張って理解したい。

# $k$ を毎回ランダムに選ぶ理由

$k$ は秘密鍵 $x$ を守るためのもの。

1. 例えば $k$ が既知だった場合、固定値 $k=1$ を考えると、

$$s\equiv H(m)+xr\pmod q$$

となるため、

$$x\equiv (s-H(m))r^{-1}\pmod q$$

より、1つの署名から $x$ が求まってしまう。

2. 同じ $k$ を2度使った場合、メッセージ $m_{1},m_{2}$ に対する署名をそれぞれ $(r,s_{1}),(r,s_{2})$ とする。

このとき、

$$\begin{align*} s_{1}&\equiv k^{-1}(H(m_{1})+xr)\pmod q\\ s_{2}&\equiv k^{-1}(H(m_{2})+xr)\pmod q \end{align*}$$

である。辺々を引くと $x$ が消えて、

$$s_{1}-s_{2}\equiv k^{-1}(H(m_{1})-H(m_{2}))\pmod q$$

したがって、

$$k\equiv (H(m_{1})-H(m_{2}))(s_{1}-s_{2})^{-1}\pmod q$$

となり、

$$x\equiv (s_{1}k-H(m_{1}))r^{-1}\pmod q$$

より、秘密鍵 $x$ も求まってしまう。線形代数って怖い！

---

以上のように、$k$ は秘密鍵 $x$ を隠すために使われている。

公開される $r=(g^{k}\bmod p)\bmod q$ から $k$ を求めることは、DLPに関係するため難しい。

また、$k$ が未知で毎回異なるため、

$$s\equiv k^{-1}(H(m)+xr)\pmod q$$

から $x$ を直接求めることもできない。

# $q\mid p-1$ ってなんのための制約？

DSAでは、$\mathbb{F}_{p}^{\times}$ の中に位数 $q$ の部分群 $\langle g\rangle$ を作りたい。

ラグランジュの定理より、部分群の位数は群の位数を割り切る必要がある。すなわち、

$$|\mathbb{F}_{p}^{\times}|=p-1$$

なので、位数 $q$ の部分群を持つために

$$q\mid p-1$$

が必要になる。逆に、コーシーの定理より、$q$ が $|\mathbb{F}_{p}^{\times}|$ を割り切るなら、位数 $q$ の元が存在する。

この部分群の生成元を $g$ とすると、

$$g^{q}\equiv 1\pmod p$$

であり、$g$ の指数は $\bmod q$ で考えられる。

これにより、公開計算は大きな $\mathbb{F}_{p}$ 上で行いながら、秘密鍵 $x$ や nonce $k$ は小さな $\mathbb{F}_{q}$ 上で扱える。