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 ✓）
暗号化・復号を手で確認
上で求めた 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 | 51 |
| 437 | 19 × 23 | 198 | 5 | 41 |
例：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 | 約10617 | ハイブリッド暗号の鍵交換 | 現在の標準（TLS, SSL等） |
なぜRSAは安全なの？
RSAの安全性は、「大きな数の素因数分解が極めて困難」という数学的性質に依存している。
⚠️ RSAの解読への脅威
- 2009年：768bitの素因数分解に成功（スーパーコンピュータで数年）
- 現在：1024bitの解読法を探索中（安全とは言い切れない）
- 現在の標準：2048bit以上を推奨（NIST勧告）
- 将来の脅威：量子コンピュータのShorアルゴリズムによる高速因数分解
楕円曲線暗号（ECC）：ビットコインが実際に使う技術
ビットコインが実際に使っているのはRSAではなく楕円曲線暗号（ECC）です。RSAよりも短い鍵長で同等の安全性を実現できる点が特徴。楕円曲線上の「離散対数問題」という数学的な困難性が、秘密鍵の安全性を保証しています。
T：公開鍵 s：秘密鍵（数百桁の整数） G：楕円曲線上の基準点
TとGからsを逆算するのは現実的な時間では不可能
🚀 RSAを実際に体験してみよう
計算の仕組みを理解したら、実際にRSA暗号を体験できる「RSAプレイグラウンド」で試してみよう！