11. ためしてみよう

では実際に、自由に選んだ２つの素数の例に P=3, Q=11 を選び、 それらを掛けた P×Q = 33 を法とする世界を利用して、ＲＳＡ暗号による暗号化を行ってみます。

相手に秘密に伝えたい平文の数値列を、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 は、

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

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

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