0からわかる、暗号(RSA)の仕組み

みなさん、こんにちは。
ついに、公開鍵暗号の核心、「オイラーの定理」の証明の解説です。

数学要素がたくさんでてきますが、じっくり解説しますので、ゆーっくりついてきてください。

それでは、「オイラーの定理」を証明しましょう・・・・のその前に

「オイラーの定理」の証明の前に、次のような事実を見てみましょう。

$1$から$n$までの数字で、$n$と互いに素な数字を「$r_1,r_2,\cdots,r_{\phi(n)}$」とします。
(例えば、$n=10$の場合、「$\phi(10)=4$」で「$r_1=1,r_2=3,r_3=7,r_4=9$」となります。)

ここで、それぞれの数字に「$M$を掛けた」ものを見てみましょう。
「$Mr_1,Mr_2,Mr_3,Mr_4,Mr_5, \cdots ,Mr_{\phi(n)}$」という「($\phi(n)$)個」の数字ができます。

この数字のリストを作るときに使う$M$と$n$は共通の約数を持たなければなんでもいいです。

具体例を見てみましょう。
例えば、$n=15$、$M=4$の場合、$15$と互いに素な数字は「1,2,4,7,8,11,13,14」なので、$M=4$を掛け算すると、「$4,8,16,28,32,44,52,56$」の「$\phi(15)=8$個」の数字になります。

このとき、一つの重要な事実が成り立ちます。

それは、これらの数字を$n$で割り算したときの余りは、ぜーーんぶバラバラで、$1$～$n$までの数字で、$n$と互いに素な数字が1つずつ出てくるという事実です。

本当にそうなるの？

ほんとかなぁ？やってみましょうか。
先ほどの、$n=15$、$M=4$の場合の、「$4,8,16,28,32,44,52,56$」の8個の数字を見てみましょう。

この8個の数字を$n=15$で割った余りを書いてみましょう。
「$4,8,1,13,2,14,7,11$」の8個になりますね。おぉ！！！全部、余りの数字は違うし、$15$と互いに素な数字「1,2,4,7,8,11,13,14」が全部でてきてます！

なんで、こんなことになるの？

これはなぜでしょうか？

実は当たり前のことなんです。だって、もし「$iM$と$jM$を$n$で割った余りが同じ」だと考えてみて下さい。
この、$iM$と$jM$は、「$Mr_1,Mr_2,Mr_3,Mr_4,Mr_5, \cdots ,Mr_{\phi(n)}$」から2つの数字をとってきたものです。
($i$と$j$は($r_1,r_2,\cdots,r_{\phi(n)}$)のどれかですよ)

$iM$を$n$で割った商を$K_i$、余りを$A$とし、$jM$を$n$で割った商を$K_j$、余りを$A$とすると、次の式が成り立ちます。
(余りが同じなので、両方とも$A$と置いています)
$$ iM = K_in+A jM = K_jn+A $$
ということは、「$iM-jM = (K_in +A) - (K_jn +A) = K_in-K_jn = n(K_i-K_j)$」となります。
一方で、「$iM-jM = M(i-j)$」なので、「$M(i-j)=n(K_i-K_j)$」ということになりますね。

「$(K_i-K_j)$」は整数なので、「$M(i-j)$」は「$n$」の倍数ということになります。

でも、「$M$」は「$n$」の倍数ではない（共通の約数を持たない）ということがわかっていますので、「$i-j$」が「$n$」の倍数になるしかありません。

でもでも、思い出してください。
「($i$と$j$は($r_1,r_2,\cdots,r_{\phi(n)}$)のどれか」でしたね。

しかも、「$i$と$j$は$n$より小さい」のです。だから「$i-j$」も「$n$より小さい」のです。

というこは、「$i-j$」も「$n$」の倍数になることはできません。

困りましたね。。。「$M(i-j)$」は「$n$」の倍数にならなければいけないのに、「$M$」も「$i-j$」も「$n$」の倍数ではないというのです。

そう、何かがおかしいです！何がおかしいんでしょうか？
これはもともと「$iM$と$jM$を$n$で割った余りが同じ」と考えたことがおかしかったのです。

ということは、「$iM$と$jM$を$n$で割った余りは違う」ということになります。
つまり、「$Mr_1,Mr_2,Mr_3,Mr_4,Mr_5, \cdots ,Mr_{\phi(n)}$」を$n$で割り算したときの余りは、ぜーーんぶバラバラになって一緒のものがでてこないんです。

更に、「$r_1,r_2,\cdots,r_{\phi(n)}$」は全部$n$と互いに素(同じ約数を持たない)数字でした(ていうか、(n\)と互いに素の数字だけを集めたんですよね)。
加えて、$M$も$n$と互いに素でした。

ということは、「$Mr_1,Mr_2,Mr_3,Mr_4,Mr_5, \cdots ,Mr_{\phi(n)}$」も全部$n$と互いに素ということですね。

ここで、例えば「$Mr_1$」を$n$で割った商を「$k_1$」、余りを「$A_1$」と置くと、「$Mr_1 = nK_1+A_1$」と書けます。「$Mr_1$」は$n$と互いに素なので、「$nK_1+A_1$」も$n$と互いに素になるはずです。

「$nK_1+A_1$」の「$nK_1$」部分が$n$の倍数になっており、$n$と互いに素ではないので、「$A_1$」が$n$と互いに素ということになります。
以上のことをまとめると、「$Mr_1,Mr_2,Mr_3,Mr_4,Mr_5, \cdots ,Mr_{\phi(n)}$」をそれぞれ$n$で割り算した余り($A_1,A_2,A_3,A_4,A_5, \cdots ,A_{\phi(n)}$)は、全て$n$と互いに素な数字、かつ$n$未満の数字ということになります。

さて、「$Mr_1,Mr_2,Mr_3,Mr_4,Mr_5, \cdots ,Mr_{\phi(n)}$」をそれぞれ$n$で割り算した余り($A_1,A_2,A_3,A_4,A_5, \cdots ,A_{\phi(n)}$)は、全て$n$と互いに素な数字かつ$n$未満あり、かつすべてバラバラです。

一方「$r_1,r_2,\cdots,r_{\phi(n)}$」も全て$n$と互いに素な数字かつ$n$未満あり、かつすべてバラバラな数字です。

結局、「$Mr_1,Mr_2,Mr_3,Mr_4,Mr_5, \cdots ,Mr_{\phi(n)}$」を$n$で割り算したときの余りは、順番は別にして、「$r_1,r_2,\cdots,r_{\phi(n)}$」と同じになるのです。

とういことは、以下の数式が成り立つことがいえます。

$$ Mr_1 \times Mr_2 \times Mr_3 \times Mr_4 \times Mr_5 \times \cdots \times Mr_{\phi(n)}= r_1 \times r_2 \times r_3 \times r_4 \times r_5 \times \cdots \times r_{\phi(n)} \pmod n $$ 左辺を$M$でまとめると(左辺は、$\phi(n)$個あるので)以下の通りになります。
$$ M^{\phi(n)}(r_1 \times r_2 \times r_3 \times r_4 \times r_5 \times \cdots \times r_{\phi(n)})= r_1 \times r_2 \times r_3 \times r_4 \times r_5 \times \cdots \times r_{\phi(n)} \pmod n $$ ここで、右辺と左辺を共通の「$r_1 \times r_2 \times r_3 \times r_4 \times r_5 \times \cdots \times r_{\phi(n)}$」で割り算すると、以下の通りになります。
$$ M^{\phi(n)} = 1 \pmod n $$ となります。おぉ！！！見事に「オイラーの定理」が成り立ってるじゃないですかぁ！

証明の途中で、$M$と$n$が互いに共通の約数をもたないという条件が重要になっていましたね。

結局、公開鍵暗号との関係は何？

結局、何の解説してるの？暗号は？

はいはい。忘れてないですよ。次回は、「オイラーの定理」と「公開鍵暗号」との関係を解明します！。