トップページ⇒tech
122コメント32KB

ＲＳＡを破るプログラムを作ろう

■ このスレッドは過去ログ倉庫に格納されています
0001デフォルトの名無しさんNGNG
要は素因数分解プログラムです
10^200クラスの数字をいかにして素因数分解するか
ちなみにＲＳＡの数字は全て２つの素数を掛けたもので出来てますので
スーパーコンピューターで１秒で10^20くらいの総当り計算をしても生きてる間に解けません

ちなみに人類は、これまでに10^174の数字を素因数分解しました
さらに上のレベルのプログラムを作りたい！
0002デフォルトの名無しさんNGNG
２
0003デフォルトの名無しさんNGNG
ttp://www.rsasecurity.com/rsalabs/challenges/factoring/numbers.html
このサイトの10^193の数字を解けば賞金$20,000
0004デフォルトの名無しさんNGNG
そういや RC5-64 はどうなった？と思ったら
とっくに解読できてたんだな。

今思えば、もの凄い電気の無駄遣いだったよ…＿|￣|○
0005デフォルトの名無しさんNGNG
>>4
http://pc3.2ch.net/test/read.cgi/jisaku/1047274285/l50
0006デフォルトの名無しさんNGNG
プログラムっていうか
そんなアルゴリズム考えられりゃ苦労しない
というより一生金に苦労しないんじゃないか
0007デフォルトの名無しさんNGNG
１０年かかるプログラムを作ったとする
１０人で１年
１００人で１ヶ月
１０００人で３〜４日か
２ｃｈの総力を使えば出来るな

これはやってみたい
0008デフォルトの名無しさんNGNG
>>7
家庭用コンピュータで10年?
0009デフォルトの名無しさんNGNG
ていうか、賞金を取ったとしてどうするんだ？
0010デフォルトの名無しさんNGNG
1000人で分けるつもりじゃないか?
一人$20で口座とか晒すやついるのか
0011デフォルトの名無しさんNGNG
RC5-72は全てのキーをチェックするのにあと1500年ほどかかるらしい。
0012デフォルトの名無しさんNGNG
>ちなみに人類は、これまでに10^174の数字を素因数分解しました
おなじ方法を使うとして 10^200 を処理するには上記の作業の 10^26 倍の時間が
かかると思われます。
任意の 10^174 程度の数字を１秒で素因子分解できるとしても 10^26 秒かかります。
これは 317京 0979兆 1983億 7645万 8650年かかるということです。
短いですね。
0013デフォルトの名無しさんNGNG
>任意の 10^174 程度の数字を１秒で素因子分解できるとしても 10^26 秒かかります
Why?
10^174程度と10^200はえらい違いだと思うんだが
0014デフォルトの名無しさんNGNG
>>13
違うよ。13 がナニを質問してるのかわからない。
0015デフォルトの名無しさんNGNG
>>10
いや、参加してたかどうかも確認できんから
どっかに寄付するのが一番
0016デフォルトの名無しさんNGNG
>>12
ちと違うな
10^200と言っても、二つの素数は10^100クラスの数字を２個掛け合わせたもの
そのどちらかを探すだけでいいので、10^13秒でいい
0017デフォルトの名無しさんNGNG
10^200 / 10^174 = 10^26
なんか計算間違ったかな？
0018デフォルトの名無しさんNGNG
>>16
あぁ勘違い。よく設問を読みましょう。
因子がわからないから因子を探しているんだから、10^200 を探さなきゃいけない。
ついでに。200桁とわかっているのだから199桁までは省略できると浅はかに考える人がいるかもしれないが
10^200 - 10^199 はほとんど 10^200 と大差がない。
0019デフォルトの名無しさんNGNG
>>18
エラトステネスの篩って知ってますか?
2つの素数をかけた合成数のもとになる素数を求めるのは
その合成数の平方根以下の素数で割れるか確認していくだけ十分ですが?
>>16
>二つの素数は10^100クラスの数字を２個掛け合わせたもの
揚げ足取るようですまないが
そのように範囲が限定されていればもっと短い時間で済むはず
(10^10クラスで割れても面白くないので実際そのくらいになるだろうが

10^87までに含まれる素数の個数と
10^100までに含まれる素数の個数の比は87:100ではない
個数の差はもっと少ないので10^13倍にも満たないと思われるかも知れないが

大きな数になればなるほどコンピュータの負担も大きくなるわけであるし、
そこまでの素数を列挙するのにかかる時間は指数的に増加していく
実際どの程度になるかは知らない
0020デフォルトの名無しさんNGNG
>>18
意味がわからん
>200桁とわかっているのだから199桁までは省略できる
何を省略するんだ？
0021デフォルトの名無しさんNGNG
脳みそとか？
002219NGNG
途中変なとこあった。虫してくり。比のとこ
0023デフォルトの名無しさんNGNG
>>19
あなたがすごく賢い人に見える
ていうか、他が・・・
0024デフォルトの名無しさんNGNG
女陰吸うぶんかい？
0025デフォルトの名無しさんNGNG
一枚の紙（ディシュペーパでもいい）を面積が半分になるように１０回折ってみろ！
0026デフォルトの名無しさんNGNG
ディシュペーパ
翻訳
皿 林家
意訳
ハヤシライス
0027デフォルトの名無しさんNGNG
そのうち量子コンピュータができるんだから無駄な努力だ
紙と鉛筆で円周率の計算するようなもんだ
0028デフォルトの名無しさんNGNG
量子コンピューターが出てきても、必ずしも短い時間で
素因数分解できるようにはならないって誰かが言ってたよ。
今までのコンピューターと根本的に別物だから
単純じゃないって事なんだろうけど、さっぱり理解不能でした。
そこらへんのところ、詳しい人がいたら教えてちょんまげ。
0029デフォルトの名無しさんNGNG
>>27
良いアルゴリズムを作ろうという努力はないのか？
ひょっとしたら、今のパソコンでも一瞬で解ける方法があるかもしれないじゃないか

シャア風に言うなら
「今の環境でも簡単にＲＳＡを解ける方法もあるはずだ。それを探せ！」
0030デフォルトの名無しさんNGNG
>>29
その「あるかもしれないじゃないか」ってのが
まさに詭弁なんだが
0031デフォルトの名無しさんNGNG
そりゃまぁ、給料くれるなら幾らでも探しますけどね、少佐殿。
0032デフォルトの名無しさんNGNG
>>31
10^200クラスの素因数分解を高速に解くプログラムを作れたら
残りの人生は金に困らないのでは？
0033デフォルトの名無しさんNGNG
いや〜それよりは、近所の川で砂金取ったり、
沈没船とか、徳川埋蔵金を探した方が
期待値は大きいと思いますがね。
0034デフォルトの名無しさんNGNG
>>33
近所の川はともかく、沈没船や徳川埋蔵金はリスクがあるからな
投資金額がそうとうかかるだろう
その点、ＲＳＡは達成できなくても何も失わない
0035デフォルトの名無しさんNGNG
こういう方法もある
RSA=b^2-a^2（a,bは整数）
として考える方法
このbはRSAの平方根を少数以下ラウンドアップしたものより少しだけ多い数値になる事が多い
例えば10870974929で考えると
これの平方根を少数以下ラウンドアップすると104264
ここから探していく
ま、次の104265が正解なんだけど
正解がどうかはb^2-RSAが整数の２乗の数値になっていればいい
この場合、a=464
求める素数はb+aとb-aだから、103801,104729になるって感じ

まあ、この方法は２つの素数が近い数字であるほど早く見つかるんだけど
でも10^200クラスの数字になると、それでも10^70〜10^80回くらいの計算が必要になりそうだけどね
やっぱり総当り的な方法はダメかな
0036デフォルトの名無しさんNGNG
焼け石に水だけど
>>35の方法は
RSAに+1して4で割り切れる数字なら、bは奇数になる法則はある
これで計算時間は半減！！ｗ
0037デフォルトの名無しさんNGNG
間違った
4で割り切れる数字ならbは偶数
割り切れないならbは奇数

>>35の例だとRSAに１足しても４の倍数になってないからbは奇数
0038デフォルトの名無しさんNGNG
続き
さらに言うならRSAに１を足した数字が３の倍数なら、bも３の倍数になる法則もある
>>35の例だと、RSAに１を足すと３の倍数になってるから、bも３の倍数になる

これで計算速度は６倍・・・か？
まだまだやね
0039デフォルトの名無しさんNGNG
>>23
>>18に比べて>>19は一見まともっぽいこと書いてるけどてんででたらめだよ。
そもそもこんなデカイ数の素因数分解でエラトステネスの篩なんか使わないから
10^13とか10^26とかの議論はまったく意味がない。
0040デフォルトの名無しさんNGNG
新発見？
>>38の続き
bが奇数ならaは必ず偶数になる
しかも偶数でなんかの２乗になる数字は末尾がかならず０か４か６になる
末尾が２や８の数字はその時点でなんかの２乗ではない
だから、>>35の例だと、b^2の末尾が３か５か９にならにゃならん
でもなんかを２乗して末尾が３になる数字は無い
だからbの末尾は５か９だ
0041デフォルトの名無しさんNGNG
違った
b^2の末尾が５か９
だからbの末尾は３か５か７だね
0042デフォルトの名無しさんNGNG
>>3
アルゴリズムまで抑えられて2万ドル程度じゃ誰もやらないんじゃないの？
0043デフォルトの名無しさんNGNG
RSA-640の末尾は６６０９
b^2-a^2の末尾が６６０９

１を足しても４の倍数じゃないから、bは奇数
１を足すと３で割れるから、bは３の倍数

a^2の末尾が００と仮定すると、bの末尾は５３か０３
a^2の末尾が？４と仮定すると、b^2の末尾が？３になるのでこれは除外
a^2の末尾が？６と仮定すると、bは５の倍数

これでもまだまだ搾り足りないか・・・・
0044デフォルトの名無しさんNGNG
aの末尾は
04,96,00,20,40,60,80のどれかで間違いない

bの末尾は53,03,?5のどれかで３の倍数

もっと先に踏み込まないと無理か・・・
0045デフォルトの名無しさんNGNG
そうやって人生を無駄遣いしている暇があるのなら

コンピュータと素因子分解
ISBN4-7952-6889-4

でも読んでやり直しなさい。最新の技法ではないが、日本語だし、扱っている数学的記述も
けして高度ではない。高〜大３向け。
0046デフォルトの名無しさんNGNG
さらに搾った
aの末尾は004,204,304,504,704,804,196,296,496,696,796,996,00,20,40,60,80
のどれか

bの末尾は103,503,703,753,953,??5のどれかで３の倍数

まだまだ搾れそう
0047デフォルトの名無しさんNGNG
>>45
棒に振ってこそ人生　ｂｙ江田島平八
0048デフォルトの名無しさんNGNG
みんな頭いいな。
0049デフォルトの名無しさんNGNG
大学の講義で習ったにもかかわらず
「へぇ、すごいね。解けないんだ〜（´･∀･`）」
で済ましてた俺。
おまいらカッコイイぞ。
0050デフォルトの名無しさんNGNG
>>46
bの末尾353もあり
おそらく7353,2353の２通りだと思う
あと103のときは1103,6103だろう
この２つはaの末尾が00に対応
0051デフォルトの名無しさんNGNG
２ｃｈなら数で勝負できるだろ？
0052デフォルトの名無しさんNGNG
■暗号化スレ■
http://pc2.2ch.net/test/read.cgi/tech/1002736958/

暗号総崩れ-素数判定が多項式時間で可能
http://pc2.2ch.net/test/read.cgi/tech/1028877628/
0053デフォルトの名無しさんNGNG
>>52
意味ね
ＲＳＡ破られてないやん
0054デフォルトの名無しさんNGNG
結局沈む運命にあるスレか
上げておこう
0055デフォルトの名無しさんNGNG
ここじゃ無理
0056デフォルトの名無しさんNGNG
>>53
世界中の優秀な数学者が取り組んでも破られてないのに、
この板の人間ていどが破るのは土台無理ってこと。
0057デフォルトの名無しさんNGNG
物理的に破壊してみた
解読を目的にしなければ我がロイヤルハンマーの前に破れぬ物は無い
0058デフォルトの名無しさんNGNG
ハンマーなのに破れるのか
0059デフォルトの名無しさんNGNG
一ついい事を教えてやろう
末尾が９のＲＳＡは*****3 x *******3
もしくは******7 x ******7
の２通りしかない

末尾が１と９の組み合わせはあり得ない
だからってそれで解けるわけじゃないがな
0060デフォルトの名無しさんNGNG
11*19=209
0061デフォルトの名無しさんNGNG
東大生なら解けるんじゃないのか？
あるいは、河合模試全国１番とか、灘高生とか、ノーベルの野依教授とか。
0062デフォルトの名無しさんNGNG
ソニン数？
0063デフォルトの名無しさんNGNG
>>61
東大生に幻想を抱きすぎだよw
0064デフォルトの名無しさんNGNG
>>61
東大生なんて腐るほどいるじゃないか
0065デフォルトの名無しさんNGNG
まあ「東大卒」なんて毎年3000人以上いるわけで
珍しくとも何ともないわな。
ttp://www.u-tokyo.ac.jp/gaiyou/2223.html
ttp://www.u-tokyo.ac.jp/gaiyou/26.html
0066デフォルトの名無しさんNGNG
東大生全員の暗算でBrute Force Attackしても解けないだろうな、
それより公文式全会員導入のほうが可能性があるのではなかろうか。

人間の計算能力なんてそんなもんです。
つうか、計算機系の大学生ならRSAの理論くらい知ってるはずなんで、
なおかつ解かれてないのだから大学生は全員解けません、教授も解けません。
解く段階のスキルの無い高校生はそれ以前の問題ですよ。
0067デフォルトの名無しさんNGNG
人間の暗算は、20桁程度が限界らしいぞ。
パソコンの足元にも及ばない。
0068デフォルトの名無しさんNGNG
>>67
うちのパソコン20桁も計算できねーよ
0069デフォルトの名無しさんNGNG
>68
PCなら長大数使えや、
十露盤なら連結しろや。
0070デフォルトの名無しさんNGNG
>>69
人間でも同じ事だろ
0071デフォルトの名無しさんNGNG
560 デフォルトの名無しさん New! 04/03/03 00:56
東大生なら解けるんじゃないのか？
あるいは、河合模試全国１番とか、灘高生とか、ノーベルの野依教授とか、
ピーターフランクルとか。彼らはこのテーマを知らないだけで、やったら
解けると思うけど。。さすがに解くまで何億年とかジョークだろ。
0072デフォルトの名無しさんNGNG
>>71
学歴版のコピペか…
気に入った（・∀・）
0073デフォルトの名無しさんNGNG
>>70
人間の短期記憶ってそんなに覚えらんないから、
PCでいえば、メインメモリも仮想記憶も使い果たした状態にすぐなる、
外部記憶の十露盤使うか、筆算するかしかない。

短期記憶を増設するにはブラックジャック先生連れてこないと無理。
0074デフォルトの名無しさんNGNG
>>72
この板だった予感
0075デフォルトの名無しさんNGNG
睡眠不足。
0076デフォルトの名無しさんNGNG
>>75
　　　 ∧＿∧　 ／￣￣￣￣￣￣￣￣￣￣￣￣￣￣
　　［（　・∀・）＜　F5は屁こいてさっさと寝ろ
|￣￣￣￣￣￣ ＼＿＿＿＿＿＿＿＿＿＿＿＿＿＿
|　　|￣￣￣￣|　　|
|　　|　 ＠　 ＠|　　|
|　　|＠　 ＠　 |　　|
|　　|＿＿＿＿|　　|
|＿＿＿＿＿＿＿_|
0077デフォルトの名無しさんNGNG
>>74
まあわざわざ他板にこの板の名無しで書き込む人は稀だわな(削除依頼くらいか)。
0078デフォルトの名無しさんNGNG
世の中にはとっさに「2067年の8月17日は何曜日？」とか
「円周率の○○○桁目はいくつ？」とか聞かれて瞬時に
答えられる一種の天才もいるのだけど、そいつらがなぜ
瞬時に答えられるのかを追究してみるのも良さそう。

現在取られてるアプローチは、結局のところ指折り数えて
「時間かかるねぇ」とか「俺はより速く指を動かせる」って
言ってるだけの様に思える。
0079デフォルトの名無しさんNGNG
>>78
きっと何かの法則を見つけてるんだよな、前者は。
円周率はきっと覚えてるだけだ。だけっつってもすごいけど
0080デフォルトの名無しさんNGNG
>>78-79
ツェラーの公式
おいおい、このスレの奴らはこんな簡単な公式も知らないのかよ
さらしage
0081デフォルトの名無しさんNGNG
>>80
そういう問題じゃない。サヴァン症候群のやつ等はツェラーの公式に
基づいて算出している訳じゃない。
0082デフォルトの名無しさんNGNG
さらしあげたつもりが自分で自分をさらしあげてしまったｗ
0083デフォルトの名無しさんNGNG
分析的なものとして論じられている精神の諸作用は、
実は、ほとんど分析を許さぬものなのである。ただ結果から見て、
それらを感知するにすぎない。そのなかでもわかっていることは、
精神の諸作用を過分に身につけている人にとっては、
これこそなによりも生き生きとした楽しみの源泉である、ということだ。
だそうな、

イントロの一音聞いただけで曲名あてたり、
同じにしか見えない萌え絵の一部から作者わかったり、するヤツは
たまに会う程度にいるよな。
0084デフォルトの名無しさんNGNG
曜日を求める公式はツェラーの公式しかない訳じゃない。

dow(m,d,y){y-=m<3;return(y+y/4-y/100+y/400+"-bed=pen+mad."[m]+d)%7;}
みたいなトリッキーなソースもある。
0085デフォルトの名無しさんNGNG
結果どうすればｲｲの？
・アルゴリズムを作ればいい
・とにかく２つの素因数を求めればいい
どっちだ


0086デフォルトの名無しさんNGNG
> ・アルゴリズムを作ればいい
効率のいいアルゴリズムということなら、どっちでも好きなほうを
実現させておくれ。
どちらかというと前者のほうが簡単なのかもしれない。
0087デフォルトの名無しさんNGNG
>86
いや適当にその素因数を当てちゃった場合は賞金あるのかなと
思ってね。
「解きましたが方法は分かりません！！」・・・ある意味凄いがw
0088デフォルトの名無しさんNGNG
そういう時は「総当りで行きました」とだけ言うんだよ
アホ丸出し
0089デフォルトの名無しさんNGNG
>88
いやいや、今の総当りだと地球があるか太陽があるか分からんから・・・

Q.総当りのアルゴリズムを教えてくれ？
A, 脳内総当りです
~~~~~~~~~~~~~~~~~~~~~
以上でいいでつか？
0090デフォルトの名無しさんNGNG
かんぽき
0091デフォルトの名無しさんNGNG
地球シミュレータとか使えばいいんじゃないの？
それか、世界中のＰＣをネットでつなぐとか。ほら、子宮ガンの解析プロジェクト
を２ちゃんでやってるじゃん。
0092デフォルトの名無しさんNGNG
強制的に素因数分解に協力させるウイルスかけば、ばっちぐー。
0093デフォルトの名無しさんNGNG
>>91
むしろ暗号解読が先に行われていたかと。
以下のプロジェクトに参加よろ。

【分散処理】またーりdistributed.net【懸賞有】
http://pc3.2ch.net/test/read.cgi/jisaku/1076947927/l50
Distributed.net の２ｃｈチーム作ってみますた
http://pc3.2ch.net/test/read.cgi/jisaku/1047274285/l50
RC5 Cracking
http://pc.2ch.net/test/read.cgi/linux/1008690862/l50
0094デフォルトの名無しさんNGNG
age mahu
0095デフォルトの名無しさんNGNG
94 名前：デフォルトの名無しさん 投稿日：2004/03/15(月) 21:54
age mahu


95 名前：getsage 投稿日：2004/03/26(金) 11:41
藍


96 名前：デフォルトの名無しさん 投稿日：2004/03/26(金) 12:13
ニューラルネットワークに解かせるなんてどうよ？
板違いか。
0096デフォルトの名無しさんNGNG
保守
0097デフォルトの名無しさんNGNG
>>95
？？何が起こったんだ
0098デフォルトの名無しさんNGNG
>>97
3月下旬の鯖移転時に一部ログが消失した。>>95は、その補完。
当時は大騒ぎだったんだよ。
0099デフォルトの名無しさんNGNG
03/26 ログ消失事件
06/15 消えたログ補完 >>95
07/28 補完カキコにレス >>97

流石にRSAを破ろうって言う人たちの時間感覚は違うね。
このスレが1000行くまでには計算が終わるかもねw
0100デフォルトの名無しさんNGNG
>>中学の時授業中にひたすらやってましたが何か?
0101デフォルトの名無しさんNGNG
よーし、パパ(ry
0102デフォルトの名無しさんNGNG
age
0103デフォルトの名無しさんNGNG
hage
0104デフォルトの名無しさんNGNG
RSAを破りたいって時に素因数とか言ってる時点でもう破れないと思うが
0105大原ゆきNGNG
>>104
どうして？
0106デフォルトの名無しさん05/03/16 08:38:20
>>105:大原ゆき
どうして?
0107デフォルトの名無しさん2005/05/29(日) 20:57:44
たぶんもうＡＲＰＡとかＮＳＡが破ってるよ。
0108デフォルトの名無しさん2005/05/30(月) 05:47:02
10^200個の並列コンピュータがあればいちころ
0109デフォルトの名無しさん2005/06/17(金) 05:12:16
素因数分解エンジン（多倍長整数演算をシングルクロックで可能なように
アキュムレータそのものを超拡張したカスタム数値プロセッサ）でも自作
すれば、あるいは・・・
0110デフォルトの名無しさん2005/06/17(金) 13:02:10
>>109
じゃあとりあえずそいつの論理回路見せてくれ
0111デフォルトの名無しさん2005/06/18(土) 14:00:35
並列コンピュータの応用問題で結構やられてると思うので、作ることが趣味という
ような人でなければ意味ないかもね。個別素子で組んでも今度は速度的に見合わん
だろうし・・・
0112デフォルトの名無しさん2005/06/18(土) 15:09:36
所詮プログラマの分際で暗号を語るなど片腹痛いね
0113デフォルトの名無しさん2005/06/18(土) 16:59:06
>>112
数学者ならいいでつか
0114デフォルトの名無しさん2005/06/22(水) 13:15:03
>>113
所詮数学者の分際でプログラムを語るなど片腹痛いね。
0115デフォルトの名無しさん2005/12/18(日) 05:23:40
所詮人間の分際で真理を語るなど片腹痛いね。
0116デフォルトの名無しさん2006/02/01(水) 15:36:34
115のいう通りだぞ
0117デフォルトの名無しさん2006/02/02(木) 09:23:41
神様ならいいでつか
0118デフォルトの名無しさん2006/05/08(月) 01:32:09
>>92
＞強制的に素因数分解に協力させるウイルスかけば、ばっちぐー。
そういえば昔ググルさんに検索頼みまくるウイルスがあったなぁ。
ググルさんが沈没したのがただただ可笑しかったが。

つーか保守&age
0119デフォルトの名無しさん2006/05/08(月) 09:02:17
人間の生き死にをどうこうしようなど、おこがましいとは思わんかね？
0120デフォルトの名無しさん2006/05/09(火) 03:12:46
計算の途中の内部状態を出力して停止させることができるように
プログラムを作る。で、出力を読み込んで途中からまた計算できる
ように作っておく。

それをまずは現在のスーパーコンピュータで動かす。やがて技術が
進歩してもっと速いスーパーコンピュータが出てきたらプログラムを
停止させてそちらに持っていって動かす、というのを繰り返すと
意外と速く計算が終わるのではないか?
0121デフォルトの名無しさん2006/05/09(火) 03:15:40
ああ、そうだ。CPUが暇になったときに裏でこっそり計算する
スクリーンセーバーを配布してやらせりゃいいんじゃないか?
って、もうとっくにこんな意見出てそうだな。
0122デフォルトの名無しさん2006/10/15(日) 17:55:55
「量子コンピュータ」があれば「Ｓｈｏｒの素因数分解アルゴリズム」で実現出来る訳だが。

http://www.iftech.or.jp/center/kbes/dictonary/cnot_01.htm
■ このスレッドは過去ログ倉庫に格納されています