✨ RSA暗号の安全性の根拠：素因数分解問題
RSA暗号の安全性は、「大きな数の素因数分解が非常に難しい」という数学的事実に基づいています。
💡 素因数分解の非対称性
掛け算：61 × 53 = 3233（一瞬で計算できる）
素因数分解：3233 = ? × ?（試行が必要、小さい数なら解けるが…）
実際のRSAでは2048ビット（600桁以上）の数を使うため、現在のスパコンでも解読に数百万年かかると言われています。
🔗 基本の計算例はSTEP1で確認しよう
📚 前提知識の確認
RSA鍵生成の5ステップ（p・q選択→n計算→φ(n)→e選択→d計算）の具体的な数値計算は、暗号の基礎（STEP1）の専門記事でp=3・q=11の小さな数値例を使って詳しく解説しています。
→ RSA暗号の計算を完全解説｜暗号化・復号の数値例と繰り返し二乗法この記事では「なぜその手順なのか」という数学的な根拠と、現実のRSAが実際にどう動くかを深掘りするよ。
🔍 各ステップの「なぜ」——数学的根拠を深掘り
なぜ e = 65537 が標準なのか？
e = 65537 = 2¹⁶ + 1 は「フェルマー素数」で、以下の利点があるため事実上の標準です：
- 計算効率が極めて高い：65537の2進数表現は「10000000000000001」で1が2つだけ。冪乗計算（m^e mod n）で必要な掛け算の回数が最少になる。
- e = 3 などの小さすぎる値のリスクを回避：eが小さいとCoppersmithの攻撃に脆弱になる場合がある。65537はその心配がない。
- 互いに素の保証：多くのランダムな素数p, qに対してφ(n)と互いに素になりやすい。
φ(n)が秘密でなければならない理由
φ(n) = (p−1)(q−1) を攻撃者が知れば、秘密指数 d を計算できます（d は e × d ≡ 1 (mod φ(n)) の解）。φ(n)を秘密にするためには「p と q そのものを秘密にする」必要があります。つまりRSAの安全性は最終的に「巨大な n を素因数分解して p と q を割り出すことが実質不可能であること」に帰着します。
なぜRSAは必ず後一に戻るのか？——フェルマーの小定理
📌 数学的証明のエッセンス
フェルマーの小定理：pが素数でaがpの倍数でなければ、a^(p-1) ≡ 1 (mod p)
RSAではこれを拡張した「オイラーの定理」を使います：
e × d ≡ 1 (mod φ(n)) が成り立つとき、(m^e)^d ≡ m (mod n) が成り立つ。
つまり「公開鍵で暗号化したメッセージは、秘密鍵で必ず元に戻る」ことが数学的に証明されているのです。
「秘密鍵を持っている人だけが元に戻せる」ことが数式で証明されてるんだよ。この数学的な確実性こそがRSAの強さね🐾 実際のRSAでは e や d の計算はコンピュータがやってくれるよ！
🔸 現実のRSAで使われる鍵長
| 鍵長 | nの桁数 | 現在の安全性 | 主な用途 |
|---|---|---|---|
| RSA-512 | 155桁 | ❌ 廃止（解読済み） | - |
| RSA-1024 | 309桁 | ⚠ 非推奨 | レガシーシステム |
| RSA-2048 | 617桁 | ✅ 現行標準 | HTTPS・TLS |
| RSA-4096 | 1234桁 | ✅ 長期保存向け | 証明書・PGP |
📌 まとめ：RSA鍵生成のポイント
- RSAの鍵は「2つの大きな素数 p, q を掛け合わせた n」に基づく
- 公開鍵 (e, n)：誰でも使えるが、暗号化にしか使えない
- 秘密鍵 (d, n)：p, q を知る人だけが計算でき、復号に使える
- 安全性の根拠：n を素因数分解して p, q を求めることが計算上不可能なこと
- 現在の標準はRSA-2048。長期保護はRSA-4096を推奨
- 暗号資産の秘密鍵も、公開鍵暗号の数学的な性質に基づいている