こんにちは！
今日は、前回解説した「大きな数の累乗の余りを計算する方法」を使って、「$7846^{13709}$」の計算をしてみましょう。
これで、暗号化する前の元のメッセージが出てきたら、大成功です！！

暗号の話に戻りましょう

それでは、早速前々回の復習です。

重要事項その2：暗号を$s$乗して$n$で割った余りは、元のメッセージ$M$に等しくなるということで、先ほどの暗号(7846)を解読しましょう！

それでは、「7846」を秘密鍵「13709」乗して、「34691」で割り算した余りを見てみましょう。

前回解説した方法を使って、「$7846^{13709} \pmod{34691}$」を計算してみましょう

「$(7846)^{13709} \pmod {34691} = (7846^{2})^{6854} \times 7846 \pmod {34691} = (61559716)^{6854} \times 7846 \pmod {34691}$」と書けます。
そして、$61559716 \pmod {34691} = 17882$なので、「$(61559716)^{6854} \times 7846 \pmod {34691} = (17882)^{6854} \times 7846 \pmod {34691}$」と書けます。

こんな感じで、すこしずつ累乗を小さくしていく地道な取り組みを、あと12回繰り返します・・・・。

「$(17882)^{6854} \times 7846 \pmod {34691} = (17882^{2})^{3427} \times 7846 \pmod {34691} = (319765924)^{3427} \times 7846 \pmod {34691}$」と書けます。
そして、$319765924 \pmod {34691} = 18977$なので、「$(319765924)^{3427} \times 7846 \pmod {34691} = (18977)^{3427} \times 7846 \pmod {34691}$」と書けます。

飽きた人は読み飛ばしてもいいですよ・・・・。

「$(18977)^{3427} \times 7846 \pmod {34691} = (18977^{2})^{1713} \times 7846 \times 18977 \pmod {34691} = (360126529)^{1713} \times 7846 \times 18977 \pmod {34691}$」と書けます。
そして、$360126529 \pmod {34691} = 33949$なので、「$(360126529)^{1713} \times 7846 \times 18977 \pmod {34691} = (33949)^{1713} \times 7846 \times 18977 \pmod {34691}$」と書けます。

まだまだやります。

「$(33949)^{1713} \times 7846 \times 18977 \pmod {34691} = (33949^{2})^{856} \times 7846 \times 18977 \times 33949 \pmod {34691} = (1152534601)^{856} \times 7846 \times 18977 \times 33949 \pmod {34691}$」と書けます。
そして、$1152534601 \pmod {34691} = 30199$なので、「$(1152534601)^{856} \times 7846 \times 18977 \times 33949 \pmod {34691} = (30199)^{856} \times 7846 \times 18977 \times 33949 \pmod {34691}$」と書けます。

まだまだやります。

「$(30199)^{856} \times 7846 \times 18977 \times 33949 \pmod {34691} = (30199^{2})^{428} \times 7846 \times 18977 \times 33949 \pmod {34691} = (911979601)^{428} \times 7846 \times 18977 \times 33949 \pmod {34691}$」と書けます。
そして、$911979601 \pmod {34691} = 22593$なので、「$(911979601)^{428} \times 7846 \times 18977 \times 33949 \pmod {34691} = (22593)^{428} \times 7846 \times 18977 \times 33949 \pmod {34691}$」と書けます。

まだまだやります。

「$(22593)^{428} \times 7846 \times 18977 \times 33949 \pmod {34691} = (22593^{2})^{214} \times 7846 \times 18977 \times 33949 \pmod {34691} = (510443649)^{214} \times 7846 \times 18977 \times 33949 \pmod {34691}$」と書けます。
そして、$510443649 \pmod {34691} = 275$なので、「$(510443649)^{214} \times 7846 \times 18977 \times 33949 \pmod {34691} = (275)^{214} \times 7846 \times 18977 \times 33949 \pmod {34691}$」と書けます。

まだまだやります。

「$(275)^{214} \times 7846 \times 18977 \times 33949 \pmod {34691} = (275^{2})^{107} \times 7846 \times 18977 \times 33949 \pmod {34691} = (75625)^{107} \times 7846 \times 18977 \times 33949 \pmod {34691}$」と書けます。
そして、$75625 \pmod {34691} = 6243$なので、「$(75625)^{107} \times 7846 \times 18977 \times 33949 \pmod {34691} = (6243)^{107} \times 7846 \times 18977 \times 33949 \pmod {34691}$」と書けます。

まだまだやります。

「$(6243)^{107} \times 7846 \times 18977 \times 33949 \pmod {34691} = (6243^{2})^{53} \times 7846 \times 18977 \times 33949 \times 6243 \pmod {34691} = (38975049)^{53} \times 7846 \times 18977 \times 33949 \times 6243 \pmod {34691}$」と書けます。
そして、$38975049 \pmod {34691} = 17056$なので、「$(38975049)^{53} \times 7846 \times 18977 \times 33949 \times 6243 \pmod {34691} = (17056)^{53} \times 7846 \times 18977 \times 33949 \times 6243 \pmod {34691}$」と書けます。

あと少しです。

「$(17056)^{53} \times 7846 \times 18977 \times 33949 \times 6243 \pmod {34691} = (17056^{2})^{26} \times 7846 \times 18977 \times 33949 \times 6243 \times 17056 \pmod {34691} = (290907136)^{26} \times 7846 \times 18977 \times 33949 \times 6243 \times 17056 \pmod {34691}$」と書けます。
そして、$290907136 \pmod {34691} = 23101$なので、「$(290907136)^{26} \times 7846 \times 18977 \times 33949 \times 6243 \times 17056 \pmod {34691} = (23101)^{26} \times 7846 \times 18977 \times 33949 \times 6243 \times 17056 \pmod {34691}$」と書けます。

まだまだやります。

「$(23101)^{26} \times 7846 \times 18977 \times 33949 \times 6243 \times 17056 \pmod {34691} = (23101^{2})^{13} \times 7846 \times 18977 \times 33949 \times 6243 \times 17056 \pmod {34691} = (533656201)^{13} \times 7846 \times 18977 \times 33949 \times 6243 \times 17056 \pmod {34691}$」と書けます。
そして、$533656201 \pmod {34691} = 4548$なので、「$(533656201)^{13} \times 7846 \times 18977 \times 33949 \times 6243 \times 17056 \pmod {34691} = (4548)^{13} \times 7846 \times 18977 \times 33949 \times 6243 \times 17056 \pmod {34691}$」と書けます。

まだまだやります。

「$(4548)^{13} \times 7846 \times 18977 \times 33949 \times 6243 \times 17056 \pmod {34691} = (4548^{2})^{6} \times 7846 \times 18977 \times 33949 \times 6243 \times 17056 \times 4548 \pmod {34691} = (20684304)^{6} \times 7846 \times 18977 \times 33949 \times 6243 \times 17056 \times 4548 \pmod {34691}$」と書けます。
そして、$20684304 \pmod {34691} = 8468$なので、「$(20684304)^{6} \times 7846 \times 18977 \times 33949 \times 6243 \times 17056 \times 4548 \pmod {34691} = (8468)^{6} \times 7846 \times 18977 \times 33949 \times 6243 \times 17056 \times 4548 \pmod {34691}$」と書けます。

まだまだやります。

「$(8468)^{6} \times 7846 \times 18977 \times 33949 \times 6243 \times 17056 \times 4548 \pmod {34691} = (8468^{2})^{3} \times 7846 \times 18977 \times 33949 \times 6243 \times 17056 \times 4548 \pmod {34691} = (71707024)^{3} \times 7846 \times 18977 \times 33949 \times 6243 \times 17056 \times 4548 \pmod {34691}$」と書けます。
そして、$71707024 \pmod {34691} = 727$なので、「$(71707024)^{3} \times 7846 \times 18977 \times 33949 \times 6243 \times 17056 \times 4548 \pmod {34691} = (727)^{3} \times 7846 \times 18977 \times 33949 \times 6243 \times 17056 \times 4548 \pmod {34691}$」と書けます。


あと1回！

「$(727)^{3} \times 7846 \times 18977 \times 33949 \times 6243 \times 17056 \times 4548 \pmod {34691} = (727^{2})^{1} \times 7846 \times 18977 \times 33949 \times 6243 \times 17056 \times 4548 \times 727 \pmod {34691} = (528529)^{1} \times 7846 \times 18977 \times 33949 \times 6243 \times 17056 \times 4548 \times 727 \pmod {34691}$」と書けます。
そして、$528529 \pmod {34691} = 8164$なので、「$(528529)^{1} \times 7846 \times 18977 \times 33949 \times 6243 \times 17056 \times 4548 \times 727 \pmod {34691} = (8164)^{1} \times 7846 \times 18977 \times 33949 \times 6243 \times 17056 \times 4548 \times 727 \pmod {34691}$」と書けます。



ふーーーーーーーーーー。お疲れさまでした。

最後に残った式は、「$(8164)^1 \times 7846 \times 18977 \times 33949 \times 6243 \times 17056 \times 4548 \times 727 \pmod {34691}$」というものでした。
あとは、これを計算すれば、終わりです。

本当に、こんなんで元のメッセージを解読できているのでしょうか？

「$(8164)^1 \times 7846 \times 18977 \times 33949 \times 6243 \times 17056 \times 4548 \times 727 \pmod{34691}$」の掛け算を全部一気にやるのはしんどい(数が大きくなりすぎる)ので、隣同士の2個ずつの掛け算をまずすると、「$64054744 \times 644250173 \times 106480608 \times 3306396 \pmod{34691}$」となります。

そして、64054744、644250173、106480608、3306396をそれぞれ「34691」で割ると、余りは、15158、3612、13929、10751なので、「$64054744 \times 644250173 \times 106480608 \times 3306396 \pmod{34691} = 15158 \times 3612 \times 13929 \times 10751 \pmod{34691}$」となります。

まだまだ、全部掛け算するのはしんどいので、またまた隣同士の掛け算をすると、「$64054744 \times 644250173 \times 106480608 \times 3306396 \pmod{34691} = 54750696 \times 149750679 \pmod{34691}$」となります。

そして、54750696、149750679をそれぞれ「34691」で割ると、余りは、8298、24323なので「$54750696 \times 149750679 \pmod{34691} = 8298 \times 24323 \pmod{34691}$」となります。


ようやくゴールが見えてきました。

最後の計算をしましょう。
「$8298 \times 24323 \pmod{34691} = 201832254 \pmod{34691} = 16$」となります！！

でました！答えは「16」です。きたぁーーーーーーーーーーーーーーー！！！

見事に、元の暗号文が解読できています。

長い、長い道のりでした。。。。。

暗号を解読する度にこんなことしなくてはいけないの？？

今回は、手作業で計算したのでしんどかったですが、この計算はパソコンにさせればあっという間にできてしまいます。
なので、秘密鍵($s$)を知っている人は、暗号文から元の文がすぐにわかるようになってるんです。


とはいえ、パソコンを使っても「公開鍵暗号」の計算より「共通鍵暗号」の計算のほうが楽です。
なので、世の中ではハイブリッド型が使われています。

ハイブリッド型とは、「共通鍵暗号」の「鍵」を伝える部分だけ「公開鍵暗号」に方式を使って行い、安全に共通鍵暗号の鍵が相手に伝わったら、共通鍵暗号でメッセージをやりとりするというものです。
公開鍵暗号を使うのは、はじめの一回だけですむので、何度もメッセージをやり取りする場合などは便利なんです。

次回のお知らせ

さて、ここまでの解説で暗号の作り方・解読の仕方はわかっていただけたと思います。

でも、どうして重要事項その1、その2が成り立つのでしょうか？
そして、公開鍵$p$と、秘密鍵$s$と、謎の数字$n$はどうやって作成するのでしょうか？

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


次回からこの謎に迫っていきます。お楽しみを！