ＮＴＴ、１０００ビット超の特殊な型の合成数に対する素因数分解を達成
暗号方式の安全性検証に有効とされる「素因数分解」において世界記録を更新
～１０００ビット超の特殊な型の合成数に対する素因数分解の達成により暗号鍵の安全性検証に貢献！～
日本電信電話株式会社（以下ＮＴＴ、本社：東京都千代田区、代表取締役社長：和田紀夫）は、ドイツのボン大学、スイスのスイス連邦工科大学ローザンヌ校（以下、ＥＰＦＬ）との共同研究により、公開鍵暗号（※１）のデファクトスタンダードＲＳＡ（※２）暗号の安全性・強度を把握する手段として世界的にチャレンジが展開されている、大きな数の素因数分解実験において、世界で初めて１０００ビットを超える特殊な型の合成数に対して、特殊数体篩（ふるい）法（※３）による素因数分解を達成しました。
このたびの実験結果は、わずかなビット数の差でも桁違いの計算量が必要となる素因数分解問題（※４）において、特殊数体篩法でのこれまでの世界記録（９１１ビット）を大きく上回り、１０００ビットを超える１０１７ビットの合成数に対する素因数分解を達成するという画期的な世界記録です。
本実験は、「（２＾１０３９－１）／５０８０７１１」という特殊な型をした合成数に対する素因数分解です。分解対象は１０１７ビットであり、これは一般の合成数を対象とした一般数体篩（ふるい）法（※５）でも約７００ビットの難しさに相当すると期待されています。
このたびの世界記録樹立は、「素因数分解問題の難しさが、安全性の根拠」といわれ、現在では１０２４ビットの暗号鍵が主流となっているＲＳＡ暗号に関し、安全性・強度の有効性をより精密に予測するうえで極めて重要な意味を持つものです。
＜研究の背景及び意義＞
インターネットの本格的な普及に伴い、電子商店やインターネット銀行などネットワークを活用した便利なサービスが身近な存在となり、インターネット上における機密情報のやり取りが大幅に増加しています。
暗号技術は情報セキュリティを確保するためのコア技術です。現在、電子署名（※６）の実現法の１つであるＲＳＡ暗号が事実上の標準規格となっており、ほとんどのウエブ閲覧ソフトに組み込まれている暗号通信プロトコルＳＳＬ（※７）においても、このＲＳＡ暗号が採用されています。
ＲＳＡ暗号の安全性が高く評価されているのは、「『素因数分解問題の難しさ』を『安全性の根拠』」としている暗号だからです。つまり、「素因数分解の効率の良い解法はまだ見つかっておらず、大きな数を素因数分解するには、いかなる高性能なコンピュータを使っても莫大な時間がかかる」という数学的な根拠に基づいて設計されているわけです。
現在の素因数分解技術と計算機能力で、どれくらいの大きさの合成数まで素因数分解が可能であるかを予測することで、暗号解読の可能性を精密に見積もることが可能となり、その結果からＲＳＡ暗号鍵長の更新時期を適切に設定し、将来に渡り安全かつ強度な暗号システムの構築に貢献することができます。
＜研究の内容＞
（１）分解候補の選定
ＮＴＴの情報流通プラットフォーム研究所（※８）（以下、ＮＴＴ研究所）により、分解対象に小さな因子がないかどうかを楕円曲線法による分解を試みることにより確認しました。その結果６５桁以下因子を見逃している確率は３．４％以下、７０桁以下因子を見逃している確率は５３．２％以下となりました。確認にはＡＭＤ社のＯｐｔｅｒｏｎ２４８（※９）を１２７．５年程度稼動させたものと同程度の計算量を要しました。
（２）篩（ふるい）処理
ボン大が作成した篩プログラムにより行いました。ＮＴＴ研究所が８４．１％、ＥＰＦＬが８．３％、ボン大が７．６％の計算資源を提供し、Ｐｅｎｔｉｕｍ Ｄ ［３ＧＨｚ］換算で９５年稼動させたものと同程度の計算量を要しました。
（３）行列
ＮＴＴ研究所及びＥＰＦＬに設置されたそれぞれ１１０台と３６台からなるＰＣクラスタを並列に２ヶ月強用い計算しました。これにより約７千万×約７千万といった巨大疎行列からなる連立方程式の非自明解を４７個得ることができました。
（４）平方根
ボン大のＰＣクラスタを数時間動かすことにより下記のとおり素因数分解が完了しました。
（※ 関連資料を参照してください。）
＜今後の展望＞
情報セキュリティ産業は、２１世紀に大きく成長すると期待されています。ＮＴＴ研究所は本実験の成果を利用し、現在デファクトであるＲＳＡの安全性を継続的に評価していくとともに、今後も、暗号理論から社会的影響まで幅広い領域におけるセキュリティ研究を推進していきます。
＜用語解説＞
※１ 公開鍵暗号
１９７６年にＤｉｆｆｉｅとＨｅｌｌｍａｎにより提案された概念。実現方式としてはＲＳＡ暗号が有名。従来の暗号方式は暗号化と復号に用いられる鍵と呼ばれる情報は同一であり、秘密に保持しておく必要があったが、公開鍵暗号では暗号化に用いる鍵を公開することができ、復号に用いる鍵のみを秘密に保持しておけば十分である。
※２ ＲＳＡ
１９７８年に公表された公開鍵暗号および電子署名方式で、Ｒｉｖｅｓｔ、Ｓｈａｍｉｒ、Ａｄｌｅｍａｎの３人の開発者の名前の頭文字からＲＳＡの名がついた。電子署名方式として現在最も広く使われている。これまでにさまざまな改良が施され、いくつかのものは電子署名法の指針や電子政府推奨暗号リストに含まれている。ＲＳＡの安全性は「法」と呼ばれるがパラメータに依存し、大きいほど安全であるが、処理性能は落ちる。現在、法のサイズとしは１０２４ビットが広く使われている。
※３ 特殊数体篩法
ａ＾ｂ±１といった形の合成数に有効に働く素因数分解アルゴリズム。１９８０年代後半にＰｏｌｌａｒｄにより原型が示され、Ｌｅｎｓｔｒａらにより完成された。その後、一般的な形の合成数でも分解可能となる一般数体篩法に拡張された。
※４ 素因数分解問題
合成数を素数の積に書き下す問題。小さな合成数に対しては、短時間で素因数分解実施可能であるが、大きな数については現実的な時間内に計算を終えることは不可能である。ただし、あまり大きくない素因子を持つ場合は、楕円曲線法によりその素因子を求めることができる。
ＲＳＡの法に使うような大きな２つの素数の積から構成される合成数の素因数分解法としては、数体篩（ふるい）法が用いられる。現在、ＲＳＡの法に使われる合成数に対しては一般数体篩法が最も高速である。
※５ 一般数体篩法
１９９０年代前半にＬｅｎｓｔｒａらにより完成された素因数分解アルゴリズム。ＲＳＡの法に使うような一般的な形の合成数の素因数分解では既知のアルゴリズムで漸近的に最も高速である。２，３，５，７，…と割っていくいわゆる試し割り法の実行時間が指数時間であるのに対し、一般数体篩法は準指数時間で完了すると評価されている。しかし現在知られている実行時間の評価は平均の上限であるので、具体的な数に対する実際の実行時間を精度よく見積もるためには計算機実験の積み重ねが必要である。
※６ 電子署名
ハンコや署名の機能を電子的に実現する技術。わが国では２００１年に、いわゆる電子署名法が制定され、法的効力を持たせることができる。
※７ ＳＳＬ（Ｓｅｃｕｒｅ Ｓｏｃｋｅｔ Ｌａｙｅｒ）
ウエブ閲覧時などの安全な暗号通信を実現するための技術。現在使われている多くのウエブ閲覧ソフトに組み込まれている。ＳＳＬを実現するための暗号要素技術として、ＲＳＡ暗号も使われている。
※８ 情報流通プラットフォーム研究所（ http://www.ntt.co.jp/islab/org/pf.html ）
情報流通プラットフォーム研究所では、お客様に安心・安全・便利にサービスをご利用頂くため、世界トップクラスの暗号技術をはじめ、セキュリティ、ＦＭＣ、インターネット・ＩＰ通信、ならびにコンピュータアーキテクチャ等の情報処理基盤技術をベースにブロードバンド＆ユビキタス時代のプラットフォームの研究開発を推進しています。
※９ Ｏｐｔｅｒｏｎ２４８
ＡＭＤ社が開発した６４ビットアーキテクチャＡＭＤ６４に基づくＣＰＵ。Ｏｐｔｅｒｏｎ２４８は動作周波数２．２ＧＨｚであるＯｐｔｅｒｏｎファミリの一員である。Ｉｎｔｅｌ社もＡＭＤ６４互換アーキテクチャとしてＥＭ６４Ｔを発表し、Ｐｅｎｔｉｕｍ ＤやＣｏｒｅ２ ＤｕｏなどのＣＰＵを発表している。
（※ ＜研究の内容＞（４）平方根は関連資料を参照してください。）