2017年4月
            1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
30            
無料ブログはココログ

« NHKスペシャル: 『魔性の難問~リーマン予想・天才たちの闘い~』の再放送 | トップページ | FC 2010: Accepted Papers »

RSA暗号の強度

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

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

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

質問1
そもそもRSA暗号の安全性と共通鍵暗号の安全性は比較できるのですか?
回答1
できます。まず、暗号の安全性を、解読に必要な計算時間(またはメモリ量)と定義します。ここで計算時間は、最良の解読方法を最良に実装した場合で考えます。例えば鍵長80ビットの(理想的な)共通鍵暗号の場合、暗号文を解読する最良の方法はしらみつぶし的に全ての鍵をチェックすることなので、解読に必要な計算時間は 2^80 (2の80乗) 回の復号に必要な時間です。RSA 暗号の場合、数体篩法と呼ばれる素因数分解法が最良であり、この実行時間によって安全性を測定します。異なる暗号の安全性は、解読に必要な計算時間によって比べます。
質問2
RSA暗号はもう少し強いように思うのですが?
回答2
以前は「鍵長1024ビットのRSA暗号の安全性は鍵長80ビットの共通鍵の安全性と等しい」と思われていました。今でもそのように書かれている文献は多いでしょう。しかしここ数年で数体篩法の理論・実装が急速に進展したため、RSA暗号の解読に必要な計算時間は低下し、その安全性は思ったよりも低いことがわかりました。今では「鍵長1024ビットのRSA暗号の安全性は鍵長70ビットの共通鍵の安全性と同等」と思われています。
質問3
RSA暗号はもう少し弱いように思うのですが?
回答3
思うだけではどなたも信じないでしょうから、是非、それを裏付ける理由(高速な素因数分解法の考案、数体篩法による高速な素因数分解結果など)を教えて下さい。

« NHKスペシャル: 『魔性の難問~リーマン予想・天才たちの闘い~』の再放送 | トップページ | FC 2010: Accepted Papers »

RSA暗号」カテゴリの記事

コメント

コメントを書く

(ウェブ上には掲載しません)

トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/177150/46807456

この記事へのトラックバック一覧です: RSA暗号の強度:

« NHKスペシャル: 『魔性の難問~リーマン予想・天才たちの闘い~』の再放送 | トップページ | FC 2010: Accepted Papers »

リンク