RSA暗号 — 素因数分解の難しさが錠前になる

「掛け算は一瞬、素因数分解は絶望的」という計算の非対称性から、誰でも施錠できるが本人しか開けられない南京錠を作る。鍵の生成から暗号化・復号、そして安全性の根拠まで、公開鍵暗号の代表 RSA を数を動かしながら分解します。

1. 公開鍵という発想 — 施錠と解錠を別の鍵に分ける

共通鍵暗号は高速ですが、「その鍵をどうやって相手に渡すか」という鍵配送問題がつきまといます。RSA の答えはこうです — 施錠する鍵と解錠する鍵を別物にしてしまえばいい。

メタファーは開いた南京錠です。ボブは開いた南京錠（公開鍵）を世界中にばらまく。誰でもそれをパチンと閉じて箱に掛けられる（＝暗号化）。しかし開けられるのは、対になる鍵（秘密鍵）を持つボブただ一人（＝復号）。閉める操作と開ける操作が別の鍵なので、閉める鍵は隠す必要がないのです。

POINT — 非対称性のからくり RSA の土台は一方向性と落とし戸（トラップドア）の2段構え。①素数どうしの掛け算 p×q は一瞬だが、積 n から p, q を割り出す素因数分解は桁が増えると爆発的に困難（一方向性）。②ただし p, q を知る者だけは φ(n) を計算でき、そこから解錠用の d を作れる（落とし戸）。「誰にとっても難しいが、秘密を知る本人にだけ抜け道がある」— これが公開鍵暗号を可能にします。

2. 鍵生成工場 — 5ステップで鍵ペアを作る

RSA の鍵ペアは、素数2つから流れ作業で作られます。下の工場で p, q, e を選び、「次のステップ」を押して5工程を順に実行してください。各部品が公開してよいもの（緑）か絶対秘密（赤）かに注目を。ここでは目で追える小さな素数を使います（実物は各309桁級です）。

鍵生成工場 — p, q から公開鍵と秘密鍵ができるまで

素数 p

素数 q

公開指数 e

⑤の d は拡張ユークリッドの互除法で求めます（計算過程を表示）。完成後は p, q, φ(n) を破棄し、手元に残すのは d だけ。e に 3 など小さすぎる値を選ぶと gcd(e, φ(n)) ≠ 1 で弾かれることがあります — 実務では e = 65537 が定番です。

e · d ≡ 1 (mod φ(n))　ただし φ(n) = (p−1)(q−1) d は「φ(n) を知る者」にしか計算できない。そして φ(n) を知るには n の素因数分解が必要 — ここが落とし戸

3. 暗号化と復号 — e で施錠、d で解錠

鍵ができたら、あとは時計の算術（mod）の世界でべき乗するだけです。メッセージを数 m にして、公開鍵 (n, e) で c = m^e mod n（施錠）。受け取った側は秘密鍵 d で m = c^d mod n（解錠）。下のデモは教科書の定番例 p=61, q=53 → n=3233, e=17, d=2753 で、繰り返し2乗法の途中経過ごと再生します。

暗号化 ⇄ 復号の往復 — べき乗剰余のアニメーション

メッセージ m

使い方

切り替えると同じ鍵ペアが逆向きにも使えることが分かります。d で作った署名 s は「d の持ち主にしか作れない」ので、e で開けて m と一致すれば本人証明になる — この話は電子署名と証明書で本格的に扱います。

(m^e)^d = m^ed = m^1+kφ(n) = m · (m^φ(n))^k ≡ m · 1^k = m (mod n) オイラーの定理「m^φ(n) ≡ 1 (mod n)（m と n が互いに素のとき）」がちょうど1周して元に戻る理由。ed ≡ 1 (mod φ(n)) はこのために仕込んであった

つまり「e 乗してから d 乗する」と、指数の世界で ed = 1 + kφ(n) となり、φ(n) 乗ごとに 1 に戻る周期性のおかげでちょうど m に帰ってくるのです。順番を入れ替えて「d 乗してから e 乗」しても同じく戻る — これが署名モードの正体です。

4. 安全性の根拠 — 素因数分解の壁

盗聴者イブは n も e も c も知っています。それでも m を取り出せないのは、d を作るのに必要な φ(n) が、n の素因数分解なしには求まらないから。ではその素因数分解はどれくらい大変なのか。桁数のスライダーを動かして、壁の高さを体感してください。

素因数分解の壁 — 桁数と総当たりの試行回数

n の桁数

10桁以下ではブラウザが実際に試し割りして分解に成功します。11桁からは「毎秒1兆回試せる仮想スパコン」のシミュレーション。総当たり（試し割り）は √n ≈ 10^桁数/2 回かかります。実際の最速アルゴリズム（一般数体篩）は総当たりよりずっと賢いものの、それでも桁数に対して準指数的に爆発するため、RSA-2048（617桁 / 2048ビット）が現在の推奨サイズです。

ただしこの壁は「古典コンピュータにとっての壁」です。量子コンピュータのショアのアルゴリズムは素因数分解を多項式時間で解いてしまうため、大規模な量子機が実現すると RSA は根本から崩れます。「量子が来たら？」の答えはショアのアルゴリズムと耐量子暗号のレッスンへ。

注意 — RSA で長文をそのまま暗号化しない実際の通信で本文をまるごと RSA にかけることはありません。理由は2つ。①べき乗剰余は AES の数百〜数千倍遅い。②教科書どおりの RSA は同じ m から必ず同じ c ができる決定性があり、そのままでは安全でない（実装では OAEP などのランダムなパディングが必須）。実務はハイブリッド構成 — RSA や鍵交換で短い「AES の鍵」だけを守り、本文は共通鍵暗号で運ぶ。TLS のしくみでこの共演を見ます。

5. まとめ — RSA の設計図

鍵生成：素数 p, q → n = pq、φ(n) = (p−1)(q−1)、gcd(e, φ(n)) = 1 な e を選び、d = e⁻¹ mod φ(n)。公開鍵は (n, e)、秘密鍵は d。
暗号化 / 復号：c = m^e mod n、m = c^d mod n。オイラーの定理が「ちょうど元に戻る」ことを保証する。
逆向きに使えば署名：d で作り e で確かめる。作れるのは d の持ち主だけ。
安全性の根拠：n から p, q を割り出す素因数分解の困難さ。推奨は 2048 ビット以上、ただし量子計算機（ショア）には破られる。

一歩先へ — 発明は二度あった RSA は 1977 年、MIT の Rivest・Shamir・Adleman が発表しました（頭文字が名前の由来）。翌年の雑誌コラムで「129桁の n の分解には4京年かかる」と紹介されましたが、その懸賞問題 RSA-129 はわずか17年後の1994年、世界中の計算機をつないだ有志に分解されます — アルゴリズムと計算機の進歩は見積もりを軽々と裏切るという教訓です。さらに後の1997年、英諜報機関 GCHQ のクリフォード・コックスが1973年に同じ方式を発明していたことが機密解除で判明。歴史に残る発明が、四半世紀ものあいだ金庫の中で眠っていたのでした。