第4回公開鍵暗号1（RSA暗号・分散署名・準同型暗号）【連載：暗号技術の基礎を学ぶ】

Last updated at 2025-12-05Posted at 2025-12-05

この記事は、 CAMPFIRE Advent Calendar 2025 の6日目の記事 の一部です。連載記事の全体は、「第0回　暗号技術の基礎を学ぶ連載記事一覧」を参照してください。

前回までに学んだ共通鍵暗号、ハッシュ関数、メッセージ認証コードは、すべて暗号化と復号に同じ鍵を使用する鍵が対称な暗号方式でした。これらの暗号は高速で実用的ですが、鍵の配送という根本的な問題を抱えています。通信相手と事前に秘密の鍵を安全に共有するには、どのような方法があるでしょうか？

この問題を解決するのが 公開鍵暗号 です。1976年、Whitfield DiffieとMartin Hellmanが提案したこの革新的な暗号方式は、暗号化用の公開鍵と復号用の秘密鍵を分離することで、鍵の配送問題を根本的に解決しました。誰でも知ることができる公開鍵で暗号化し、所有者のみが知る秘密鍵で復号するという非対称性により、事前の秘密共有なしに安全な通信が可能になったのです。

今回の記事では、公開鍵暗号の代表例である RSA暗号 を中心に、署名への応用、分散署名、準同型暗号まで学んでいきます。
特に、現実のRSA暗号においては、重要な安全性担保のために単純なRSA問題だけではない工夫がされている点は非常に重要なポイントになります。

※この記事は、文章案の作成や表現の調整、内容の検証や修正のサポート等に生成AIを利用しています。

4.1 公開鍵暗号の基本原理
 4.2 RSA暗号の動作原理の理解
 4.3 RSA暗号の数学的基盤
 4.4 RSA暗号の実装
 4.5 RSA暗号の安全性向上
 4.6 RSA署名
 4.7 分散署名
 4.8 準同型暗号
 4.9 準同型暗号の実践的応用
 4.10 実世界での活用
 4.11 まとめ

4.1 公開鍵暗号の基本原理

公開鍵暗号の重要な点は、暗号化と復号に異なる鍵を使用する 非対称性 にあります。この仕組みを理解するために、まず公開鍵暗号の基本的な構成要素を見てみましょう。

公開鍵暗号は3つのアルゴリズムで構成されます。まず 鍵生成アルゴリズム で公開鍵 $\text{pk}$ と秘密鍵 $\text{sk}$ のペアを生成し、 暗号化アルゴリズム で公開鍵を使って平文 $m$ を暗号文 $c$ に変換し、最後に 復号アルゴリズム で秘密鍵を使って暗号文を元の平文に戻します。重要なのは、すべての平文 $m$ に対して $\text{Dec}(\text{sk}, \text{Enc}(\text{pk}, m)) = m$ が成り立つことです。

この非対称性により、誰でも公開鍵を使って暗号化できますが、復号は秘密鍵を持つ者だけが可能になります。これが鍵の配送問題を解決する鍵となります。

4.2 RSA暗号の動作原理の理解

公開鍵暗号の代表格であるRSA暗号が、実際にどのように動作するのかを見ていきます。まずは具体的な数値例を使って、鍵生成から暗号化、復号までの流れを体験することで、RSA暗号の本質を理解します。

小さな数値で理解するRSA暗号

実際のRSA暗号では安全性のため、数百ビットの巨大な数を使いますが、ここでは理解しやすいように小さな数で説明します。

ステップ1: 鍵の生成

AliceがRSA暗号を使うために、まず鍵のペアを生成します。

2つの素数を選ぶ: $p = 61$、$q = 53$ を選びます
それらを掛け合わせる: $n = p \times q = 61 \times 53 = 3233$ を計算します
トーシェント関数を計算: $\phi(n) = (p-1) \times (q-1) = 60 \times 52 = 3120$ を計算します
公開指数を選ぶ: $e = 17$ を選びます（$\phi(n)$ と互いに素な数）
秘密指数を計算: $d \times e \equiv 1 \pmod{\phi(n)}$ を満たす $d$ を求めると $d = 2753$ が得られます

公開鍵: $(n, e) = (3233, 17)$ （誰でもアクセス可能）
秘密鍵: $d = 2753$ （Aliceだけが知っている）

ステップ2: 暗号化

BobがAliceに「$65$」というメッセージを送りたいとします。BobはAliceの公開鍵 $(n, e) = (3233, 17)$ を使って暗号化します。

\begin{align}
c &= m^e \bmod n \\
&= 65^{17} \bmod 3233 \\
&= 2790
\end{align}

Bobは暗号文「$2790$」をAliceに送信します。この暗号文を見ても、秘密鍵を知らない第三者は元のメッセージを復元できません。

ステップ3: 復号

Aliceは受け取った暗号文「$2790$」を、自分の秘密鍵 $d = 2753$ を使って復号します。

\begin{align}
m &= c^d \bmod n \\
&= 2790^{2753} \bmod 3233 \\
&= 65
\end{align}

元のメッセージ「$65$」が正しく復元されました。

RSA暗号がなぜ動くのか？

ここまでで簡素化してRSA暗号が動作することを見てきました。ですが、これがなぜ正しく動作するのでしょうか？

なぜ公開鍵で暗号化した暗号文が秘密鍵で復号できるのか？
なぜ秘密鍵なしでは復号できないのか？
なぜ素数を選ぶのか？
トーシェント関数 $\phi(n)$ とは何か？
秘密指数 $d$ はどうやって求めるのか？

これらの疑問を解決するためには、RSA暗号を支える数学的な背景を理解する必要があります。ここから、群論、オイラーの定理、素因数分解問題といった数学的な背景を詳しく学んでいきます。

RSA暗号の3つの重要な性質

次へ進む前に、RSA暗号の中心となる3つの性質を確認しておきます。

非対称性: 暗号化（公開鍵使用）と復号（秘密鍵使用）で異なる鍵を使う
一方向性: 公開鍵での暗号化は簡単だが、秘密鍵なしでの復号は極めて困難
数学的保証: 秘密鍵なしの復号の困難性は、数学的に証明可能

これらの性質がどのように実現されているのか、数学的な視点から掘り下げていきます。

4.3 RSA暗号の数学的基盤

ここまでで、RSA暗号の動作を見てきましたが、ここからはその背後にある数学的理論を詳しく学んでいきます。群論やオイラーの定理といった古典的な数学が、どのようにして現代の暗号技術を支えているのかを理解しましょう。

このセクション（4.3節）と次の4.4節では、より詳細な数学的背景を説明していきます。RSA暗号の数学的背景や詳細な高速化技術等に興味がない場合は、4.5節以降に進むこともできます。

群と剰余環

RSA暗号を理解するためには、まず群と 剰余環 の理論を学ぶ必要があります。

群の基本概念

群：集合 $G$ とその上の二項演算 $\cdot$ の組 $(G, \cdot)$ が、以下を満たすとき、これを群と呼びます。

結合律：任意の $a, b, c \in G$ に対して $(a \cdot b) \cdot c = a \cdot (b \cdot c)$
単位元の存在：ある元 $e \in G$ が存在し、任意の $a \in G$ に対して $e \cdot a = a \cdot e = a$
逆元の存在：任意の $a \in G$ に対して、ある元 $a^{-1} \in G$ が存在し、$a \cdot a^{-1} = a^{-1} \cdot a = e$

可換群（アーベル群）：さらに群の任意の要素 $a, b \in G$ に対して $a \cdot b = b \cdot a$ が成り立つとき、$G$ を可換群といいます。

部分群：群 $G$ の部分集合 $H$ が $G$ と同じ演算で群をなすとき、$H$ を $G$ の部分群といいます。

群の位数：有限群 $G$ の要素の個数 $|G|$ を群の位数といいます。なお、有限群とは、その集合の要素が有限個の群です。

剰余環

剰余環 $\mathbb{Z}_n$：整数 $n > 1$ に対して、剰余環 $\mathbb{Z}_n$ は以下のように定義されます。

$$\mathbb{Z}_n = {0, 1, 2, \ldots, n-1}$$

この集合上で加法と乗法を以下のように定義します。

加法：$a + b \pmod{n}$
乗法：$a \cdot b \pmod{n}$

環の性質

加法について可換群をなす
乗法について結合律と交換律が成り立つ
分配律：$a \cdot (b + c) = a \cdot b + a \cdot c$
零元は $0$、単位元は $1$

オイラーのトーシェント関数とその性質

オイラーのトーシェント関数 $\phi(n)$ は、$n$ 以下で $n$ と互いに素な正整数の個数を表します。

$$\phi(n) = |{a \in {1, 2, \ldots, n} \mid \gcd(a, n) = 1}|$$

重要な性質

素数 $p$ に対して、$\phi(p) = p-1$
互いに素な正整数 $m, n$ に対して
$$\phi(mn) = \phi(m)\phi(n)\ (乗法的性質)$$
素数 $p$ と正整数 $k$ に対して
$$\phi(p^k) = p^k - p^{k-1} = p^k(1-1/p)$$
一般に、$n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$ の素因数分解に対して
$$\phi(n) = n \prod_{i=1}^k \left(1 - \frac{1}{p_i}\right)$$

ユークリッドの互除法と拡張ユークリッド互除法

RSA暗号の秘密鍵を計算するためには、モジュラ逆元を求める必要があります。その基盤となるのが ユークリッドの互除法 と 拡張ユークリッド互除法 です。

ユークリッドの互除法

ユークリッドの互除法は、2つの整数の最大公約数（$\gcd$）を効率的に計算するアルゴリズムです。

アルゴリズム：整数 $a, b$ （$a \geq b > 0$）に対して、

\begin{align}
a &= q_1 b + r_1 \quad (0 \leq r_1 < b) \\
b &= q_2 r_1 + r_2 \quad (0 \leq r_2 < r_1) \\
r_1 &= q_3 r_2 + r_3 \quad (0 \leq r_3 < r_2) \\
&\vdots \\
r_{n-2} &= q_n r_{n-1} + r_n \quad (0 \leq r_n < r_{n-1}) \\
r_{n-1} &= q_{n+1} r_n + 0
\end{align}

このとき、$\gcd(a, b) = r_n$ （最後の$0$でない剰余）となります。

例：$\gcd(3120, 17)$ を計算してみましょう（RSA暗号の例で使った数値です）。

\begin{align}
3120 &= 183 \times 17 + 9 \\
17 &= 1 \times 9 + 8 \\
9 &= 1 \times 8 + 1 \\
8 &= 8 \times 1 + 0
\end{align}

したがって、$\gcd(3120, 17) = 1$ です。

拡張ユークリッド互除法

拡張ユークリッド互除法は、ユークリッドの互除法を拡張して、 ベズーの等式 を満たす整数 $x, y$ を求めるアルゴリズムです。

ベズーの等式：整数 $a, b$ に対して、$\gcd(a, b) = d$ とすると、

$$ax + by = d$$

を満たす整数 $x, y$ が存在します。

アルゴリズムの考え方：ユークリッドの互除法の各ステップを逆にたどることで、$x, y$ を求めます。

具体例：$17x \equiv 1 \pmod{3120}$ を満たす $x$ （すなわち、$e = 17$ のモジュラ逆元 $d$）を求めてみましょう。

これは $17x + 3120y = 1$ を満たす整数 $x$ を求める問題です。

ユークリッドの互除法の各ステップを変形します：

\begin{align}
1 &= 9 - 1 \times 8 \\
&= 9 - 1 \times (17 - 1 \times 9) \\
&= 2 \times 9 - 1 \times 17 \\
&= 2 \times (3120 - 183 \times 17) - 1 \times 17 \\
&= 2 \times 3120 - 367 \times 17
\end{align}

したがって、$17 \times (-367) + 3120 \times 2 = 1$ となります。

$x = -367 \equiv -367 + 3120 = 2753 \pmod{3120}$ なので、$d = 2753$ が秘密鍵となります。

アルゴリズムの実装

拡張ユークリッド互除法は以下のように実装できます。

入力：整数 $a, b$ （$a \geq b > 0$）
出力：$\gcd(a, b)$ と、$ax + by = \gcd(a, b)$ を満たす整数 $x, y$

ExtendedGCD(a, b):
    if b = 0:
        return (a, 1, 0)
    else:
        (d, x′, y′) = ExtendedGCD(b, a mod b)
        x = y′
        y = x′ - ⌊a/b⌋ × y′
        return (d, x, y)

計算量：ユークリッドの互除法と同様に、$O(\log \min(a, b))$ の時間で計算できます。これは非常に効率的なアルゴリズムです。（$\min(a, b)$ は $a, b$のうちより小さい値）

モジュラ逆元の計算

RSA暗号では、$ed \equiv 1 \pmod{\phi(n)}$ を満たす $d$ を求める必要があります。これは拡張ユークリッド互除法を使って効率的に計算できます。

$\gcd(e, \phi(n)) = 1$ のとき、拡張ユークリッド互除法により $ex + \phi(n)y = 1$ を満たす $x, y$ が求まります。この $x$ を $\phi(n)$ で正規化したものが求める $d$ です。

$$d = x \bmod \phi(n)$$

この計算は多項式時間で実行可能であり、RSA暗号の鍵生成を実用的にしています。

ラグランジュの定理と乗法群

ラグランジュの定理：有限群 $G$ の任意の部分群 $H$ の位数は、$G$ の位数の約数です。

この定理から、有限群 $G$ の任意の元 $g$ の位数は、$G$ の位数の約数であることが従います。

乗法群と位数

乗法群：剰余環 $\mathbb{Z}_n$ の乗法群 $\mathbb{Z}_n^*$ は以下のように定義されます。

$$\mathbb{Z}_n^* = {a \in \mathbb{Z}_n \mid \gcd(a, n) = 1}$$

性質

$\mathbb{Z}_n^*$ は乗法について群をなす
位数は $\phi(n)$（オイラーのトーシェント関数）

ここで位数とは、群 $G$ の元 $g$ の位数は、$g^k = 1$ となる最小の正整数 $k$ です。

中国剰余定理

中国剰余定理：互いに素な整数 $n_1, n_2, \ldots, n_k$ に対して、連立合同式

\begin{align}
x &\equiv a_1 \pmod{n_1} \\
x &\equiv a_2 \pmod{n_2} \\
&\vdots \\
x &\equiv a_k \pmod{n_k}
\end{align}

は一意な解 $x \pmod{N}$ を持ちます。ここで $N = n_1 \cdot n_2 \cdots n_k$ です。

証明

存在性：$N_i = N/n_i$ とおきます。$\gcd(n_i, N_i) = 1$ より、$N_i$ の逆元 $M_i$ が存在します（$N_i \cdot M_i \equiv 1 \pmod{n_i}$）。

解は以下で与えられます。

$$x = a_1 \cdot N_1 \cdot M_1 + a_2 \cdot N_2 \cdot M_2 + \cdots + a_k \cdot N_k \cdot M_k$$

一意性：$x, y$ が両方とも解であるとすると、$x \equiv y \pmod{n_i}$ が全ての $i$ について成り立ちます。$n_i$ が互いに素であることから、$x \equiv y \pmod{N}$ が従います。

オイラーの定理

RSA暗号の動作原理は、18世紀の数学者レオンハルト・オイラーが発見した オイラーの定理 に基づいています。

オイラーの定理：$\gcd(a, n) = 1$ なる整数 $a, n$ に対して、

$$a^{\phi(n)} \equiv 1 \pmod{n}$$

が成り立ちます。ここで $\phi(n)$ はオイラーのトーシェント関数です。

証明：$\mathbb{Z}_n^*$ の位数が $\phi(n)$ であることから、ラグランジュの定理により任意の元 $a$ の位数は $\phi(n)$ の約数です。したがって、$a^{\phi(n)} \equiv 1 \pmod{n}$ が成り立ちます。

フェルマーの小定理

フェルマーの小定理：素数 $p$ と、$p$ と互いに素な整数 $a$ に対して、

$$a^{p-1} \equiv 1 \pmod{p}$$

が成り立ちます。

証明：素数 $p$ に対して $\phi(p) = p-1$ であることから、オイラーの定理の特殊な場合です。

落とし戸つき一方向性関数

公開鍵暗号の中心的な役割を担うのが 落とし戸つき一方向性関数（trapdoor one-way function）という数学的構造です。

一方向性関数：関数 $f: X \rightarrow Y$ が一方向性を持つとは、以下の2つの性質を満たすことです。

$f(x)$ の計算が容易（多項式時間で計算可能）
$y = f(x)$ が与えられたとき、$x$ を求めることが計算困難

落とし戸つき一方向性関数：一方向性関数 $f$ に対して、特別な秘密情報（落とし戸）$t$ が存在し、以下を満たすとき、$f$ を落とし戸つき一方向性関数といいます。

落とし戸 $t$ なしでは、$y = f(x)$ から $x$ を求めることが計算困難
落とし戸 $t$ があれば、$y = f(x)$ から $x$ を効率的に計算可能

RSA暗号における落とし戸つき一方向性関数を具体的に見てみましょう。公開鍵 $(n, e)$ が与えられたとき、関数 $f(m) = m^e \bmod n$ は以下の性質を持ちます。

一方向性：$c = m^e \bmod n$ の計算は容易ですが、$c$ から $m$ を求めること（$m = c^{1/e} \bmod n$）は素因数分解問題と同等に困難です
落とし戸：ただし、秘密鍵 $d$ を知っていれば、$m = c^d \bmod n$ により効率的に平文を復元できます

この構造により、公開鍵で暗号化することは誰でもできますが、復号は秘密鍵を持つ者だけが可能になります。このような落とし戸つき一方向性関数の存在が、公開鍵暗号を実現する数学的基盤となっています。

素因数分解問題

RSA暗号の落とし戸つき一方向性関数を支える計算困難性の根拠が、 素因数分解問題 です。

素因数分解問題とは、大きな合成数 $n = p \times q$ （ $p, q$ は素数）が与えられたとき、 $p$ と $q$ を見つける問題です。一見単純に見えますが、数が大きくなるにつれて計算量が爆発的に増加します。現在知られている最良の古典アルゴリズムである 一般数体ふるい法 の計算量は $O(e^{((64/9)^{1/3} + o(1)) \times (\ln n)^{1/3} \times (\ln \ln n)^{2/3}})$ で、512ビットのRSA鍵は1999年に分解されましたが、1024ビットの鍵は現在も分解されていません（ただし、安全性に対する余裕が小さく、推奨はされていません）。

4.4 RSA暗号の実装

鍵生成

オイラーの定理を基に、RSA暗号の鍵生成プロセスを構築していきます。まず大きな素数 $p, q$ をランダムに選択し、 $n = p \times q$ を計算します。次に $\phi(n) = (p - 1)(q - 1)$ を求め、公開指数 $e$ を選択します。通常 $e = 65537 = 2^{16} + 1$ が使われ、これは $\gcd(e, \phi(n)) = 1$ （$\gcd$ = 最大公約数）を満たす必要があります。最後に、拡張ユークリッドアルゴリズムを使って秘密指数 $d$ を計算し、 $d \times e \equiv 1 \pmod{\phi(n)}$ を満たすようにします。

例えば、 $p = 61, q = 53$ の場合、 $n = 3233$ 、 $\phi(n) = 3120$ となり、 $e = 17$ を選ぶと $d = 2753$ が得られます。これで公開鍵 $(n, e) = (3233, 17)$ と秘密鍵 $d = 2753$ のペアが完成します。

暗号化と復号

暗号化は単純に $c = m^e \bmod n$ で行われ、復号は $m = c^d \bmod n$ で行われます。この仕組みが正しく動作する理由は、オイラーの定理にあります。

$\gcd(m, n) = 1$ における復号の正しさを確認してみましょう。

\begin{align}
c^d &= (m^e)^d \\
&= m^{ed} \\
&= m^{1 + k\phi(n)} \\
&= m \times (m^{\phi(n)})^k \\
&\equiv m \times 1^k = m \pmod{n}
\end{align}

ここで $ed \equiv 1 \pmod{\phi(n)}$ より $ed = 1 + k\phi(n)$ となる整数 $k$ が存在し、オイラーの定理により $m^{\phi(n)} \equiv 1 \pmod{n}$ が成り立つため、最終的に $m$ が復元されます。

次に、$\gcd(m, n) \neq 1$ の場合を考えてみましょう。場合分けをして考えていきます。

$m$ が $p$ の倍数だが $q$ の倍数でない場合（$p \mid m, q \nmid m$）から考えます。

$p$ を法として：$m \equiv 0 \pmod{p}$ より $c^d \equiv 0^d \equiv 0 \equiv m \pmod{p}$
$q$ を法として：$\gcd(m, q) = 1$ よりフェルマーの小定理が適用でき、$m^{q-1} \equiv 1 \pmod{q}$

$ed \equiv 1 \pmod{(p-1)(q-1)}$ より $ed = 1 + k(p-1)(q-1)$ なので、
```
\begin{align}
c^d &\equiv m^{ed} \\
&\equiv m^{1 + k(p-1)(q-1)} \\
&\equiv m \cdot (m^{q-1})^{k(p-1)} \\
&\equiv m \cdot 1^{k(p-1)} \\
&\equiv m \pmod{q}
\end{align}
```
中国剰余定理により、$c^d \equiv m \pmod{p}$ かつ $c^d \equiv m \pmod{q}$ から、 $c^d \equiv m \pmod{n}$ が成り立ちます。

同様に、$m$ が $q$ の倍数だが $p$ の倍数でない場合（$q \mid m, p \nmid m$）も、上記と同様の手順で $c^d \equiv m \pmod{n}$ が成り立つことが示せます。

最後に、$m$ が $n$ の倍数（つまり $m$ が $p$ と $q$ の両方の倍数）の場合を考えます。この場合、$m \equiv 0 \pmod{p}$ かつ $m \equiv 0 \pmod{q}$ より、$c^d \equiv 0^d \equiv 0 \equiv m \pmod{p}$ かつ $c^d \equiv 0^d \equiv 0 \equiv m \pmod{q}$ が成り立ちます。中国剰余定理により、$c^d \equiv m \pmod{n}$ が成り立ちます。

このように、RSA暗号は平文の値に関わらず常に正しく復号できることが保証されています。

ここまでがRSA暗号の基本的な原理です。ここから実装時に利用される各種最適化手法について簡単に説明します。

実用的な高速化技術

RSA暗号の実用性を高めるため、いくつかの高速化技術が開発されています。これらの技術は、数学的理論に基づいて設計されており、計算量を大幅に削減します。

中国剰余定理（RSA-CRT）

中国剰余定理を利用した復号では、大きな指数の計算を小さな指数の計算に分割します。

復号時、$m_1 = c^{d \bmod (p-1)} \bmod p$ と $m_2 = c^{d \bmod (q-1)} \bmod q$ を計算し、これらを組み合わせて最終的な平文を復元します。

中国剰余定理により、$m \equiv m_1 \pmod{p}$ かつ $m \equiv m_2 \pmod{q}$ を満たす $m \bmod n$ は一意に定まります。

$$m = m_2 + q \cdot ((m_1 - m_2) \cdot q^{-1} \bmod p)$$

この方法により、指数の大きさが約半分になり、計算量が約4倍高速化されます。

Montgomery乗算

Montgomery乗算は、剰余乗算を高速化する技法です。数を特殊な表現に変換することで、除算を避けて剰余計算を高速化できます。RSAの実装では広く使用されています。

Sliding-Window法

Sliding-Window法は、指数のビット列で1が連続する部分（ウィンドウ）をまとめて処理し、必要な乗算回数を減らすことで高速にべき乗計算を行う手法です。奇数べきの事前計算テーブルを利用することで、通常のバイナリ法より効率的に 0 と 1 の連続部分を処理できます。実装やウィンドウ幅に依存しますが、一般に通常のバイナリ法に比べ、おおよそ20〜40%程度高速化できます。

素数生成アルゴリズム

RSA暗号の鍵生成では、大きな素数 $p, q$ の生成が重要です。

Miller-Rabin素数判定法は、フェルマーの小定理を拡張した確率的素数判定法で、実用的な速度で高精度に素数を判定できます。複数回の試行により誤判定確率を $4^{-k}$ 以下に抑えることができ（$k$ は試行回数）、現代のRSA実装で広く使用されています。

計算量と効率性

RSA暗号の各操作は、鍵長の多項式時間で実行可能です。鍵生成、暗号化、復号のいずれも効率的に計算でき、特にCRT復号により復号処理を約4倍高速化できます。これらの最適化技術により、RSA暗号は実用的な性能を実現しています。

実装上の考慮事項

実際のRSA実装では、暗号化を高速化するため公開指数 $e = 65537$ を使用し、タイミング攻撃を防ぐため定数時間実装を採用します。また、CRT復号では計算を並列化することで、複数コアでの高速化が可能です。これらの技術により、RSA暗号は実用的な性能を実現しています。

4.5 RSA暗号の安全性向上

素のRSA暗号の課題

RSA暗号において、あまり知られていない重要な点として、ここまで説明してきた素のRSA暗号の実装には大きな問題があります。素のRSA暗号は 決定性暗号 であるため、同じ平文は常に同じ暗号文になってしまいます。また、小さな平文の場合、 $m^e < n$ となって暗号文から平文が直接計算できてしまう脆弱性があります（モジュロ計算なしで暗号文と平文の関係が $c = m^e$ となるので、単に暗号文のe乗根を取れば平文に戻せるようになる）。さらに、同じ $n$ で異なる $e$ を使用した場合の 共通モジュラス攻撃 も存在します。これらの理由から、素のRSA暗号ではOW-CPA安全性までしか満たさず、現代の暗号として必要な安全性（IND-CCA2）を担保できません。

OAEP（Optimal Asymmetric Encryption Padding）

これらの問題を解決するために開発されたのが OAEP（Optimal Asymmetric Encryption Padding） です。OAEPは、平文にランダム性を導入し、非決定的な挙動にすることで、RSA暗号の安全性を大幅に向上させます。

暗号化では、平文 $m$ にランダム値 $r$ を組み合わせ、 $G(r) \oplus m$ と $H(G(r) \oplus m) \oplus r$ を計算してこれらを連結してからRSA暗号化を行います。復号時は、RSA復号後に連結された値を分離し、 $r$ を復元してから $m$ を抽出します。

この仕組みにより、 IND-CCA2安全性 を提供し、ランダムオラクルモデルでの数学的証明が可能になります。これが現代のRSA暗号実装の標準となっています。

RFC8017とパディングスキームの標準化

RSA暗号の実装を標準化した文書が RFC8017（PKCS#1 v2.2） です。この文書では、複数のパディングスキームが定義されており、それぞれ異なる特性と安全性を持っています。

RSAES-PKCS1-v1_5

RSAES-PKCS1-v1_5 は、1993年にPKCS#1 v1.5で定義されたパディングスキームで、長年にわたって広く使用されてきました。しかし、1998年に Bleichenbacher攻撃 が発見され、この方式が適応的選択暗号文攻撃（CCA2）に対して脆弱であることが明らかになりました。この攻撃はパディングオラクル攻撃の一種で、復号オラクルからパディングエラーの情報を利用して平文を復元できます。
また、2017年には、このBleichenbacher攻撃が TLS 1.2でも適切に実装されていないことにより発生することが発見されました（ROBOT）。

現在の推奨事項として、新規実装ではRSAES-PKCS1-v1_5の使用を避け、既存システムでは可能な限りOAEPへの移行が推奨されています。RFC8017では互換性のためにこの方式が含まれていますが、新規使用は非推奨とされています。

暗号化パディングスキームの比較

RFC8017で定義される暗号化パディングスキームを比較すると、以下のようになります。

方式	安全性	推奨事項
OAEP	IND-CCA2安全性を提供。ランダムオラクルモデルでの数学的証明が可能	RFC8017で推奨される方式
PKCS1-v1_5	安全性証明がなく、実用的な攻撃（Bleichenbacher攻撃）が存在	新規使用は非推奨。既存システムではOAEPへの移行を推奨

この比較から、現代のRSA暗号実装ではOAEPを使用することが重要であることがわかります。

RSA暗号の安全性理論

RSA暗号の安全性を理解するためには、暗号学における安全性の形式的定義と、それらがどのように数学的に証明されるかを学ぶ必要があります。

安全性の形式的定義

暗号学では、攻撃者の能力と目標に応じて複数の安全性概念が定義されています（詳細は第1回参照）。

選択平文攻撃に対する一方向性（OW-CPA）：攻撃者が暗号文から平文を復元することが計算困難であることを意味します。形式的には、ランダムに選ばれた平文 $m$ の暗号文 $c = \text{Enc}(\text{pk}, m)$ が与えられたとき、$m$ を求めることが困難であることを要求します。

選択平文攻撃に対する識別不可能性（IND-CPA）：攻撃者が2つの平文 $m_0, m_1$ のどちらが暗号化されたかを識別できないことを意味します。攻撃者は公開鍵と暗号化オラクルにアクセスできますが、暗号文から平文の内容を推測できません。

適応的選択暗号文攻撃に対する識別不可能性（IND-CCA2）：最も強力な安全性概念で、攻撃者は復号オラクルにもアクセスできます。チャレンジ暗号文以外の任意の暗号文を復号して情報を収集できますが、それでも平文を識別できません。

RSA問題の困難性

RSA暗号の安全性は、RSA問題の困難性に基づいています。RSA問題とは、与えられた $(n, e, c)$ に対して、$c \equiv m^e \pmod{n}$ を満たす $m$ を求める問題です。

この問題の困難性は、素因数分解問題の困難性と関連しています。もし $n = pq$ を素因数分解できれば、$\phi(n) = (p-1)(q-1)$ を計算し、拡張ユークリッド互除法で $d$ を求めることで、$m = c^d \bmod n$ で平文を復元できます。

逆に、RSA問題を解くアルゴリズムが存在すれば、それを利用して素因数分解を行うことも可能です。しかし、素因数分解を用いずにRSA問題を効率的に解く方法が存在するかどうかは未解決問題です。理論的には、RSA問題が素因数分解よりも易しい可能性が排除されておらず、RSA暗号の安全性が素因数分解問題と厳密に等価であるかは、暗号理論における重要な未解決問題の一つとなっています。

攻撃手法の数学的分析

Wiener攻撃：秘密鍵 $d$ が小さすぎる場合の攻撃です。$d < \frac{1}{3}n^{1/4}$ のとき、連分数展開により $d$ を効率的に求めることができます。

数学的には、$ed \equiv 1 \pmod{\phi(n)}$ より $ed = 1 + k\phi(n)$ となる整数 $k$ が存在します。$d$ が小さいとき、$\frac{e}{n} \approx \frac{k}{d}$ となり、連分数展開で $\frac{k}{d}$ を近似できます。

低指数攻撃：公開指数 $e$ が小さく、平文 $m$ も小さい場合、$m^e < n$ となって $m = \sqrt[e]{c}$ で平文を直接計算できます。

サイドチャネル攻撃：実装時の電力消費やタイミング情報から秘密鍵を推測する攻撃です。バイナリ法の実装では、0ビットと1ビットで電力消費が異なるため、秘密鍵のビットパターンが漏洩する可能性があります。

最下位ビットの安全性

興味深いことに、RSA暗号の最下位ビット（LSB）は、RSA問題と同等に困難であることが証明されています。

定理：暗号文から平文の最下位ビットを求めるオラクルが存在する場合、そのオラクルを $O(\log n)$ 回呼び出すことで、多項式時間でRSA暗号を解読できます。

この証明は、二分探索アルゴリズムを用います。$c' = c \cdot (2^i)^e \bmod n$ を計算し、$O_L(c')$ でLSBを取得することで、平文が区間 $[0, \frac{n}{2^i})$ に含まれるかどうかを判定できます。$\log n$ 回の反復により、正確な平文を復元できます。

OAEPの安全性証明

RSA-OAEPのIND-CCA2安全性は、ランダムオラクルモデルで数学的に証明されています。

証明の概要：

攻撃者がRSA-OAEPを破ることを仮定
ランダムオラクルへの問い合わせを監視
特定の問い合わせが発生した時点でRSA問題を解く
この還元により、RSA-OAEPの安全性がRSA仮定に基づくことを示す

この証明により、適切に実装されたRSA-OAEPは、素因数分解が困難である限り、IND-CCA2安全性を提供することが保証されます。

4.6 RSA署名

ディジタル署名の必要性

RSA暗号の仕組みを理解したところで、今度はその逆の応用を考えてみましょう。暗号化では公開鍵で暗号化し秘密鍵で復号しましたが、署名では秘密鍵で署名を生成し、公開鍵で検証を行います。これにより、メッセージの認証と 否認防止 を実現できます。

署名アルゴリズムは秘密鍵 $\text{sk}$ とメッセージ $m$ から署名 $\sigma$ を生成し、検証アルゴリズムは公開鍵 $\text{pk}$ 、メッセージ $m$ 、署名 $\sigma$ から有効性を判定します。

基本的なRSA署名の仕組み

RSA署名は、暗号化の逆の操作として実装されます。署名生成では $\sigma = m^d \bmod n$ を計算し、署名検証では $m = \sigma^e \bmod n$ が成り立つかチェックします。

しかし、この基本的な実装には重大な問題があります。任意の $\sigma$ に対して $m = \sigma^e \bmod n$ を計算できるため、署名の偽造が容易になってしまいます。また、ハッシュ関数を使用しないため、長いメッセージに対する安全性も不十分です。

FDH署名：安全性の確立

これらの問題を解決するために開発されたのが Full Domain Hash (FDH) 署名です。FDH署名では、まずメッセージ $m$ をハッシュ関数 $H$ でハッシュ化して $h = H(m)$ を計算し、その後 $\sigma = h^d \bmod n$ で署名を生成します。検証時は $h = \sigma^e \bmod n$ を計算し、 $H(m) = h$ かどうかをチェックします。

この仕組みにより、 EUF-CMA（選択メッセージ攻撃に対する存在偽造困難性） を提供し、ランダムオラクルモデルでの数学的証明が可能になります。これが現代のRSA署名実装の基盤となっています。

RFC8017で標準化された署名パディングスキーム

RFC8017では、署名用のパディングスキームとして複数の方式が定義されています。FDH署名の理論的基盤を実装向けに最適化した方式と、互換性のために残されている方式があります。

RSASSA-PSS

RSASSA-PSS（Probabilistic Signature Scheme） は、RFC8017で推奨される現代的な署名方式です。ランダム性を導入した確率的署名であり、EUF-CMA安全性をランダムオラクルモデルで証明可能です。FDH署名の理論的基盤を実装向けに最適化した形式となっています。

RSASSA-PKCS1-v1_5

RSASSA-PKCS1-v1_5 は、1993年に定義され、長年にわたって広く使用されてきた署名方式です。理論的な安全性証明はありませんが、実用的な攻撃は知られておらず、既存システムとの互換性のためにRFC8017に含まれています。ただし、PSSの方が理論的に安全であるため、新規実装ではPSSの使用が推奨されています。

署名パディングスキームの比較

RSA署名で使用されるパディングスキームを比較すると、以下のようになります。

方式	特徴	推奨事項
FDH署名	理論的な基盤となる方式。安全性証明の基礎を提供	理論的な理解に有用。実用ではほぼ使われない
RSASSA-PSS	実装向けに最適化された形式。EUF-CMA安全性をランダムオラクルモデルで証明可能	RFC8017で推奨される方式
RSASSA-PKCS1-v1_5	1993年に定義され、長年広く使用。理論的な安全性証明はないが、実用的な攻撃は知られていない	新規使用は非推奨。既存システムとの互換性のために使用可能

この比較から、現代のRSA署名実装ではRSASSA-PSSを使用することが推奨されることがわかります。

4.7 分散署名

単一秘密鍵のリスク

RSA署名の安全性は秘密鍵の保護に依存していますが、単一の秘密鍵を一箇所に保存することは大きなリスクを伴います。秘密鍵の漏洩、紛失、または内部犯による不正使用など、 単一障害点 が存在してしまいます。

この問題を解決するために開発されたのが 分散署名 です。秘密鍵を複数の参加者で分割して保持することで、鍵管理の安全性を大幅に向上させ、不正使用を防止できます。

Shamirの秘密分散法

分散署名は、 Shamirの秘密分散法 （Shamirによる$(t, k)$-閾値秘密分散）を応用して実現されます。秘密鍵 $d$ を多項式 $f(x) = d + a_1x + a_2x^2 + \cdots + a_{t-1}x^{t-1}$ で表現し、各参加者 $i$ に $f(i)$ を分配します。多項式補間を用いて、 $t$ 人以上の参加者が集まれば秘密鍵 $d$ を再構成できますが、 $t-1$ 人以下の参加者では秘密鍵を再構成できない仕組みを実現します。ただし、閾値署名では実際に秘密鍵を復元せず、各参加者は自分の分散片だけを利用します。

分散署名生成では、秘密鍵を再構成することなく、各参加者が自分の分散片を用いて部分署名を計算します。これらを署名方式に応じた閾値署名アルゴリズムを用いて完全な署名が生成されます。完全署名は、通常の署名と同じ形式で第三者に検証可能です。

実用的な運用上の課題

分散署名の実装では、定期的な鍵の再分散や参加者の追加・削除時の処理など、運用上の課題があります。また、部分署名の並列生成や通信オーバーヘッドの最小化など、効率性の向上も重要な検討事項となります。

4.8 準同型暗号

暗号化と計算の両立

従来の暗号では、データを暗号化すると計算ができなくなってしまいます。しかし、 準同型暗号 は、暗号文のまま演算を行える特別な暗号方式です。これにより、データの秘匿性を保ちながら計算を実行できるようになります。

準同型暗号には 加法準同型性 と 乗法準同型性 があります。加法準同型性では $\text{Enc}(m_1) \times \text{Enc}(m_2) = \text{Enc}(m_1 + m_2)$ が成り立ち、乗法準同型性では $\text{Enc}(m_1) \times \text{Enc}(m_2) = \text{Enc}(m_1 \times m_2)$ が成り立ちます。

Paillier暗号の数学的基盤

Paillier暗号 は、加法準同型性を持つ代表的な準同型暗号です。

Carmichael関数

Carmichael関数 $\lambda(n)$ は、オイラーのトーシェント関数 $\phi(n)$ に類似した関数で、$n = pq$（$p, q$ は素数）のとき $\lambda(n) = \text{lcm}(p-1, q-1)$ となります（$\text{lcm}$ は最小公倍数）。Paillier暗号では、この関数を用いて鍵を生成します。

Paillier暗号のアルゴリズム

鍵生成（KeyGen）

大きな素数 $p, q$ を選ぶ（$|p| = |q| = \lambda$）
$n = p \cdot q$ を計算
$\lambda(n) = \text{lcm}(p-1, q-1)$ を計算
生成元 $g \in \mathbb{Z}_{n^2}^*$ を選ぶ（通常 $g = n + 1$）
$\mu = (L(g^{\lambda(n)} \bmod n^2))^{-1} \bmod n$ を計算
- ここで $L(x) = \frac{x-1}{n}$
公開鍵：$(n, g)$、秘密鍵：$(\lambda(n), \mu)$

暗号化（Enc）

乱数 $r \overset{$}{\leftarrow} \mathbb{Z}_n^*$ を選ぶ
暗号文 $c = g^m \cdot r^n \bmod n^2$ を計算

復号（Dec）

$m = L(c^{\lambda(n)} \bmod n^2) \cdot \mu \bmod n$ を計算

正当性の数学的証明

定理：Paillier暗号方式は正当性を満たします。

証明の概要：暗号文 $c = g^m \cdot r^n \bmod n^2$ を復号すると、Carmichael関数の性質により $r^{n\lambda(n)} \equiv 1 \pmod{n^2}$ となるため、$c^{\lambda(n)} \equiv g^{m\lambda(n)} \pmod{n^2}$ が得られます。$L$ 関数を適用すると $L(g^{m\lambda(n)}) = m \cdot L(g^{\lambda(n)})$ となり、最終的に $m' = m \cdot L(g^{\lambda(n)}) \cdot \mu = m$ が復元されます（$\mu$ は $L(g^{\lambda(n)})$ の逆元）。

加法準同型性の証明

定理：Paillier暗号は加法的準同型性を持ちます。

証明の概要：2つの暗号文 $c_1 = g^{m_1} \cdot r_1^n$ と $c_2 = g^{m_2} \cdot r_2^n$ の積を計算すると、$c_1 \cdot c_2 = g^{m_1 + m_2} \cdot (r_1 \cdot r_2)^n \bmod n^2$ となります。これを復号すると $(m_1 + m_2) \bmod n$ が得られるため、暗号文の積が平文の和に対応します。

安全性の基盤

Paillier暗号の安全性は 合成剰余判定問題（DCR） の困難性に基づいています。DCR問題とは、 $n$ と $z \in \mathbb{Z}_{n^2}^*$ が与えられたとき、 $z$ が $n$ 乗剰余かどうかを判定する問題で、この問題の計算困難性がPaillier暗号の安全性を保証しています。

4.9 準同型暗号の実践的応用

電子投票システム

準同型暗号の最も魅力的な応用例の一つが 電子投票システム です。従来の電子投票では、投票内容の秘匿性、集計の正確性、二重投票の防止という三つの課題を同時に解決することが困難でした。

Paillier暗号を使った電子投票システムでは、投票者が投票内容（例えば $0$ で反対、 $1$ で賛成）を暗号化して $\text{Enc}(0)$ または $\text{Enc}(1)$ として提出します。集計者は暗号化された投票をそのまま掛け合わせることで $\text{Enc}(0) \times \text{Enc}(1) \times \text{Enc}(1) = \text{Enc}(2)$ を計算し、最終的に復号して賛成2票という結果を得ます。

この仕組みにより、個々の投票内容は秘匿されたまま、正確な集計結果のみが得られるという理想的な電子投票システムが実現されます。

プライバシー保護計算

準同型暗号は、 プライバシー保護計算 の基盤技術としても注目されています。統計データの分析では、個人データを暗号化したまま統計処理を行い、個人情報を開示することなく分析結果を取得できます。

機械学習の分野でも、暗号化されたデータでの学習が可能になり、モデルの精度を保ちながらプライバシーを保護することができます。これにより、医療データや金融データなど、機密性の高いデータを活用した分析が安全に実行できるようになります。

4.10 実世界での活用

RSA暗号

学んできたRSA暗号の理論は、現代のインターネット通信の基盤となっています。 TLS/SSL プロトコルでは、鍵交換時の認証やサーバー証明書の検証にRSA暗号が使用されてきました。現在は楕円曲線暗号への移行が進んでいますが、RSA暗号は依然として重要な役割を果たしています。

電子署名 の分野では、ソフトウェア配布の署名、ディジタル証明書（X.509）、そしてWindowsやmacOSでのコード署名など、私たちの日常的なデジタル生活を支えています。また、 暗号資産 の分野では、マルチシグウォレットや分散署名による鍵管理など、新しい応用も生まれています。

分散署名

分散署名の技術は、特に HSM（Hardware Security Module） の分野で活用されています。金融機関での鍵管理やクラウドHSMサービスでは、秘密鍵の安全な管理が生命線となるため、分散署名による保護が不可欠です。

準同型暗号

準同型暗号の応用は、まだ発展途上ですが、 電子投票 システムでは政府や企業での投票システム、さらにはブロックチェーン投票など、新しい可能性が模索されています。

プライバシー保護計算 の分野では、医療データの分析や金融データの統計処理など、機密性の高いデータを活用した新しいサービスが期待されています。

4.11 まとめ

今回の記事では、公開鍵暗号のうち、RSA暗号の基礎と、その安全性を向上させる各種パディングスキーム、署名への活用までを見てきました。さらに、秘密鍵管理における分散署名による解決策、そして暗号文のまま計算ができる準同型暗号の概要も学びました。

次回：離散対数問題に基づく公開鍵暗号

「第5回　公開鍵暗号2（離散対数問題に基づく暗号とIDベース暗号）」では、素因数分解問題と並ぶ現代暗号のもう一つの重要な数学的基盤である 離散対数問題 とそれに基づく暗号技術について学びます。Diffie-Hellman鍵共有の詳細、ElGamal暗号の仕組みと安全性、そして楕円曲線暗号（ECDH、ECDSA）など、RSA暗号とは異なるアプローチによる公開鍵暗号を学んでいきます。

楕円曲線暗号は、RSA暗号よりも短い鍵長で同等の安全性を実現できるため、現在の暗号技術で広く使用されています。TLS 1.3の鍵共有（ECDHE）、ビットコイン・イーサリアムでの署名、SSH接続における鍵交換など、現代の暗号技術の核心となる技術を、理論と実装の両面から詳しく学んでいきます。

第4回 公開鍵暗号1（RSA暗号・分散署名・準同型暗号）【連載：暗号技術の基礎を学ぶ】

目次