電子署名
概要
電子署名（digital signature）とは、秘密鍵を持つ者だけが文書に対して作れ、対応する公開鍵で誰でも正しさを確かめられる印、またはそれを作る鍵生成・署名・検証の 3 つの手順の組（署名方式）である。標準的な安全性は、好きな文書の署名を何度でも見た攻撃者が新しい文書の正しい署名を作れないこと（選択文書攻撃のもとでの存在的偽造不可能性）である。文書をそのまま冪にする RSA 署名は乗法性で偽造されるが、衝突困難なハッシュ関数に通してから安全な方式で署名すれば安全になる。離散対数にもとづく Schnorr 署名は、署名ごとの乱数を使い回すと秘密鍵が一次式で求まる。
RSA暗号 の小さな鍵 $n=3233=61\cdot53$、$e=17$、$d=2753$ で、秘密の $d$ を持つ人が文書を表す数 $m=65$ に $s=65^{2753}\bmod 3233=588$ を付けて公開する。誰でも公開鍵で $588^{17}\bmod3233=65$ を計算して、$s$ が $m$ に合うことを確かめられる。一方で、$588$ と $65$ の組は $d$ を使わなくても作れてしまう。$588$ を先に決めて $588^{17}\bmod 3233$ を計算すれば、それに合う「文書」が出てくるからである。
秘密鍵を持つ者だけが作れ、公開鍵で誰でも確かめられる文書の印を 電子署名（digital signature）という。上の計算の仕組みが電子署名として安全かどうかは、攻撃者に何を許し、何を作られたら破られたとみなすかを決めてはじめて問える。標準的な基準は、攻撃者が好きな文書の署名を何度でも見たあとでも、新しい文書の正しい署名を作れないこと（存在的偽造不可能性）である。上の「文書をそのまま冪にする」RSA 署名はこの基準を満たさない。文書を値域の大きい ハッシュ関数 に通してから冪にする形は、ハッシュ関数を無作為な関数とみなすモデルのもとで、RSA の逆向きの計算が難しいという仮定から安全であることが示されている。
この記事では、署名方式とその正しさ・存在的偽造不可能性を定義し、次を証明する。文書をそのまま冪にする RSA 署名が乗法性によって偽造されること（thm-sig-rsa-forgery）。ハッシュしてから署名する方式が、元の方式の安全性とハッシュ関数の衝突困難性から安全になること（thm-sig-hash-sign）。Schnorr 署名が正しく検証されること（prop-sig-schnorr-correct）と、署名に使う乱数を使い回すと秘密鍵が漏れること（thm-sig-schnorr-nonce）。
定義
公開鍵暗号 の定義「公開鍵暗号方式」と同じく、各手順は効率よく（鍵の長さの多項式時間で）計算でき、乱数を使ってよい手順とする。
有限集合 $\mathcal M$（文書の集合）について、次の 3 つの手順の組 $(\mathsf{Gen},\mathsf{Sign},\mathsf{Ver})$ を 署名方式（signature scheme）という。
- 鍵生成 $\mathsf{Gen}$ は乱数を使い、公開鍵（検証鍵）$\mathit{pk}$ と 秘密鍵（署名鍵）$\mathit{sk}$ の組を出力する。
- 署名 $\mathsf{Sign}$ は秘密鍵と文書 $m\in\mathcal M$ から、乱数を使ってよい手順で 署名 $\sigma=\mathsf{Sign}(\mathit{sk},m)$ を出力する。
- 検証 $\mathsf{Ver}$ は公開鍵・文書・署名から、乱数を使わない手順で「受け入れる」か「退ける」を出力する。
さらに、$\mathsf{Gen}$ が出力しうるすべての $(\mathit{pk},\mathit{sk})$ とすべての $m\in\mathcal M$ について、確率 $1$ で $\mathsf{Ver}(\mathit{pk},m,\mathsf{Sign}(\mathit{sk},m))$ が「受け入れる」となること（正しさ）を要求する。
この形は BS23 Definition 13.1（pp. 528–529）による。公開鍵暗号では公開鍵で暗号化し秘密鍵で戻すのに対し、署名では秘密鍵で作り公開鍵で確かめる。
署名方式 $\mathcal S=(\mathsf{Gen},\mathsf{Sign},\mathsf{Ver})$ と攻撃者 $\mathsf A$ について、次の実験を考える。
- $(\mathit{pk},\mathit{sk})\leftarrow\mathsf{Gen}$ を実行し、$\mathit{pk}$ を $\mathsf A$ に渡す。
- $\mathsf A$ は文書 $m_1,m_2,\dots\in\mathcal M$ を、それまでの答えを見ながら 1 つずつ選んで送り、そのたびに $\sigma_i=\mathsf{Sign}(\mathit{sk},m_i)$ を受け取る（選択文書攻撃）。
- 最後に $\mathsf A$ は組 $(m,\sigma)$ を出力する。
$\mathsf{Ver}(\mathit{pk},m,\sigma)$ が「受け入れる」で、かつ $m\notin\{m_1,m_2,\dots\}$ のとき $\mathsf A$ の勝ちとし、勝つ確率を $\operatorname{Adv}^{\mathrm{sig}}(\mathsf A,\mathcal S)$ と書く。効率のよいどの攻撃者でもこれが無視できるほど小さいとき、$\mathcal S$ は 安全、または 選択文書攻撃のもとで存在的に偽造不可能（existentially unforgeable under a chosen message attack、EUF-CMA）であるという。勝ちの条件の 2 つ目を $(m,\sigma)\notin\{(m_1,\sigma_1),(m_2,\sigma_2),\dots\}$ に替えたものを 強い意味で安全（strongly secure）という。
確率は鍵生成・署名・攻撃者のすべての乱数についてとる。「効率がよい」「無視できる」は ハッシュ関数 の定義「衝突困難性」の直後の説明と同じ意味である。攻撃者が勝つときに出力する組を 存在的偽造 という。偽造する文書は攻撃者が自由に選んでよく、意味のある文書である必要はない。公開鍵は公開されているので、攻撃者は自分で検証を行える。このため検証の問い合わせを攻撃者に別に許す必要はない。以上は BS23 Attack Game 13.1・Definition 13.2・Attack Game 13.2・Definition 13.3（pp. 529–530）による。
RSA 署名
RSA暗号 の定義「RSA暗号の鍵・暗号化・復号」の鍵 $(n,e)$（公開鍵）と $d$（秘密鍵）を使う。文書の集合を $\mathcal M=\{0,1,\dots,n-1\}$ とし、$m$ の署名を $\sigma=m^d\bmod n$ とする。検証では $\sigma^e\equiv m\pmod n$ のとき受け入れる。
RSA暗号 の定理「復号の正しさ」により、$n$ と互いに素でない数も含めて、すべての $0\le x< n$ について $x^{de}\equiv x\pmod n$ である。$\sigma^e\equiv m^{de}\equiv m$ なので、この方式は正しい。これは RSA暗号 の注意「署名への応用」の方式そのものである。
公開鍵 $(n,e)$ の教科書的 RSA 署名について、次が成り立つ。
- 問い合わせなしの偽造：どの $\sigma\in\{0,\dots,n-1\}$ についても、$m:=\sigma^e\bmod n$ とおけば $(m,\sigma)$ は受け入れられる。
- 乗法性：$(m_1,\sigma_1)$、$(m_2,\sigma_2)$ が受け入れられるなら、$(m_1m_2\bmod n,\ \sigma_1\sigma_2\bmod n)$ も受け入れられる。
- 任意の文書の偽造：どの $m\in\{0,\dots,n-1\}$ についても、署名の問い合わせを高々 1 回して $m$ の正しい署名を作る効率のよい手順で、問い合わせる文書が $m$ と異なるものがある。
とくに、この方式は安全でない（1 の攻撃者は $\operatorname{Adv}^{\mathrm{sig}}=1$）。
- $\sigma^e\equiv m\pmod n$ は $m$ の定め方そのものである。問い合わせをしていないので、$m$ は新しい文書である。
- $(\sigma_1\sigma_2)^e=\sigma_1^e\sigma_2^e\equiv m_1m_2\pmod n$ による。
- まず $\gcd(m,n)=1$ の場合を考える。$n$ が奇数なら $r=2$、偶数なら $r=n-1$ とし（どちらも $\gcd(r,n)=1$ で、$n\ge6$ より $r\not\equiv1\pmod n$）、$\hat m:=mr^e\bmod n$ の署名 $\hat\sigma$ を問い合わせ、$\sigma:=\hat\sigma r^{-1}\bmod n$ を出力する（$r^{-1}$ は 拡張Euclidの互除法 で計算できる）。$\hat\sigma^e\equiv\hat m$ なので
$$ \sigma^e\equiv\hat\sigma^e(r^{-1})^e\equiv mr^e(r^e)^{-1}\equiv m\pmod n $$
であり、$\sigma$ は $m$ の正しい署名である。$\hat m\equiv m$ とすると、$m$ は法 $n$ で可逆なので $r^e\equiv1$ となる。$\gcd(e,\varphi(n))=1$ より $e$ 乗は法 $n$ の可逆元の上の全単射なので（$ed\equiv1\pmod{\varphi(n)}$ により $x\mapsto x^d$ が逆写像になる）、$r\equiv1\pmod n$ となって $r$ の選び方に反する。よって $\hat m\ne m$ である。
$m=0$ なら $\sigma=0$ が問い合わせなしで正しい署名である。$0< m< n$ かつ $g:=\gcd(m,n)>1$ なら、$g$ は $n$ の素因数 $p$ か $q$ で、もう一方は $n/g$ である。すると $\varphi(n)=(p-1)(q-1)$ が分かり、$ed\equiv1\pmod{\varphi(n)}$ を解いて秘密鍵 $d$ を計算できるので、問い合わせなしに $m^d\bmod n$ を作れる。$\square$
3 の手順は、$m$ に $r^e$ を掛けて隠し、別の文書に見せかけるので、目隠し（blinding）と呼ばれる（BS23 p. 537 の式 (13.4) の前後）。1 と 3 の攻撃は BS23 §13.3 の「The importance of hashing」（pp. 536–537）にある。RSA暗号 の注意「署名への応用」で $d$ なしでは難しいと考えられているとした計算は、署名の問い合わせをせずに、一様に無作為に選ばれて与えられた $m$ の署名を作ることであり、1〜3 はそれと矛盾しない。
$n=3233$、$e=17$、$d=2753$ とする。
- 乗法性：$2$ の署名は $2^{2753}\bmod3233=1027$、$3$ の署名は $1857$ である。$1027\cdot1857\bmod3233=2902$ は $6$ の正しい署名で、実際 $2902^{17}\bmod3233=6$ である。
- 目隠し：$m=65$ の署名を、$65$ を問い合わせずに作る。$r=2$ とすると $2^{17}\bmod3233=1752$ で、$\hat m=65\cdot1752\bmod3233=725$ である。$725$ の署名 $\hat\sigma=1176$ を問い合わせ、$2^{-1}\equiv1617$（$2\cdot1617=3234\equiv1$）を掛けると $1176\cdot1617\bmod3233=588$ となり、冒頭の $65$ の署名 $588$ が得られる。
ハッシュしてから署名する
$\mathcal S=(\mathsf{Gen},\mathsf{Sign},\mathsf{Ver})$ を文書の集合 $\mathcal M$ の上の署名方式、$\{H_k\colon\mathcal M'\to\mathcal M\}_{k}$ を公開の母数 $k$ で決まる ハッシュ関数 の族とする。新しい方式 $\mathcal S'$ を次で定める。
- 鍵生成：母数 $k$ を衝突困難性の実験で母数を与えるときと同じ選び方で選び、$(\mathit{pk},\mathit{sk})\leftarrow\mathsf{Gen}$ とする。公開鍵は $(k,\mathit{pk})$、秘密鍵は $(k,\mathit{sk})$ である。
- 署名：$\mathsf{Sign}'(m)=\mathsf{Sign}(\mathit{sk},H_k(m))$（$m\in\mathcal M'$）。
- 検証：$\mathsf{Ver}'(m,\sigma)=\mathsf{Ver}(\mathit{pk},H_k(m),\sigma)$。
$\mathcal S$ が正しければ $\mathcal S'$ も正しい。$\mathcal M'$ は $\mathcal M$ よりずっと大きくてよく、短い文書しか署名できない方式から長い文書の署名方式が作れる（BS23 §13.2 の式 (13.1)、p. 532。そこでは $H$ を 1 つの関数として扱っている）。
$\mathcal S$ が安全で、$\{H_k\}$ が衝突困難（ハッシュ関数 の定義「衝突困難性」）ならば、$\mathcal S'$ は安全である。詳しくは、$\mathcal S'$ を攻撃する効率のよい攻撃者 $\mathsf A$ に対し、$\mathsf A$ を中で 1 回動かす効率のよい手順として、$\mathcal S$ の攻撃者 $\mathsf B_1$ と衝突を探す手順 $\mathsf B_2$ があって
$$
\operatorname{Adv}^{\mathrm{sig}}(\mathsf A,\mathcal S')\le\operatorname{Adv}^{\mathrm{sig}}(\mathsf B_1,\mathcal S)+\Pr[\mathsf B_2\text{ が衝突を出力する}]
$$
が成り立つ。
$\mathsf A$ が $\mathcal S'$ の実験で問い合わせる文書を $m_1,\dots,m_Q$、出力を $(m,\sigma)$ とし、次の 2 つの事象を考える。$W$：$\mathsf A$ が勝つ。$C$：ある $i$ で $H_k(m)=H_k(m_i)$。
$\mathsf B_1$：$\mathcal S$ の実験で $\mathit{pk}$ を受け取り、自分で母数 $k$ を鍵生成と同じ選び方で選んで $(k,\mathit{pk})$ を $\mathsf A$ に渡す。$\mathsf A$ が $m_i$ を問い合わせたら、自分の挑戦者に $H_k(m_i)$ を問い合わせ、返ってきた署名をそのまま $\mathsf A$ に渡す。$\mathsf A$ が $(m,\sigma)$ を出力したら $(H_k(m),\sigma)$ を出力する。$\mathsf A$ が見るものは $\mathcal S'$ の実験とまったく同じ分布をもつ。$W$ が起き $C$ が起きないとき、$\mathsf{Ver}(\mathit{pk},H_k(m),\sigma)$ は受け入れで、$H_k(m)$ は $\mathsf B_1$ が問い合わせた $H_k(m_1),\dots,H_k(m_Q)$ のどれとも異なるので、$\mathsf B_1$ が勝つ。よって $\Pr[W\cap C^c]\le\operatorname{Adv}^{\mathrm{sig}}(\mathsf B_1,\mathcal S)$。
$\mathsf B_2$：母数 $k$ を受け取り、自分で $(\mathit{pk},\mathit{sk})\leftarrow\mathsf{Gen}$ を実行して $(k,\mathit{pk})$ を $\mathsf A$ に渡し、問い合わせには $\mathsf{Sign}(\mathit{sk},H_k(m_i))$ を答える。これも $\mathcal S'$ の実験と同じ分布である。最後に $H_k(m)=H_k(m_i)$ かつ $m\ne m_i$ となる $i$ があれば $\{m,m_i\}$ を出力する。$W$ が起きれば $m$ は新しく $m\ne m_i$（すべての $i$）なので、$W\cap C$ のとき $\mathsf B_2$ は衝突を出力する。よって $\Pr[W\cap C]\le\Pr[\mathsf B_2\text{ が衝突を出力する}]$。
2 つを足すと $\Pr[W]=\Pr[W\cap C^c]+\Pr[W\cap C]$ から主張の不等式が出る。右辺の 2 項は仮定によりどちらも無視できるほど小さいので、$\mathcal S'$ は安全である。$\square$
この定理は BS23 Theorem 13.1（p. 533）にあたる。定理は $\mathcal S$ が安全であることを仮定しているので、教科書的 RSA 署名にハッシュを付けたものには直接は使えない。値が $\{0,\dots,n-1\}$ の大きな部分（$n/4$ 個以上の元からなる集合）を動くハッシュ関数 $H$ で $\sigma=H(m)^d\bmod n$ とする方式（full domain hash）は、$H$ を一様に無作為な関数とみなす ランダムオラクルモデル のもとで、RSA の逆向きの計算が難しいという仮定から安全であることが示されている（BS23 Theorem 13.3（p. 535）と Theorem 13.4（p. 538）。この記事では証明しない）。このとき thm-sig-rsa-forgery の 1 の攻撃は、$\sigma^e$ に等しいハッシュ値をもつ文書を探す問題になり、2・3 の攻撃は $H(m_1)H(m_2)$ や $H(m)r^e$ をハッシュ値にもつ文書を探す問題になる。
Schnorr 署名
以下、$G$ を素数位数 $q$ の 巡回群、$g$ をその生成元とし、$G$ での 離散対数 問題（$g^\alpha$ から $\alpha\in\mathbb Z/q\mathbb Z$ を求める問題）が難しいとする。$C\subseteq\mathbb Z/q\mathbb Z$ を十分大きな集合、$H\colon\mathcal M\times G\to C$ をハッシュ関数とする。
- 鍵生成：$\alpha\in\mathbb Z/q\mathbb Z$ を一様に選び、秘密鍵を $\alpha$、公開鍵を $u=g^\alpha$ とする。
- 署名：$t\in\mathbb Z/q\mathbb Z$ を一様に選び、$u_t=g^t$、$c=H(m,u_t)$、$z=t+\alpha c$ とする。署名は $\sigma=(u_t,z)$ である。
- 検証：$c=H(m,u_t)$ を計算し、$g^z=u_t\,u^c$ なら受け入れる。
この形は BS23 §19.2（p. 763）による。$g^q=1$ なので、指数は $\mathbb Z/q\mathbb Z$ の元として意味をもつ。
def-sig-schnorr の手順で作った署名は受け入れられる。
検証で計算する $c=H(m,u_t)$ は署名のときの $c$ と同じである。$g^z=g^{t+\alpha c}=g^t(g^\alpha)^c=u_t\,u^c$ による。$\square$
$H$ をランダムオラクルとみなすと、$G$ での離散対数の仮定のもとで Schnorr 署名は安全である（BS23 Theorem 19.7（p. 764）と、離散対数への帰着をまとめた評価 (19.6)（p. 768）。この記事では証明しない）。ただし安全性は、乱数 $t$ が署名ごとに新しく一様に選ばれることに頼っている。
同じ秘密鍵 $\alpha$ で文書 $m_0,m_1$ に署名した $\sigma_0=(u_{t_0},z_0)$、$\sigma_1=(u_{t_1},z_1)$ が得られ、$c_i=H(m_i,u_{t_i})$ とする。
- $t_1=t_0$ で $c_1\ne c_0$ なら、$\alpha=(z_1-z_0)(c_1-c_0)^{-1}$ である。$t_1=t_0$ は $u_{t_1}=u_{t_0}$ と同値なので、公開の値から気づける。
- より一般に、既知の $a,b\in\mathbb Z/q\mathbb Z$ で $t_1=at_0+b$ となっていて、$c_1\ne ac_0$ なら、$\alpha=(z_1-az_0-b)(c_1-ac_0)^{-1}$ である。
2 を示せば、1 は $a=1$、$b=0$ の場合である。署名の式から $z_0=t_0+\alpha c_0$、$z_1=t_1+\alpha c_1=at_0+b+\alpha c_1$ である。第 1 式の $a$ 倍と $b$ を第 2 式から引くと
$$
z_1-az_0-b=\alpha(c_1-ac_0)
$$
となる。$q$ は素数なので $c_1-ac_0\ne0$ は $\mathbb Z/q\mathbb Z$ で可逆であり、$\alpha$ の式が得られる。1 の後半は、$t\mapsto g^t$ が $\mathbb Z/q\mathbb Z$ から $G$ への全単射であることによる。$\square$
2 は BS23 Exercise 19.1（p. 808）の主張である。$H$ をランダムオラクルとみなすと、$m_0\ne m_1$ のとき $c_1$ は $c_0$ と独立に $C$ から一様に選ばれるので、$c_1=ac_0$ となる確率は $1/\lvert C\rvert$ 以下である。実際の機器でも、すべての署名で同じ乱数を使ったために秘密鍵が知られた例がある（BS23 p. 771。そこでは ECDSA について述べ、Schnorr 署名にも同じことが起きるとしている）。対策として、秘密鍵と文書から擬似乱数関数で $t$ を決める決定的な方式が使われる（BS23 p. 771）。
$p=23$ の平方剰余のなす位数 $q=11$ の部分群で $g=2$ とする（公開鍵暗号 の例「法 23 の位数 11 の部分群での暗号化」と同じ群）。秘密鍵 $\alpha=7$ の公開鍵は $u=2^7\bmod23=13$ である。$t=5$ で $u_t=2^5\bmod23=9$ とし、2 つの文書のハッシュ値が $c_0=3$、$c_1=8$ だったとする。
- $z_0=5+7\cdot3=26\equiv4\pmod{11}$。検証：$g^{z_0}=2^4=16$、$u_t\,u^{c_0}=9\cdot13^3\equiv9\cdot12=108\equiv16\pmod{23}$。
- $z_1=5+7\cdot8=61\equiv6\pmod{11}$。検証：$g^{z_1}=2^6=64\equiv18$、$u_t\,u^{c_1}=9\cdot13^8\equiv9\cdot2=18\pmod{23}$。
2 つの署名の $u_t$ がどちらも $9$ なので、同じ $t$ が使われたと分かる。thm-sig-schnorr-nonce の 1 から $\alpha=(6-4)(8-3)^{-1}=2\cdot5^{-1}\equiv2\cdot9=18\equiv7\pmod{11}$（$5\cdot9=45\equiv1$）となり、秘密鍵が復元される。
楕円曲線暗号 の定理「乱数の使い回しによる秘密鍵の復元」は、ECDSA 署名で同じことが起きることを示している。また同記事の定理「ECDSA の検証の正しさ」の後半により、ECDSA では署名 $(r,s)$ から同じ文書の別の署名 $(r,N-s)$ が誰にでも作れるので、ECDSA は強い意味で安全でない（BS23 p. 771）。
条件を外した反例
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| thm-sig-hash-sign の、元の方式 $\mathcal S$ の安全性 | $\mathcal S$ を教科書的 RSA 署名、$H_k$ を $\mathcal M$ の恒等写像（衝突がない）とする | $\mathcal S'$ の安全性：$\mathcal S'=\mathcal S$ は thm-sig-rsa-forgery で偽造される |
| thm-sig-hash-sign の衝突困難性 | $H_k(m)=H_k(m')$ となる $m\ne m'$ が母数から計算できる族 | $\mathcal S'$ の安全性：$m$ の署名を問い合わせ、$(m',\sigma)$ を出力すると勝つ |
| def-sig-schnorr の、$t$ を署名ごとに独立に一様に選ぶこと | $t_1=at_0+b$（$a,b$ は既知。同じ $t$ は $a=1$、$b=0$）、ex-sig-schnorr-23 | 秘密鍵 $\alpha$ が公開の値から分からない |
| def-sig-schnorr の、$c$ の計算に $u_t$ を入れること | $c=H(m)$ とする | 安全性：問い合わせなしに偽造できる |
2 行目：$\mathcal S'$ の署名は $H_k(m)$ だけで決まるので、$\mathsf{Ver}(\mathit{pk},H_k(m'),\sigma)=\mathsf{Ver}(\mathit{pk},H_k(m),\sigma)$ は受け入れで、$m'$ は問い合わせていない。3 行目は thm-sig-schnorr-nonce による。4 行目：攻撃者は文書 $m$ と $z\in\mathbb Z/q\mathbb Z$ を任意に選び、$c=H(m)$、$u_t:=g^zu^{-c}$ とおいて $(u_t,z)$ を出力する。$u_t\,u^c=g^z$ なので受け入れられる。$u_t$ を $c$ より後に決められることが偽造を許しており、$c=H(m,u_t)$ では $u_t$ を先に決めなければ $c$ が定まらない。
補足
署名を確かめる人は、使う公開鍵が本当に署名者のものかを別に知る必要がある。実際には、信頼された機関（認証局）が「この公開鍵はこの人のもの」という文に自分の秘密鍵で署名したもの（証明書）を配り、確かめる側は認証局の公開鍵を前もって持っておく（BS23 Chapter 13 の冒頭、p. 527）。署名の安全性の定義は、公開鍵が正しく渡っていることを前提にしている。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
