Chapter 16
RSA — 素因数分解の困難性に賭ける
この章の位置づけ. 1976 年まで、暗号を使うには送り手と受け手があらかじめ秘密の鍵を共有している必要があると考えられていた。 ディフィーとヘルマンがこの前提を覆す考え方を発表し（17 章）、1977 年に MIT の Rivest、Shamir、Adleman が具体的な公開鍵暗号を作った。それがRSAである。 鍵を 2 つに分け、暗号化の鍵を誰にでも公開しても安全でいられる理由を、15 章の道具で導く。
この章で使う既出の用語（定義は各リンク先）. \(a \bmod n\)と\(a \equiv b \pmod n\)・\(\gcd\)・逆元と拡張ユークリッドの互除法（01 章）、繰り返し二乗法（01 章 6 節）、位数（02 章 1 節）、 パディング・選択暗号文攻撃・オラクル（12 章 3 節）、タイミング攻撃（13 章 5 節）、 \(\varphi(n)\)（15 章 1 節）、オイラーの定理とフェルマーの小定理（15 章 2 節）、中国剰余定理と RSA の高速化・Bellcore 攻撃（15 章 3 節）、準指数時間と\(L_n[\cdot]\)の記法（15 章 5 節）、ミラー・ラビン・テスト（15 章 6 節）
1. 鍵生成
- 大きな素数\(p, q\)をランダムに選ぶ（それぞれ 1024 ビット以上）。ランダムな奇数を作ってはミラー・ラビン・テストにかけ、素数が出るまで繰り返す。
- \(n = pq\)を計算する（公開）。
- \(\varphi(n) = (p-1)(q-1)\)を計算する（秘密）。
- \(\gcd(e, \varphi(n))=1\)となる\(e\)を選ぶ（公開）。通常は\(e = 65537\)を使う。
- \(ed \equiv 1 \pmod{\varphi(n)}\)となる\(d\)、つまり\(e\)の法\(\varphi(n)\)での逆元を計算する（秘密）。手順 4 の\(\gcd(e, \varphi(n)) = 1\)は、この逆元が存在するための条件である。拡張ユークリッドの互除法で\(ex + \varphi(n)y = 1\)となる\(x, y\)を求めれば、\(x \bmod \varphi(n)\)が\(d\)である。
| 公開鍵 | 秘密鍵 | |
|---|---|---|
| 構成 | \((n, e)\) | \((n, d)\)、および\(p, q, \varphi(n)\) |
\(e = 65537\)を使う理由: \(65537 = 2^{16}+1\)は素数で、2 進表現が10000000000000001と 1 が 2 個だけである。繰り返し二乗法では 2 乗 16 回と掛け算 1 回で済み、暗号化が速い。 \(e = 3\)のように小さすぎると危険である。平文\(M\)が短く\(M^3 < n\)になると、\(\bmod n\)の余りを取る操作が何もしないので、暗号文\(C = M^3\)の普通の 3 乗根を取るだけで\(M\)が分かってしまう（低指数攻撃）。65537 は速さと安全のバランスが良い値である。
2. 暗号化と復号
平文を\(0 \leq M < n\)の整数で表し、
で暗号化・復号する。上の図で小さな素数を選ぶと、鍵生成から暗号化・復号までの全手順が表示される。
3. なぜ復号できるのか（正しさの証明）
示すこと: \(0 \leq M < n\)のすべての\(M\)について\((M^e)^d \equiv M \pmod n\)。
方針: \(M\)が\(n\)と互いに素ならオイラーの定理がそのまま使える。互いに素でない場合は、法\(p\)と法\(q\)に分けて考え、中国剰余定理で合わせる。
準備
\(d\)の定義より\(ed \equiv 1 \pmod{\varphi(n)}\)なので、ある整数\(k \geq 0\)があって
と書ける。
場合 1: gcd(M, n) = 1 のとき
オイラーの定理（15 章 2 節）より\(M^{\varphi(n)} \equiv 1 \pmod n\)なので
場合 2: gcd(M, n) ≠ 1 のとき
見落とされやすいが、この場合も必要である。\(n = pq\)の約数は\(1, p, q, pq\)だけなので、\(\gcd(M, n) \neq 1\)なら\(M\)は\(p\)か\(q\)の倍数である。 \(M = 0\)なら\(0^{ed} = 0 = M\)で成り立つので、以下\(1 \le M < n\)とし、\(M\)が\(p\)の倍数だとする（\(q\)の倍数の場合も同様）。
法\(p\)で見る: \(M \equiv 0 \pmod p\)なので\(M^{ed} \equiv 0 \equiv M \pmod p\)。
法\(q\)で見る: \(M\)が\(q\)の倍数でもあれば\(pq = n\)の倍数になり\(1 \le M < n\)に反するので、\(\gcd(M,q)=1\)である。フェルマーの小定理より\(M^{q-1}\equiv1 \pmod q\)で、\(\varphi(n)=(p-1)(q-1)\)なので
合わせる: \(M^{ed}\)と\(M\)は法\(p\)でも法\(q\)でも合同である。\(p, q\)は互いに素なので、中国剰余定理の一意性（15 章 3 節）より\(M^{ed}\equiv M \pmod{n}\) ∎
オイラーの定理、フェルマーの小定理、中国剰余定理という 15 章の 3 つの道具が、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\)を繰り返し二乗法で計算する。\(17 = 16 + 1\)なので\(65^{16}\)と\(65^1\)が必要である。2 乗を繰り返して（毎回 3233 で割った余りを取る）
よって\(C \equiv 789 \times 65 = 51285 = 15 \times 3233 + 2790\)で、\(C = 2790\)である。
復号: \(2790^{2753} \bmod 3233\)を求める。\(2753 = 2048 + 512 + 128 + 64 + 1\)なので、2 乗を 11 回繰り返して
を作り、この 5 つを掛け合わせる（掛け算 4 回）と 65 に戻る。\(2790\)を 2752 回掛けるのに比べてずっと速い。
CRT を使った復号（15 章 3 節）: 指数を\(d \bmod (p-1) = 2753 \bmod 60 = 53\)、\(d \bmod (q-1) = 2753 \bmod 52 = 49\)に減らし、小さな法で計算する。
\(M \equiv 4 \pmod{61}\)、\(M \equiv 12 \pmod{53}\)を中国剰余定理で解く。\(53^{-1} \bmod 61 = 38\)、\(61^{-1} \bmod 53 = 20\)なので
となり、同じ 65 が得られる。
4. 安全性
頼っている困難性
RSA 問題: \(n, e, C\)から、\(M^e \equiv C \pmod n\)を満たす\(M\)（法\(n\)での「\(e\)乗根」）を求める問題。
これは素因数分解問題と強く関係している。
- \(n\)を素因数分解できれば、\(\varphi(n)\)が分かり、\(d\)が計算でき、RSA は完全に破れる。
- 逆に、RSA 問題が解ければ素因数分解できるかどうかは証明されていない。ただし 40 年以上、素因数分解を経由しない解き方は見つかっておらず、実務では「RSA を破ることは素因数分解すること」とみなして鍵長を決めている。
素因数分解の計算量
| アルゴリズム | 計算量 |
|---|---|
| 試し割り | \(O(\sqrt n)\) |
| Pollard の ρ 法 | \(O(n^{1/4})\) |
| 二次ふるい法 (QS) | \(L_n[1/2]\)（準指数時間） |
| 一般数体ふるい法 (GNFS) | \(L_n[1/3, 1.923]\)（現在最良） |
\(L_n[\alpha, c] = \exp\!\left(c\,(\ln n)^{\alpha}(\ln\ln n)^{1-\alpha}\right)\)は15 章 5 節で出た準指数時間の記法である。\(\alpha\)が小さいほど速く、\(\alpha = 1/3\)の GNFS は\(n\)がおよそ 100 桁を超えるとほかの方法より速い。
記録: RSA-250（250 桁、829 ビット）が 2020 年に分解された。計算量は約 2700 コア年（CPU コア 1 個を 1 年動かした仕事量の 2700 倍）だった。
推奨鍵長: 2030 年までは 2048 ビット以上、それ以降も使うなら 3072 ビット以上。
5. 実装上の落とし穴（ここが実務で最重要）
(a) 教科書どおりの RSA は使ってはいけない
\(C = M^e \bmod n\)をそのまま使うと、次の問題がある。
① 同じ平文は必ず同じ暗号文になる: 平文の候補が少ない場合（「はい」か「いいえ」など）、攻撃者は公開鍵で候補を全部暗号化して比べれば、平文が分かる。
② 暗号文どうしを掛けられる（乗法準同型性）:
攻撃者は平文を知らないまま暗号文を操作できる。これを使うと、「どんな暗号文でも復号してくれるが、狙いの\(C\)だけは断る」相手（選択暗号文攻撃の設定）から、\(C\)の平文を引き出せる。 乱数\(r\)を選んで\(C' = C \cdot r^e \bmod n\)を復号してもらうと、返ってくるのは\(M' = (M^e r^e)^d \equiv M r \pmod n\)である。\(C'\)は\(C\)と無関係に見えるので断られない。あとは\(M = M' \cdot r^{-1} \bmod n\)で\(M\)が求まる（ブラインディング攻撃）。
(b) パディング方式
平文\(M\)をそのまま\(e\)乗せず、乱数や決まった書式を付け足して\(n\)未満の整数に整形してから暗号化する。この整形をパディングという。① と ② はどちらも\(M\)をそのまま使うことが原因なので、パディングで防ぐ。
| 方式 | 用途 | 状態 |
|---|---|---|
| PKCS#1 v1.5 | 暗号化 | 非推奨（Bleichenbacher 攻撃） |
| OAEP | 暗号化 | 推奨 |
| PSS | 署名 | 推奨 |
OAEPは乱数を混ぜ込むので、同じ平文でも毎回違う暗号文になる。さらに、形式の正しくない暗号文は復号されないように作られており、選択暗号文攻撃に対しても安全であることが（ハッシュ関数を理想化したモデルのもとで）証明されている。
Bleichenbacher 攻撃（1998 年）: PKCS#1 v1.5 では、復号後にパディングの書式が正しいかを検査する。サーバが「パディングが不正」というエラーを返すと、攻撃者はサーバを、自分の作った暗号文が正しい書式に復号されるかどうかを答えてくれるオラクル（中身は見せないが問い合わせには答える相手）として使える。 ② の性質を使って\(C \cdot r^e\)の形の暗号文を大量に送り、書式が合う\(r\)を集めて\(M\)の範囲を絞り込んでいくと、1024 ビットの鍵で数十万〜百万回程度の問い合わせで暗号文を復号できてしまう。 12 章 3 節で「選択暗号文攻撃は非現実的ではない」と述べた実例である。20 年近く後の 2017 年にも、Facebook や PayPal を含む多数のサーバに同じ脆弱性が残っていることがROBOT 攻撃として報告された。
(c) 素数生成の失敗
同じ素数を使い回すと、すぐに破れる: 2 つの公開鍵\(n_1 = pq_1\)、\(n_2 = pq_2\)が共通の素数\(p\)を持つと、\(\gcd(n_1,n_2) = p\)がユークリッドの互除法ですぐに求まる。 2012 年の大規模な調査では、インターネット上の TLS の公開鍵の約 0.5% がほかの鍵と素数を共有しており、秘密鍵が計算できる状態だった。機器の起動直後に乱数生成器が十分に初期化されていなかったことが原因である。
(d) サイドチャネル攻撃
計算の結果以外に漏れる情報（時間、消費電力など）から秘密を推定する攻撃をサイドチャネル攻撃という。
- タイミング攻撃: 繰り返し二乗法は\(d\)のビットが 1 のときだけ掛け算を 1 回多く行うので、計算時間を精密に測ると\(d\)のビットが漏れる。対策として、どのビットでも同じ命令を同じ時間で実行する定数時間実装（ビットが 0 でも掛け算をして結果を捨てる、など）が必要である。
- 電力解析: 消費電力の波形から掛け算の有無が読める。1 回の波形を直接読む SPA（単純電力解析）と、多数の波形を統計処理する DPA（差分電力解析）がある。
- フォールト攻撃: CRT で高速化した計算の途中に誤りを起こさせると、\(\gcd\)で\(q\)が求まる（15 章 3 節の Bellcore 攻撃）。
6. RSA の現在地
RSA は使われる場面が減りつつある。
- 同じ安全性に必要な鍵が長い（3072 ビット。楕円曲線なら 256 ビット、15 章 5 節）。
- 署名も鍵交換も、楕円曲線を使うほうが速い。
- 十分大きな量子コンピュータがあれば、ショアのアルゴリズムで多項式時間で破られる。ショアのアルゴリズムは、\(a^x \bmod n\)が\(x\)について繰り返す周期（\(a\)の位数）を量子計算で求め、位数から\(\gcd\)の計算で\(n\)の素因数を得る方法である。楕円曲線暗号も同様に破られる。ただし、そのような量子コンピュータはまだ作られていない。
TLS 1.3 では RSA による鍵交換が廃止され、楕円曲線ディフィー・ヘルマン鍵交換（ECDHE、17 章）が標準になった。RSA は署名と、既存システムとの互換性のために残っている。 それでも RSA は、オイラーの定理によって「公開鍵で暗号化し、秘密鍵で復号する」仕組みが成り立つことを見るのに最も分かりやすい例である。