パスワードを忘れた? アカウント作成
7020 story

RSA-576が素因数分解される 91

ストーリー by Oliver
延々と割り算 部門より

巨大な数の素因数分解に賞金をかけているRSA ChallengeのひとつであるRSA-576の素因数分解にドイツ連邦情報技術保安局のチームが成功した。RSA-576は576ビット長の巨大な整数(10進数で174桁)で、素因数分解の成功に1万米ドルの賞金がかけられていた。RSA Challengeはまだこの解を正解認定していないが、解答とされている素数をかけるとRSA-576が得られることを簡単に自分でも確認できる。RSA Challengeの背景と今回の素因数分解に使われた手法についてはMathworldの記事が詳しい。
RSAを筆頭に公開鍵暗号はふたつの巨大な素数をかけるのは簡単だが、その結果をまた元の素数に因数分解するのは困難、という性質に基づいている。素因数分解が可能になれば公開鍵から秘密鍵が計算できるので、今回の発表はひとつの576bit長のRSA鍵そのものの解読に相当する。

この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。
  • by pooka (16946) on 2003年12月08日 18時45分 (#450461) 日記
    そんな人向けに→ココ [asahi-net.or.jp]
  • 参考URL (スコア:1, 参考になる)

    by Anonymous Coward on 2003年12月08日 18時37分 (#450457)
    http://www.nfsnet.org/
    • by Anonymous Coward
      説明のないURLはブラクラの疑いあり。アクセス注意。
      • by Anonymous Coward
        確認して警告する度胸がなかったのね。

        # 仰っていることは正論ですけど。
      • by Anonymous Coward
        説明があればブラクラの疑いはないのか。
      • by Anonymous Coward
        たかがブラクラ、そんなに騒ぐことでもあるまい。
        アプリケーションが1つ落ちるなんて日常だろうに。
        ---
        Welcome to NFSNET
        The goal of the NFSNET project is to use the Number Field Sieve to find the factors of increasingly large numbers.
        What is the Number Field Sieve? Click here to view a section of our frequently asked questions.
        We're currently working on 2^811-1, a composite number with 245 decimal digits and just one known factor, 326023. Assuming we have no challengers (never a safe assumption!) the facto
  • 3980750 8642406493 7397125500 5503864911 9906436234 2526708406 3851895759 4638895726 1768583317
    ×
    4727721 4610743530 2536223071 9730482246 3291469530 2097116459 8521711305 2071125636 3590397527

    Unix 使いなら GNU bc を起動して、
    3980750 8642406493 7397125500 5503864911 9906436234 2526708406 3851895759 4638895726 1768583317 * 4727721 4610743530 2536223071 9730482246 3291469530 2097116459 8521711305 2071125636 3590397527
    とタイプ。

    Java開発環境があるなら、BigIntegerを使って計算。

    Google!の電卓機能 [google.com]は計算結果を丸めてしまうのでダメでした。
    --
    _.. ._._._ _... ._._._ ._. ._._._
    物は試しだ。コメントのしきい値を2にしてごらん
    • by Anonymous Coward
      JavaScript電卓 [faireal.net]のAとBにそれらの数を放り込むというお手軽な方法もあります。手元の環境では一瞬で計算できました

      結果が正しいのかは…知りません(笑)
      • by Anonymous Coward
        redundant気味ですが結果も。

        A = 39 80750 86424 06493 73971 25500 55038 64911 99064 36234 25267 08406 38518 95759 46388 95726 17685 83317
        B = 47 27721 46107 43530 25362 23071 97304 82246 32914 69530 20971 16459 85217 11305 20711 25636 35903 97527
        A+B = 87 08472 32531 50023 99333 48572 52343 47158 31979 05764 46238 24866 23736 07064 67100 21362 53589 80844
        A*B = 1881 98812 92060 79638 38697 23946 16504 39807 16356 33794 17382 70076 33564 22988 85971 52346 65485 31906 06065 04743 04531 73880 11303 39671 61996

    • by Anonymous Coward
      ちなみに、正解は こちら [rsasecurity.com]

      18819881292060796383869723946165043980716356337941
      73827007633564229888597152346654853190606065047430
      45317388011303396716199692321205734031879550656996
      221305168759307650257059

      # 大文字をたくさん書きすぎですか。はぁそうですか。
      # という事で無駄にイラナイ事を書いてみる
      ## まだ大文字書きすぎですか。はぁそ

    • by Anonymous Coward

      そしてrubyなら素で計算できる。

  • 576bit長 (スコア:1, 興味深い)

    by Anonymous Coward on 2003年12月08日 19時35分 (#450480)
    512 + 64 = 576 ですが一見半端な数字に見えます。
    このビット長には何か意味があるんでしょうか。
    • キバヤシ算 (スコア:2, おもしろおかしい)

      by Anonymous Coward on 2003年12月08日 22時18分 (#450577)
      576bitは72*8bit。すなわち72と8。
      それに解読された日付20031203、
      全てを掛けると11537972928。
      当然RSAなのでR(13)S(19)A(1)すなわち18191を加えると
      11537991119になる。

      一見ランダムな数値に見えるが、
      1が9不自然に多いので取り除くと537
      アナグラムとして並び替えると 5 7 3
      すなわちコナミ!

      これはコナミによるゲーム業界支配を予告する
      暗号だったのだよ!!!
      親コメント
      • Re:キバヤシ算 (スコア:3, おもしろおかしい)

        by onyonyo (15599) on 2003年12月08日 22時33分 (#450585)
        いいや違う、コナミは隠れ蓑だ
        本当は 新たな「7,5,3」支配をたくらむ「ペコちゃん千歳飴」 のフジヤが
        密かに暗号解読をし、世界を支配する予告 なのだ!!

        主力商品が「見るキー」だし。


        #お後がよろしいようで・・・・
        親コメント
    • Re:576bit長 (スコア:1, 参考になる)

      by Anonymous Coward on 2003年12月08日 19時42分 (#450489)
      RSAのページ [rsasecurity.com]を見ればわかりますが、64bit単位でチャレンジがあります。
      ですから、576=512+64 ではなく、576=64*9 と考えるのが正しい(って言うか、そう考えるとわかりやすい)。
      親コメント
      • by Anonymous Coward
        #450480です。つまり答えとなる素数のビット長を32ビット単位に
        設定しているってことですね。フォローありがとうございます。

        /* #450486は無視して下さい。考え違いをしていました m(_ _)m */
    • by Anonymous Coward
      #450480です。自己レス。24ビットの自乗ですね。
      もうちょっと考えてから書き込めばよかった。
      失礼しました。
  • ちょっと調べた所、RSA 暗号は512, 768, 1024bit が使われているとのことです。 単純にbit 数が二倍になると解くのにかかる時間は二倍じゃ済まないというのは 予想できます。 とすると、1024bit の暗号を使っていれば大丈夫なんでしょう。

    心配なのは素因巣分解のアルゴリズムが改良されていくと短いbit 数の暗号を解く時間も劇的に短くなるのではないのか、という事です。 例えば、今回の方法を使ってそこら辺のパソコンで512bit の暗号を解くとしたらどのくらいの時間がかかるんでしょうか?

    • 今回のはどれくらい解析に時間がかかったのかわかりませんが、相当な時間がかかったことは間違いありません。ものの本 [amazon.co.jp]によれば、 512 ビットの問題は1999年に解かれたらしいですが、9週間の前計算と292台のコンピュータでの5.2カ月の計算が必要だったということです。

      また、専門家ではないので外しているかもしれませんが、 RSA 以外にも公開鍵暗号の方式はありますから(そちらは別な困難な問題にもとづいている)、ここで解けたからといって、そこまで不安視することはないのではないか、と思います。

      量子コンピュータが実用化されたら何ビットだろうとダメという話もありますが(笑)。
      親コメント
    • by Anonymous Coward on 2003年12月08日 21時44分 (#450555)
      >解くのにかかる時間は二倍じゃ済まない
      RSA暗号は指数関数的に解読が困難になっていくので、1024bitは512bitに比べて2^512倍の時間がかかるはずだったとおもいます。

      >心配なのは素因巣分解のアルゴリズムが改良されていくと
      アルゴリズムが多少改良されるくらいなら問題はかなり小さいです。むしろ、理論的に簡単に素因数分解ができる方法が見つかったら、RSAは使えなくなります。ただし、過去に多くの天才数学者が挑戦していますが、この命題は解決されていません。それより、それができたらフィールズ賞ものか?
      親コメント
      • >>解くのにかかる時間は二倍じゃ済まない
        >RSA暗号は指数関数的に解読が困難になっていくので、
        >1024bitは512bitに比べて2^512倍の時間がかかるはずだったとおもいます。
        いいえ、RSA暗号(素因数分解)はそこまで難しい問題ではありません。

        今回用いられた「一般数体ふるい法(GNFS)」は、指数時間よりもずっと早く
        素因数分解を行なうことができます。
        http://mathworld.wolfram.com/NumberFieldSieve.html
        # そういう意味で、素因数分解は解くのに準指数時間かかる問題と呼ばれます。

        日本語だとこちら↓のサイトが詳しいでしょうか。
        http://www.rkmath.rikkyo.ac.jp/~kida/bunkai.htm
        親コメント
      • ありがとうございます。参考になりました。

        劇的に速く素因数分解ができる方法は未だ見つかっていないので
        時間を見積もるには総当たりで考えればいいということですか。

        親コメント
      • by Anonymous Coward on 2003年12月09日 0時11分 (#450641)
        「巨大合成数の素因数分解を素早くやる方法はまだ見つかってない」

        それは良く知られた事。

        で、ヤバいのは「巨大合成数の素因数分解を素早くやる方法はない」事が
        証明されていない点ですよね。

        だから明後日辺りに驚異的な素因数分解理論が見つかる可能性もゼロじゃない。

        量子コンピュータの平行計算による暗号解読の実現とどちらが先
        なのか...
        親コメント
  • 負けずに日本も (スコア:1, おもしろおかしい)

    by Anonymous Coward on 2003年12月08日 21時24分 (#450539)
    名乗りをあげてほしいものです。>京都府警
  • by yg (12833) on 2003年12月09日 0時12分 (#450643)
    このストーリー、「その気になれば」というコメントが2回でています。
    ひとつは計算速度で、ひとつは容量で。ちょっとおもしろいなとおもいました。

    とはいうものの、512ビットから64ビットだけ増えて576ビットになったことによってどのくらい増えたか理屈ではわかるが(2^64倍)、やはり感覚的にはわからないので、笑えないが。

    とりあえず、こんな風にしてわかったきになろうっと
    2^64=18446744073709551616
    2^128=340282366920938463463374607431768211456
    2^192=6277101735386680763835789423207666416102355444464034512896
    2^256=115792089237316195423570985008687907853269984665640564039457584007913129639936
    ...

    ここから先は投稿フィルタにひっかかりました。
  • by Anonymous Coward on 2003年12月08日 19時39分 (#450487)
    素因数分解がそんなに難しいのなら、かけあわせる元となるふたつの素数が素数であるということを確認することも、難しいのではないでしょうか?

    もし元の素数が素数であることが (たとえばパソコンレベルで) 簡単に分かるのなら、かけあわせた結果できる巨大な数も、その気になれば (たとえばスーパーコンピュータを使って) 簡単に素因数分解できてしまうような気がします。

    • Re:素人の質問 (スコア:5, 参考になる)

      by Anonymous Coward on 2003年12月08日 20時23分 (#450511)
      素人にもわかりやすいように、多少ゴマ化しながら説明しましょう。

      ここにとある数字 102210419 があります。
      これを素因数分解するには、最大で √102210419 (≒10109)まで割り算してやる必要があります。
      実はこの数字 102210419 は5桁の最初の素数 10069 と、次の素数 10151 をかけたものなのですが、10069 が素数である事を確認するためには √10069 (≒100)まで割り算してやれば済みます。
      2つの数字を確認するにしても、その2倍の200回割り算してやれば良い訳で、1万回対200回という事で50倍の計算量の差になります。

      数字が大きくなればこの計算量の差はもっと開いてきます。
      たとえば、5桁の最大の素数 99971 と、その一つ前 99839 をかけた 9981004669 で考えれば、√9981004669(≒99904)と √99971(≒316)で158倍(99904/(316*2))の計算量です。

      この計算量の差が、キモなのです。

      親コメント
    • Re:素人の質問 (スコア:2, 参考になる)

      by sakamoto (8009) on 2003年12月08日 19時49分 (#450495) 日記
      素数判定問題は2002年に 決定性多項式時間で判定できる [iitk.ac.in]ことが 分かってます(それ以前も乱数を使えば誤りの可能性はあるけど 高速に出来ることはわかってました)。 ということで、あなたが「その気になる」なり方を発表すれば、 偉大な業績になると思いますので、是非御発表下さい。
      --
      -- 哀れな日本人専用(sorry Japanese only) --
      親コメント
      • by gatekeeper (18246) on 2003年12月09日 2時43分 (#450690) 日記
        RSAって確か「素因数分解ができる」ならば「解ける」けど、
        逆は証明されてなかったような。
        すなわち、何らかの画期的な方法を使えば素因数分解せずとも
        RSAを解ける可能性がないことは否定されてなかったような。
        # まぁこれもあまたの数学者が挑戦してきたことだと思うので
        # 超天才でもない限りちょっとした気合や根性ではできないと思うけど。
        親コメント
        • by sakamoto (8009) on 2003年12月09日 11時01分 (#450866) 日記
          ええ、「素因数分解ほど難しくない」ことが分かっているだけです。 ただ、「暗号文から 1 bit だけ解読する難しさと全部を解読する難しさ は同じ」ことは分かってますので 1bit でも解読することは 難しそうです。

          一方 Primarity in P の論文を読むと、今までの積み重ねから とうとうできたかという感想を持ちました。 超天才というよりは日頃の鍛錬の成果なのかなぁと思いました。

          --
          -- 哀れな日本人専用(sorry Japanese only) --
          親コメント
      • by Anonymous Coward
        2002年以前にも、公開鍵暗号方式は存在したように思うのですが、当時はどうやっていたのでしょうか?
        • by Anonymous Coward on 2003年12月08日 20時02分 (#450505)

          sakamoto さんの記事の丸かっこ内に書いてあるとおり、「誤る可能性はあるけど高速なアルゴリズム」を使ってたのですよ。

          # もちろん確定的なテストも使ってますが、あまりに遅いものは使ってないと思います。
          # トリビアですが、確率的な素数テストを通過してしまう合成数を「擬素数」と呼びます。

          親コメント
    • by Anonymous Coward
      フェルマーテストやらミラーテストなんつー便利な方法があったりします
    • by Anonymous Coward
      要は現在知られている方法では、
      「素因数分解」は
      「素数かどうか判定する」ことに比べてずっと大変で、
      「素因数分解」は桁が2倍程度に増えるだけで、非常に時間がかかる。
      ということから、暗号が成立する
      (大きな2つの素数を見つけることはできるが、
      そのような数をかけたものはちょっとやそっとじゃ
      因数分解できない)
      のではないかと。
typodupeerror

ソースを見ろ -- ある4桁UID

読み込み中...