「暗号解読」を読んで質問

**名無しさん＠お腹いっぱい。** · 2007/09/02(日) 23:10:49

素人質問ですが、よろしくお願いします。

現在RSA暗号化方式が時間がかかるって理由で
主流って書いてあるんだけど、
例えば既知の素数のリストを使ったりしても難しいの？

**名無しさん＠お腹いっぱい。** · 2007/09/02(日) 23:27:13

>>1
言いたい事は何となく分かった。

まず、既知の素数のリスト(有限)だけではあらゆる素因数分解を行えないため計算可能ではない。
つまり、素因数分解できる保証が無いということだ。

でも必要十分な素数が生成してあるならば、多項式時間で解決できると思うよ。
(素数の数は入力データ長に対して対数オーダーだから)

世界のどこかには膨大な素数を生成しているハッカーが居るのかもね。

暗号解読は面白ね。
俺も一昨年くらいに読んだ。

**名無しさん＠お腹いっぱい。** · 2007/09/03(月) 01:22:55

>>2

どうもです。

さすがに素数そのものは特許にできないだろうから、
見つけた素数は各企業・機関が独自に保持してるのかなー、なんて。

そう考えると正にイタチゴッコですね。

**名無しさん＠お腹いっぱい。** · 2007/09/03(月) 20:25:08

まじれす。数が多すぎでどうにもならない。

今RSAのキーのうち法 N の長さは 1024 ビットぐらいで、N = p q とすると
p や q は長さ512 ビット、大きさにすると 2^512 ぐらい、
この付近の大きさまで素数表をつくると、個数勘定で 2^512/(512 ln 2) 個ぐらいに
なる。計算は神様がやってくれても、こんな大きいディスクは誰にもつくれない。

**名無しさん＠お腹いっぱい。** · 2007/09/07(金) 01:20:58

googleで計算してみると

(2^512) / (512 ln(2)) = 3.77800352 × 10^151

まさに理論上は解読出来るけど、ってことか。
ありがとうございます。

**名無しさん＠お腹いっぱい。** · 2007/09/15(土) 14:31:04

　　こんな酷いリンチはに許せない！！　

足立区綾瀬で、少年Ａ＝横Ｏ祐Ｏ（当時宮Ｏ）と少年Ｃ＝ミＯト伸Ｏは、
プラスティク工場からアルバイトを終えて帰る女子高生を自転車ごと
蹴り倒して誘拐、少年Ｃの自宅に４０日間監禁し暴行して殺害しました。
少年Ｃの両親と兄は自宅２階での監禁を知っていましたが黙認しました。
少年Ｃは街で知合った仲間を自宅に呼び込み金を受取り、女子高生を暴行させたり
ヌードダンスを踊らせていました。彼女はどのような気持ちだったでしょうか？
女子高生の遺体の手足には焼かれたヤケドがあり、乳首は溶け落ち、
性器と肛門に異物が挿入され、栄養失調で痩せ細った体でした。
　「女子高生コンクリート詰め殺人事件」
　　　 http://www8.ocn.ne.jp/~moonston/lynch.htm
ご存知かもしれませんが、この事件の副主犯、少年Ｂ＝神Ｏ（旧姓はＯ倉）は
再び暴行・監禁事件を起こして服役していました。

**名無しさん＠お腹いっぱい。** · 2007/10/03(水) 23:25:28

質問だけど、何で素因数分解できれば多項式でRSAの鍵当てられるの？

**名無しさん＠お腹いっぱい。** · 2007/10/04(木) 12:05:30

http://ja.wikipedia.org/wiki/RSA%E6%9A%97%E5%8F%B7
ここでも読め。