整数論と暗号 ― RSA暗号はなぜ安全なのか

フェルマー・オイラー・拡張ユークリッドが RSA 暗号の各パーツに対応することを明らかにし，鍵生成・暗号化・復号の仕組みと安全性の根拠（素因数分解の困難性）を解説します．シリーズの総括としてすべての定理の繋がりを振り返ります．

2026年2月27日

整数論は「数学の女王」と呼ばれ，長い間純粋数学の象徴でした．しかし 1977 年，Rivest・Shamir・Adleman の 3 人が整数論の定理を組み合わせて公開鍵暗号を構成し，世界を変えました．このシリーズで学んだ定理が，RSA 暗号のどのパーツに対応しているかを見ていきましょう．

1 公開鍵暗号のアイデア

注意 1 (鍵配送問題).

従来の暗号（共通鍵暗号）では，送信者と受信者が同じ鍵を共有する必要があります．しかし，鍵を安全に共有するにはすでに安全な通信路が必要 ― という鶏と卵の問題がありました．

公開鍵暗号は，この問題を一方向関数のアイデアで解決します．「鍵をかけるのは誰でもできるが，開けるのは鍵の持ち主だけ」― 南京錠のような仕組みです．

2 RSA 暗号の仕組み

定義 2 (RSA 鍵生成).

大きな素数 $p, q$ をランダムに選び， $n = pq$ を計算します
$φ (n) = (p - 1) (q - 1)$ を計算します（オイラーの関数）
$g cd (e, φ (n)) = 1$ をみたす $e$ を選びます（通常 $e = 65537$ ）
$e d \equiv 1 (mod φ (n))$ をみたす $d$ を計算します（拡張ユークリッドの互除法）

公開鍵：

(n, e)

，秘密鍵：

d

．

注意 3.

ここで使われている道具を確認しましょう：

素数（第3回）： $p, q$ の選択
オイラーの関数（第4回）： $φ (n)$ の計算
拡張ユークリッドの互除法（第2回）： $d$ の計算

定義 4 (RSA 暗号化と復号).

平文を整数

m

（

0 \leq m < n

）として，

暗号化： $c \equiv m^{e} (mod n)$ （公開鍵 $e$ で暗号化）
復号： $m \equiv c^{d} (mod n)$ （秘密鍵 $d$ で復号）

3 復号の正当性 ― オイラーの定理が鍵

なぜ $c^{d} \equiv m (mod n)$ が成り立つのでしょうか？

定理 5 (RSA の正当性).

g cd (m, n) = 1

のとき，

(m^{e})^{d} \equiv m (mod n)

．

証明.

e d \equiv 1 (mod φ (n))

より，

e d = 1 + k φ (n)

（ある整数

k

）．

(m^{e})^{d} = m^{e d} = m^{1 + k φ (n)} = m \cdot (m^{φ (n)})^{k}

オイラーの定理（第4回）より

m^{φ (n)} \equiv 1 (mod n)

．したがって，

(m^{e})^{d} \equiv m \cdot 1^{k} = m (mod n)

□

注意 6.

g cd (m, n) \neq = 1

の場合（

p ∣ m

または

q ∣ m

）も，CRT（第5回）を使って

mod p

と

mod q

で別々に確認すれば，

(m^{e})^{d} \equiv m (mod n)

が成り立つことがわかります．

4 安全性の根拠 ― 素因数分解の困難性

注意 7 (なぜ安全か).

攻撃者は公開鍵

(n, e)

を知っていますが，秘密鍵

d

を求めるには

φ (n) = (p - 1) (q - 1)

が必要です．

φ (n)

を知るには

n

を

p \times q

に素因数分解する必要があります．

素因数分解の困難性：

n = pq

の計算は一瞬ですが，

n

から

p, q

を復元するのは（

p, q

が十分大きいとき）現在知られているアルゴリズムでは天文学的な時間がかかります．これが RSA の安全性の根拠です．

注意 8 (計算量のギャップ).

掛け算： $p \times q$ は $O ((lo g n)^{2})$ （多倍長乗算）で一瞬
素因数分解：最速の古典アルゴリズム（一般数体篩法）でも $exp (O ((lo g n)^{1/3} (lo g lo g n)^{2/3}))$ という準指数時間
2048 ビットの $n$ の素因数分解は，現在の計算機では数千年以上かかると推定されています

この掛け算は簡単だが因数分解は困難という非対称性が，RSA の安全性を支えています．

5 各パーツとシリーズの対応

注意 9 (シリーズの定理たちの活躍).

RSA 暗号の各パーツが，このシリーズで学んだ定理に対応しています：

第1回（mod 演算）：すべての計算が $mod n$ の世界で行われる
第2回（ユークリッドの互除法）：秘密鍵 $d$ の計算（ $e d \equiv 1 (mod φ (n))$ の逆元）
第3回（算術の基本定理）：素因数分解の一意性が安全性の前提
第4回（フェルマー・オイラーの定理）：復号の正当性の証明
第5回（中国剰余定理）： $mod p$ と $mod q$ で別々に復号して合成する高速化（CRT-RSA）
第6回（二次剰余）：Rabin 暗号（RSA の変種）の理論的基盤
第7回（連分数）：小さな秘密鍵 $d$ への攻撃（Wiener の攻撃は連分数を使う）

6 RSA の具体例

例 10 (小さな数での RSA).

鍵生成： $p = 61, q = 53$ ， $n = 3233$ ， $φ (n) = 60 \times 52 = 3120$
$e = 17$ （ $g cd (17, 3120) = 1$ ）
拡張ユークリッド： $17 d \equiv 1 (mod 3120)$ → $d = 2753$ （ $17 \times 2753 = 46801 = 15 \times 3120 + 1$ ）
暗号化： $m = 65$ → $c \equiv 6 5^{17} (mod 3233) = 2790$
復号： $279 0^{2753} mod 3233 = 65$ （繰り返し二乗法で計算）

7 現代の展望

注意 11 (量子コンピュータの脅威).

ショアのアルゴリズムは量子コンピュータ上で多項式時間で素因数分解を行えます．十分な量子ビットをもつ量子コンピュータが実現すれば，RSA は破られます．このため，格子暗号や同種写像暗号など耐量子暗号（Post-Quantum Cryptography）の研究が進んでいます．

注意 12.

しかし重要なのは，RSA が破られたとしても，その背後にある整数論の美しさは失われないということです．mod 演算，ユークリッドの互除法，フェルマーの小定理，中国剰余定理 ― これらは何千年も前から存在する数学的真理であり，暗号以外にも無数の応用をもちます．

8 シリーズの総括

注意 13.

8回にわたる整数論「教科書の行間」シリーズを振り返りましょう：

mod 演算：情報を捨てる射影． $Z / n Z$ の環構造
ユークリッドの互除法：不変量に基づく $O (lo g)$ のアルゴリズム．ベズーの等式
算術の基本定理：素因数分解の一意性．ユークリッドの補題が鍵
フェルマーの小定理： $(Z / p Z)^{*}$ の群構造．逆元 $a^{p - 2}$
中国剰余定理：分割統治の代数版． $Z / mn Z ≅ Z / m Z \times Z / n Z$
二次剰余： $x \mapsto x^{2}$ の 2:1 性．相互法則の驚き
連分数：互除法の別の顔．最良有理近似とペル方程式
RSA 暗号：すべての定理が合流する応用

整数論は，最も素朴な対象（

1, 2, 3, \dots

）から始まりながら，驚くほど深い構造と広い応用をもつ分野です．このシリーズが，教科書の行間に隠された「なぜ」を照らす一助になれば幸いです．

整数論代数学教科書の行間

Folio公式

数学の「教科書が書かない行間」をLaTeXで．Folio公式アカウントです．

0 followers·105 articles

整数論と暗号 ― RSA暗号はなぜ安全なのか

1 公開鍵暗号のアイデア

2 RSA 暗号の仕組み

3 復号の正当性 ― オイラーの定理が鍵

4 安全性の根拠 ― 素因数分解の困難性

5 各パーツとシリーズの対応

6 RSA の具体例

7 現代の展望

8 シリーズの総括

Share your expertise with the world

More from Folio公式

Folio LaTeXの基本 ― 標準LaTeXとの違いと始め方

カタラン数はなぜどこにでも現れるのか ― 括弧列・二分木・格子経路の不思議な一致

漸化式と母関数 ― 数列を「関数」にすると何が見えるか

包除原理はなぜ「足して引いて」を繰り返すのか ― ベン図からメビウス関数へ