鍵
d の求め方:拡張ユークリッドの互除法
各行は、すぐ上の2行の割り算から得られます。余りが1の行では、最後の列が d です(負の場合は φ(n) を足します)。
| 商 | 余り | e の係数 |
|---|
メッセージ
ネットワークで送信
| ビット | 二乗 | m を掛ける |
|---|
鍵を破る
RSA暗号デモ
RSA を使えば、誰でもあなたの公開鍵でメッセージに鍵をかけられますが、それを開けられるのは秘密鍵を持つあなただけです。その裏にあるのは、学校で習う数行の算数です。2つの素数、1回の掛け算、余り、そして巧妙な逆数です。自分で選んだ素数から鍵ペアを作り、メッセージを1文字ずつ暗号化・復号し、あなたからのものだと誰でも確認できるよう署名し、最後に攻撃者になって n を素因数分解し、本物の鍵がなぜ数百桁も必要なのかを確かめましょう。 2つの素数 p と q を選ぶか、「新しい素数」を押してください。アプリが公開鍵 (e, n) と秘密鍵 d を作り、拡張ユークリッドの互除法で d を求める過程を示します。メッセージを入力すると、各文字が公開鍵で暗号化され、秘密鍵で復号されます。行をクリックすると、繰り返し二乗法で計算されるべき乗が表示されます。「署名」に切り替えると代わりに秘密鍵で署名し、「n を素因数分解」を押すと小さな鍵がどれほど早く破られるかがわかります。
使い方
- 2つの素数 p と q を入力するか、大きさを選んで「新しい素数」を押します。アプリが n、φ(n)、e、d を計算し、d の求め方を示します。
- メッセージを入力し、「暗号化」か「署名」を選びます。各文字は数に変換され、mod n でべき乗されます。行をクリックすると繰り返し二乗法の過程が表示されます。
- 「n を素因数分解」を押すと、イブが n を2つの素数に分解して秘密鍵を取り戻します。
鍵の仕組み
2つの素数を掛け合わせます。n = p × q です。p = 61、q = 53 なら n = 3233 になります。φ(n) = (p − 1)(q − 1) = 3120 という数は、n より小さく n と共通の因数を持たない数の個数で、p と q を知っている人にしか計算できません。3120と共通の因数を持たない e = 17 を選び、e × d が φ(n) の倍数より1大きくなる d を求めます。ここでは d = 2753 です。17 × 2753 = 46801 = 15 × 3120 + 1 だからです。(e, n) を公開し、d は手元に残します。メッセージ m は c = mᵉ mod n になり、cᵈ mod n で m に戻ることがオイラーの定理によって保証されます。
破るのが難しい理由
攻撃者に必要なものはすべて n の因数の中に隠れています。n = 3233 では何の守りにもなりません。奇数の約数を試していくと、20数回で53が見つかります。しかし、手間は n の平方根とともに増えます。2048ビットの法はおよそ617桁あり、知られているどの方法でも、現存するどのコンピューターでも、実用的な時間で素因数分解することはできません。署名は RSA を逆向きに使います。s = mᵈ mod n は秘密鍵でしか作れず、sᵉ mod n で m に戻ることは誰でも確かめられます。
よくある質問
なぜ誰も公開鍵から d を計算できないのですか?
d を求めるには φ(n) = (p − 1)(q − 1) が必要で、φ(n) を得るには p と q が必要です。n からそれらを取り戻すことは n を素因数分解することを意味し、数百桁の数に対しては速い方法が知られていません。このデモではおもちゃの鍵を一瞬で素因数分解できますが、それこそが本物の鍵がこれほど大きい理由を示しています。
なぜメッセージを1文字ずつ暗号化するのですか?
おもちゃの鍵が小さいからです。RSA で暗号化できるのは n より小さい数だけです。n = 3233 ならどの文字コードも収まりますが、文全体は収まりません。本物の RSA は2048ビット以上の法を使い、同じメッセージが二度と同じように暗号化されないようメッセージをランダムなバイトでパディングし、実際には AES のようなより高速な暗号のための短い鍵だけを暗号化します。
繰り返し二乗法は何をするのですか?
m²⁷⁵³ mod n のような巨大なべき乗を、巨大な数を一度も書き出さずに計算します。指数を2進数で書き、そのビットを順にたどります。ビットごとにそれまでの結果を二乗し、1のビットでは m を掛け、そのたびに mod n の余りをとります。2048ビットの指数でも、二乗は約2048回で済みます。
暗号化と署名の違いは何ですか?
暗号化には受信者の公開鍵を使うので、元に戻せるのは受信者の秘密鍵だけです。署名には送信者の秘密鍵を使うので、誰でも送信者の公開鍵で確認でき、メッセージがその鍵の持ち主から来たもので、改ざんされていないことがわかります。
メッセージはどこかに送信されますか?
いいえ。すべてお使いのブラウザー内で計算され、素数とメッセージはこのブラウザーのローカルストレージに保存されます。
試してみますか?
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
エディターへ