こんにちは。いよいよ、公開鍵暗号の最後の解説記事です。
さみしいですか?・・・むしろ、ようやく終わったという気持ちの方が多い気がします。
最後は公開鍵暗号の安全性についてです。
「共通鍵方式」のように、鍵自体を他人に教える必要がないので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÷3=44.33333⋯」なので、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×b」を計算することは簡単なのですが、「a×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÷3=44.33333⋯」なので、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×b」を計算することは簡単なのですが、「a×b」からaやbを計算するのはとっても大変なんですね。
いや、そうはいってもテクノロジーは進化するから、そのうちabからa,bを推測することができるようになるのでは?
確かに、世の中が進化すると巨大な数字からa,bを推測することができるようになるかもしれません。そういったテクノロジーの中で、最も有力視されているのが量子コンピュータです。
量子コンピュータは、大量の計算を一瞬で計算する能力があります。
だから、たくさんのaの候補に対して、一瞬で巨大な数字が割り切れるかどうかを判定することができるかもしれないのです。
いまのところ、量子コンピュータは実現するかどうかわかりませんが、世の中の人たちは量子コンピュータが実現すると現在使っている暗号が安全じゃなくなると考えているのはこの事情からです。
終わりに
これで、公開鍵暗号の解説は終わりです。ふーー。長い間、付き合っていただきありがとうございました。
私たちが普段使っている暗号について、少しでも仕組みをゼロから理解してもらえれば幸いです。
ちなみに、この公開鍵暗号の方式は、今回解説したRSA暗号以外にも、楕円曲線暗号やDSA等があります。
興味があったら、他の方式も調べてみてくださいね。