Link

リンク

サルにも分かるRSA暗号

RSA暗号の世界

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

RSA暗号は、自由に選んだ異なる 二つの素数を掛けた数 を法とする世界を利用します。 素数というのは、例えば、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 乗すると自分自身に戻っている でしょう!(水色のセルの部分) このように、2つの素数( P, Q とします)をかけた数を法とする世界では、全ての数が自分自身に戻るべき乗数が必ず存在します。 そして、これが何乗なのかは、最初の2つの素数 ( P , Q ) によって決まります。 つまり、実はその2つの素数さえ分かってさえいれば、このべき乗数は 簡単に 求められるのです。

それは、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 は任意の正の整数)
から求めることができます。

どうでしょう? 例えば2つの素数 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 乗でも同様のことが起こっているのが分かります。

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

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

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

戻る
進む
ページ上部へ