こんにちは。いよいよ、公開鍵暗号の最後の解説記事です。
さみしいですか？・・・むしろ、ようやく終わったという気持ちの方が多い気がします。
最後は公開鍵暗号の安全性についてです。
「共通鍵方式」のように、鍵自体を他人に教える必要がないので\(s\)がバレる可能性は低いですが、みんなに教えている\(p\)や\(ab\)から\(s\)を推定されてしまったら困りますよね。
\(s\)は、\(ps = z(a-1)(b-1)+1\)が成り立つように作られていました。
すでに\(p\)はみんなに教えていますし、\(z\)はどんな整数でもいいので、この式の中で\(a\)と\(b\)がバレれば、\(s\)を他人が計算することもできてしまいます。
では、\(a\)、\(b\)はバレてしまう可能性はあるのでしょうか？
一番の脅威は「\(ab\)」をみんなに教えているということです。
皆さんは、\(133\)という数字から、\(a,b\)を推定できますか？
\(a,b\)は素数ということがわかっているので、あてずっぽうですが、例えば\(a=3\)だと思ってみましょうか。
\(a=3\)のとき、これに掛け算して\(133\)になる都合のいい\(b\)は見つかりません。。(「\(133 \div 3 = 44.33333 \cdots \)」なので、\(b\)がうまく計算できないですね)
では、\(a\)を他の素数だと思って確かめてみましょう。実は、\(a=5\)のときもうまく行きません。
うまくいくのは、\(a=7\)のときです。このとき、\(b=19\)となり、\(a,b\)を推測したことになります。
結局、\(a,b\)がバレるのか！？危なくない？
いやいや、早とちりしないでください。
先ほどは、「\(ab=133\)」ぐらいの大きさだったから、「\(a=3,a=5,a=7\)」と適当に\(a\)を当てはめていくと\(b\)を見つけることができました。
でも、「\(ab\)」が次のような数だったらどうでしょうか。
(これは、googleが公開している\(ab\)です)
22340958030155388525612362890176830581462852590410727187378168104311508658126996249607429594527042742471528419537303094520457508048799216947022053214519659267715706807066088918149612927006970522424957487146051206740408211030975705256528502123279347425109843556467505667667853903972940905103400919562835461269943098372804418694718838828910921912754910697910309565810908175406548611570793559339905347100072534216086613092470244838590349475551496566181250264386614819416648400716116099115122547586611215238120612414168152402668302781682867734827130661976392229547785874639998505311456469135214428245476589579458483157129
・・・・。
・・・・・・・・。
絶対無理ですよね・・・。
こんな巨大数字を割り切れる\(a\)を試行錯誤で探すなんで、コンピュータを使っても何十年という時間がかかってしまいます。。
だから、巨大な\(ab\)を作る（\(a\)や\(b\)を巨大な素数にする）と、\(ab\)を教えても\(a\)や\(b\)は推測されないのです。
「\(a \times b\)」を計算することは簡単なのですが、「\(a \times b\)」から\(a\)や\(b\)を計算するのはとっても大変なんですね。
そういったテクノロジーの中で、最も有力視されているのが量子コンピュータです。
量子コンピュータは、大量の計算を一瞬で計算する能力があります。
だから、たくさんの\(a\)の候補に対して、一瞬で巨大な数字が割り切れるかどうかを判定することができるかもしれないのです。
いまのところ、量子コンピュータは実現するかどうかわかりませんが、世の中の人たちは量子コンピュータが実現すると現在使っている暗号が安全じゃなくなると考えているのはこの事情からです。
ふーー。長い間、付き合っていただきありがとうございました。
私たちが普段使っている暗号について、少しでも仕組みをゼロから理解してもらえれば幸いです。
ちなみに、この公開鍵暗号の方式は、今回解説したRSA暗号以外にも、楕円曲線暗号やDSA等があります。
興味があったら、他の方式も調べてみてくださいね。
さみしいですか？・・・むしろ、ようやく終わったという気持ちの方が多い気がします。
最後は公開鍵暗号の安全性についてです。
\(p\)や\(ab\)を教えたときに、\(a\)、\(b\)、\(s\)はバレないの？
暗号の仕組みはわかったのですが、\(s\)が他の人にバレてしまったら終わりです。「共通鍵方式」のように、鍵自体を他人に教える必要がないので\(s\)がバレる可能性は低いですが、みんなに教えている\(p\)や\(ab\)から\(s\)を推定されてしまったら困りますよね。
\(s\)は、\(ps = z(a-1)(b-1)+1\)が成り立つように作られていました。
すでに\(p\)はみんなに教えていますし、\(z\)はどんな整数でもいいので、この式の中で\(a\)と\(b\)がバレれば、\(s\)を他人が計算することもできてしまいます。
では、\(a\)、\(b\)はバレてしまう可能性はあるのでしょうか？
一番の脅威は「\(ab\)」をみんなに教えているということです。
「\(ab\)」から「\(a\)」、「\(b\)」を推測することは可能か？
例えば、「\(ab=133\)」だったとしましょう。皆さんは、\(133\)という数字から、\(a,b\)を推定できますか？
\(a,b\)は素数ということがわかっているので、あてずっぽうですが、例えば\(a=3\)だと思ってみましょうか。
\(a=3\)のとき、これに掛け算して\(133\)になる都合のいい\(b\)は見つかりません。。(「\(133 \div 3 = 44.33333 \cdots \)」なので、\(b\)がうまく計算できないですね)
では、\(a\)を他の素数だと思って確かめてみましょう。実は、\(a=5\)のときもうまく行きません。
うまくいくのは、\(a=7\)のときです。このとき、\(b=19\)となり、\(a,b\)を推測したことになります。
結局、\(a,b\)がバレるのか！？危なくない？
いやいや、早とちりしないでください。
先ほどは、「\(ab=133\)」ぐらいの大きさだったから、「\(a=3,a=5,a=7\)」と適当に\(a\)を当てはめていくと\(b\)を見つけることができました。
でも、「\(ab\)」が次のような数だったらどうでしょうか。
(これは、googleが公開している\(ab\)です)
22340958030155388525612362890176830581462852590410727187378168104311508658126996249607429594527042742471528419537303094520457508048799216947022053214519659267715706807066088918149612927006970522424957487146051206740408211030975705256528502123279347425109843556467505667667853903972940905103400919562835461269943098372804418694718838828910921912754910697910309565810908175406548611570793559339905347100072534216086613092470244838590349475551496566181250264386614819416648400716116099115122547586611215238120612414168152402668302781682867734827130661976392229547785874639998505311456469135214428245476589579458483157129
・・・・。
・・・・・・・・。
絶対無理ですよね・・・。
こんな巨大数字を割り切れる\(a\)を試行錯誤で探すなんで、コンピュータを使っても何十年という時間がかかってしまいます。。
だから、巨大な\(ab\)を作る（\(a\)や\(b\)を巨大な素数にする）と、\(ab\)を教えても\(a\)や\(b\)は推測されないのです。
「\(a \times b\)」を計算することは簡単なのですが、「\(a \times b\)」から\(a\)や\(b\)を計算するのはとっても大変なんですね。
いや、そうはいってもテクノロジーは進化するから、そのうち\(ab\)から\(a,b\)を推測することができるようになるのでは？
確かに、世の中が進化すると巨大な数字から\(a,b\)を推測することができるようになるかもしれません。そういったテクノロジーの中で、最も有力視されているのが量子コンピュータです。
量子コンピュータは、大量の計算を一瞬で計算する能力があります。
だから、たくさんの\(a\)の候補に対して、一瞬で巨大な数字が割り切れるかどうかを判定することができるかもしれないのです。
いまのところ、量子コンピュータは実現するかどうかわかりませんが、世の中の人たちは量子コンピュータが実現すると現在使っている暗号が安全じゃなくなると考えているのはこの事情からです。
終わりに
これで、公開鍵暗号の解説は終わりです。ふーー。長い間、付き合っていただきありがとうございました。
私たちが普段使っている暗号について、少しでも仕組みをゼロから理解してもらえれば幸いです。
ちなみに、この公開鍵暗号の方式は、今回解説したRSA暗号以外にも、楕円曲線暗号やDSA等があります。
興味があったら、他の方式も調べてみてくださいね。