第2章公開鍵暗号

この章の目標

• 共通鍵暗号の鍵配送問題と、公開鍵暗号・デジタル署名が何を解決するのかを説明できる
• RSA 暗号と RSA 署名の正しさを（平文が $n$ と互いに素でない場合も含めて）証明し、秘密鍵から $n$ が素因数分解できることを示せる
• 教科書的 RSA の危険（準同型性、小さい指数と同報攻撃、共通法）を小さい数で実演し、パディングの役割を説明できる
• ディフィー–ヘルマン鍵共有・エルガマル暗号・DSA の正しさを証明し、安全性がどの計算問題に依存するかを述べられる
• 中間者攻撃と公開鍵基盤の役割、安全性の定義（一方向性・識別不可能性）の考え方を説明できる

前提：第1章、04-algebra 第1章（中国剰余定理・原始根・オイラーの規準）、04-algebra 第2章（巡回群・元の位数）。

初めて訪れる通販サイトにカード番号を送るとき、その通信は暗号化されている。しかし、サイトとあなたは事前に秘密の鍵を打ち合わせていない。見知らぬ相手と、盗聴されている通信路の上で、どうやって秘密を共有するのか――これが公開鍵暗号の解いた問題である。

本章では、RSA 暗号、ディフィー–ヘルマン鍵共有、エルガマル暗号、DSA の仕組みを扱う。それぞれについて、証明できること（正しく復号・検証できること、ある計算ができれば別の計算もできるという帰着）と、仮定していること（素因数分解や離散対数が難しいこと）を区別する。また、教科書に載っている素朴な形（教科書的 RSA）が実際にはどう破れるか、規格がそれをどう防いでいるかを、小さい数で確かめる。

2.1 共通鍵暗号と鍵配送問題

送信者と受信者が同じ鍵 $k$ を共有し、暗号化 $c = E_k(m)$ と復号 $m = D_k(c)$ に使う方式を共通鍵暗号 (symmetric-key encryption) という。最も単純な例は、長さ $\ell$ のビット列 $m$ と鍵 $k$ のビットごとの排他的論理和 $c = m \oplus k$ である。

命題 2.1（ワンタイムパッド, one-time pad）鍵 $K$ を $\lbrace 0, 1 \rbrace^\ell$ から一様に、平文 $M$ と独立に選び、$C = M \oplus K$ とする。このとき $C$ は $\lbrace 0, 1 \rbrace^\ell$ 上の一様分布に従い、$M$ と独立である。

証明. 任意の $m, c$ について $P(C = c, M = m) = P(K = c \oplus m, M = m) = 2^{-\ell}P(M = m)$。$m$ について和をとると $P(C = c) = 2^{-\ell}$ なので、$P(C = c, M = m) = P(C = c)P(M = m)$。$\square$

つまり暗号文からは平文について何の情報も得られない（シャノンの完全秘匿性）。ただし鍵は平文と同じ長さが必要で、一度しか使えない。同じ鍵で 2 つの平文を暗号化すると $c_1 \oplus c_2 = m_1 \oplus m_2$ となり、平文の関係が漏れる。実用の共通鍵暗号は AES（FIPS 197、鍵は 128・192・256 ビット）などで、安全性は証明されていないが、長年の解析に耐えてきたことが根拠である。

共通鍵暗号の弱点は、鍵を事前に安全に共有しなければならないことである（鍵配送問題）。$N$ 人が互いに通信するには $N(N - 1)/2$ 個の鍵が必要になる。1976 年にディフィーとヘルマンは、暗号化の鍵を公開してしまう公開鍵暗号 (public-key cryptography) の考え方を示し、翌 1977 年にリベスト・シャミア・エーデルマンが RSA 暗号を発表した（英国の政府通信本部ではそれ以前に同様の方式が考案されていたことが 1997 年に公表されている）。実際の通信では、公開鍵暗号や鍵共有で共通鍵を共有し、データ本体は高速な共通鍵暗号で暗号化する（ハイブリッド暗号）。

2.2 一方向性関数と落とし戸

定義 2.2（一方向性関数と落とし戸, 非形式的）多項式時間で計算できる関数 $f$ で、ランダムな $x$ に対して $f(x)$ だけから $f(y) = f(x)$ となる $y$ を求めることが、どんな多項式時間のアルゴリズムでも無視できる確率（2.10 節）でしかできないものを一方向性関数 (one-way function) という。ある秘密の情報（落とし戸, trapdoor）を知っていれば逆算が易しくなるものを、落とし戸つき一方向性関数という。

候補は、$(p, q) \mapsto pq$（逆算は素因数分解）、$x \mapsto g^x \bmod p$（逆算は離散対数）、$x \mapsto x^e \bmod n$（落とし戸は $n$ の素因数分解）などである。

一方向性関数の存在は証明されていない（存在を証明すれば P ≠ NP も証明されることになる）。公開鍵暗号の安全性は、「数十年にわたって多くの研究者が攻撃を試みても、効率的な逆算法が見つかっていない」という経験的な根拠に支えられた仮定である。たとえば 2020 年に、829 ビット（10 進 250 桁）の RSA の法（RSA-250）が数体ふるい法で分解されている（第3章）。

2.3 RSA 暗号

$n = pq$（$p, q$ は相異なる素数）に対し、$\lambda(n) = \operatorname{lcm}(p - 1, q - 1)$ とおく（カーマイケル関数）。

定義 2.3（RSA 暗号）

• 鍵生成：相異なる大きな素数 $p, q$ をランダムに選び（第1章 1.8 節）、$n = pq$ とする。$\gcd(e, \lambda(n)) = 1$ となる $e$（$65537$ がよく使われる）を選び、$d = e^{-1} \bmod \lambda(n)$ を拡張ユークリッドの互除法で求める。公開鍵は $(n, e)$、秘密鍵は $d$（と $p, q$）である。
• 暗号化：平文 $m \in \lbrace 0, 1, \dots, n - 1 \rbrace$ に対し $c = m^e \bmod n$。
• 復号：$m = c^d \bmod n$。

定理 2.4（RSA 暗号の正しさ）$p, q$ を相異なる素数、$n = pq$ とし、正の整数 $e, d$ が $ed \equiv 1 \pmod{\lambda(n)}$ をみたすとする。このとき任意の整数 $m$ について $m^{ed} \equiv m \pmod{n}$ である。特に $x \mapsto x^e \bmod n$ は $\mathbb{Z}/n\mathbb{Z}$ 上の全単射で、その逆写像は $x \mapsto x^d \bmod n$ である。

証明. $ed \geq 1$ と $ed \equiv 1$ より $ed = 1 + k\lambda(n)$（$k \geq 0$）と書ける。法 $p$ で考える。$p \nmid m$ なら、フェルマーの小定理と $p - 1 \mid \lambda(n)$ より

$p \mid m$ なら $ed \geq 1$ より両辺とも $0$ と合同である。同様に $m^{ed} \equiv m \pmod{q}$。$p \neq q$ なので中国剰余定理（04-algebra 第1章 定理 1.28）より $m^{ed} \equiv m \pmod{n}$。最後の主張は、$x \mapsto x^e$ と $x \mapsto x^d$ の合成がどちらの順でも恒等写像になることから従う。$\square$

$\lambda(n)$ は $\varphi(n) = (p - 1)(q - 1)$ を割るので、$ed \equiv 1 \pmod{\varphi(n)}$ でもよい（04-algebra 第1章 定理 1.53）。$\lambda(n)$ を使うと $d$ が小さくなり、規格（FIPS 186-5）も $\lambda(n)$ で $d$ を定めている。$\gcd(m, n) \neq 1$ の平文でも正しく復号できるが、そのような $m$ の割合は $1/p + 1/q - 1/n$ で無視できるほど小さく、しかも $\gcd(m, n)$ が $n$ の素因数を与えてしまう。なお $n$ が平方因子をもつと定理は成り立たない（問題 2.2）。

例 2.5 $p = 61$, $q = 53$, $n = 3233$ とすると $\lambda(n) = \operatorname{lcm}(60, 52) = 780$。$e = 17$ とすると $d = 17^{-1} \bmod 780 = 413$（$17 \cdot 413 = 7021 = 9 \cdot 780 + 1$）。$\varphi(n) = 3120$ を使えば第1章の例 1.8 の $d = 2753$ になり、これでも復号できる。平文 $m = 65$ は $c = 65^{17} \bmod 3233 = 2790$ に暗号化され、$2790^{413} \equiv 2790^{2753} \equiv 65$ と復号される（第1章の例 1.10 は中国剰余定理によるこの計算である）。$n$ と互いに素でない $m = 122 = 2 \cdot 61$ も、$c = 1830$ から $1830^{413} \equiv 122$ と正しく戻る（すべて計算機で確認した）。

公開鍵だけから $c$ を復号する問題（RSA 問題）は、$n$ を素因数分解できれば $\lambda(n)$ と $d$ が計算できるので解ける。逆に RSA 問題が素因数分解と同じくらい難しいかどうかは未解決である。一方、秘密鍵 $d$ を求めることは素因数分解と同じくらい難しいことが証明できる。

定理 2.6（秘密鍵から素因数分解へ）$n = pq$（$p, q$ は相異なる奇素数）とし、$\lambda(n)$ の正の倍数 $k$（たとえば $k = ed - 1$）が与えられたとする。$k = 2^s t$（$t$ は奇数）と書く。$a \in \lbrace 1, \dots, n - 1 \rbrace$ を一様に選ぶと、確率 $1/2$ 以上で「$\gcd(a, n) > 1$ である」か「列 $a^t, a^{2t}, \dots, a^{2^s t} \pmod{n}$ に、$x \not\equiv \pm 1$, $x^2 \equiv 1$ となる項 $x$ が現れる」のどちらかが起こり、どちらの場合も $n$ の素因数が得られる。

証明. $\gcd(a, n) > 1$ なら $\gcd(a, n)$ が素因数である。後者の場合は第1章の補題 1.19 より $\gcd(x - 1, n)$ が素因数である。以下 $a$ が単元のとき、後者が確率 $1/2$ 以上で起こることを示せばよい。中国剰余定理より、$a$ が単元全体を一様に動くとき、$a_p = a \bmod p$ と $a_q = a \bmod q$ は独立にそれぞれの単元群を一様に動く。$p - 1 \mid k$ より $(a_p^t)^{2^s} = 1$ なので、$a_p^t$ の位数は $2^\alpha$（$0 \leq \alpha \leq s$）の形で、同様に $a_q^t$ の位数を $2^\beta$ とする。

$\alpha > \beta$ なら、$x = a^{2^{\alpha - 1}t}$ は法 $p$ で位数 2 の元、すなわち $-1$ である（巡回群 $(\mathbb{Z}/p\mathbb{Z})^\times$ で位数 2 の元は $-1$ だけ）。また $2^\beta \mid 2^{\alpha - 1}$ より $x \equiv 1 \pmod{q}$。よって $x \not\equiv \pm 1$, $x^2 \equiv 1 \pmod{n}$ となる。$\alpha < \beta$ でも同様である。したがって $P(\alpha \neq \beta) \geq 1/2$ を示せばよい。

法 $p$ の原始根 $g$ をとり $a_p = g^j$ と書くと、$j$ は $\lbrace 0, \dots, p - 2 \rbrace$ を一様に動く。$p - 1 = 2^v w$（$w$ は奇数）とすると、$p - 1 \mid k$ より $w \mid t$ で、$t/w$ は奇数である。04-algebra 第2章の命題 2.19(3) より $g^{jt}$ の位数は $(p - 1)/\gcd(p - 1, jt) = 2^v/\gcd(2^v, j)$。よって $\alpha = v$ となるのは $j$ が奇数のときに限り、その確率はちょうど $1/2$ である。ゆえにどの値 $c$ についても $P(\alpha = c) \leq 1/2$ で、独立性より

$\square$

この手順を繰り返せば、$r$ 回で失敗する確率は $2^{-r}$ 以下である。逆に素因数分解ができれば $d$ は計算できるので、$d$ を知ることと素因数分解を知ることは（確率的多項式時間で）同値である。

例 2.7 $n = 3233$, $e = 17$, $d = 2753$ では $k = 46800 = 2^4 \cdot 2925$。$a = 2$ では列が $1514, 3232, 1, 1, 1$ となり、$-1 \equiv 3232$ を経て $1$ になるので失敗する。$a = 3$ では $2256, 794, 1, 1, 1$ で、$x = 794$ は $1$ の非自明な平方根であり、$\gcd(793, 3233) = 61$ を得る。

import math
import random

def factor_from_d(n, e, d, rng):
    """RSA の公開鍵 (n, e) と秘密鍵 d から n の素因数を 1 つ求める。"""
    k = e * d - 1                    # λ(n) の倍数
    s, t = 0, k
    while t % 2 == 0:
        s, t = s + 1, t // 2
    while True:
        a = rng.randrange(2, n - 1)
        g = math.gcd(a, n)
        if g > 1:
            return g                 # a がたまたま n と共通因数をもった
        x = pow(a, t, n)
        for _ in range(s):
            y = x * x % n
            if y == 1 and x != 1 and x != n - 1:
                return math.gcd(x - 1, n)   # 1 の非自明な平方根 x から因数を得る
            x = y

rng = random.Random(0)
p = factor_from_d(3233, 17, 2753, rng)
print(p, 3233 // p)

実行結果は 53 61 である。2048 ビットの $n$ でも一瞬で終わる。

鍵の長さについて、米国の NIST SP 800-57 Part 1 Rev. 5（2020 年）は、既知の最良の攻撃（第3章の数体ふるい法）の計算量をもとに次の対応を示している（表 2 の一部。全体は第3章 3.11 節）。

2.4 RSA 署名

公開鍵暗号の役割を入れ替えると、デジタル署名ができる。秘密鍵の持ち主だけが作れて、誰でも公開鍵で検証できるデータである。

定義 2.8（RSA 署名）鍵は RSA 暗号と同じとする。メッセージ（のハッシュ値を符号化した整数）$m$ に対し、署名を $s = m^d \bmod n$ とする。検証者は $s^e \equiv m \pmod{n}$ が成り立てば受理する。

正しい署名が受理されることは定理 2.4 から従う。しかし、ハッシュ関数を通さない教科書的 RSA 署名は偽造できる。

例 2.9 (1) 好きな $s$ を選んで $m = s^e \bmod n$ とおけば、$(m, s)$ は正しい署名つきメッセージになる（$n = 3233$, $e = 17$ で $s = 1000$ なら $m = 175$）。攻撃者が $m$ を自由に選べない「存在的偽造」だが、2.10 節の安全性の定義は満たさない。(2) $s_1, s_2$ が $m_1, m_2$ の署名なら、$s_1 s_2 \bmod n$ は $m_1 m_2 \bmod n$ の署名である。

実際の RSA 署名では、メッセージをハッシュ関数で固定長の値にし、乱数を混ぜて $n$ とほぼ同じ長さに符号化してから $d$ 乗する（RSA-PSS。2.5 節）。

2.5 教科書的 RSA の危険とパディング

定義 2.3 のままの RSA（教科書的 RSA, textbook RSA）には、次の弱点がある。

(1) 決定的である. 同じ平文はいつも同じ暗号文になる。平文の候補が少なければ（「賛成」か「反対」など）、攻撃者は候補をすべて公開鍵で暗号化して比べればよい（問題 2.8）。

(2) 準同型性. $(m_1 m_2)^e = m_1^e m_2^e$ より、暗号文の積は平文の積の暗号文である。これを使うと、「$c$ そのもの以外なら何でも復号して返す」サーバーから $c$ の平文を引き出せる（選択暗号文攻撃）。

例 2.10 $n = 3233$, $e = 17$ で $c = 2790$ を解読したい。乱数 $r = 1000$ を選び、$c' = c \cdot r^{17} \bmod n = 2790 \cdot 175 \bmod 3233 = 67$ を復号させると、$m' = 340$ が返る。$m' \equiv mr$ なので、$r^{-1} \bmod 3233 = 333$ を掛けて $m = 340 \cdot 333 \bmod 3233 = 65$ を得る。サーバーには $c$ と無関係に見える $67$ しか見えていない。

(3) 小さい指数. $e = 3$ で $m < n^{1/3}$ なら $m^3 < n$ なので、$c = m^3$ は整数として成り立ち、$c$ の整数の 3 乗根で $m$ が求まる（$n = 7387$ で $m = 19$ なら $c = 6859 = 19^3$）。$e = 3$ で 2048 ビットの $n$ を使い、128 ビットの共通鍵をそのまま暗号化すると、まさにこの状況になる（署名の規格 FIPS 186-5 は $e$ を $2^{16} < e < 2^{256}$ の奇数に限っているが、本質的な対策は後で述べるパディングである）。

命題 2.11（ハスタッドの同報攻撃, Håstad's broadcast attack）同じ平文 $m$ を、公開指数 $e$ が共通でどの 2 つも互いに素な $e$ 個の法 $n_1, \dots, n_e$ で暗号化した暗号文 $c_i = m^e \bmod n_i$ が得られたとする（$0 \leq m < \min_i n_i$）。中国剰余定理で $x \equiv c_i \pmod{n_i}$（$0 \leq x < N = n_1 \cdots n_e$）を求めると $x = m^e$ であり、$m$ は $x$ の整数の $e$ 乗根として求まる。

証明. $m^e \equiv c_i \pmod{n_i}$ がすべての $i$ で成り立ち、$0 \leq m^e < n_1 \cdots n_e = N$ なので、中国剰余定理の一意性より $x = m^e$。$\square$

例 2.12 $e = 3$、法を $n_1 = 47 \cdot 59 = 2773$, $n_2 = 53 \cdot 71 = 3763$, $n_3 = 83 \cdot 89 = 7387$（どれも $3 \nmid \varphi(n_i)$）とし、同じ $m = 2026$ を送る。

def crt(residues, moduli):
    """法がどの 2 つも互いに素なときの中国剰余定理。0 以上 N 未満の解と N を返す。"""
    N = 1
    for m in moduli:
        N *= m
    x = 0
    for r, m in zip(residues, moduli):
        Ni = N // m
        x += r * Ni * pow(Ni, -1, m)
    return x % N, N

def iroot(k, x):
    """k 乗が x 以下になる最大の整数を二分探索で求める。"""
    lo, hi = 0, 1 << (x.bit_length() // k + 1)
    while lo < hi:
        mid = (lo + hi + 1) // 2
        if mid ** k <= x:
            lo = mid
        else:
            hi = mid - 1
    return lo

ns = [47 * 59, 53 * 71, 83 * 89]   # 3 人の受信者の法（公開指数はどれも e = 3）
cs = [pow(2026, 3, n) for n in ns] # 盗聴者が集めた 3 つの暗号文
x, N = crt(cs, ns)
print(cs, x, iroot(3, x))

実行結果は [1864, 1622, 3199] 8316073576 2026 で、$x = 2026^3$ から平文が復元される。素因数分解は一切していない。

(4) 共通法. 同じ $n$ を複数の利用者で共有し、公開指数 $e_1, e_2$ だけを変えるのは危険である。定理 2.6 により、自分の $(e_1, d_1)$ を知る利用者は $n$ を素因数分解でき、他人の $d_2$ も計算できる。外部の攻撃者でも、同じ $m$ が $\gcd(e_1, e_2) = 1$ の 2 つの指数で暗号化されていれば、$ue_1 + ve_2 = 1$ となる整数 $u, v$ をとって $c_1^u c_2^v \equiv m^{ue_1 + ve_2} = m$ と平文を得る（負の指数は法 $n$ の逆元で計算する。問題 2.3）。

これらの弱点を防ぐのがパディング（平文の符号化）である。OAEP（ベラーレ–ロガウェイ、1994 年）の考え方を示す。ハッシュ関数 $G, H$ と乱数 $r$ を使い、

として、ビット列 $X \mathbin{\Vert} Y$（$\mathbin{\Vert}$ は連結）を整数とみて $e$ 乗する。復号では $X, Y$ から $r = Y \oplus H(X)$、$m \mathbin{\Vert} z = X \oplus G(r)$ を計算し、$z = 0^{k_1}$ でなければ拒否する。乱数 $r$ により暗号化は確率的になり（(1) の対策）、符号化は $n$ とほぼ同じ長さになり（(3) の対策）、でたらめに作った暗号文はほぼ確実に拒否されるので積の関係も使えない（(2) の対策）。RSA-OAEP は、ハッシュ関数を理想化したモデル（ランダムオラクルモデル）のもとで、RSA 問題が難しいと仮定すれば選択暗号文攻撃に対して安全であることが証明されている。署名用には、乱数（ソルト）とハッシュ値から符号化を作る PSS が同様の役割を果たす。細部は PKCS #1（RFC 8017）で規定されている。

2.6 ディフィー–ヘルマン鍵共有

公開の通信路だけで共通鍵を作る方法である。以下、$p$ を素数、$q$ を $p - 1$ を割る素数、$g \in (\mathbb{Z}/p\mathbb{Z})^\times$ を位数 $q$ の元とし、$G = \langle g \rangle$ とおく（群 $G$ の位数は $q$）。

定義 2.13（ディフィー–ヘルマン鍵共有, Diffie–Hellman key exchange）$(p, q, g)$ は公開されているとする。アリスは $a \in \lbrace 1, \dots, q - 1 \rbrace$ をランダムに選んで $A = g^a \bmod p$ を、ボブは $b$ を選んで $B = g^b \bmod p$ を送る。アリスは $K = B^a \bmod p$、ボブは $K = A^b \bmod p$ を計算する。

$B^a = g^{ab} = A^b$ なので、2 人は同じ $K$ を得る。盗聴者が見るのは $p, q, g, A, B$ だけである。

例 2.14 $p = 467 = 2 \cdot 233 + 1$, $q = 233$（素数）, $g = 4 = 2^2$（位数 $233$）とする。$a = 153$, $b = 197$ なら $A = 207$, $B = 97$ で、$K = 97^{153} \equiv 207^{197} \equiv 193 \pmod{467}$。

定義 2.15（離散対数に関する問題）$G = \langle g \rangle$ を位数 $q$ の巡回群とする。

• 離散対数問題 (DLP)：$g^x$ から $x \bmod q$ を求める。
• 計算ディフィー–ヘルマン問題 (CDH)：$g^x, g^y$ から $g^{xy}$ を求める。
• 判定ディフィー–ヘルマン問題 (DDH)：$(g^x, g^y, g^{xy})$ と $(g^x, g^y, g^z)$（$x, y, z$ は一様ランダム）を見分ける。

DLP が解ければ CDH が解け（$x$ を求めて $(g^y)^x$）、CDH が解ければ DDH が解ける。逆向きは一般には知られていない。DH 鍵共有を盗聴から守るには少なくとも CDH が難しくなければならず、共有した $K$ を「ランダムな値と見分けがつかない」鍵として使うには DDH の困難さが要る。群の選び方は重要である。

命題 2.16 $p$ を奇素数、$g$ を法 $p$ の原始根とする（$G = (\mathbb{Z}/p\mathbb{Z})^\times$ 全体）。このとき $g^a, g^b$ から $g^{ab}$ のルジャンドル記号が計算でき、DDH は易しい。

証明. オイラーの規準（04-algebra 第1章 定理 1.49）と $g^{(p-1)/2} \equiv -1$（$g$ の位数が $p - 1$ だから）より、$\left(\frac{g^x}{p}\right) \equiv g^{x(p-1)/2} \equiv (-1)^x$。よって $\left(\frac{g^{ab}}{p}\right) = (-1)^{ab}$ は、$\left(\frac{g^a}{p}\right) = \left(\frac{g^b}{p}\right) = -1$ のときだけ $-1$ である。ルジャンドル記号は反復二乗法で計算できる。3 つ目の成分のルジャンドル記号がこの予測と一致するかを調べれば、本物の組は必ず一致し、ランダムな $g^z$ は確率 $1/2$ でしか一致しないので、見分けられる。$\square$

そこで実用では、$q$ が十分大きい素数となる部分群（例 2.14 のように安全素数 $p = 2q + 1$ の平方剰余の群など）を使う。群の位数が小さい素因数だけの積だと、離散対数はポーリッヒ–ヘルマン法で易しくなる（第3章）。SP 800-57 は、112 ビットの安全性に $p$ を 2048 ビット、$q$ を 224 ビットとする組を対応させている。

2.7 エルガマル暗号

DH 鍵共有の片方を固定の公開鍵にすると、公開鍵暗号ができる（エルガマル、1985 年）。

定義 2.17（エルガマル暗号, ElGamal encryption）群 $G = \langle g \rangle$（位数 $q$）は 2.6 節のとおりとする。秘密鍵は $x \in \lbrace 1, \dots, q - 1 \rbrace$、公開鍵は $h = g^x$。平文 $m \in G$ に対し、$k \in \lbrace 1, \dots, q - 1 \rbrace$ を暗号化のたびにランダムに選び、暗号文を $(c_1, c_2) = (g^k, mh^k)$ とする。復号は $m = c_2 (c_1^x)^{-1}$。

命題 2.18 (1) エルガマル暗号は正しく復号できる。(2) 公開鍵と暗号文から平文をつねに求めるアルゴリズムと、CDH をつねに解くアルゴリズムは、一方から他方を多項式時間で構成できる。

証明. (1) $c_1^x = g^{kx} = h^k$ なので $c_2(c_1^x)^{-1} = m$。(2) CDH が解ければ、$h = g^x$ と $c_1 = g^k$ から $h^k = g^{xk}$ を求めて $m = c_2(h^k)^{-1}$。逆に復号アルゴリズムがあれば、$g^x, g^y$ に対し公開鍵 $h = g^x$、暗号文 $(g^y, 1)$ を与えると $m = (g^{xy})^{-1}$ が返るので、$g^{xy} = m^{-1}$。$\square$

例 2.19 例 2.14 の群で $x = 127$ とすると $h = 4^{127} \bmod 467 = 145$。$m = 100 = 10^2$（平方剰余なので $G$ の元）を $k = 213$ で暗号化すると $(c_1, c_2) = (374, 122)$。復号では $c_1^x = 374^{127} \equiv 160$ で、$122 \cdot 160^{-1} \equiv 100 \pmod{467}$。

エルガマル暗号は乱数 $k$ を使うので確率的である。一方、$(c_1, tc_2)$ は $tm$ の暗号文になる（準同型性）ので、選択暗号文攻撃には弱い。また $k$ を使い回すと平文の比が漏れる（問題 2.5）。実用では DH 鍵共有で共通鍵を作り、データは共通鍵暗号で暗号化する方式が主流である。

2.8 デジタル署名アルゴリズム（DSA）

DSA は、エルガマルの署名方式を素数位数の部分群に移して短くした方式で、米国の規格 FIPS 186 として 1994 年に制定された。

定義 2.20（DSA）公開パラメータを素数 $p, q$（$q \mid p - 1$）と位数 $q$ の元 $g \in (\mathbb{Z}/p\mathbb{Z})^\times$ とする。秘密鍵は $x \in \lbrace 1, \dots, q - 1 \rbrace$、公開鍵は $y = g^x \bmod p$。$h$ をメッセージのハッシュ値（$q$ のビット長に切り詰めた整数）とする。

• 署名：秘密の乱数 $k \in \lbrace 1, \dots, q - 1 \rbrace$ を署名のたびに選び、$r = (g^k \bmod p) \bmod q$, $s = k^{-1}(h + xr) \bmod q$ とする。$r = 0$ または $s = 0$ なら $k$ を選び直す。署名は $(r, s)$。
• 検証：$0 < r < q$, $0 < s < q$ を確かめ、$w = s^{-1} \bmod q$, $u_1 = hw \bmod q$, $u_2 = rw \bmod q$, $v = (g^{u_1}y^{u_2} \bmod p) \bmod q$ とし、$v = r$ なら受理する。

定理 2.21（DSA の正しさ）正しく作られた署名は受理される。

証明. $s \not\equiv 0$ なので $w$ が定まり、$s \equiv k^{-1}(h + xr)$ より $h + xr \equiv sk \pmod q$。よって $u_1 + xu_2 \equiv w(h + xr) \equiv wsk \equiv k \pmod{q}$。$g$ の位数は $q$ なので $g^{u_1}y^{u_2} = g^{u_1 + xu_2} = g^k$ が法 $p$ で成り立ち、$v = (g^k \bmod p) \bmod q = r$。$\square$

例 2.22 $(p, q, g) = (467, 233, 4)$, $x = 127$, $y = 145$, $h = 100$, $k = 51$ とする。$g^k \bmod p = 289$ より $r = 289 \bmod 233 = 56$。$k^{-1} \bmod 233 = 32$ で、$s = 32 \cdot (100 + 127 \cdot 56) \bmod 233 = 32 \cdot 222 \bmod 233 = 114$。検証では $w = 114^{-1} \bmod 233 = 186$, $u_1 = 193$, $u_2 = 164$ で、$4^{193} \cdot 145^{164} \equiv 243 \cdot 55 \equiv 289 \pmod{467}$ より $v = 56 = r$。

$k$ が漏れたり、2 つの署名で同じ $k$ を使ったりすると、秘密鍵 $x$ が計算されてしまう（問題 2.6。楕円曲線版の ECDSA での詳しい分析は第4章）。なお FIPS 186-5（2023 年 2 月）では、DSA は署名の生成には承認されなくなり（この規格の実施日より前に作られた署名の検証には使える）、承認される署名方式は RSA・ECDSA・EdDSA の 3 つになった。

2.9 中間者攻撃と公開鍵基盤

DH 鍵共有の $A, B$ には「誰が送ったか」の情報がない。通信路を書き換えられる攻撃者マロリーは、アリスの $A$ を自分の $Z = g^z$ にすり替えてボブに渡し、ボブの $B$ も $Z$ にすり替えてアリスに渡す。アリスは $g^{az}$ を、ボブは $g^{bz}$ を「共有した鍵」と思い込むが、マロリーは両方を計算でき、2 人の通信を復号・改ざんして中継できる（中間者攻撃, man-in-the-middle attack。問題 2.4）。数学的にはどの計算問題も解いていない。

防ぐには、受け取った公開鍵が本当に相手のものかを確かめる必要がある。公開鍵基盤 (PKI) では、認証局 (CA) が「この公開鍵はこのドメイン名の持ち主のもの」という文書（証明書）にデジタル署名する。ブラウザや OS は少数のルート認証局の公開鍵をあらかじめ信頼しており、証明書の署名の連鎖をたどって検証する。TLS 1.3 では、サーバーは使い捨ての DH（または楕円曲線 DH）の値を送り、証明書の秘密鍵でそれまでのやりとり全体に署名する。すり替えれば署名の検証に失敗する。使い捨ての DH 鍵を使うので、後でサーバーの秘密鍵が漏れても過去の通信は解読されない（前方秘匿性, forward secrecy）。

2.10 安全性の定義

「安全」を数学的に定義すると、証明できることとできないことがはっきりする。攻撃者は確率的多項式時間のアルゴリズムとし、鍵の長さを表すセキュリティパラメータ $\kappa$（カーマイケル関数 $\lambda(n)$ と区別するため $\kappa$ と書く）について、任意の多項式の逆数より速く $0$ に近づく関数を無視できる (negligible) という。

• 一方向性（OW-CPA）：公開鍵とランダムな平文の暗号文から、平文全体を求められる確率が無視できる。
• 識別不可能性（IND-CPA）：次のゲームで攻撃者が勝つ確率と $1/2$ の差（優位）が無視できる。(i) 鍵を生成し、攻撃者に公開鍵を渡す。(ii) 攻撃者が同じ長さの平文 $m_0, m_1$ を選ぶ。(iii) 一様ランダムな $b \in \lbrace 0, 1 \rbrace$ について $m_b$ の暗号文を渡す。(iv) 攻撃者は $b$ を当てれば勝ち。
• IND-CCA2：IND-CPA のゲームで、攻撃者は (iii) の暗号文以外なら何でも復号してもらえる。

IND-CPA は「暗号文から平文の部分的な情報（偶奇や大小関係など）さえ漏れない」ことを表す、一方向性よりずっと強い要求である。

命題 2.23 暗号化が決定的な（乱数を使わない）公開鍵暗号は、IND-CPA 安全ではない。

証明. 攻撃者は相異なる $m_0, m_1$ を選び、受け取った暗号文 $c$ と、自分で公開鍵を使って計算した $m_0$ の暗号文を比べ、一致すれば $b = 0$、しなければ $b = 1$ と答える。復号できる方式では $m_0 \neq m_1$ の暗号文は異なるので、つねに勝つ。$\square$

したがって教科書的 RSA は IND-CPA 安全でない。準同型性をもつ方式（教科書的 RSA、エルガマル暗号）は、例 2.10 のように問題の暗号文を変形して復号してもらえるので IND-CCA2 安全でない。一方、次のことが仮定のもとで証明されている（本書では主張のみ）：素数位数の群でのエルガマル暗号は DDH 仮定のもとで IND-CPA 安全である。RSA-OAEP はランダムオラクルモデルと RSA 仮定のもとで IND-CCA2 安全である。署名については「好きなメッセージに署名してもらえても、新しいメッセージの署名を作れない」（EUF-CMA）が標準的な定義で、教科書的 RSA 署名は例 2.9 により満たさないが、RSA-PSS はランダムオラクルモデルと RSA 仮定のもとで満たす。

これらの証明はどれも「攻撃者がいれば、仮定した難しい問題を解くアルゴリズムが作れる」という帰着の形をしている。証明された安全性とは、仮定が正しい限りでの安全性である。

まとめ

• 共通鍵暗号には鍵配送問題がある。ワンタイムパッドは完全秘匿だが、鍵の使い回しで破れる。
• 公開鍵暗号の安全性は、一方向性関数の存在という未証明の仮定と、長年の解析という経験的根拠に依存する。
• RSA の正しさ $m^{ed} \equiv m \pmod{pq}$（$ed \equiv 1 \bmod \lambda(n)$）は、$\gcd(m, n) \neq 1$ の場合も含めて成り立つ。秘密鍵 $d$ を知れば $n$ は確率的に素因数分解できる。
• 教科書的 RSA は決定的で準同型性をもち、小さい指数・同報・共通法の攻撃に弱い。OAEP・PSS のパディングで防ぐ。
• DH 鍵共有・エルガマル暗号・DSA は素数位数の部分群で使う。DH とエルガマルの安全性は CDH・DDH の困難さに、DSA は少なくとも離散対数の困難さに依存する。原始根で生成される群全体ではルジャンドル記号が漏れる。
• DSA の秘密の乱数 $k$ の再利用は秘密鍵を漏らす。
• 認証のない鍵共有は中間者攻撃に弱く、証明書と公開鍵基盤で公開鍵の持ち主を保証する。
• 安全性の定義（OW-CPA, IND-CPA, IND-CCA2, EUF-CMA）と帰着による証明は、仮定のもとでの安全性を与える。推奨鍵長は規格とともに変わる。

演習問題