Link

リンク

サルにも分かるRSA暗号

ためしてみよう

自由に選べる2つの素数として P=3, Q=11 を使い、これらを掛けた P×Q = 33 を法とする世界で、実際にRSA暗号による暗号化を行ってみます。

相手に秘密に伝えたい平文の数値列を、7 13 17 24 などとします(実際に文字を暗号化する時は、一旦文字を数値に直すのです)。 これを友人から自分に送ってもらうことを想定します。 まず、暗号化するための鍵(公開鍵暗号方式の概念を覚えていますか?暗号化するための鍵はみんなに公開してしまうのです)を決めます。 すなわち、33 を法とする世界で暗号化の際に一旦何乗するかということです。

では、この公開する鍵を適当に 3 に決めましょう(但し、実際は適当にはとれず多少の制限があります)。 そしてこれを友人に伝えます。" 33 を法として、鍵を 3 として暗号化してくれ" と。 よって公開する情報は、法とする数 33 と公開鍵 3 です。 友人は平文 7 13 17 24 を言われた通りの条件で暗号化します。 33 を法とする世界でのべき乗表をもう一度下記に示しておきますので、参考にしてください。

7 は 3 乗すると 13。
次に 13 は 3 乗すると 19。
次に 17 は 3 乗すると 29。
最後に 24 は 3 乗すると 30。
よって、平文 7 13 17 24 の暗号文は 13 19 29 30 となります。

この暗号文を受け取ったあなたはこれを復号して平文に戻します。 それには、公開した鍵 3 のペアとなる秘密の鍵を求め、さらにその数分だけ暗号文をべき乗すればよいはずです。 33 を法とする時、存在する全ての数は n×(3-1)×(11-1) + 1 乗すると元に戻るので、3 という鍵で暗号化したなら(既に 3 乗されているので)、3 乗した時の数をさらにある数 (D) 乗した結果が、全体として n×(3-1)×(11-1) + 1 乗 (n は任意の整数)になるようにすればいいのです。 分かりますか?

A を平文の数値とする時、暗号化に使った鍵が 3 なので A を暗号化した後の値はすでに 3 乗されているため、全体として A が再び元の A に戻るだけのべき乗にしてしまうような 秘密の鍵 D は、

(A3)D = A{n × (P - 1) × (Q - 1) + 1}

という関係がなければならないので(但し n は自由な正の数)、

3 × D = n × (P - 1 ) × (Q - 1 ) + 1

3 × D = n × (3 - 1 ) × (11 - 1 ) + 1

D = n × 2 × 10 + 1

3

という式を満たす必要があります。 このような D としては … n が 1 の時に D=7 となります。 この 7 が、暗号化の鍵 (E) を 3 とした時の暗号文を復号できる秘密の鍵 (D) となります。 送られてきた暗号文 13 19 29 30 を、求めた秘密の鍵 7 で復号してみましょう。 33 を法とする世界で考えるんでしたね。

まず 13 は 7 乗すると 7 。
次に 19 は 7 乗すると 13。
次に 29 は 7 乗すると 17。
最後に 30 は 7 乗すると 24。
結果、7 13 17 24 となり、最初の平文に一致します。 見事に復号することができました。

戻る
進む
ページ上部へ