Internet Watch logo
記事検索
最新ニュース

RSA-576素因数分解コンテストで数学者のグループが解答を出す


 米RSA Laboratoriesは27日、同社が実施した素因数分解コンテスト「RSA-576」を世界各地の数学者が協力して解読することに成功したことを正式に認め、研究者グループに1万ドルの賞金を授与したと発表した。この素因数分解に成功したことは2003年12月3日にRSAに報告されていた。

 RSA-576とは、2進法で576桁(10進法で174桁)の数を素因数分解するコンテスト。RSA暗号は、「小さい数を掛け合わせて大きな数にすることは一瞬で計算できるが、大きな数を素因数分解するには、どんな高速なコンピュータを使用しても多大な時間がかかる」という法則に基づいて設計されている暗号だ。そのため、素因数分解に関する研究は、公開鍵暗号の解読に関する研究ということもできる。RSAがこの素因数分解コンテストを行なうのは、世界中の優秀な頭脳にこの問題に取り組んでもらい、RSA暗号の限界を確かめ続けることで結果的に同社の暗号の安全性を高めるためだ。

 RSA-576で出題された数字は、

  18819881292060796383869723946165043980716356337941
  73827007633564229888597152346654853190606065047430
  45317388011303396716199692321205734031879550656996
  221305168759307650257059

であり、これを素因数分解した結果は、

  39807508642406493739712550055038649119906436234252
  6708406385189575946388957261768583317
   ×
  47277214610743530253622307197304822463291469530209
  7116459852171130520711256363590397527

だった。

 今回コンテストに挑戦して素因数分解に成功したのは、ドイツのScientific Computing InstituteとPure Mathematics Institute、オランダのNational Research Institute for Mathematics and Computer Scienceおよびその他複数の組織である。ドイツにあるExperimental Mathematics InstituteとBundesamt fur Sicherheit in der Informationstechnologie(BSI)も解読に使用するハードウェアを提供したほか、米国、カナダ、英国の数体ふるい法ネットワーク所属の数学者たちも参加している。

 なお、現在インターネットや携帯電話で使用される代表的な暗号鍵の大きさは最低でも1024bit(10進法で310桁)であるため、今回576bit(10進法で174桁)の暗号が解読されたとしても実質的な影響はない。

 RSAでは継続的にコンテストを行なっている。次のコンテストは640bitを素因数分解するコンテストであるRSA-640で、2万ドルの賞金がかかっている。ちなみに最高賞金がかかっているコンテストはRSA-2048(10進法で617桁)であり、この素因数分解に成功すれば20万ドルの賞金が授与される。


関連情報

URL
  ニュースリリース(英文)
  http://www.rsasecurity.com/company/news/releases/pr.asp?doc_id=3520


( 青木大我 taiga@scientist.com )
2004/04/28 12:01

- ページの先頭へ-

Internet Watch ホームページ
Copyright (c) 2004 Impress Corporation All rights reserved.