📝 この記事の目次
✨ RSA暗号の安全性の根拠：素因数分解問題
RSA暗号の安全性は、「大きな数の素因数分解が非常に難しい」という数学的事実に基づいています。
💡 素因数分解の非対称性
掛け算：61 × 53 = 3233（一瞬で計算できる）
素因数分解：3233 = ? × ?（試行が必要、小さい数なら解けるが…）
実際のRSA暗号では2048ビット（617桁）以上の数を使うため、現在の最速のスパコンをもってしても現実的な時間内での解読は事実上不可能とされています。
🔗 RSA暗号の計算手順：公開鍵・秘密鍵の生成5ステップを確認しよう
📚 前提知識の確認
RSA鍵生成の5ステップ（p・q選択→n計算→φ(n)→e選択→d計算）の具体的な数値計算は、公開鍵暗号（STEP4）の専門記事でp=3・q=11の小さな数値例を使って詳しく解説しています。
→ RSAの数学を手計算で理解する（暗号化・復号の数値例）この記事では「なぜその手順なのか」という数学的な根拠と、現実の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とnが互いに素であれば (m^e)^d ≡ m (mod n) が成り立つ。
（実際のRSAではp・qが非常に大きいため、この条件は実質的に常に満たされます。）
つまり「公開鍵で暗号化したメッセージは、秘密鍵で必ず元に戻る」ことが数学的に証明されているのです。
💡 なお、現代のRSA実装（NISTガイドライン等）では、オイラーのφ(n)より小さな値であるカーマイケルのλ(n)（最小公倍数ベース）を使うことが推奨されています。入門解説としてはφ(n)で問題ありませんが、実際の実装ではλ(n)が使われている点は知っておくと◎です。
「秘密鍵を持っている人だけが元に戻せる」ことが数式で証明されてるんだよ。この数学的な確実性こそがRSA暗号の強さね🐾 実際のRSAでは e や d の計算はコンピュータがやってくれるよ！
🔸 RSA暗号の推奨鍵長：2048bitが現在の標準である理由
| 鍵長 | nの桁数 | 現在の安全性 | 主な用途 |
|---|---|---|---|
| RSA-512 | 155桁 | ❌ 廃止（解読済み） | - |
| RSA-1024 | 309桁 | ⚠ 非推奨 | レガシーシステム |
| RSA-2048 | 617桁 | ✅ 現行標準（NIST推奨） | HTTPS・TLS |
| RSA-4096 | 1234桁 | ✅ 長期保存向け | 証明書・PGP |
💡 NIST SP 800-131A Rev.2 等では、2030年まではRSA-2048が許容されますが、2031年以降はより安全なRSA-3072以上への移行が求められています。
📌 まとめ：RSA鍵生成のポイント
- RSA暗号の鍵は「2つの大きな素数 p, q を掛け合わせた n」に基づく
- 公開鍵 (e, n)：誰でも使えるが、暗号化にしか使えない
- 秘密鍵 (d, n)：p, q を知る人だけが計算でき、復号に使える
- 安全性の根拠：n を素因数分解して p, q を求めることが計算上不可能なこと
- 現在の標準はRSA-2048。長期保護はRSA-4096を推奨
- ビットコイン等の暗号資産の秘密鍵は、RSAではなく楕円曲線暗号（ECC: secp256k1）を使用。ただし「秘密鍵の一方向性」という根本原理はRSA暗号と同じ
本サイトのRSA暗号の解説は、仕組みをわかりやすく理解するための「教育用（Textbook RSA）」として簡略化されています。
- 実際のシステムでは、十分な鍵長（RSA-2048以上など）が必要です。
- 解説されている純粋なRSA（パディングなし）のままでは、同じメッセージが常に同じ暗号文になるなどの脆弱性があります。実際の通信や開発では、必ずOAEPなどのパディング方式を適用した安全なライブラリを使用してください。
📚 参考文献・情報源
- Rivest, R. L., Shamir, A., & Adleman, L. (1978). A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM, 21(2), 120–126.
- NIST SP 800-131A Rev.2 — Transitioning the Use of Cryptographic Algorithms and Key Lengths
- NIST Post-Quantum Cryptography プロジェクト
※ この記事の技術情報はNISTガイドラインおよび暗号学の標準的な文献に基づいています。
