NTTなど、「素因数分解問題」で世界記録更新--公開鍵暗号解読に一歩近づくか

田中好伸(編集部) 2010年01月08日 19時18分

  • このエントリーをはてなブックマークに追加

 NTTは1月8日、グループのNTT情報流通プラットフォーム研究所(NTT研究所)が海外の研究機関と共同で、公開鍵暗号の安全性の根拠となる「素因数分解問題」で世界記録を更新したことを発表した。

 これまでの世界記録は663ビット、10進200ケタだが、新しい世界記録は768ビット、10進232ケタで100ビット以上上回っている。独ボン大学、仏の国立情報学自動制御研究所(INRIA)、オランダの国立情報工学・数学研究所(CWI)と共同で研究した。

 素因数分解問題は、その難解さから現在公開鍵暗号として普及している「RSA暗号」の安全性の根拠になる。素因数分解可能なビット数の検証は、RSA暗号の安全性や強度の有効性をより精密に予測する上で極めて重要とされている。

 これまでの世界記録を大きく上回る700ビットを超える素因数分解が可能になったが、これは将来的にRSA暗号で使われている1024ビットの素因数分解も達成できる可能性があることを示唆するものと注目される。その延長線上として、RSA暗号より強度が高く、より効率的な暗号技術を利用する必要性も高まるだろうと、NTTは見ている。

 NTT研究所は、暗号技術全般の安全性を継続的に評価していくとともに、次世代暗号として、楕円曲線上の演算規則を利用した「楕円曲線暗号」の普及に務めていくとしている。

 素因数分解問題は、合成数を素数の積に分解するというもの。小さな合成数に対しては、短時間で素因数分解できるが、大きな数の場合、現実的な時間内に計算できることは困難といわれている。

 RSA暗号に使われるような、大きな2つの素数の積から構成される合成数の素因数分解法は「数体篩(ふるい)法」が用いられる。現在、RSA暗号に使われる合成数には「一般数体篩法」と呼ばれるやり方が高速とされている。今回の世界記録更新にも、この一般数体篩法を活用している。

 一般数体篩法は、「多項式選択」「篩」「filtering」「線形代数」「平方根」――という5つのステップから構成される。このうちの篩と線形代数が最も計算量を要するステップとされる。各ステップで選択すべきパラメータが多数存在し、パラメータの選択で計算量が大きく変化するが、有効な選択方法はあまり解明されていないという。今回の共同研究では、このパラメータを適切に選択することで、高速に計算することに成功したとしている。

ZDNet Japan 記事を毎朝メールでまとめ読み(登録無料)

  • このエントリーをはてなブックマークに追加

この記事を読んだ方に

関連キーワード
セキュリティ

関連ホワイトペーパー

連載

CIO
デジタル“失敗学”
コンサルティング現場のカラクリ
Rethink Internet:インターネット再考
インシデントをもたらすヒューマンエラー
トランザクションの今昔物語
エリック松永のデジタルIQ道場
研究現場から見たAI
Fintechの正体
米ZDNet編集長Larryの独り言
大木豊成「仕事で使うアップルのトリセツ」
山本雅史「ハードから読み解くITトレンド放談」
田中克己「2020年のIT企業」
松岡功「一言もの申す」
松岡功「今週の明言」
内山悟志「IT部門はどこに向かうのか」
林 雅之「デジタル未来からの手紙」
谷川耕一「エンプラITならこれは知っとけ」
大河原克行「エンプラ徒然」
内製化とユーザー体験の関係
「プロジェクトマネジメント」の解き方
ITは「ひみつ道具」の夢を見る
セキュリティ
企業セキュリティの歩き方
サイバーセキュリティ未来考
ネットワークセキュリティの要諦
セキュリティの論点
スペシャル
ざっくりわかるSNSマーケティング入門
課題解決のためのUI/UX
誰もが開発者になる時代 ~業務システム開発の現場を行く~
「Windows 10」法人導入の手引き
ソフトウェア開発パラダイムの進化
エンタープライズトレンド
10の事情
座談会@ZDNet
Dr.津田のクラウドトップガン対談
Gartner Symposium
IBM World of Watson
de:code
Sapphire Now
VMworld
Microsoft WPC
Microsoft Connect()
HPE Discover
Oracle OpenWorld
Dell EMC World
AWS re:Invent
AWS Summit
PTC LiveWorx
吉田行男「より賢く活用するためのOSS最新動向」
古賀政純「Dockerがもたらすビジネス変革」
中国ビジネス四方山話
ベトナムでビジネス
日本株展望
企業決算
このサイトでは、利用状況の把握や広告配信などのために、Cookieなどを使用してアクセスデータを取得・利用しています。 これ以降ページを遷移した場合、Cookieなどの設定や使用に同意したことになります。
Cookieなどの設定や使用の詳細、オプトアウトについては詳細をご覧ください。
[ 閉じる ]