もう一度、暗号化の方法を復習

これまで、見てきた内容を踏まえて、もう一度暗号化の方法を簡単に振り返りましょう。

イメージしやすいように、私が暗号メッセージを受け取る人のつもりになって書いてみます。

事前準備：2つの素数$a$と$b$と、「$ps=z(a-1)(b-1)+1$」が成り立つ$p,s$の二つの数字を用意し、$ab,p$を世の中に公開する。
(但し、$a$、$b$は公開しちゃダメですよ。あくまで$a \times b$の値だけ公開します)

公開する方法はなんでもいいです。例えば、自分のホームページに「私に暗号メッセージを送りたい人はこの$ab,p$を使ってね」と書くとか。

暗号送信：私に暗号メッセージを送りたい人は、送りたいメッセージを何らかの方法で数字に変換し、私のホームページ上に掲載されている$ab,p$の二つの数字を使って、以下の数式で変換したものを送ってもらう。

$$ M^p \pmod ab $$ ちなみに、$M$というのが、送りたいメッセージを何らかの方法で数字に変換したものです。

暗号受信：暗号化したメッセージを受け取ると、私は自分しかしらない数字($s$)を使って、次の変換を行って暗号を解読する。
$$ R^s \pmod ab $$ ちなみに、$R$というのが、暗号化されたメッセージです。

なぜ、これでうまくいくかもう一度おさらい

なぜ、これで元のメッセージがでるかという点について、今まで解説してきたことを総動員して解説します。

$R$は、結局$M^p \pmod{ab}$だったので、$R^s \pmod {ab}$は$M^{ps} \pmod {ab}$となります。

そして、$p,s$は$ps = z(a-1)(b-1)+1$だったので、$M^{ps} \pmod {ab}$は$M^{z(a-1)(b-1)+1} \pmod {ab}$となります。

$M^{z(a-1)(b-1)+1} \pmod {ab}$を少し変形すると、$M \times (M^{(a-1)(b-1)})^z \pmod {ab}$となります。
そして、$a$、$b$が素数のとき、$\phi(ab)=\phi(a)\phi(b)=(a-1)(b-1)$となる事実を使うと、$M \times (M^{(a-1)(b-1)})^z \pmod {ab}$は$M \times (M^{\phi(ab)})^z \pmod {ab}$と書けます。

最後に、オイラーの定理「$M^{phi(n)}=1 \pmod n$」という事実を使うと$M \times (M^\phi(ab))^z \pmod {ab}$は$M \times 1^z \pmod {ab}$となり、これは$M \pmod {ab}$となります。

結局、暗号化されたメッセージ$R$を$s$乗すると、$R^s = M \pmod {ab}$となり、元のメッセージを知ることができます。

これで、公開鍵暗号の仕組みをぜーーーんぶ知ったことになります。おめでとうございます！！

次回のお知らせ

次回は、この解説の締めくくりとして、公開鍵暗号は本当に安全なのか（秘密鍵($s$)を知らない人に、本当に元のメッセージがバレないのか）という点を見てみます。