10. ＲＳＡ暗号の世界

ＲＳＡ暗号ではある数を法（モジュロ）とする世界で、平文の数値を別の数値に変換することは分かりました。それでは次に、ＲＳＡ暗号を支えるこの世界の数値の興味深い性質をお話しします。

ＲＳＡ暗号は、自由に選んだ異なる二つの素数を掛けた数を法とする世界を利用します。素数というのは、例えば、2, 3, 5, 7, 11, ... のように、その数自身と 1 以外の自然数では割りきることができない 2 以上の整数のことです。 4 は 2 で、 6 は 2 や 3 で割りきることができるから素数ではありません。では、そのような世界の例として、二つの素数に 3 と 11 を選び、これらを掛けた数 33 を法とする世界を考えてみましょう。 33 を法とする世界に存在する数は、0 から 32 までだけです（ 33 までいったら 0 に戻るからです）。

この世界に存在する全ての数のべき乗を全て求めて表にしてみます。

これは、ある数値の○乗はいくつか？という表です。一番左の列がべき乗されるこの世界の数、一番上の行が何乗するかという数です。例えば、べき乗される数が 2 の時は、 1 乗で 2、 2 乗で 4、 3 乗で 8、 4 乗で 16、 5 乗で 32、 6 乗で 64 … 64 は 33 を法とする世界では 31 になります。そしてまた、 6 乗で 62 … 62 は 33 を法とする世界では 29 … という風に続けていきます。

さて、この表をよく見て下さい。 33 を法とする世界に存在する 1 から 32 までの全ての数は、べき乗する度に予想のつかない数に変わっていきながらも、全ての数はなんと11 乗又は 21 乗すると自分自身に戻っているでしょう！（水色のセルの部分）このように、２つの素数（ P, Q とします）をかけた数を法とする世界では、全ての数が自分自身に戻るべき乗数が必ず存在します。そして、これが何乗なのかは、最初の２つの素数 ( P , Q ) によって決まります。つまり、実はその２つの素数さえ分かってさえいれば、このべき乗数は簡単に求めることができるのです。

それは、P と Q からそれぞれ 1 を引いた P-1 と Q-1 の最小公倍数に 1 を足した数です。すべての数は、この数の回数だけべき乗した時、必ずもとの数に戻るのです。そして、そのようになるべき乗数は、一定のペースでまたやってきます。そのペースとは、 P-1 と Q-1 の最小公倍数です。従って、P×Q を法とする世界で、全ての数が自分自身に戻るべき乗数は、n × （ P-1 と Q-1 の最小公倍数）+ 1と表すことができます。ちなみに (P-1)×(Q-1) という式は必ず（ P-1 と Q-1 の最小公倍数）の倍数になりますので、このべき乗数の一部は簡単に、

n × (P - 1) × (Q - 1) + 1
（但し n は任意の正の整数）

として求めることができます。

どうでしょう、先程の２つの素数 P=3, Q=11 とする時、 P-1=2 と Q-1=10 の最小公倍数は 10 であり、n × （ P-1 と Q-1 の最小公倍数）+ 1 は n=1 で 1×10 + 1 = 11 となりますが、確かに上記の表を見てみると 11 乗でどの数も必ず自分自身に戻っています！また、n×(P-1)×(Q-1) + 1も、 n=1 で 1×(3-1)×(11-1) + 1 = 2×10 + 1 = 21 となり、上記の表と同じく、 21 乗でも同様のことが起こっているのが分かります。

さぁ、これをどう暗号化に利用するのでしょうか？気が付きますか？ＲＳＡ暗号では、このように適当な素数 P , Q を掛けた数 P×Q を法とする世界を考え、暗号化したい平文の数値（但し P×Q 未満）を、「適当な数」分だけべき乗してしまうのです。ここで何乗するかというのが１つ目の鍵(E) となります。 すると、あらゆる数は予想がつかない数に変換されます。これが暗号化でこれにより変換された数値が暗号文（暗号語）となるのです。そして、この暗号化された数値をもとの数値に戻す復号を行なうには、暗号化の際べき乗した数（ E乗）の部分から、全体として自分自身に戻るようなべき乗数になるようさらにべき乗してやればよいのです。このべき乗数が鍵 (E) に対応するもう一つの鍵 (D) となるのです。

ここで「わざわざ (D) 乗しなくても単に (E) 乗根を求めれば元の数が得られるのでは？」という疑問を持たれる人もいるかもしれません。それは確かに私たちが住んでいる普通の世界なら可能です。例えば 2 を 4 乗して 16 を得た時、 16 の 4 乗根を求めれば元の 2 が得られます。しかし、今、この暗号で利用している素数を二つかけ合わせた数を法とする世界は我々の世界のような単純な割算はできないため、逆に（ E乗）分を逆算して元の数に戻すことができないのです。これが暗号化に使用した鍵では復号ができない「からくり」になっているのです。

いかがでしょうか？ＲＳＡ暗号のからくりが、なんとなく分かってきましたか？まだわかっていなくても、大丈夫。次でもう一度具体的に解説しますから。