こんにちは！
今日は、前回解説した「大きな数の累乗の余りを計算する方法」を使って、「\(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\)に等しくなる
次回からこの謎に迫っていきます。お楽しみを！
今日は、前回解説した「大きな数の累乗の余りを計算する方法」を使って、「\(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\)に等しくなる
次回からこの謎に迫っていきます。お楽しみを！