🔐RSAの鍵はどうやって作る？鍵生成の仕組みと数理的背景

🔍 鍵がなければ始まらない！RSAのはじまりは「素数選び」から

RSA暗号の安全性の土台となるのが、2つの大きな素数です。これを「p」と「q」とします。

• たとえば、p = 61、q = 53 のように選びます。
• ただし実際には、数百桁にも及ぶ超巨大素数が選ばれます。

この2つの素数こそが、RSAの最初のパズルピース。セキュリティの要なのです。

---

🧮 共通の値「N」を作ろう！p × q の計算が始まり

2つの素数 p, q を選んだら、次はその積を計算して「N」を作ります。

• 計算式は： N = p × q
• N は、公開鍵と秘密鍵の両方で使われる重要な値

この N の大きさがそのままRSA暗号の“強さ”を表します。300桁を超えるNも珍しくありません。

---

📐 オイラー関数「φ(N)」ってなに？鍵生成のカギを握る数式

次に求めるのが「オイラーのトーシェント関数（φ関数）」です。

• φ(N) = (p – 1) × (q – 1)

この φ(N) は、「Nと互いに素な数がいくつあるか」を表す値で、RSA暗号の核とも言える存在です。

---

🔑 公開鍵「E」を決めよう！φ(N)と“仲が悪い”数を探すにゃ

次に、「E（公開鍵の指数）」を決定します。

• 条件は： 1 < E < φ(N) かつ Eとφ(N)が互いに素
• よく使われるEの例： 65537（素数）

Eは公開されるため、誰でも使って暗号化ができる数値。セキュリティ上のバランスと計算効率の良さから、65537が選ばれることが多いです。

---

🛡️ 秘密鍵「D」を求める魔法の式！Eの逆数をmodで探せ

公開鍵Eが決まったら、次に秘密鍵Dを求めます。

Dの条件は：

• E × D ≡ 1 (mod φ(N))

つまり、EとDはmod φ(N) における「逆数」の関係です。

この計算は、「拡張ユークリッド互除法」というアルゴリズムを使って行われます。

---

🧷 公開鍵と秘密鍵はこうやって使う！セットで役割分担

ここまでで以下のような鍵ペアが生成されました：

• 🔓 公開鍵： (E, N)
• 🔐 秘密鍵： (D, N)

使用方法は次のとおりです：

1. 送信者が「公開鍵」を使って暗号化
2. 受信者が「秘密鍵」を使って復号

公開鍵は誰とでも共有可能。でも、秘密鍵は絶対に他人に見せてはいけません！

---

🚀 暗号の裏にある高速計算：バイナリ法で効率UP！

RSA暗号での暗号化・復号の計算は「べき乗剰余計算」と呼ばれ、非常に大きな数を扱います。

そこで登場するのが「バイナリ法」という高速計算のテクニック。

バイナリ法のポイント：

• 指数（EやD）を2進数に変換
• 各ビットに応じて計算を分岐
• 不要な掛け算を避け、計算を最小化！

これにより、何百桁ものべき乗計算が数十回の処理で完了できるのです。

---

📘 まとめ：数のチカラで生まれる“見えない盾”

RSA暗号の鍵生成は、次のようなステップで行われます：

1. 大きな素数を2つ選ぶ（p, q）
2. 積をとってNを作る（N = p × q）
3. φ(N) = (p – 1) × (q – 1) を計算
4. E（公開鍵）を決定（φ(N)と互いに素）
5. D（秘密鍵）を計算（E × D ≡ 1 mod φ(N)）

このすべてのステップに“数学の知恵”が詰まっていて、計算だけで情報の安全が守られているのです。