p, q が素数でない場合は最近接の素数に丸められます。e は gcd(e, φ(n)) = 1 を満たす値が必要です。
左＝鍵対 (n, φ, e, d)／右＝暗号化フロー m → [^e mod n] → c → [^d mod n] → m'
RSA は素因数分解の困難性を安全性の根拠とする公開鍵暗号です。鍵生成は次の手順で行います。
2 つの素数 p, q を選び、公開モジュラスとオイラー関数を計算：
$$n = p\,q, \qquad \varphi(n) = (p-1)(q-1)$$
公開指数 e は φ(n) と互いに素：gcd(e, φ(n)) = 1。秘密指数 d は e の法 φ(n) における逆元（拡張ユークリッド互除法で計算）：
$$e\,d \equiv 1 \pmod{\varphi(n)}$$
暗号化と復号は、いずれも法 n のべき乗で行います：
$$c = m^{e} \bmod n, \qquad m' = c^{d} \bmod n$$
前提として 0 ≤ m < n が必要です。フェルマー・オイラーの定理から m' = m が保証されます。
RSA 暗号シミュレーターとは
🙋
RSA って名前は聞いたことあるんですけど、結局何をしてるんですか？このシミュレーターを開いたら数字がたくさん出てきて、ちょっとビビりました。
🎓
ざっくり言うと、2 つの素数 p, q を秘密に持っておいて、その積 n = p·q だけを公開する仕組みなんだ。上のシミュレーターの初期値だと p=11, q=13 で n=143。誰でも n を見られるけど、n から元の p, q を「素因数分解」するのが大変だから安全、という発想だよ。「鍵対」の箱を見ると、n と e は公開、p, q, d は秘密、と色分けしてあるはずだ。
🙋
じゃあ「e」と「d」は何ですか？「平文 m」を 42 にすると、暗号文が 81 になりましたけど。
🎓
e は公開指数、d は秘密指数。暗号化は $c = m^e \bmod n$ で、初期値だと $42^7 \bmod 143 = 81$。これが「c」の箱に出てる数字だね。手で計算すると、$42^2 = 1764 \equiv 48 \pmod{143}$、$42^4 \equiv 48^2 = 2304 \equiv 16$、最後に $42^7 = 42 \cdot 48 \cdot 16 = 32256 \equiv 81 \pmod{143}$ となる。電卓で追える範囲だ。
🙋
復号の方は？「d=103」って出てますけど、$81^{103}$ なんて手で計算できる気がしないんですが…
🎓
そこは「法べき乗（modular exponentiation）」というテクニックを使う。一気に巨大な数を作らずに、毎回 mod n を取りながら 2 乗を繰り返すんだ。シミュレーターの中では BigInt と二進展開で計算してる。重要なのは結果で、$81^{103} \bmod 143$ がちゃんと 42 に戻る。「m\'」の箱が緑色で 42 になってるなら、復号成功だ。
🎓
フェルマー・オイラーの定理が効いてる。$e \cdot d \equiv 1 \pmod{\varphi(n)}$ となるよう d を選んでいるから、$(m^e)^d = m^{ed} \equiv m \pmod n$ になる。実務では p, q を 1024 ビット級にして n を 2048 ビット以上に取るけど、原理はこのデモと同じだよ。「e」を変えてみると d も変わって、c も全然違う値になるのを試してみて。
よくある質問
なぜ素数 p, q を秘密にしないといけないのですか？
p, q が漏れると φ(n) = (p−1)(q−1) が即座に計算でき、e から d も拡張ユークリッド互除法で求められてしまうため、誰でも秘密鍵を再構成して復号できてしまいます。RSA の安全性の核心は「n を素因数分解して p, q を取り出すのが現実的な時間ではできない」ことに依存しており、p, q を直接知られた瞬間に、その仮定が無意味になります。
公開指数 e は通常 65537 と聞きますが、なぜですか？
65537 = 2¹⁶ + 1 は素数（フェルマー素数）で、ほとんどの φ(n) と互いに素になります。また 2 進数表現が「100000000000000001」と 1 が 2 つだけなので、法べき乗を二進展開で計算する際の積回数が極めて少なく、暗号化が高速です。一方で十分大きいため、e=3 のような小さすぎる指数で起こる Coppersmith 型の攻撃にも強い、というバランスから定番として使われています。
このデモを実際の通信に使ってもよいですか？
使ってはいけません。本ツールは仕組みを直感的に理解するための教育デモで、p, q を 100 未満の小さな素数に制限しています。n は 3 桁〜4 桁程度しかなく、誰でも数秒で素因数分解できてしまいます。実運用では n を 2048 ビット以上（10 進で 600 桁以上）にすることが現代の標準です。さらに実装ではパディング（OAEP など）と乱数化が必須で、教科書 RSA をそのまま使うのは禁忌とされています。
スライダーを動かしたら「m ≥ n」と警告が出ました。何が悪いのですか？
RSA は法 n のもとで計算するため、平文 m は 0 ≤ m < n を満たす必要があります。たとえば p=3, q=5 だと n=15 しかなく、m=42 は明らかに範囲外です。このとき m を暗号化しても、復号で「m mod n」しか復元できず、元の値 42 には戻れません。p, q を大きくして n を 100 以上にするか、m をもっと小さくしてください。実装では長いメッセージを「n 未満のブロック」に分割するか、共通鍵暗号と組み合わせるのが普通です。
実世界での応用
HTTPS / TLS の鍵交換と署名： Web ブラウザがサイトに接続するときの「鍵マーク」の裏側で、サーバー証明書の署名検証や、通信開始時の共通鍵交換のフォールバックとして RSA は今でも広く使われています。証明書チェーンを上にたどると、ルート CA の公開鍵による RSA 署名が出てくるのが普通です。
PGP / GnuPG によるメール暗号化と署名： 個人や企業のメール暗号化、ソフトウェアリリースの署名（Linux ディストリビューションのパッケージ署名など）で RSA 鍵対が長く利用されてきました。長期的な「身元」を担保する用途と相性がよく、人間が指紋（フィンガープリント）で鍵を確認する文化が根付いています。
SSH 公開鍵認証： サーバーへのリモートログインで広く使われる ssh-rsa 鍵は、まさに本デモと同じ仕組みの拡大版です。クライアントは秘密鍵 d でチャレンジに署名し、サーバーは登録済み公開鍵 (n, e) で検証します。最近は Ed25519 への移行も進んでいますが、RSA 4096 ビット鍵は依然現役です。
マイナンバーカードや IC カードの認証： e-Tax のログインや本人確認で使われる IC カードの中には、RSA 秘密鍵が安全な領域に格納されており、署名計算がカード内部で完結するよう設計されています。秘密鍵がカードから一切出ないため、PC が侵害されても鍵は守られる、という運用が成立します。
よくある誤解と注意点
最も多い誤解は、「教科書 RSA をそのまま実装すれば安全」と考えてしまう ことです。本シミュレーターで示しているのは「決定的な」RSA で、同じ平文を暗号化すると常に同じ暗号文になります。これだと辞書攻撃で「典型的な短いメッセージ」が即座に特定されてしまいます。実装では OAEP（Optimal Asymmetric Encryption Padding）などの乱数を含むパディングを必ず併用し、同じ平文でも毎回違う暗号文になるようにします。また、署名用途では PSS パディングが現在の推奨です。
次に多いのが、鍵長を「ビット数だけ」で評価する ミスです。「RSA 2048 ビット」と聞くと共通鍵暗号の 2048 ビットと同等のように感じますが、実際の安全性は「等価安全性」で測ります。RSA 2048 ビットの安全性は、共通鍵暗号でいうと約 112 ビットに相当します。AES-128 と同等にしたければ RSA 3072 ビット、AES-256 と同等にしたければ 15360 ビットが必要、というのが NIST のガイドラインです。鍵長は方式間で単純比較できない、と覚えてください。
最後に、「公開鍵で暗号化、秘密鍵で復号」という対応関係が常に成り立つわけではない 点に注意してください。RSA は数学的には対称的で、(e で暗号化 → d で復号) と (d で暗号化 → e で復号) のどちらも可能です。前者を「暗号化」、後者を「署名」と呼んで区別します。ただし実務ではそのまま流用するのは危険で、用途ごとに別の鍵を使う・PKCS#1 のスキームに従う、といった分離が必須です。本デモは数学的な裏側を見せるためにあえてシンプルにしていますが、実装上は「暗号化用の鍵で署名する」ような流用は避けてください。