サルにも分かるRSA暗号

解読法と素因数分解

効率良い解き方が見つかっていない素因数分解も、コンピュータを使えばかなりの桁まで現実的に行えます。 ところが、その数を構成する二つの素数 P と Q が少し大きくなっただけで、割り出すのに必要な計算時間が莫大に増えてしまうのです。 現在、素数が 50 桁づつのペア(掛けて 100 桁)程度なら、現実的にコンピュータで素因数分解できます。 というのは、RSA暗号の発明者の一人で RSA Security 社の創業メンバーでもある Rivest 博士が 1970 年に出題した 129 桁の数(2つの素数をかけ合わせた数)の素因数分解問題( RSA-129 問題)が、1994年に多重多項式ふるい法という方法によって解かれたというニュースが流れたからです。

その2つの素数をかけ合わせた 129 桁の数とは、

1143816257578888676692357799761466120102182967212423625 6256184293570693524573389783059712356395870505898907514 7599290026879543541

です。これをつくり出す2つの素数は、

3490529510847650949147849619903898133417764638493387843 990820577

3276913299326670954996198819083446141317764296799294253 9798288533

です。

何だか不思議ですね。 この二つの素数をかけ合わせるのは、根気があればあなたが机上で計算することもできるというのに、逆にかけ合わせた数をこのニつの素数に分解するのは 1600 台のコンピュータを並列処理してやっと求められたというのですから。

しかも実際のRSA暗号では 最低でも 77 桁程度の2つの素数を P, Q に用意し、それを掛けた計 155 桁程の数 P×Q を法としてきました。 これにより、鍵になる2つの数値の桁数も大きなものとなります。 129 桁と 155 桁程では近いと思われるかも知れませんが、1 桁増えるだけで莫大な計算時間を要することになってしまうのです。 これは素因数分解を解く効率的な方法が見つかってないことが原因です (※1)

「でも、コンピュータの計算速度の進化ってすごいのでは?」という声もあるでしょう。 それは確かに言えています。 ムーアの法則のように「コンピュータの計算速度が二倍になった」などと言うのは、短期間で起こり得ることだからです。 これほど増速し続けてきた分野は他に無いかもしれません。 だってそうでしょう?「新幹線が増速! 200Km/h から夢の 400Km/h へ!」などという話は聞いたことがありません。 「F1なんてもっとスゴイ!来シーズンは、300Km/h から嵐の 600Km/h だ!」などという話も聞いたことがありません。

確かにコンピュータの計算速度の進化はすごいです。 でも、それにも増して、素数の桁を上げた時に素因数分解に必要となる時間の増加は大きいのです。 従って、もしコンピュータの進化によって現在の桁数の素因数分解できる時代が来たら、用いる素数の桁数を上げてしまえばよいのです。 1991 年以降 RSA Security 社の研究部門である RSA Laboratories は、色々な桁数の「素数と素数を掛けた数」の素因数分解問題を出題する RSA Factoring Challenge と言うコンテストを実施して「その時代のコンピュータでRSA暗号を安全に保つには、どの程度の桁数の素数が必要か」を把握してきました。 2003 年の年末時点では素数と素数を掛けた数が 174 桁の数が、100 台の業務用コンピュータで協調計算させて 3 ヶ月で素因数分解できることが実証されています(※2)

一方、現在のRSA暗号では素数と素数を掛け合わせた後(法とする数)が 310 桁以上にもなる数を用いています。 これでは、現在の数学で巨大な素因数分解を行うには、コンピュータにはない直感力や第六感、神をも味方につけた超人的な運を手に入れるしかないでしょう。 確率的には、残念ながら競馬やパチンコ、宝くじとは比べ物になりません。 しかしならRSA暗号には、万が一にも素因数分解に非常に効率的な方法が見つかり、一気に解かれてしまう可能性が「絶対にあり得ない」訳ではないことは把握しておかねばなりません。 ただ、素因数分解問題の長い歴史上、多くの研究者たちをもってしても見つけられなかった上、今後もすぐに見つかりそうな気配はありません。

そもそも素因数分解に限らず「あらゆる数学の問題には、必ず効率的に解ける方法がある」という考え方、つまり「素因数分解にも実は効率的な解法があるけど今はまだ見つかっていないだけだ」という考え方と「いや、中には効率的な求め方がない問題もある」という二つの考え方があり、どちらが正しいのか証明はされていません。 興味を持ったれた方は、素因数分解の効率的な解法だけでなく、もっと究極的なこうした問題の証明 (※3) に挑戦するのもよいでしょう。 一方、RSA暗号に問題がないかを学術的に考えたいだけであれば、実は真っ向から素因数分解にチャレンジせずとも、素因数分解をせずに解読できる攻撃法が無いかを考える道もあります (※4)。 実際、素因数分解のような簡単に解けない問題として知られる「ナップザック問題」を利用した公開鍵暗号には、発表後、こうした方法で解読できることが分かってしまいました。 このように、暗号が持っている数理のマジックが皆さんの興味をひくならば、世界の暗号はどんどん強く安全になっていくことでしょう。

ちなみに P, Q に利用する素数は、現在実際に使われている 155 桁程度以下のものなら 10 の 150 乗個 (10000000....ゼロが 150 個)以上は存在することが分かっています。 これは宇宙の原子の数以上であり、ここから得られる公開鍵・秘密鍵は、世界中の人々はもとより、あらゆる生命に1つづつ割り当てたとしても使い果たすことはありません。

※1 鍵の長さと輸出規制

暗号技術は各国で戦略物資に当たるとされ、かつてその技術と利用の輸出は厳しく規制されてきました。 本文でも触れましたが、暗号は一般的に 鍵に使う数値の桁数(鍵長) を大きくすると解読が困難になっていきます。 この性質を鑑み、暗号の輸出規制は「鍵に用いる数値の桁数」を制限することで行われるのが一般的です。 例えば、アメリカでは近年まで厳しい輸出規制が行われてきたことが知られており、国内用の暗号装置と比較して、国外への輸出品には極端に鍵の桁数の短いものだけが認められてきました。

この輸出してよい鍵の桁数が突然拡張されることがあり、それは暗号解読技術で世界最先端と言われるアメリカ政府のセキュリティ機関NSA (National Security Aagency) でその長さの鍵の暗号解読が可能になった証拠ではないかという噂が存在してきました。 つまり、アメリカ政府は自身が解読できるようになったものだけを輸出許可してきたのではないかという噂です。 しかし前世期末から現在に至る暗号技術の進化はめざましく、現在普及している暗号は既にNSAでも簡単に解読することは不可能だろうと考えられています。 このように、暗号の数学的理論(「プリミティブ」と呼ばれます)そのものを突いて解読することは、もはや国家的な組織であっても「無理」と言える段階に来ています。

現実のシステムでは、秘匿化情報が暗号の理論的欠陥から解読されることは皆無に等しく、むしろソーシャルアタック(関係者の人為的ミス、背任的行為など)や、セキュリティホール(ソフトウェアの実装ミス=バグ、不適切な運用方法)が原因となることの方がはるかに多いのが現状です。

「不適節な運用」とは、全体システムの一部に暗号化されていない通信路や旧式暗号を含んでいる部分があることが引き金となって情報が漏洩し、本来なら安全な暗号まで連鎖的に解析・解読されることを含んでいます。 かつて日本の外務省が使用したパープル暗号(米国での呼び名)は、その運用中に、まだ旧式暗号の機器しか行き渡っていなかった場所があったことから旧式暗号でも同じ文章を伝えており、そこから漏れる情報がパープル自体の解析に繋ったと言われています。

近年ではコンピュータの電気的性質・物理的性質を突いて、機器から漏れる電磁波の変化や、使用中の電力量の変化を測定することで解読する方法も現実的になりつつあり、あえて不要な計算を混ぜるなどの対策が必要となってきています。

※2 RSA Factoring Challenge

冒頭に述べた 1970 年の RSA-129 問題も、1991 年以降はこのコンテストの問題の一つになっていました。 まず 1991 年に 2 つの素数を掛けた数が 100 桁の数の素因数分解が実証され(コンテスト名称は "RSA-100" )、それから年々 "RSA-110", "RSA-120", − 冒頭に述べた "RSA-129" −, "RSA-130", "RSA-140", "RSA-155", "RSA-160" が解かれていきました(それぞれ末尾の値が出題された整数の桁数を表します)。

174 桁の問題からはコンピュータの世界での数の表記法(二進数と言います)に合わせたコンテスト名称で呼ばれており、174 桁の場合の名称は「 RSA-576 」と呼ばれていました。 これがコンテストで実証された素因数分解です(2003年の年末現在)。 実際に出題された 174 桁の整数は、

188198812920607963838697239461650439807163563379417382 700763356422988859715234665485319060606504743045317388 011303396716199692321205734031879550656996221305168759 307650257059

でした。そして、解析によって判明した 2 つの素数は、

398075086424064937397125500550386491199064362342526708 406385189575946388957261768583317

472772146107435302536223071973048224632914695302097116 459852171130520711256363590397527

でした。

現在は、"RSA-640" ( 193 桁) 〜 "RSA-2048" ( 617 桁) の問題が開催中にあり、一般には RSA-640 がチャレンジされている状態です。 この RSA-2048 は現在の RSA 暗号が広く用いている桁数です。

このコンテスト結果は「それぞれの桁数の鍵を用いたRSA暗号の強度」が間接的に把握できるものであって、その結果から「RSA暗号自体のアルゴリズムが危険」というのは全く的外れなことなのでご注意下さい。 時代に応じて解読できる桁数が増していることは把握できますが、「この桁数の素因数分解に、こんな設備でこんなに時間がかかる。実際のRSA暗号は、さらに大きな桁数を用いている」ことから安全性の高さを知ることができる「解読」だと言えます。

※3 P と NP 問題 ( P≠NP 予想)

効率的に解ける問題の集合を「P」、解答の正しさを効率的に調べられる問題の集合を「NP」とする時、もし世の中には「どんな問題にも効率的な解法がある」のなら P=NP、「効率的な解法のない問題もある」のなら P≠NP と言えます。 どちらが正しいかは証明されておらず、現代数学の重要な未解決問題の一つになっています。

もし P=NP が証明されたとすると、素因数分解は、得られた答えが正しいか(=「 2 つの素数を掛けて元の値になるか?」)を簡単に調べられるので、素因数分解自体も効率的な解法が必ず存在すると言えることになります。 つまり「効率的な解法があるのに見つかっていない」だけで、まだ具体的な攻撃方法が見付かって無くても「必ずRSA暗号は破れる」という証明はされたことになってしまいます。 ただ、素因数分解のような「 P ではない」と推測される問題について、世界の研究者が長年取り組んでも効率的な解法は見つかっていないことから、P≠NP だろうと言われており「 P≠NP 予想」などと呼ばれています。

※4 素因数分解の難しさとRSA暗号の解読

実は「素因数分解が難しい」ならば「RSA暗号の解読も難しい」という関係には完全な証明がされているわけではありません。 真正面からRSA暗号を解読しようとすれば素因数分解を行う必要があり、それが「素因数分解が難しければRSA暗号の解読も難しいだろう」という根拠になっているだけなのです。 つまり、現在のところ素因数分解は困難ですが、その素因数分解をせずにRSA暗号を解読できる抜け道が、もしかしたら存在するかもしれないのです。 現実的には難しいだろうと言われていますが、一応RSA暗号はこのような要素を抱えています。 一方、我が日本のNTTは、この「素因数分解の難しさ」と「その暗号解読の難しさ」が等しいことを数学的に証明できた公開鍵暗号、EPOC(エポック)を発明しています。 EPOCは、「素因数分解が難しければ」=「 EPOC の解読も難しい」ことが証明されており、素因数分解の効率的な方法を見つける以外には、この暗号を解読する効率的方法がないと言えます。

戻る
進む
ページ上部へ