📖 この記事でわかること
- RSA暗号の鍵生成4ステップ（p・q選択→N計算→L算出→E・D決定）
- 小さな数値（p=3, q=5）を使った手計算での暗号化・復号の体験
- インタラクティブツールで任意の素数での鍵生成をシミュレーション
- 9bit〜2048bitまで、ビット数と安全性・用途の違い
- RSA暗号の現実の脅威と量子コンピュータ対策の現状
⚡ 30秒でわかるRSAの全体像
- 2つの素数 p, q から公開鍵（N, E）と秘密鍵（D）を生成
- 送信者は公開鍵Eで暗号化：
C = ME mod N - 受信者は秘密鍵Dで復号：
M = CD mod N - 素因数分解の困難性により、Nが公開されても秘密鍵は割り出せない
RSA暗号は「大きな素数の掛け算は簡単だけど、答えから元の素数を求めるのは超難しい」という性質を使った暗号です。でも「難しい」と言われても実感がわかないかもしれません。そこで今回は、実際に手で計算できる小さな数値で動きを確認してみましょう！
RSA鍵生成の4ステップ
RSAの鍵生成は次の4つのステップで行います。これを「小さな数」で確認してみましょう。
🔑 鍵生成の流れ（p = 3, q = 5 の例）
p = 3, q = 5 → N = 3 × 5 = 15
L = lcm(3-1, 5-1) = lcm(2, 4) = 4
E = 3（gcd(3, 4) = 1 ✓）
3 × D mod 4 = 1 → D = 11（3×11=33, 33 mod 4 = 1 ✓） ※ D は「3, 7, 11, 15…」（L=4の倍数を加えた値）がすべて数学的に有効です。上の計算ツールでは最小値の D=3 が表示されますが、どちらを使っても正しく復号できます。
暗号化・復号を手で確認
上で求めた N=15, E=3, D=11 を使って、実際に平文 M = 7 を暗号化・復号してみましょう。
📝 暗号化の計算（M = 7 → 暗号文 C）
公式：C = ME mod N
計算：C = 73 mod 15 = 343 mod 15
343 ÷ 15 = 22 余り 13（22 × 15 = 330, 343 - 330 = 13）
➡️ 暗号文 C = 13
✅ 復号の計算（C = 13 → 平文 M）
公式：M = CD mod N
計算：M = 1311 mod 15
1311 = 1,792,160,394,037… （大きい！）
これ mod 15 を計算すると → 7
➡️ 復号結果 M = 7（元の平文に戻った！ ✓）
🧮 RSA手計算ウォークスルーツール
2つの素数を入力すると、鍵生成・暗号化・復号のステップを自動で計算して表示します。小さな素数（3〜20程度）から試してみてください！
🔐 RSA鍵生成ウォークスルー
📋 もっとリアルな例：9bit RSA（N = 323）
手計算では小さな数で確認しましたが、実際に使うにはもっと大きな数が必要です。以下は 9bit（N が9桁二進数）の鍵ペアの例です。上記の計算と同じ4ステップで生成されています。
📊 9bit RSA 鍵ペアリスト
| N（法） | 素数の積 | L | E（公開鍵） | D（秘密鍵） |
|---|---|---|---|---|
| 323 | 17 × 19 | 144 | 17 | 17 |
| 391 | 17 × 23 | 176 | 19 | 139 |
| 437 | 19 × 23 | 198 | 5 | 119 |
例：N=323, E=17, D=17 → 平文 M=7 を暗号化 → C = 717 mod 323 を計算
9bitのN=323だと、平文は1〜322の整数に対応。ASCII文字1文字（8bit = 0〜255）を暗号化するのに使えるよ🐾
でも現実のRSAは2048bit以上！素数も何百桁もある数を使うんだ。
ビット数と送れるメッセージ量の関係
RSAで暗号化できる平文のサイズは、Nのビット数によって決まります。
| ビット数 | N の最大値 | 送れるメッセージの目安 | 現実の用途 |
|---|---|---|---|
| 4bit | 15 | 1〜14の整数（手計算の例） | 学習・演習用 |
| 9bit | 511 | ASCII 1文字（0〜255） | 演習・体験用 |
| 17bit | 131,071 | ASCII 2文字（0〜65535） | 演習用 |
| 2048bit | 約10616 | ハイブリッド暗号の鍵交換 | 現在の標準（TLS, SSL等） |
なぜRSAは安全なの？
RSAの安全性は、「大きな数の素因数分解が極めて困難」という数学的性質に依存しています。
⚠️ RSAの解読への脅威
- 2009年：768bitの素因数分解に成功（大規模分散コンピューティングで約2年（約２000コア年相当））
- 現在：1024bitの解読法を探索中（安全とは言い切れない）
- 現在の標準：2048bit以上を推奨（NIST勧告）
- 将来の脅威：量子コンピュータのShorアルゴリズムによる高速因数分解
本サイトのRSA暗号の解説は、仕組みをわかりやすく理解するための「教育用（Textbook RSA）」として簡略化されています。
- 実際のシステムでは、十分な鍵長（RSA-2048以上など）が必要です。
- 解説されている純粋なRSA（パディングなし）のままでは、同じメッセージが常に同じ暗号文になるなどの脆弱性があります。実際の通信や開発では、必ずOAEPなどのパディング方式を適用した安全なライブラリを使用してください。
🔗 関連コンテンツ
