[第2回] 暗号講座（RSAについて）
前回は、暗号講座ということで、古典暗号から現代暗号に関する技術に関して、それらの概要を
述べてきました。今回は、現代暗号の公開鍵暗号方式の中のRSA暗号に焦点を
当てて、話を進めてみようかと思います。
RSAとは？
RSA暗号とは、桁数が大きい合成数の素因数分解問題が困難であることを
安全性の根拠とした暗号です。例を使って説明すると、9021を素因数分解するのには時間がかかる、
ということです。現実には、9021のような数であれば、コンピュータを使えば素因数分解は現実時間内
でできてしまいます。しかしこれが、150桁や200桁の数を素因数分解するとなると、現実時間では
おそらく計算できません。RSA暗号は、このように、桁数が大きな合成数の素因数分解問題
はおそらく困難であることを根拠に現在使われています。
RSA暗号について、続きでさらに詳しく書いていきます
RSA暗号の桁数
実際に使われている合成数の桁数はどれくらいなのだろうか？
その答えは、2004年の時点で、合成数を1024～4096ビット（10進数で300～1000桁）程度にすることを
推奨しているようです。2004年のデータなので、現在は恐らく2048～8192ビット程度を推奨しているのでは
ないか？と思われます。
実際、「RSA Challenge 解読コンテスト」において、2005年の時点で663ビットの合成数に対し、
素因数分解を行うことができた、という実例があるようです。実際にこの数に対しては、
300台近くのコンピュータを7ヶ月以上走らせることにより素因数分解できた、らしいです。
RSAを解読するには？
RSA暗号を解読するには、
- 離散対数を求める
- ブルート・フォース・アタックで総当り
- 分かっている情報から秘密鍵を求める
- 何らかの方法で、素因数分解を行う
といった方法があるのですが、このいづれに対しても、適切なアルゴリズムが見つかっていない、ということで、
このRSA暗号が現在使われています。
逆に言えば、これらのうち、どれか1つでも適切なアルゴリズムが見つかれば、RSA暗号は容易に解読することが
可能となり、暗号としては使われなくなってしまう、と考えられています。
量子アルゴリズムからの素因数分解へのアプローチ
現在のコンピュータ上で大きな数を効率的に素因数分解するアルゴリズムは現在見つかっていないのですが、
量子コンピュータと呼ばれるコンピュータ（現在は実現できていない）が存在したとすれば、
大きな数を効率的に素因数分解できる、と証明されています。
つまり、量子コンピュータが実現されれば、現在のRSA暗号は解けてしまうということです。
素因数分解の量子アルゴリズムと量子暗号
量子コンピュータが開発されると、現在のRSA暗号は無駄になってしまいます。ということで、新しい別の
暗号が必要になるのではないか？ということで、研究されてきたのが、同じ量子コンピュータを用いて
実現される量子暗号と呼ばれる暗号方式です。量子コンピュータが出現しても、この
暗号方式を使うことにより、秘匿に通信を行うことができるようになります。
量子コンピュータの出現に対するリスク
現在、研究機関などにおいて、量子コンピュータの研究を盛んに行っているのですが、この
量子コンピュータが開発されてしまうとどうなるか？というと、おそらく今使われているPCが全て
セキュリティ上のリスクに晒されてしまいます。しっかり説明すると、量子コンピュータが開発されたとしても、
その量子コンピュータに全てのコンピュータが即座に置き換わる
参考書籍
参考サイト
関連記事
[PR]
トラックバック
http://yamablo.com/2009/06/06-191629.php/trackback
