公開鍵暗号と素因数分解 2010年1月13日
ネットスクエアの志藤です。
明けましておめでとうございます。
今年もよろしくお願いします。
今回は、公開鍵暗号の素因数分解のお話を書きたいと思います。
皆さんは、公開鍵暗号で使用される２つの鍵、公開鍵と秘密鍵が、
どのようにして作られているか、ご存知でしょうか？
簡単に言うと、２つの大きな素数を掛け合わせた値を基にして鍵を作っています。
言い方変えると、
公開鍵に含まれる値が素因数分解できれば秘密鍵を作ることができる
ということです。
「そんな簡単な仕組みなの？本当に公開鍵暗号は大丈夫？」
と思われる方もいるかもしれませんが、
実は現在の最先端技術を持ってしても、
２５６桁の整数を素因数分解するには数百万年かかる
と言われています。
これは現実的には求めることが困難という解釈ができるので安心、というお話なんですが、
数年で２３２桁（768ビット整数）の素因数分解に成功というニュースが、
ITProで紹介されていました。
ＳＳＬやＳＳＨで使用されている公開鍵暗号。
２５６桁（1024ビット整数）が数年で素因数分解される日も近いかもしれませんね。