【セキュリティ】512ビットのRSAキーは1000円程度の費用をかければ数十時間で解読できてしまう [すらいむ★]

**すらいむ ★** · 2025/01/10(金) 22:27:34.72

512ビットのRSAキーは1000円程度の費用をかければ数十時間で解読できてしまう

　メールのなりすましを防ぎ、正しい人物から送信されたことを証明する仕組みとして「DKIM」がありますが、DKIMの署名に使用されるRSAキーが短いと簡単に解読されてしまうことをエンジニアのアンドレアス・ウルフ氏が解説しています。

　How We Cracked a 512-Bit DKIM Key for Less Than $8 in the Cloud
　https://dmarcchecker.app/articles/crack-512-bit-dkim-rsa-key

（以下略、続きはソースでご確認ください）

Gigazine 2025年01月09日 12時20分
https://gigazine.net/news/20250109-512-bit-dkim-rsa-key/

**名無しのひみつ** · 2025/01/10(金) 22:42:09.97

1024ならその何倍？

**名無しのひみつ** · 2025/01/10(金) 22:53:18.91

PGPとか使ってるやついるの？

**名無しのひみつ** · 2025/01/11(土) 01:00:55.35

RSA-512とか20年前に非推奨だろ...
1999年に懸賞金付きのチャレンジで解読されとるわ

>>2
1024もダメ
2048はそろそろ危ない
AES-128相当の強度が欲しければ3072にしろと言ってるが
非対称暗号はRSAなんて使わずに楕円曲線系のを使っとけと思う

**名無しのひみつ** · 2025/01/11(土) 03:44:56.23

>>4
RSAって巨大素数のデータを事前に用意してれば簡単に解けそう

**名無しのひみつ** · 2025/01/11(土) 18:35:02.01

x以下の素数の個数は素数定理によりx/ln(x)個と近似できるので
たぶんあなたが考えているより候補はずっと多い
例えば2048bitなら10の613乗個ぐらいは候補がある
事前に用意しようがしまいが総当たりに時間がかかるから鍵が十分に長ければ安全という話だ

**名無しのひみつ** · 2025/01/11(土) 18:47:21.07

ＷＩＦＩとか大丈夫なん？

**名無しのひみつ** · 2025/01/12(日) 01:29:43.12

もちつけ
素数を数えるんだ

**名無しのひみつ** · 2025/01/12(日) 02:12:09.14

DKIMクラックして何すんだ？

**名無しのひみつ** · 2025/01/12(日) 06:36:40.65

>>4氏の言うように楕円曲線系やその類の暗号化が最適だと思えます。
tomeapp.jp/archives/1282
が、現実こんな感じで通信相手が異なるハードウェアを用いることで浮動小数点の誤差が発生し
複合化できない懸念が…

**名無しのひみつ** · 2025/01/12(日) 11:08:10.40

>>10
全然わからない話にそれっぽいこと言って
恥さらしにくるモチベーションはどこから来るの？

**名無しのひみつ** · 2025/01/12(日) 11:16:29.18

俺は寝れない時、素数を小さい方から思い出しているぜ

**名無しのひみつ** · 2025/01/12(日) 11:48:33.65

>>8
数十時間あれば数え切れるぞ

**名無しのひみつ** · 2025/01/13(月) 19:46:32.66

1と2が素数か悩んでる間に大体寝られる

**名無しのひみつ** · 2025/01/14(火) 00:32:48.12

>>13
へえ、最近発見されてる最大の素数は2^1億3627万9841乗-1で10進数だと4100万桁あるんだがたったの数十時間でそこまでたどり着けるのか。
精神と時の部屋に住んでるの？

**名無しのひみつ** · 2025/01/19(日) 08:31:42.38

数体篩法を使ってやったのかな。
RSA暗号を解読する、つまり長桁512ビット程度の整数を
n=pq と素因数分解するというサービスをクラウドに
立ち上げて、利用時間に従って料金をとれば良いよね。

**名無しのひみつ** · 2025/01/19(日) 09:44:18.78

RSA暗号も楕円暗号もアーベル群の暗号なので、どうして楕円がRSAよりも短い鍵で
安全だと言えるのか、正しく説明してみてほしい。

**名無しのひみつ** · 2025/01/19(日) 10:18:14.73

学術的にはさておき
現実には暗号なんて10回間違えればシャットされるから
複雑な必要は無い。

むしろ長いパスワードは覚えられないから
書いて置く必要があり
現実にはセキュリティ上脆弱になる。

**名無しのひみつ** · 2025/01/19(日) 13:57:37.66

合成数ｎを得て、それをローカルにネチネチと時間を掛けてｐｑに
因数分解しておく。そうして本番で1発でさっとやれば、
1回も間違えないからシャットアウトなどされない。

**名無しのひみつ** · 2025/01/19(日) 13:59:14.41

どこかのWebサーバーで、Webの記入欄にNを入れると、しばらく計算して
因数分解できた結果のPとQを表示する、そういうものを作れば、誰もが
ああ短い鍵ではダメなんだねというのがよく分かるようになる。

**名無しのひみつ** · 2025/01/21(火) 08:03:46.37

情報設問
[問]　A君は、便利なツールを使って2つの長が～い素数PとQを生成しました、
それを用いて合成数Nを造り、それでRSA暗号に用いていたところ、
あっさり破られてしまっていることが判明したとします。
その原因や理由について考えてみましょう（配点5点）。