公開鍵暗号と素因数分解 2010年1月13日

ネットスクエア志藤です。

明けましておめでとうございます。
今年もよろしくお願いします。

今回は、公開鍵暗号の素因数分解のお話を書きたいと思います。

皆さんは、公開鍵暗号で使用される2つの鍵、公開鍵と秘密鍵が、
どのようにして作られているか、ご存知でしょうか?

簡単に言うと、2つの大きな素数を掛け合わせた値を基にして鍵を作っています。

言い方変えると、
公開鍵に含まれる値が素因数分解できれば秘密鍵を作ることができる
ということです。

「そんな簡単な仕組みなの?本当に公開鍵暗号は大丈夫?」
と思われる方もいるかもしれませんが、
実は現在の最先端技術を持ってしても、
256桁の整数を素因数分解するには数百万年かかる
と言われています。

これは現実的には求めることが困難という解釈ができるので安心、というお話なんですが、
数年で232桁(768ビット整数)の素因数分解に成功というニュースが、
ITProで紹介されていました。

SSLやSSHで使用されている公開鍵暗号。
256桁(1024ビット整数)が数年で素因数分解される日も近いかもしれませんね。

Comments are closed.