RSA暗号の強度

せっかくトラックバックを通じて質問いただいたので、お答えしたいと思います。

質問

とある文献に鍵長1024ビットのRSA暗号と鍵長70ビットの共通鍵暗号の安全性は同等と書かれていました。また、鍵長2048ビットのRSA暗号と鍵長100ビットの共通鍵暗号の安全性は同等とも書かれていました。RSA暗号の強度ってそんなものなんでしょうか？

回答

そんなものです。

さすがにこれでは何なので、もう少し想定質問とその回答を書いておきます。

質問１

そもそもRSA暗号の安全性と共通鍵暗号の安全性は比較できるのですか？

回答１

できます。まず、暗号の安全性を、解読に必要な計算時間(またはメモリ量)と定義します。ここで計算時間は、最良の解読方法を最良に実装した場合で考えます。例えば鍵長80ビットの(理想的な)共通鍵暗号の場合、暗号文を解読する最良の方法はしらみつぶし的に全ての鍵をチェックすることなので、解読に必要な計算時間は 2^80 (2の80乗) 回の復号に必要な時間です。RSA 暗号の場合、数体篩法と呼ばれる素因数分解法が最良であり、この実行時間によって安全性を測定します。異なる暗号の安全性は、解読に必要な計算時間によって比べます。

質問２

RSA暗号はもう少し強いように思うのですが？

回答２

以前は「鍵長1024ビットのRSA暗号の安全性は鍵長80ビットの共通鍵の安全性と等しい」と思われていました。今でもそのように書かれている文献は多いでしょう。しかしここ数年で数体篩法の理論・実装が急速に進展したため、RSA暗号の解読に必要な計算時間は低下し、その安全性は思ったよりも低いことがわかりました。今では「鍵長1024ビットのRSA暗号の安全性は鍵長70ビットの共通鍵の安全性と同等」と思われています。

質問３

RSA暗号はもう少し弱いように思うのですが？

回答３

思うだけではどなたも信じないでしょうから、是非、それを裏付ける理由(高速な素因数分解法の考案、数体篩法による高速な素因数分解結果など)を教えて下さい。