「公開鍵暗号」の概念を数式にしてみよう

これまでの復習ですが、「公開鍵暗号」は次のようなものでした。

前提：ある方法で、メッセージ$M$と、公開鍵($p$)と、秘密鍵($s$)と、謎の数字($n$)を作成する。
重要事項その1：「メッセージ($M$)を$p$乗して$n$で割った余り」を暗号とする。(例え$p$や$n$を知っていたとしても、暗号から元の($M$)を推測することはできない)
重要事項その2：暗号を$s$乗して$n$で割った余りは、元のメッセージ$M$に等しくなる

この「重要事項その1」を数式で表すと、暗号化したメッセージ($M_{暗号}$)は次のように書けます。

$$ M_{暗号}=M^p \pmod n $$
そして、 「重要事項その2」を数式で表すと、暗号化したメッセージ($M_{暗号}$)から次のようにして元のメッセージ($M$)が取り出せます。

$$ M_{暗号}^s=M \pmod n $$
この2つの数式を組み合わせると次の数式が成り立てばいいことがわかります。
(「重要事項その2」の式の$M_{暗号}$の部分に、「重要事項その1」の式の$M_{暗号}$を入れています)

$$ (M^p)^s=M \pmod n $$
「$(M^p)^s$」は、$M$を$p$回掛け算したもの全体を$s$回掛け算するので、結局「$p \times s$」回掛け算することになります。

例えば、「$(M^2)^3$」だと「$M^2$」を3回掛け算するので「$M^2 \times M^2 \times M^2$」となり、各項目の「$M^2$」は「$M$を2回掛け算する」ということなので「$(M \times M) \times (M \times M) \times (M \times M)$」になり、結局$M$を「$2 \times 3=6$」回掛け算することになります。

だから、先ほどの式は次のように変形することができます。

$$ M^{ps}=M \pmod n $$
この式が成り立てば、理想の公開鍵暗号は絵に描いた餅ではなくなります。

ここで、オイラーの定理を思い出しましょう。

$n$が自然数で、$M$と$n$が互いに共通の約数をもたないとき、次の式が成り立つ。
$$ M^{\phi(n)}=1 \pmod n $$ この「オイラーの定理」をスタート地点にして、変形していった後に、先ほどの「公開鍵暗号の式」になれば、「公開鍵暗号の式」は成り立つことがわかりますね。

$\phi$関数の秘密を知ろう

その前に、1つだけ$\phi$関数のことで、知っておいてほしいことがあります。
それは、「$m$と$n$が素数の場合、$\phi(mn)=\phi(m)\phi(n)=(m-1)(n-1)$が成り立つ」ということです。
(前に解説した通り、$n$が素数の場合、$\phi(n)=n-1$になることを想い出してください。そのため、重要なのは「$\phi(mn)=\phi(m)\phi(n)$が成り立つ」ことです。）

なぜ、「$m$と$n$が素数の場合、$\phi(mn)=\phi(m)\phi(n)$が成り立つ」か見ていきましょう。
$\phi(mn)$というのは、1から$mn$までの数字で$mn$の1以外の約数と同じ約数を持たない数は何個あるかということでした。

ここでは、1から$mn$までの数字の数($mn$個ですね！)から、$mn$の約数と同じ約数をもつ数の個数を引き算することで、$\phi(mn)$を調べてみましょう。

まずは、$mn$の約数と同じ約数をもつ数の個数を調べてみます。

$m$と$n$は素数なので、$mn$の約数は、$1,m,n,mn$のみになります。

それぞれの約数について、1から$mn$までの数字で同じ約数を持つものが何個あるか見ていきます。

まず、1から$mn$までの数字で$mn$を約数として持つ数は、$mn$の1個しかありません。
次に、1から$mn$までの数字で$m$を約数として持つ数は、$m,2m,3m,\dots,(n-2)m,(n-1)m,nm$の$n$個です。
次に、1から$mn$までの数字で$n$を約数として持つ数は、$n,2n,3n,\dots,(m-2)n,(m-1)n,mn$の$m$個です。

そのため、1から$mn$までの数字で$mn$か$m$か$n$かを約数に持つ数は、$1+n+m$個になりま・・・・せんね。
このままでは、$mn$を3回重複して数えてることになるので、$1+n+m-2$個、つまり、$n+m-1$個になります。

1から$mn$までの数字は$mn$個あるので、1から$mn$までの数字で$mn)\と互いに素な数は、\(mn$から「1から$mn$までの数字で$mn$か$m$か$n$かを約数に持つ数」を引き算したものになります。

つまり、「$mn-(n+m-1)$」になりますね。
この式を展開すると「$mn-n-m+1)$」になります。

そして、$n$でまとめると「$n(m-1)-m+1)$」になります。
最後に、$m-1$でまとめると、「$n-1)(m-1)$」になります。

だから、「$m$と$n$が素数の場合、$\phi(mn)=\phi(m)\phi(n)=(m-1)(n-1)$が成り立つ」のです。

オイラーの定理の変形

では、先ほどの$\phi(mn)$の秘密を使って、「オイラーの定理」を変形していきましょう。
「オイラーの定理」は次のようなものでした。
$$ M^{\phi(n)}=1 \pmod n $$
このとき、後のことを考えてこの式の両辺を$z$乗しておきます。($z$は5とか10といったただの数字です)
両辺を等しく$z$乗するので「=(イコール)」の関係は崩れません

$$ (M^{\phi(n)})^z=1^z \pmod n $$ この式は次のように変形できますね。

$$ (M^{z\phi(n)})=1 \pmod n $$
次に、公開鍵暗号の式は「$M^{ps}=M \pmod n $」だったので、先ほどの式の両辺を$M$倍してみましょう。

$$ M \times M^{z\phi(n)}=M \pmod n $$
$M^{z\phi(n)}$は、$M$を\「$z\phi(n)$」回掛け算するという意味なので、さらにもう一回$M$を掛けると、$M$を「$z\phi(n)+1$」回掛け算することになります。

つまり、「$M \times M^{z\phi(n)}=M^{z\phi(n)+1}$」なのです。
これを使って先ほどの式を変形すると次のようになります。

$$ M \times M^{z\phi(n)}=M^{z\phi(n)+1}=M \pmod n $$
なんか、「$M^{ps}=M \pmod n $」に近づいてきましたね。
あとは、「$ps$」と「$Z\phi(n)+1$」が同じになれば完璧です。

こうなると、$z\phi(n)$がちょっと邪魔ですね。見慣れない記号なので、どう扱ったらいいのかわかりません。
そこで、2つの素数、$a$と$b$を使って$\phi(n)$を消してみましょう。

オイラーの定理「$M^{z\phi(n)+1}=M \pmod n $」に出てくる$n$は自然数で$M$と互いに素であれば、何でもよかったですね。
そこで、$n=ab$としてみてください。そうすると、オイラーの公式は次のように書けます。

$$ M^{z\phi(ab)+1}=M \pmod{ab} $$ ここで、「$\phi(ab)=\phi(a)\phi(a)=(a-1)(b-1)$」ということを思い出してください。

すると、「オイラーの公式」は次のように書けます。
$$ M^{z(a-1)(b-1)+1}=M \pmod{ab} $$ 面倒くさそうな$z\phi(n)$がなくなりましたね。

あとは「$ps = z(a-1)(b-1)+1$」になるような$ps$を見つけることができればOKです。

「$ps = z(a-1)(b-1)+1$」となる$ps$の見つけ方

結論から言えば、$p$と$(a-1)(b-1)$が互いに素、$s$と$(a-1)(b-1)$が互いに素であれば、$p,s,z$を見つけることができます。

これは、「オイラーの定理」を証明したときと似たような方法で証明できます。
簡単に説明しときますね。

記号がややこしくなるので、「$(a-1)(b-1)=x$」と置いて、お話させてください。
次のような$x-1$個の数の集まりを考えます。

「$p,2p,3p,\cdots ,(x-2)p ,(x-1)p$」

このとき、この$x-1$個の数字を、$x$で割り算したときの余りを考えます。
この余りは、一緒になることはありません。

だって、もし「$ip$と$jp$を$x$で割った余りが同じ」だと考えてみて下さい。
この$ip)$と$jp$は「$p,2p,3p,\cdots ,(x-2)p ,(x-1)p$」から2つの数字をとってきたものです。
($i$と$j$は($1,2,3,\cdots,(x-2),(x-1)$)のどれかですよ)

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

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

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

でもでも、思い出してください。
$i$と$j$は「($1,2,3,\cdots,(x-2),(x-1)$)のどれか」でしたね。

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

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

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

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

ということは、「$ip$と$jp$を$x$で割った余りは違う」ということになります。
つまり、「$p,2p,3p,\cdots ,(x-2)p ,(x-1)p$」の$x-1$個の数字を、$x$で割り算したときの余りは、全部違うということです。

一方で、$x$で割り算したときの余りは「$1,2,3,\cdots,(x-2),(x-1)$」の$x-1$種類のどれかになるはずです。

この2つのことを合わせて考えると、「$p,2p,3p,\cdots ,(x-2)p ,(x-1)p$」を$x$で割り算したときの余りは「$1,2,3,\cdots,(x-2),(x-1)$」のどれかになるということですね。

ということは、「$p,2p,3p,\cdots ,(x-2)p ,(x-1)p$」を$x$で割り算したときの余りが「$1$」となる数が1つ必ずあるはずです。

それを、「$Sp$」とします（$S$は「$1,2,3,\cdots,(x-2),(x-1)$」のどれかです）。
そして、それを$x$で割り算したときの商を$Z$とすると、「$Sp=Zx+1$」と書けます。

「$x=(a-1)(b-1)$」と置いていたので、それをもとに戻すと「$Sp=Z(a-1)(b-1)+1$」となります。

もともとの疑問は、$p$と$(a-1)(b-1)$が互いに素、$s$と$(a-1)(b-1)$が互いに素であれば、$ps = z(a-1)(b-1)+1$」となる$p,s,z$を発見できるかということでしたが、今解説した方法を使うと、$p,s,z$を発見できることがわかりました。

まとめると・・・

ある素数$a$と$b$があって、$p$と$(a-1)(b-1)$が互いに素、$s$と$(a-1)(b-1)$が互いに素であれば次の式が成り立ちます。
$$ M^{ps}=M \pmod ab $$ いやぁ・・・やっとゴールまでたどり着けました。
オイラーの公式を変形してここまでたどり着けることを、しっかりと覚えておいてくださいね。

次回のお知らせ

ここまで、いろんな解説にお付き合いいただきありがとうございます。
次回は、いままで解説してきたことを総まとめして、「公開鍵暗号」の実現方法について解説します。

これで、あなたも「公開鍵暗号」マスターです！！

「公開鍵暗号」の概念を数式にしてみよう

\(\phi\)関数の秘密を知ろう

オイラーの定理の変形

「\(ps = z(a-1)(b-1)+1\)」となる\(ps\)の見つけ方

まとめると・・・

次回のお知らせ