14. 解読法と素数
効率良い解法の見つかっていない素因数分解も、 コンピュータを使えばかなりの桁までは行えます。 ところが、その数を構成する二つの素数 P と Q が少し大きくなっただけで、 割り出すのに必要な計算時間が莫大に増えてしまうのです。 現在、素数が 50 桁づつのペア（掛けて 100 桁）程度であれば、 なんとかコンピュータで素因数分解をすることができます。 というのはＲＳＡ暗号の発明者の一人で 現在の RSA Security 社の創業メンバーでもある Rivest が 1970 年に出題していた 129 桁の数（２つの素数をかけ合わせた数） の素因数分解問題 （ RSA-129 問題） が、1994年 に多重多項式ふるい法という方法によって解かれた というニュースが流れたからです。
その２つの素数をかけ合わせた 129 桁の数とは、
です。
そして、これをつくり出す２つの素数は、
と
です。
不思議ですね、この二つの素数を掛けて上の数を求めるのは、 根気さえあれば、今、あなたが机上で計算することもできるというのに、 逆に、上の数を下のニつの素数に分解するのは 1600 台のコンピュータを並列処理してやっと求められたというのですから…。
しかも、実用化された ＲＳＡ暗号 では最低でも77 桁程度の２つの素数を P, Q に用意し、 それを掛けた計 155 桁程の数 P×Q を法としてきました。 これにより、鍵になる２つの数値の桁数も大きなものとなります。 129 桁と 155 桁程では近いと思われるかも知れませんが、 1 桁増えるだけで莫大な計算時間を要することになってしまうのです。 これは素因数分解を解く効率的な方法が見つかってないことが原因です (※1)。
「でも、コンピュータの計算速度の進化ってすごいのでは？」 という声もあるでしょう。それは確かに言えています。 ムーアの法則として知られるように、 「コンピュータの計算速度が二倍になった」などと言うのは、 ほんの短期間で起こり得ることだからです。 これほど増速し続けてきた分野は他にありませんよね。 だってそうでしょう、 「来月から、新幹線が増速！ 200Km/h から 夢の 400Km/hへ！」 などという話は聞いたことがありません。 「いやいや、F1なんてもっとスゴイ！ 来シーズンは、300Km/h から 嵐の 600Km/h だ！」 などという話も聞いたことがありません。
確かにコンピュータの計算速度の進化はすごいです。 でも、それにも増して、 素数の桁を上げた時に素因数分解に必要となる時間の増加は大きいのです。 従って、もしもコンピュータの進化によって、 現在の桁数の素因数分解をすることができる時代が来てしまったら、 素数の桁を上げてしまえばよいのです。 1991 年以降 RSA Security 社の研究部門である RSA Laboratories は、 「その時代のコンピュータで ＲＳＡ暗号 を安全に保つには どの程度の桁数の素数が必要か」 を把握することなどを目的に、 いろいろな桁数の 「素数と素数を掛けた数」 の素因数分解問題を出題する RSA Factoring Challenge と言うコンテストを実施しています。 2003 年の年末時点では素数と素数を掛けた数が 174 桁の数が、 100 台の業務用コンピュータで協調計算させて 3 ヶ月で素因数分解できることが実証されています(※2)。
一方、現在の ＲＳＡ暗号 では一般的には素数と素数を掛け合わせた後 （法とする数） が 310 桁にもなる数を用いています。 これでは、現在の数学で巨大な素因数分解を行うには、 コンピュータにはない直感力や第六感、 神をも味方につけた超人的な運を手に入れるしかないでしょう。 確率的には、残念ながら競馬やパチンコ、宝くじとは比べ物になりません。 しかしならＲＳＡ暗号には、 万が一にも素因数分解に非常に効率的な方法が見つかり、 一気に解かれてしまう可能性が 100% あり得ないわけではないことは把握しておかねばなりません。 ただ、素因数分解問題の長い歴史上、 頭のよい多くの暗号学者・数学者たちをもってしても見つけられなかった上、 今後、すぐに見つかりそうな気配もありません。
そもそも素因数分解に限らず、 「あらゆる数学の問題には、必ず効率的に解ける方法がある」 という考え方、 つまり 「素因数分解にも実は効率的な解法があるけど 今はまだ見つかっていないだけだ」 という考え方と、 「いや、中には効率的な求め方がない問題もあるのだ」 という二つの考え方があり、どちらが正しいのかの証明もされていません。 興味を持ったれた方は、素因数分解の効率的な解法だけでなく、 もっと根元的なこんな問題の証明 (※3) に挑戦するのもよいでしょう。 しかし、逆にＲＳＡ暗号を解読するという目的だけならば、 実は真っ向から素因数分解にチャレンジせずとも、 素因数分解をせずに解読できる攻撃法を考えるといった道もあります (※4)。 実際、素因数分解のように簡単に解くことができない問題として有名な 「ナップザック問題」 を利用した暗号には、 発表後、こうした方法で解読できることが分かってしまいました。 このように、暗号が持っている数理のマジックが皆さんの興味をひくならば、 世界の暗号はどんどん強く安全になっていくことでしょう。
ちなみに P, Q に利用する素数は、 現在実際に使われている 155 桁程度以下のものなら 10 の 150 乗個 （10000000....ゼロが 150 個） 以上は存在することが分かっています。 これは宇宙の原子の数以上であり、 これらから得た公開鍵・秘密鍵は、 世界中の人々はもとより、 あらゆる生命に１つづつ割り当てたとしても使い果たすことはありません。
暗号技術は各国で戦略物資に当たるとされ、 その技術と利用の輸出が厳しく規制されてきました。 本文でも触れましたが、暗号は一般的に鍵に使う数値の桁数（鍵長）を 大きくすると解読が困難になっていきます。 そのような性質を鑑み、暗号の輸出規制は、この 「鍵に用いる数値の桁数」 を制限することで行われるのが一般的です。 例えば、アメリカでも近年まで厳しい規制が行われていたのが知られており、 国内用の暗号装置と比較し、 国外への輸出品には極端に鍵の桁数の短いものだけが認められてきました。
この輸出してよい鍵の桁数、突然拡張されることがあったことから、 それは暗号解読技術で世界最先端を行くと言われるアメリカ政府のセキュリティ機関 ＮＳＡ でその長さの鍵の暗号解読が可能になった証拠ではないかという噂が、 昔から根強く存在してきました。つまり、 アメリカ政府は政府によって解読できるようになったものについてだけ、 輸出を許可してきたのではないか、という噂です。 しかし前世期末から現在に至る暗号技術の進化はめざましく、 現在普及している暗号は既に ＮＳＡ であっても簡単に解読することは不可能であると考えられているのが現実です。 このように、暗号自体の理論を突いて容易に解読することは、 もはや国家的な組織であっても 「現実的には無理」 と言える段階に来ています。
つまり現実のシステムでは、 秘匿化情報が暗号の理論的欠陥から解読されることは皆無に等しく、 むしろソーシャルエンジニアリング （関係者の人為的ミス，背任的行為など） や、 セキュリティホール （ソフトウェアの実装上の不具合＝バグ、 非暗号化通信や旧式暗号部分を含んでいることなどが原因になる連鎖的解読 ＝システム全体としての設計ミス、 コンピュータの電気的性質・物理的性質を突くなど） が原因となることの方がはるかに多いのが現状です。
実は、冒頭に述べた 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 桁の整数は、
です。そして、解析により判明した 2 つの素数とは、
と
でした。
現在は、"RSA-640" （ 193 桁） 〜 "RSA-2048" （ 617 桁） の問題が開催中にあり、一般には RSA-640 がチャレンジされている状態です。
これまでのコンテスト結果は、 「特定桁数の鍵を用いた場合の ＲＳＡ暗号 の強度」 が間接的に把握できるものであって、 その結果から 「ＲＳＡ暗号自体のアルゴリズムが危険」 というのは全く的外れなことなのでご注意下さい。 時代ごとに解析性能が高くなっていることは把握できますが、 「この桁数の素因数分解に、こんな設備でこんなにも時間がかかる。 実際のＲＳＡ暗号は、さらに大きな桁数を用いている」 ということから逆に安全性を知ることができる 「解読」 です。
効率的に解ける問題を「P」、 解答の正しさを効率的に調べられる問題を「NP」とする時、 もしも世の中には 「どんな問題にも効率的な解法がある」のなら Ｐ＝ＮＰ 、 「効率的な解法のない問題がある」のなら Ｐ≠ＮＰ と言えます。 しかし、どちらが正しいかの証明はされておらず、 現代数学の重要な未解決問題の一つになっています。
もしも P=NP が証明されてしまったとすると、 素因数分解は、得られた答えが正しいか （＝「 2 つの素数を掛ければ元の値になるか？」） を簡単に調べられるので、 それ自身を解く効率的な解法も必ず存在すると言えることになります。 すなわち 「効率的な解法があるのに見つかっていない」 だけで、 「必ずＲＳＡ暗号は破れる」という証明はされたことになってしまいます。 しかし、素因数分解などの「 P ではない」と考えられている問題について、 世界中の数学者が長年取り組んでも効率的な解法は見つかっていないため、 P≠NP だろうと言われており 「 P≠NP 予想 」などと呼ばれています。
