RSAは、これまでの2つの展示室とは違う「公開鍵暗号」です。暗号化用の鍵(公開鍵)と 復号用の鍵(秘密鍵)が別々で、公開鍵は誰に見られても構いません。
A幕: 617桁との対面
これは実際のRSA-2048の公開鍵の数(n)です。2つの素数の積でできています。
この数を2つの素数に分解できれば、この暗号は破れます。
B幕: 素数をつくる(ライブ)
⚠️ ここで作った鍵は展示用の簡易実装です。実際の通信には絶対に使わないでください。
C幕: べき剰余の階段
短いメッセージをデモ鍵で暗号化する様子(c = m^65537 mod n)を再生します。
復号(先頭・末尾のみ抜粋、実際は約2048段)
D幕: 非対称の崖
掛け算はA幕のように一瞬です。では逆に、積から2つの素数を割り出す(素因数分解)のは? 桁数を24bit→56bitへ増やしながら、試し割りでかかる時間を実測します。
フェルマーの小定理〜RSAの正しさ(概略)
pを素数、gcd(a,p)=1のとき a^(p-1) ≡ 1 (mod p)。これがオイラーの定理へ拡張され、 n=p×qのとき a^φ(n) ≡ 1 (mod n) (φ(n)=(p-1)(q-1))が成り立つ。 e×d ≡ 1 (mod φ(n)) となるように d を選んでおけば、 (m^e)^d = m^(ed) = m^(1+kφ(n)) ≡ m (mod n) となり、暗号化と復号が互いに戻ることが保証される。
公開鍵は暗号化に、秘密鍵は復号に使います。この向きを逆にすると――秘密鍵で 署名し公開鍵で検証する――「本人証明」になります。ウェブサイトの証明書にも RSA(や後述の楕円曲線)が使われています。