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鍵そのものの解読に相当する。
素因数分解って何だっけ? (スコア:3, 興味深い)
Re:素因数分解って何だっけ? (スコア:3, 参考になる)
元の式が違ってるようですね。正しくは
です。これは と実質同じです。いずれにせよ収束が遅いので実用にはなりません。僕は27年前、マチンの公式を使っていました。くわしくは 円周率の公式集 [kyutech.ac.jp]というのがあるのでそちらを。
Re:素因数分解って何だっけ? (スコア:1, 参考になる)
# これだと確か10000ぐらいまで計算しても3.1415まで行かなかったはず
参考URL (スコア:1, 参考になる)
Re:参考URL (スコア:0)
Re:参考URL (スコア:0)
# 仰っていることは正論ですけど。
Re:参考URL (スコア:0)
Re:参考URL (スコア:0)
Re:参考URL (スコア:0)
Re:参考URL (スコア:0)
アプリケーションが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
検証はコチラで (スコア:1)
×
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にしてごらん
Re:検証はコチラで (スコア:0)
結果が正しいのかは…知りません(笑)
Re:検証はコチラで (スコア:0)
Re:検証はコチラで (スコア:0)
18819881292060796383869723946165043980716356337941
73827007633564229888597152346654853190606065047430
45317388011303396716199692321205734031879550656996
221305168759307650257059
# 大文字をたくさん書きすぎですか。はぁそうですか。
# という事で無駄にイラナイ事を書いてみる
## まだ大文字書きすぎですか。はぁそ
Re:検証はコチラで (スコア:0)
そしてrubyなら素で計算できる。
Re:検証はコチラで (スコア:1)
Re:検証はコチラで (スコア:0)
576bit長 (スコア:1, 興味深い)
このビット長には何か意味があるんでしょうか。
キバヤシ算 (スコア:2, おもしろおかしい)
それに解読された日付20031203、
全てを掛けると11537972928。
当然RSAなのでR(13)S(19)A(1)すなわち18191を加えると
11537991119になる。
一見ランダムな数値に見えるが、
1が9不自然に多いので取り除くと537
アナグラムとして並び替えると 5 7 3
すなわちコナミ!
これはコナミによるゲーム業界支配を予告する
暗号だったのだよ!!!
Re:キバヤシ算 (スコア:3, おもしろおかしい)
本当は 新たな「7,5,3」支配をたくらむ「ペコちゃん千歳飴」 のフジヤが
密かに暗号解読をし、世界を支配する予告 なのだ!!
主力商品が「見るキー」だし。
#お後がよろしいようで・・・・
Re:キバヤシ算 (スコア:2, おもしろおかしい)
「mamanoaji-」
Re:576bit長 (スコア:1, 参考になる)
ですから、576=512+64 ではなく、576=64*9 と考えるのが正しい(って言うか、そう考えるとわかりやすい)。
Re:576bit長 (スコア:0)
設定しているってことですね。フォローありがとうございます。
/* #450486は無視して下さい。考え違いをしていました m(_ _)m */
Re:576bit長 (スコア:0)
もうちょっと考えてから書き込めばよかった。
失礼しました。
これはどのくらいヤバいことなんでしょうか? (スコア:1)
心配なのは素因巣分解のアルゴリズムが改良されていくと短いbit 数の暗号を解く時間も劇的に短くなるのではないのか、という事です。 例えば、今回の方法を使ってそこら辺のパソコンで512bit の暗号を解くとしたらどのくらいの時間がかかるんでしょうか?
Re:これはどのくらいヤバいことなんでしょうか? (スコア:2, 参考になる)
また、専門家ではないので外しているかもしれませんが、 RSA 以外にも公開鍵暗号の方式はありますから(そちらは別な困難な問題にもとづいている)、ここで解けたからといって、そこまで不安視することはないのではないか、と思います。
量子コンピュータが実用化されたら何ビットだろうとダメという話もありますが(笑)。
Re:これはどのくらいヤバいことなんでしょうか? (スコア:1)
# 世の中には128bit 暗号がたくさんあるみたいですが、
# 自分の中では512bit くらいないとヤバイということにしておきます。
Re:これはどのくらいヤバいことなんでしょうか? (スコア:4, 参考になる)
> # 自分の中では512bit くらいないとヤバイということにしておきます。
あなたの言う 128bit 暗号はおそらく DES とか RC5 とか AES などの
共通鍵暗号方式の鍵長を指しているのでしょうが、今回の件は公開鍵
暗号方式のことです。
共通鍵暗号方式と公開鍵暗号方式の、しらみつぶし攻撃に対する
耐性の比較を、暗号技術大全" [amazon.co.jp] より引用します。
(共通鍵=公開鍵)
56bit=384bit
64bit=512bit
80bit=768bit
112bit=1792bit
128bit=2304bit
公開鍵と一括りにされると (スコア:1, 参考になる)
# 「暗号技術大全」で言うところの公開鍵ってRSA鍵のことなんでしょうね
Re:公開鍵と一括りにされると (スコア:1, 参考になる)
Re:これはどのくらいヤバいことなんでしょうか? (スコア:1, 参考になる)
RSA暗号は指数関数的に解読が困難になっていくので、1024bitは512bitに比べて2^512倍の時間がかかるはずだったとおもいます。
>心配なのは素因巣分解のアルゴリズムが改良されていくと
アルゴリズムが多少改良されるくらいなら問題はかなり小さいです。むしろ、理論的に簡単に素因数分解ができる方法が見つかったら、RSAは使えなくなります。ただし、過去に多くの天才数学者が挑戦していますが、この命題は解決されていません。それより、それができたらフィールズ賞ものか?
Re:これはどのくらいヤバいことなんでしょうか? (スコア:3, 参考になる)
>RSA暗号は指数関数的に解読が困難になっていくので、
>1024bitは512bitに比べて2^512倍の時間がかかるはずだったとおもいます。
いいえ、RSA暗号(素因数分解)はそこまで難しい問題ではありません。
今回用いられた「一般数体ふるい法(GNFS)」は、指数時間よりもずっと早く
素因数分解を行なうことができます。
http://mathworld.wolfram.com/NumberFieldSieve.html
# そういう意味で、素因数分解は解くのに準指数時間かかる問題と呼ばれます。
日本語だとこちら↓のサイトが詳しいでしょうか。
http://www.rkmath.rikkyo.ac.jp/~kida/bunkai.htm
Re:これはどのくらいヤバいことなんでしょうか? (スコア:1)
劇的に速く素因数分解ができる方法は未だ見つかっていないので
時間を見積もるには総当たりで考えればいいということですか。
Re:これはどのくらいヤバいことなんでしょうか? (スコア:1, 参考になる)
それは良く知られた事。
で、ヤバいのは「巨大合成数の素因数分解を素早くやる方法はない」事が
証明されていない点ですよね。
だから明後日辺りに驚異的な素因数分解理論が見つかる可能性もゼロじゃない。
量子コンピュータの平行計算による暗号解読の実現とどちらが先
なのか...
負けずに日本も (スコア:1, おもしろおかしい)
その気になれば (スコア:1)
ひとつは計算速度で、ひとつは容量で。ちょっとおもしろいなとおもいました。
とはいうものの、512ビットから64ビットだけ増えて576ビットになったことによってどのくらい増えたか理屈ではわかるが(2^64倍)、やはり感覚的にはわからないので、笑えないが。
とりあえず、こんな風にしてわかったきになろうっと
2^64=18446744073709551616
2^128=340282366920938463463374607431768211456
2^192=6277101735386680763835789423207666416102355444464034512896
2^256=115792089237316195423570985008687907853269984665640564039457584007913129639936
...
ここから先は投稿フィルタにひっかかりました。
素人の質問 (スコア:0)
もし元の素数が素数であることが (たとえばパソコンレベルで) 簡単に分かるのなら、かけあわせた結果できる巨大な数も、その気になれば (たとえばスーパーコンピュータを使って) 簡単に素因数分解できてしまうような気がします。
Re:素人の質問 (スコア:5, 参考になる)
ここにとある数字 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:素人の質問 (スコア:1)
で御指摘の親コメントの論法の問題点ですが、特定の問題の複雑さを 示すのに、始めに手法を与えて、その手法の手間を問題にしている 部分で、その手法を選んだ妥当性について論じていません。 これは問題だと思います。
-- 哀れな日本人専用(sorry Japanese only) --
Re:素人にわかるようにチャレンジ!!! (スコア:1)
素因数分解をするには、与えられた数から素因数を一つ見つける必要があります。 もし、素因数の候補が見つかったら、それが与えられた数の素因数かどうかは、 実際に割算をすればチェックできます(このように答が正しいかのチェックが 容易にできる問題をNP問題とか言います)。従って、素因数分解の難しさは 実際の割算ではなく、与えられた数から素因数の候補を見つけることにあります。 現在、量子コンピュータを使用しない限りは、この候補を見つける効率の良い 方法はわかってません。複雑な数論を使わない限り、1 から与えられた数 の平方根のうちのどれか位しかわかりません(複雑な数論を使っても 与えられた数の桁数個程度まで絞りこむことはできてません)。 従って、与えられる数が10倍になる(桁が一桁増える)と、候補の数は数個増える どころではなく、数倍に膨れ上がります。このように桁が増えるにつれ、計算の 手間が数倍になっていくような計算を指数時間と言います。
一方、素数に関しては、様々な定理が成り立つことが知られています。 素数にしか成り立たない定理に合成数を代入するとおかしなことになります。 このような定理の例としては、素数 p に対して、任意の数のp-1乗したものを pで割ると余りが 1 になる(フェルマーの小定理)などがあります。 特に群論に関する定理に対しては、おかしなことが発生すると集合のサイズが 1/2 以下になってしまうことがわかっています。 この性質をうまく利用すると、与えられた数が 素数かどうかをチェックする式を桁数(の何乗か)に比例した数程度に絞る ことができるようになります。 与えた数の桁数の何乗かに計算の手間が比例する計算を多項式時間とか P とか 言います。
# 行数はなんとかなったけど、分量はちょっと多めかな? 素数判定まで おまけにつけたので許して下さい
-- 哀れな日本人専用(sorry Japanese only) --
Re:素人の質問 (スコア:2, 参考になる)
-- 哀れな日本人専用(sorry Japanese only) --
Re:素人の質問 (スコア:1)
逆は証明されてなかったような。
すなわち、何らかの画期的な方法を使えば素因数分解せずとも
RSAを解ける可能性がないことは否定されてなかったような。
# まぁこれもあまたの数学者が挑戦してきたことだと思うので
# 超天才でもない限りちょっとした気合や根性ではできないと思うけど。
Re:素人の質問 (スコア:1)
一方 Primarity in P の論文を読むと、今までの積み重ねから とうとうできたかという感想を持ちました。 超天才というよりは日頃の鍛錬の成果なのかなぁと思いました。
-- 哀れな日本人専用(sorry Japanese only) --
Re:素人の質問 (スコア:0)
Re:素人の質問 (スコア:1, 興味深い)
sakamoto さんの記事の丸かっこ内に書いてあるとおり、「誤る可能性はあるけど高速なアルゴリズム」を使ってたのですよ。
# もちろん確定的なテストも使ってますが、あまりに遅いものは使ってないと思います。
# トリビアですが、確率的な素数テストを通過してしまう合成数を「擬素数」と呼びます。
Re:素人の質問 (スコア:1)
そう考えれば、x=2^n-1が素数かどうか判定するのにO(2^n)かかるアルゴリズムも、多項式時間アルゴリズムということになってしまいますからね。
Re:素人の質問 (スコア:1)
たとえば、3からsqrt(n)までのすべての奇数で割ってみるという 一番素朴なアルゴリズムの計算量は、割り算が定数時間としてO(n^0.5)となります。ここで問題のサイズとしてnそのものをとれば、この素朴アルゴリズムは立派な多項式時間アルゴリズムと解釈できるわけです。
しかし常識的にはln nをサイズとして考えるべきなので、そうすると計算量はO(2^((ln n)/2))となり、桁数の指数関数となります。
Re:素人の質問 (スコア:0)
素人な答え (スコア:0)
「素因数分解」は
「素数かどうか判定する」ことに比べてずっと大変で、
「素因数分解」は桁が2倍程度に増えるだけで、非常に時間がかかる。
ということから、暗号が成立する
(大きな2つの素数を見つけることはできるが、
そのような数をかけたものはちょっとやそっとじゃ
因数分解できない)
のではないかと。
Re:素人の質問 (スコア:1)
また、暗号を送る際、平文となる数は、合成数と互いに素でなければなりません。 平文の定義域が連続している場合、最小の素因数よりも小さい値までの 範囲までしか送ることができません。
-- 哀れな日本人専用(sorry Japanese only) --