ＮＩＣＴと富士通など、専用ハードウェアによる素因数分解実験に成功
世界初、専用ハードウェアによる素因数分解実験に成功
～暗号の安全性向上に向けてソフト・ハード技術を融合～
独立行政法人情報通信研究機構（理事長：長尾真。以下、ＮＩＣＴ）および、富士通株式会社（代表取締役社長：黒川博昭、本社：東京都港区、以下富士通）、株式会社富士通研究所（代表取締役社長：村野和雄、本社：神奈川県川崎市、以下富士通研究所）は、専用ハードウェアを用いて、暗号に用いられる素因数分解問題＊１ を解く実験に世界で初めて成功しました。
素因数分解問題は、インターネットの暗号通信などで広く用いられるＲＳＡ暗号＊２の安全性の根拠となっています。本実験は専用ハードウェアによる暗号解読の可能性を検証する第一歩であり、将来の暗号の安全性を高める上で重要な成果となります。
本実験は、平成１６年に開始したＮＩＣＴの委託研究制度「高度通信・放送研究開発に係る委託先公募」を基に、ＮＩＣＴが富士通との間で進めてきた委託研究「素因数分解の困難性に基づく暗号の技術的評価に関する研究開発」の枠組みの中で行われたものです。また、本実験にあたっては富士通研究所が富士通と独自開発した計算処理ソフトウェアも利用しました。
【開発の背景】
インターネットの本格的な普及に伴い、ネットショッピングやインターネット銀行などネットワークを活用した便利なサービスが身近な存在になる一方、秘密情報が漏れないように情報セキュリティを確保することが重要な課題となっています。
暗号技術は情報セキュリティを確保するためのコア技術です。特にＲＳＡ暗号は、ウェブの暗号通信プロトコルＳＳＬ＊３などでも採用されており、インターネットで最もよく使われる暗号アルゴリズムとなっています。
ＲＳＡ暗号は、素因数分解問題を解ければ解読できるため、ＲＳＡ暗号の安全性を保証するには素因数分解問題がいかに難しいかを検証することが重要です。これまで、ソフトウェアによる素因数分解実験は数多く行われてきましたが、専用ハードウェアによる分解実験は行われていませんでした。
【開発した技術】
今回、世界で初めて専用ハードウェアによる素因数分解実験システムを開発しました。その特長は以下の通りです。
１．最も効率的な素因数分解アルゴリズムとして知られている、一般数体篩（ふるい）法＊４をベースとし、最大７６８ビットの数まで入力可能としました。ボトルネックとなる篩処理を行う専用ハードウェアを開発し、篩処理以外の線型代数処理および平方根計算処理はソフトウェアにより実現し、それらを組み合わせることにより実験システムを構成しました。
２．メモリアクセス回路の最適化および新たなデータ格納法の採用により、メモリ利用効率ならびにメモリアクセス処理の並列数を最大限まで引き上げました。
報道資料
３．ＦＰＧＡ＊５ならびにリコンフィギュラブルプロセッサＤＡＰＤＮＡ－２＊６を用いて、コア計算処理部を分離することにより、回路配置を最適化し、開発期間を短縮しました。
本システムを用いた分解実験の対象とした数は、Ｃｕｎｎｉｎｇｈａｍ Ｐｒｏｊｅｃｔ＊７から未分解の４２３ビット（１０進１２８桁）の数を選びました。本システムを約１ヶ月間動かすことで、下記の通り素因数分解が完了しました（６２桁と６６桁の素因数に分解）。
１１００２９２２８７２４９６８５３４０５９３８３１９１８２７３０８８０３３１３１３７４２５１４３３９１６８６９０４７５８５３５６０９０６５３２６６２７６４３１３９８２４１０６２７８４８０１６５４９３７１５５７１４２６９６９８６４４１７５６４８８９５８６５７
＝
４５４９３６３７２９２８１６４６４８５２０６７０１４７３６５７１３３９７９２３１５４１９８５９７８４２１８０７６８７５８４１ ×
２４１８５６３０１８３１３３８４３７５３７７８７８９８０９６０６２６９２３５９８１９５４３３０３６１９８６４０７４４１０３８２９７７
この実験結果を分析することにより、専用ハードウェアによる暗号解読の可能性を精密に見積ることができ、その結果を考慮してＲＳＡ暗号鍵長の更新時期を適切に設定し、将来の安全な暗号システムに貢献することができます。
【今後】
今回の実験では、現実に用いられているＲＳＡ暗号の鍵（一般には１０２４ビット）よりも小さい合成数の分解実験を行ったため、現実のＲＳＡ暗号が直ちに解読できることを示すものではありません。
アルゴリズムの改良により、更なる高速化を行った場合の暗号解読の可能性を分析することが今後の課題となります。今後、より精密なＲＳＡ暗号の安全性・強度評価をすすめるとともに、情報デジタル社会の基盤を支える暗号技術全般に関して、研究開発活動を推進していきます。
《ＮＩＣＴの委託研究制度》
ＮＩＣＴがテーマを指定して公募し、研究開発を民間等に委託する制度。民間企業等の研究設備や研究者の研究開発能力の活用により、より一層効果的な研究開発を図るため、ＮＩＣＴが評価委員会の審査を経て決定した研究開発課題を指定して公募し、評価委員会の審査後、プロジェクトの採択を行い、提案した民間企業や大学等に研究開発を委託している。
＜委託研究に関するお問合せ先＞
情報通信研究機構 連携研究部門
委託研究グループ
Ｔｅｌ： ０４２－３２７－７１９７、ＦＡＸ： ０４２－３２７－５６０４
Ｅ－ｍａｉｌ： shouji.shingo@nict.go.jp
＜研究開発に関するお問合せ先＞
株式会社富士通研究所
ＩＴコア研究所 セキュアコンピューティング研究部
Ｔｅｌ： ０４４－７５４－２６８１（直通）
Ｅ－ｍａｉｌ： integer-factoring@ml.labs.fujitsu.com
【用語説明】
＊１ 素因数分解問題
合成数を素数の積に書き下す問題。小さな合成数に対しては、短時間で素因数分解実施可能であるが、大きな数については現実的な時間内に計算を終えることは不可能と考えられている。
＊２ ＲＳＡ暗号
１９７８年に公表された公開鍵暗号および電子署名方式で、Ｒｉｖｅｓｔ、Ｓｈａｍｉｒ、Ａｄｌｅｍａｎの３人の開発者の名前の頭文字からＲＳＡの名がついた。公開鍵暗号・電子署名方式として、現在最も広く使われている。ＲＳＡ暗号は、鍵が長くなるにしたがって安全性は増すが、処理性能は落ちる。鍵と同程度の大きさの合成数の素因数分解問題が解ければ、ＲＳＡ暗号も解読される。
＊３ ＳＳＬ（Ｓｅｃｕｒｅ Ｓｏｃｋｅｔｓ Ｌａｙｅｒ）
ウェブ閲覧時などに安全に暗号通信するための技術。現在使われている多くのウェブブラウザに組み込まれている。ＳＳＬを実現するための暗号要素技術として、ＲＳＡ暗号も使われている。
＊４ 一般数体篩法（いっぱんすうたいふるいほう）
素因数分解の分解方式の一つ。現在最も高速である。
＊５ ＦＰＧＡ（Ｆｉｅｌｄ Ｐｒｏｇｒａｍｍａｂｌｅ Ｇａｔｅ Ａｒｒａｙ）
論理回路をユーザーがプログラムできるＬＳＩ。一般的に少量生産の場合、カスタムチップ（ＡＳＩＣ）に比べて実装コストを抑えることができる等、ハードウェアの試作段階に適している。
＊６ ＤＡＰＤＮＡ－２
アイピーフレックス社と富士通が開発したダイナミックリコンフィギュラブル（動的再構成）プロセッサ。
内部にＤＡＰ（Ｄｉｇｉｔａｌ Ａｐｐｌｉｃａｔｉｏｎ Ｐｒｏｃｅｓｓｏｒ）と呼ばれるＲＩＳＣプロセッサと、ＤＮＡ（Ｄｉｓｔｒｉｂｕｔｅｄ Ｎｅｔｗｏｒｋ Ａｒｃｈｉｔｅｃｔｕｒｅ）と呼ばれるマトリクス状に論理演算装置が配置された独自プロセッサのデュアルコアプロセッサ。ＤＮＡ内には３７６個の演算器が配置され、アプリケーションに応じて論理回路を動的に再配置可能であるという特長を持つ。
＊７ Ｃｕｎｎｉｎｇｈａｍ Ｐｒｏｊｅｃｔ
ｂｃ±１（ｂ＝２，３，５，６，７，１０，１１，１２，ｃ：大）という形で表される数を素因数分解するプロジェクト。