情報セキュリティ:暗号のはなし 平成28年5月27日 青木
1.コンピュータの計算速度の進化にも増して、素数の桁を上げた時に素因数分解に必要となる時間の増加は大きい。 もしコンピュータの進化によって、現在の桁数の素因数分解ができる時が来たら、暗号で用いる素数の桁数をもっと上げる必要がでてくる。1991 年以降 RSA社はコンテストで、パソコンの進歩に合わせて桁数探索をしてきた。
*RSA:Rivest、Shamir、Adleman(1977)
2.1991 年以降 RSA社の研究部門は、色々な桁数の「素数と素数を掛けた数」の素因数分解問題を出題するコンテストを実施して「その時代のコンピュータでRSA暗号を安全に保つには、どの程度の桁数の素数が必要か」を把握してきた。2003 年の年末時点では素数と素数を掛けた数が 174 桁の数が、100 台の業務用コンピュータで協調計算させて 3 ヶ月で素因数分解できることが実証された。現在のRSA暗号では素数Aと素数Bを掛け合わせた数が 310 桁にもなる数を用いている。
3.万が一にも素因数分解に非常に効率的な方法が見つかり、一気に解かれてしまう可能性が「絶対にあり得ない」わけではない。数学の問題には「必ず効率的に解ける方法がある」という考え方と「いや、中には効率的な求め方がない問題もある」という考え方があり、どちらが正しいのか証明はされていない数学上の難問の一つだ。
4.効率的に解ける問題の集合を「P」、解答の正しさを効率的に調べられる問題の集合を「NP」とする時、「どんな問題にも効率的な解法がある」のなら P=NP、「効率的な解法のない問題もある」のなら P≠NP 。 どちらが正しいかは証明されていない。現代数学の重要な未解決問題の一つだ。 *懸賞金100万ドル(1億円)
*P:Polynomial-time computability , NP:Nondeterministic Polynomial-time
5.暗号に利用する素数は実際に使われている 155 桁程度以下なら 10 の 150 乗個 (10000000....ゼロが 150 個)以上は存在する。 これは宇宙の原子の数以上で、ここから得られる公開鍵・秘密鍵はあらゆる生命に1つづつ割り当てても使い果たせない。
6.実は「素因数分解が難しい」ならば「RSA暗号の解読も難しい」という関係には完全な証明がされていない。 真正面からRSA暗号を解読しようとすれば素因数分解を行う必要があり、それが「素因数分解が難しければRSA暗号の解読も難しいだろう」という根拠になっているだけだ。量子コンピュータはこの壁を突破する可能性が示されている。
7.NTTは、素因数分解の難しさと「その暗号解読の難しさ」が等しいことを数学的に証明できた公開鍵暗号、EPOCを開発した。 EPOCは「素因数分解が難しければ」=「 この解読も難しい」ことが証明され、素因数分解の効率的な方法を見つける以外には、この暗号を解読する効率的方法はない。 以上