Chapter 16
RSA — 素因数分解の困難性に賭ける
公開鍵暗号という発想の衝撃. 1976 年まで、暗号には絶対の前提があった——「送り手と受け手は、事前に秘密の鍵を共有していなければならない」。
ディフィーとヘルマンはこれを覆す論文を書き（17 章）、 1977 年に MIT の Rivest・Shamir・Adleman が具体的な方式を作った。それが RSA である。
鍵を 2 つに分け、片方を全世界に公開する。 それでも安全—— なぜそんなことが可能なのか、15 章の道具で完全に導出する。
1. 鍵生成
- 大きな素数\(p, q\)をランダムに選ぶ（各 1024 ビット以上、ミラー・ラビンで判定）
- \(n = pq\) を計算（公開）
- \(\varphi(n) = (p-1)(q-1)\) を計算（秘密）
- \(\gcd(e, \varphi(n))=1\) となる\(e\)を選ぶ（公開。通常 65537）
- \(d \equiv e^{-1} \pmod{\varphi(n)}\) を拡張ユークリッドで計算（秘密）
| 公開鍵 | 秘密鍵 | |
|---|---|---|
| 構成 | \((n, e)\) | \((n, d)\)、および\(p,q,\varphi(n)\) |
なぜ\(e = 65537\)なのか. \(65537 = 2^{16}+1 = \texttt{0x10001}\)は素数で、2 進表現が
10000000000000001と 1 が 2 個だけ。 繰り返し二乗法（01 章）では2 乗 16 回 + 掛け算 1 回で済み、極めて高速である。小さすぎる\(e\)（\(e=3\)など）は危険: 平文が短いと\(m^3 < n\)になり、 \(\bmod n\)が効かず普通の 3 乗根を取るだけで解けてしまう（低指数攻撃）。 65537 は「速い」と「安全」のバランス点である。
2. 暗号化と復号
（\(M < n\)の整数として平文を表現する。）
3. なぜ復号できるのか（正しさの証明）
示すこと: \((M^e)^d \equiv M \pmod n\)
準備
\(d\)の定義より\(ed \equiv 1 \pmod{\varphi(n)}\)、つまりある整数\(k\)があって
場合 1: \(\gcd(M, n) = 1\) のとき
オイラーの定理（15 章）より\(M^{\varphi(n)} \equiv 1 \pmod n\)。よって
場合 2: \(\gcd(M,n) \neq 1\) のとき（見落とされがちだが必要）
\(n=pq\)なので\(M\)は\(p\)か\(q\)の倍数。\(M\)が\(p\)の倍数だとする（\(q\)の倍数でも同様）。
法\(p\)で見る: \(M \equiv 0\)なので\(M^{ed} \equiv 0 \equiv M \pmod p\) ✓
法\(q\)で見る: \(\gcd(M,q)=1\)（\(M\)が\(pq\)の倍数なら\(M \ge n\)で範囲外）なので、 フェルマーの小定理より\(M^{q-1}\equiv1 \pmod q\)。\(\varphi(n)=(p-1)(q-1)\)なので
統合: \(M^{ed} \equiv M\)が法\(p\)でも法\(q\)でも成立。 \(p,q\)は互いに素なので、中国剰余定理（15 章）より\(M^{ed}\equiv M \pmod{pq=n}\) ∎
15 章の 3 つの道具（オイラーの定理・フェルマーの小定理・CRT）が、 ここで揃って RSA の正しさを支えている.
実例（小さな数で）
\(p=61, q=53\) → \(n = 3233\)、\(\varphi(n) = 60\times52 = 3120\) \(e = 17\)（\(\gcd(17,3120)=1\) ✓） \(d = 17^{-1} \bmod 3120 = 2753\)（拡張ユークリッド。検算: \(17\times2753 = 46801 = 15\times3120+1\) ✓）
暗号化: \(M = 65\) → \(C = 65^{17} \bmod 3233 = 2790\) 復号: \(2790^{2753} \bmod 3233 = 65\) ✓
4. 安全性
依拠する困難性
RSA 問題: \(n, e, C\)から\(M = C^{1/e} \bmod n\)を求める。
これは素因数分解問題と強く関係する:
- \(n\)を素因数分解できれば → \(\varphi(n)\)が分かり → \(d\)が計算でき → 全面的に破れる
- 逆（RSA 問題が解ければ素因数分解できる）は未証明だが、実質同等と考えられている
素因数分解の計算量
| アルゴリズム | 計算量 |
|---|---|
| 試し割り | \(O(\sqrt n)\) |
| Pollard ρ | \(O(n^{1/4})\) |
| 二次篩 (QS) | \(L_n[1/2]\) |
| 一般数体篩 (GNFS) | \(L_n[1/3, 1.923]\)（現在最良） |
記録: RSA-250（829 ビット）が 2020 年に分解された（約 2700 CPU コア年）。
推奨鍵長: 2048 ビット以上（2030 年まで）、長期なら 3072 ビット以上。
5. 実装上の落とし穴（ここが実務で最重要）
(a) 教科書 RSA は使ってはいけない
\(C = M^e \bmod n\)をそのまま使うと、以下の問題がある:
① 決定的である: 同じ平文は必ず同じ暗号文になる。 平文の候補が少ない場合（「はい/いいえ」など）、全部暗号化して比較すれば分かる。
② 乗法準同型性:
攻撃者は平文を知らないまま暗号文を操作できる。 これを使うと選択暗号文攻撃で秘密鍵なしに復号できる（ブラインディング攻撃）。
(b) パディング方式
| 方式 | 用途 | 状態 |
|---|---|---|
| PKCS#1 v1.5 | 暗号化 | 非推奨（Bleichenbacher 攻撃） |
| OAEP | 暗号化 | 推奨 |
| PSS | 署名 | 推奨 |
OAEP はランダム性を注入して確率的にし、CCA 安全性を持たせる。
Bleichenbacher 攻撃（1998）の教訓. PKCS#1 v1.5 では、復号後にパディング形式が正しいかを検査する。 サーバが「パディング不正」というエラーを返すと、攻撃者はそれをオラクルとして使い、 約 100 万回の問い合わせで暗号文を復号できてしまう。
12 章で「選択暗号文攻撃は非現実的ではない」と述べた実例がこれである。 しかも 20 年以上経った 2017 年にも ROBOT 攻撃として、 Facebook や PayPal を含む多数のサーバに同じ脆弱性が残っていることが判明した。
(c) 素数生成の失敗
同じ素数を再利用すると即座に破れる: 2 つの公開鍵\(n_1 = pq_1\)、\(n_2 = pq_2\)が 共通の\(p\)を持つと、\(\gcd(n_1,n_2) = p\)がユークリッドの互除法で一瞬で求まる。
2012 年の大規模調査で、インターネット上の TLS 証明書の約 0.5% が 他の証明書と素数を共有しており、秘密鍵が計算可能だった（乱数生成器の初期化不良が原因）。
(d) サイドチャネル攻撃
- タイミング攻撃: べき乗の計算時間から\(d\)のビットが漏れる → 定数時間実装が必須
- 電力解析 (SPA/DPA): 消費電力波形から鍵が読める
- フォールト攻撃: CRT 高速化中にエラーを注入すると\(\gcd\)で\(q\)が求まる（15 章）
6. RSA の現在地
RSA は「枯れた技術」になりつつある.
- 鍵が長い（3072 ビット vs 楕円曲線 256 ビット）
- 署名・鍵交換とも楕円曲線のほうが高速
- 量子コンピュータのショアのアルゴリズムで多項式時間で破られる（ただし RSA だけでなく 楕円曲線も同様）
TLS 1.3 では鍵交換から RSA が外され、楕円曲線ディフィー・ヘルマン (ECDHE) が標準になった。 RSA は署名用途と、既存システムとの互換性のために残っている。
とはいえ RSA は公開鍵暗号の原理を学ぶ最良の教材である。 「オイラーの定理を使えば、公開鍵で暗号化し秘密鍵で復号できる」という論理は、 数論と暗号が結びついた歴史的瞬間そのものである。
7. まとめ
| 項目 | 内容 |
|---|---|
| 鍵生成 | \(n=pq\)、\(ed\equiv1 \pmod{\varphi(n)}\) |
| 暗号化 / 復号 | \(C=M^e\)、\(M=C^d\) |
| 正しさの根拠 | オイラーの定理 + フェルマー + CRT（15 章） |
| 安全性 | 素因数分解の困難性 |
| 高速化 | 繰り返し二乗法（01 章）、CRT（15 章） |
| 実務の鉄則 | 教科書 RSA を直接使わない。OAEP/PSS を使う |