RSA暗号のおもちゃ

2つの素数を選び、メッセージを入力して、RSAがそれを暗号化してから復号する様子を見てみよう。

計算例 — RSA暗号のおもちゃ

秘密鍵 (n, d)	1783

ページを開いたときに計算機が表示する値です。上の入力を変えると再計算されます。

インタラクティブシミュレーションを読み込んでいます...

レッスン

理論 — RSA暗号のおもちゃ

RSA は一つの演算を二度使うだけのものです。暗号化は m^e mod n、復号は c^d mod n — 同じ剰余べき乗で、指数だけが違います。仕掛けは、二度かければ元のメッセージに戻り、しかも片方の指数を知ってももう片方については何も分からない、そういう組を選ぶことにあります。パネルが表示しているものはすべて、その組を探す作業です。1978 年にリベスト、シャミア、エーデルマンが発表し — そして 1997 年に GCHQ が機密指定を解いて初めて分かったことですが — クリフォード・コックスがその四年前に同じものを見つけ、引き出しにしまっていました。

各記号の意味

n: 法 p·q。公開されます。秘密なのはその因数であって、数そのものではありません。
φ(n): オイラーのトーシェント (p−1)(q−1)。パネルがこれを出せるのは p と q を渡されているからで、n しか持たない攻撃者には出せません。n から φ を得ることは素因数分解と同じだけ難しいのです。
e: 公開指数。φ(n) と互いに素な数ならどれでもよく、だからこそ素数を変えると値が変わります。
d: 秘密指数 e⁻¹ mod φ(n)。剰余逆元をひとつ求めるだけ — φ を知っていれば一瞬で、知らなければそれがすべてです。

公式の導き方

素数を掛けます。n = p·q、既定値では 61 · 53 = 3233。この数は公開されます。3233 から 61 と 53 を取り戻すのは手計算でも一瞬で、これがこれを正直に「おもちゃ」と呼ぶ理由です。
φ(n) = (p−1)(q−1) = 60 · 52 = 3120 を計算します。ここが全体の要です。n は公開、φ(n) は非公開であり、一方から他方へ至る既知の道は素因数分解を通る道だけです。
φ(n) と互いに素な e を選び、e·d ≡ 1 (mod φ(n)) を d について解きます。パネルは 7⁻¹ mod 3120 = 1783 と表示します。この段階がそうではないことに注意してください。難しくないのです。φ さえ分かれば剰余逆元をひとつ求めるだけ。d の秘密性は、φ の秘密性だけに乗っています。
往復が成り立つ理由。構成上 e·d = 1 + kφ(n) なので m^ed = m^1+kφ(n) ≡ m (mod n) — オイラーの定理です。復号は別に考案された逆演算ではなく、最初の操作を打ち消す指数を使った同じべき乗です。

表示の読み方

注目すべき行は e です。これは定数ではありません。既定の素数では 7 と出ますが、p を 67 にすると 5 になります。理由はすぐ上の行にあります。e は φ(n) と互いに素でなければならず、φ が 3120 から 3432 に変わったのです。次に画面上の二つの指数を比べてください。e = 7 に対し d = 1783。公開側は極小で秘密側はそうではなく、どちらも偶然ではありません。e は暗号化を安くするためわざと小さく選ばれ、d は逆元が返してきた値そのものです。最後の行は成功の証拠です。m′ = 42、あなたが入力した数です。

前提: メッセージが n より小さい数であること。n = 3233 では 3232 より上に暗号化できるものは何もありません。だからこそ本物の RSA はメッセージを直接暗号化しません。数百ビットのパディング済み共通鍵を暗号化し、本文はより高速な暗号に運ばせます。さらに p ≠ q であること、そして二つ目の法で同じ素数を再利用しないことも前提です。因数を共有する二つの法は、最大公約数ひとつで両方とも破られます。
成り立たない場合: このページは何も素因数分解せずに破れます。p = 67、q = 53、メッセージを 3 にしてください。パネルは e = 5 を選び、暗号文として 243 を表示します。これはただの 3⁵ です。3⁵ は n = 3551 より小さいので、剰余をとる操作は一度も起きていません。暗号文はふつうのべき乗であり、243 の 5 乗根は 3 です。鍵なし、素因数分解なし、メッセージは戻ってきました。m = 5 を試せば 3125、すなわち 5⁵ が出ます。m = 8 でようやくべき乗が n を超え、暗号文は役に立たない 809 になります。これはこのページの欠陥ではありません。誰も裸の数を暗号化しない理由そのものです。本物の RSA はまずメッセージを構造化された乱数で埋めます。それを定めているのが RFC 8017 であり、べき乗を暗号システムに変えているのもそれです。

秘密鍵は選ぶものではなく導かれるもの 🖖

パネルが d を組み立てる様子を見てください。既定の素数では φ(n) = 60 · 52 = 3120 と表示され、次に e = 7 が選ばれます。本来優先される 65537 が、ここでは φ そのものより大きいためです。そして最後に d ≡ 7⁻¹ mod 3120 = 1783 を計算します。この最後の手順はモジュラ逆元をひとつ求めるだけで、どんな計算機でも一瞬です。d 自体に秘密は何もありません。φ(n) からそのまま出てきますし、φ(n) は p と q からそのまま出てきます。つまり RSA が隠しているのは秘密指数ではなく素因数分解なのです。ここでは n = 3233 で、あなたがこの文を読み終える前にノートパソコンが分解してしまいます。RSA-2048 の法は十進617桁ですが、画面上の手順はそれ以外まったく同じです。

あなただけが開けられる南京錠 🖖

RSAは誰にでも開いた南京錠(あなたの公開鍵)を渡し、メッセージに掛けて閉じることはできても、再び開けられるのはあなたの秘密鍵だけです。閉じる鍵と開ける鍵が違うので、公開鍵は世界中に見せて公開しても、復号の方法は明かされません。このツールでは小さな素数で一連の流れを丸ごと試せますが、実際のシステムは同じ手順を何百桁もの数で行います。

暗号化を逆に回すと署名になる 🖖

同じRSAの計算を逆方向に回すと、メッセージを隠す代わりに誰が送ったかを証明できます。あなたが秘密鍵でメッセージを「復号」すると、誰もが公開鍵でそれを「暗号化」し直して、本当にあなたから来たものかを確かめられます。これがデジタル署名です。つまり一つの計算が、どちらの鍵を先に使うかを入れ替えるだけで、機密性と認証の両方を支えているのです。

全プロセスの詳細解説

p = 61 と q = 53 のための RSA キーペア 5 ステップ
p = 61 および q = 53 に対するRSA鍵対を生成し、m = 42 を暗号化せよ。以下のすべての数値は、公開指数を含めて、これら3つの数値から導かれる。
1. モジュラス（法）は公開され、トーティエントは破棄されるが、どちらも素数からの乗算1回で得られる。φ(n) は n 未満で n と共通の因数を持たない整数の個数を数えたものであり、相異なる2つの素数の積に対しては (p − 1)(q − 1) となる。
  
  $n = 61 \cdot 53 = 3233, ϕ (n) = (61 - 1) (53 - 1) = 60 \cdot 52 = 3120$
2. 公開指数は modulo φ において逆元が存在しなければならず、これは φ と互いに素であることを意味する。φ を素因数分解すると小さな候補が除外され、利用可能な最小の奇数指数として 7 が残る。実際の鍵では 65537 が使用されるが、それはこの φ よりも大きいため、ツールは最小の互いに素な数へとフォールバックする。
  
  $3120 = 2^{4} \cdot 3 \cdot 5 \cdot 13 ⟹ g cd (3, ϕ) = 3, g cd (5, ϕ) = 5, g cd (7, ϕ) = 1 ⟹ e = 7$
3. modulo 3120 における 7 の逆元を求めることは、拡張ユークリッドの互除法そのものである。3回の割り算で余り 1 に到達し、これら同じ3行の式を逆にたどることで、その 1 を 3120 と 7 の一次結合として書き表すことができる。
  
  $3120 = 445 \cdot 7 + 5, 7 = 1 \cdot 5 + 2, 5 = 2 \cdot 2 + 1 ⟹ 1 = 3 \cdot 3120 - 1337 \cdot 7$
4. その一次結合における 7 の係数は負であり、負の逆元はモジュラスを1回加算することで正に変換される。暗号化は単一のべき乗余剰演算となり、42 を自身と7回掛け合わせるのではなく、2回の二乗を行うことで完了する。
  
  $d \equiv - 1337 \equiv 1783 (mod 3120), c = 4 2^{4} \cdot 4 2^{2} \cdot 42 = 1550 \cdot 1764 \cdot 42 \equiv 240 (mod 3233)$
5. 復号を総当たりで確認する必要は決してなく、現実的な鍵サイズでは不可能でもある。2つの指数は、それらの積が φ の倍数より 1 大きくなるように構築されており、n と互いに素な任意の m（42 はこれに該当する）に対してオイラーの定理により完了する。
  
  $e d = 7 \cdot 1783 = 12481 = 4 \cdot 3120 + 1 ⟹ c^{d} \equiv m^{e d} = m (m^{ϕ})^{4} \equiv m = 42$
解答

ツールは n = 3233、φ = 3120、d = 1783、c = 240 と出力し、240 が 42 に正常に復号されることを確認する。注目すべき点は φ の本質である。φ は p や q と並ぶ第2の秘密ではなく、同じ秘密を異なる形で記述したものに過ぎない。n と φ が与えられれば、p + q = n − φ + 1 = 114 および pq = 3233 が得られ、判別式が完全平方となる二次方程式から、わずか1行で 61 と 53 が導き出される。したがって、φ を漏洩する鍵生成器は、素数をそのまま出力したのと全く同じくらい完全に素因数分解を漏洩させていることになる。φ が1度だけ計算され、d を求めるために使用された後に破棄されるのはそのためである。

$p + q = n - ϕ + 1 = 114, pq = 3233 ⟹ x^{2} - 114 x + 3233 = 0 ⟹ x = 61, 53$
RSAセキュリティを破るための3233の61 × 53への素因数分解 6 ステップ
パネルはあなたがページを読み終える前に 3233 を 61 × 53 に分解します。この素因数分解こそ RSA の安全性のすべてで、見たところ一瞬で破られています。鍵長がひとつ上がると同じ問題がなぜ不可能になるのか、計算しましょう。
1. パネルが出発点にする 2 つの数——法と、2 つの素数から決まるオイラー関数の値。
  
  $n = 61 \times 53 = 3233, ϕ (n) = 60 \times 52 = 3120$
2. 攻撃者に必要な事実はひとつだけ。小さいほうの素数は法の平方根を超えられません。それより大きければ、自分より小さい相方が必要になるからです。
  
  $p \leq n ⟹ 3233 = 56.86, π (56) = 16$
3. 探索は 56 までの素数、つまり 16 個で済みます。16 番目が 53。16 回の割り算は安全性ではなく、丸め誤差です。
  
  $53 < 56.86 \in {2, 3, 5, \dots, 53} ⟹ k \leq 16$
4. では実際に使われる法を入れます。2048 ビットとは n が 2²⁰⁴⁸ 付近ということで、その平方根は 2¹⁰²⁴、およそ 10³⁰⁸ です。
  
  $n \approx 2^{2048} ⟹ n = 2^{1024} \approx 1 0^{308}$
5. 値段をつけます。毎秒 10 億回の試し割りでも 10²⁹⁹ 秒——宇宙の年齢はおよそ 4 × 10¹⁷ 秒です。
  
  $\frac{1 0 ^{308}}{1 0 ^{9} s ^{- 1}} = 1 0^{299} s \approx 1 0^{291} yr$
6. この大きさの数に時間という単位は不向きです。むしろ物理的な何かと比べましょう。
  
  $1 0^{308} ⋙ 1 0^{80}$
解答

10³⁰⁸に対する16回の除算。10³⁰⁸は観測可能な宇宙に存在する原子の数の10²²⁸倍であり、カウンターを保存することすらできません。重要なのは大きさよりも形です。攻撃者の計算量が √n で増大するのに対し、鍵のサイズは log n で増加します。したがって、鍵を2ビット拡張するたびに、防御側のコストは2ビット増えるだけで、解読のコストは2倍に跳ね上がります。この非対称性こそが核心なのです。ツールが一瞬で答えを出したのは、実演の失敗ではありません。3233とは、非対称性が機能する余地を与えられなかったモジュラスの姿であり、それをお見せすることこそがこの実演の目的なのです。

$16 ⟷ 1 0^{308}; O (n), n = 2^{2048}$

参考文献 (4)

The idea RSA is an instance of — public keys, two years earlier: W. Diffie & M. Hellman, "New directions in cryptography." IEEE Transactions on Information Theory 22(6), 644–654, 1976.
What real RSA wraps round the message, and why the bare exponentiation on this page is not a cryptosystem: K. Moriarty (Ed.), B. Kaliski, J. Jonsson & A. Rusch, "PKCS #1: RSA Cryptography Specifications Version 2.2." RFC 8017, November 2016 — RSAES-OAEP in §7.1.
The scheme the tool walks through, including e·d ≡ 1 mod φ(n): R. L. Rivest, A. Shamir and L. Adleman, "A method for obtaining digital signatures and public-key cryptosystems." Communications of the ACM 21(2), 120–126, 1978.
Why the security rests on factoring rather than on hiding d: A. J. Menezes, P. C. van Oorschot and S. A. Vanstone, Handbook of Applied Cryptography, §8.2. CRC Press, 1996. ISBN 978-0-8493-8523-0.

42Math チーム · 更新 2026-08-17

公表された資料と照合しています。訂正のご指摘を歓迎します。編集方針 · 訂正

コンピューティングのレッスン一覧 →

例題

p=61, q=53 - p=61, q=53: 教科書でおなじみのRSA
非常に小さな素数 - p=7, q=11: 小さな素数で、計算の流れを追いやすい
より大きな素数 - p=101, q=103: より大きな鍵空間
教科書の例 - p=17, q=19: 教科書の演習問題