はーい。今日も元気にマニアックな内容について解説します！
今回は公開鍵暗号の流れを、具体例を使って解説していきます。
前回はイメージだけだったので、具体例を見て更に納得してみてください。
今回は、具体的な数字で解説してみますので、雰囲気をつかんでみましょう。
今回は、メッセージ(\(M\))を「16」としてみます。そして、公開鍵(\(p\))を「5」、秘密鍵(\(s\))を「13709」、謎の数字(\(n\))を「34691」とします。
(公開鍵(\(p\)、秘密鍵(\(s\))、謎の数字(\(n\))の作り方は後程説明します。)
前回解説した暗号の作り方は「メッセージ(\(M\))を\(p\)乗して\(n\)で割った余り」でした。
このことを、数式で書くと「\(16^5 \pmod{34691}\)」と書けます。
「\(\pmod n\)」というのは、「nで割り算した余り」を意味しています。
今回の場合、「\(16^5\)=1048576」なので、それを「\(n=34691\)」で割り算すると、答えは「7846」となります。
たった、これだけで暗号化は終了です。
本当に暗号化できているか考えてみましょう。
もし、この「7846」と、「\(p=5\)」と「\(n=34691\)」が悪い人にバレたとします。
つまり、悪い人は「何かの数字を\(p\)乗(今回の場合は5乗)して、\(n\)(今回の場合は34691)で割った余りが7846」ということを知っているわけです。
このとき、悪い人は「何かの数字」を推測することはできるでしょうか？
皆さんも、悪い人になったつもりで、やってみてください。(答えは16になることを皆さんは知ってますが、知らないふりして考えてくださいね)
わかりました？
難しいですよね・・・。実はめちゃくちゃ難しいんです。
例えば、34691で割った余りが7846になる数として、「42537」があります。
ということは、求めたい数字を\(x\)とすると、\(x^5=42537\)になればいいのですが、そんな\(x\)はあるでしょうか？
\(x\)を適当に10だと思ってみましょう。\(10^5=100000\)なので「42537」より大きくなっちゃいます。
では、\(x\)に9を当てはめてみましょう。すると、\(9^5=59049\)なのでまだ、「42537」より大きくなっちゃいます。
じゃあ、\(x\)に8ではどうでしょうか？。すると、\(8^5=32768\)なので、今度は「42537」より小さくなってしまいます・・・・。
あれ？\(x\)に当てはまる数がない！？ってことになりません？
いえいえ、そうではないんです。
初めに34691で割った余りが7846になる数として「42537」としましたが、「77228」も34691で割った余りが7846になる数ですし、「111919」もそうです・・・
このように、34691で割った余りが7846になる数は無限にあるんです。
そのため、\(x\)を見つけるためには、いろんな「34691で割った余りが7846になる数」で先ほどのような探索が必要になります。
これって、計算するのにめちゃくちゃ時間がかかりますよね。だから、めちゃくちゃ難しくて、現実的には解読することは無理なんです。
例えめちゃめちゃがんばって、10年かけて解読しても、10年後にはその暗号には意味がなくなってることが多いですよね。
先ほど書いた重要事項をもう一回書きますので、見てください。
重要事項その2：暗号を\(s\)乗して\(n\)で割った余りは、元のメッセージ\(M\)に等しくなる
ふむふむ。受け取った暗号を秘密鍵(\(s\))乗して、\(n\)で割るだけでいいんだ。。。めっちゃ簡単じゃないっすか！
では、早速、「7846」を秘密鍵「13709」乗して、「34691」で割り算した余りを見てみましょう。
まず、「\(7846^{13709}\)」を計算してみましょう・・・・・。って、すんごい大きい数になってしまいそうですよね。。。
どうしましょ。
そこで、次回は、ちょっとだけ寄り道して、大きな数の累乗の余り計算をする方法を解説しましょう。
この方法がわかれば、どんな大きい数字の計算でも自由にできるようになります！乞うご期待でございます！！
今回は公開鍵暗号の流れを、具体例を使って解説していきます。
前回はイメージだけだったので、具体例を見て更に納得してみてください。
今回は、具体事例の紹介なので覚えることはないんです・・・。たまにはこんな日も(^_^)
公開鍵暗号の具体例
前回の解説では、\(M\)や\(p,s,n\)といった記号を使って解説しましたが、記号だけではイメージがわきにくいですね。今回は、具体的な数字で解説してみますので、雰囲気をつかんでみましょう。
今回は、メッセージ(\(M\))を「16」としてみます。そして、公開鍵(\(p\))を「5」、秘密鍵(\(s\))を「13709」、謎の数字(\(n\))を「34691」とします。
(公開鍵(\(p\)、秘密鍵(\(s\))、謎の数字(\(n\))の作り方は後程説明します。)
前回解説した暗号の作り方は「メッセージ(\(M\))を\(p\)乗して\(n\)で割った余り」でした。
このことを、数式で書くと「\(16^5 \pmod{34691}\)」と書けます。
「\(\pmod n\)」というのは、「nで割り算した余り」を意味しています。
今回の場合、「\(16^5\)=1048576」なので、それを「\(n=34691\)」で割り算すると、答えは「7846」となります。
たった、これだけで暗号化は終了です。
本当に暗号化できているか考えてみましょう。
本当に暗号化できてるの？
元のメッセージは「16」でした。それを暗号化すると「7846」になりました。もし、この「7846」と、「\(p=5\)」と「\(n=34691\)」が悪い人にバレたとします。
つまり、悪い人は「何かの数字を\(p\)乗(今回の場合は5乗)して、\(n\)(今回の場合は34691)で割った余りが7846」ということを知っているわけです。
このとき、悪い人は「何かの数字」を推測することはできるでしょうか？
皆さんも、悪い人になったつもりで、やってみてください。(答えは16になることを皆さんは知ってますが、知らないふりして考えてくださいね)
わかりました？
難しいですよね・・・。実はめちゃくちゃ難しいんです。
例えば、34691で割った余りが7846になる数として、「42537」があります。
ということは、求めたい数字を\(x\)とすると、\(x^5=42537\)になればいいのですが、そんな\(x\)はあるでしょうか？
\(x\)を適当に10だと思ってみましょう。\(10^5=100000\)なので「42537」より大きくなっちゃいます。
では、\(x\)に9を当てはめてみましょう。すると、\(9^5=59049\)なのでまだ、「42537」より大きくなっちゃいます。
じゃあ、\(x\)に8ではどうでしょうか？。すると、\(8^5=32768\)なので、今度は「42537」より小さくなってしまいます・・・・。
あれ？\(x\)に当てはまる数がない！？ってことになりません？
いえいえ、そうではないんです。
初めに34691で割った余りが7846になる数として「42537」としましたが、「77228」も34691で割った余りが7846になる数ですし、「111919」もそうです・・・
このように、34691で割った余りが7846になる数は無限にあるんです。
そのため、\(x\)を見つけるためには、いろんな「34691で割った余りが7846になる数」で先ほどのような探索が必要になります。
これって、計算するのにめちゃくちゃ時間がかかりますよね。だから、めちゃくちゃ難しくて、現実的には解読することは無理なんです。
例えめちゃめちゃがんばって、10年かけて解読しても、10年後にはその暗号には意味がなくなってることが多いですよね。
意味不明の数字に変換された暗号を受け取った人はどうするればいいの？
ここで登場するのが、秘密鍵\(s\)です。先ほど書いた重要事項をもう一回書きますので、見てください。
重要事項その2：暗号を\(s\)乗して\(n\)で割った余りは、元のメッセージ\(M\)に等しくなる
ふむふむ。受け取った暗号を秘密鍵(\(s\))乗して、\(n\)で割るだけでいいんだ。。。めっちゃ簡単じゃないっすか！
では、早速、「7846」を秘密鍵「13709」乗して、「34691」で割り算した余りを見てみましょう。
まず、「\(7846^{13709}\)」を計算してみましょう・・・・・。って、すんごい大きい数になってしまいそうですよね。。。
どうしましょ。
次回のお知らせ
次回は、今回の続きで暗号化された「7846」という数字を解読しよう！と思ったのですが、大きな数字を計算する方法が必要そうです。そこで、次回は、ちょっとだけ寄り道して、大きな数の累乗の余り計算をする方法を解説しましょう。
この方法がわかれば、どんな大きい数字の計算でも自由にできるようになります！乞うご期待でございます！！