RSA：2つの素数から鍵ができる

2つの素数 p, q から n=pq と公開鍵 e・秘密鍵 d を作り、m^e mod n（暗号化）と m^d mod n（復号）が往復することを体感します。

素数 p —

素数 q —

公開指数 e の候補 —

平文の数 m —

秘密鍵 d をずらす +0

法 n = p × q

—

φ(n) = (p−1)(q−1)

—

公開鍵 (e, n)

—

秘密鍵 d ≡ e⁻¹ (mod φ)

—

鍵生成のレシピ（p, q → n, φ, e, d）

暗号化・復号の往復（m → c → m）

RSA では、まず2つの素数 p・q をかけて n = pq を作り、φ(n) = (p−1)(q−1) を求めます。
公開鍵 e は φ(n) と互いに素な数、秘密鍵 d は e·d ≡ 1 (mod φ) を満たす数（e の逆数）。(e, n) を公開し、d は秘密にします。
暗号化は c = m^e mod n、復号は m = c^d mod n。d がぴったり合えば元の m に戻り、d を1ずらすと復号が壊れます。スライダーで確かめましょう。

いま何が起きている？

ここがポイント

鍵は素数から生える ── p, q を決めれば n・φ・e・d まで芋づる式に決まる。
e と d は鏡像 ── e·d ≡ 1 (mod φ) なので m^(ed) ≡ m となり往復する。
d を1ずらすと壊れる ── 逆数の条件を外れた途端、復号結果は元に戻らない。これが秘密鍵の正体。
安全性は素因数分解の難しさ ── 公開の n から p, q を割り出せなければ d は作れない（トイ例は小さいので分解は簡単）。