RSA暗号を破壊するとの論文が発表されるも「ほぼ誤報」とみられる 32
本当ならすごそうだけども 部門より
数学者で暗号学者であるClaus Peter Schnorr氏の発表した未査読の論文が話題となっている。この論文はRSA暗号を破壊するレベルで劇的に高速化したアルゴリズムを開発したとするものだ。筆者であるClaus Peter Schnorr氏はドイツ・フランクフルト大学の有名な暗号の専門家として知られていることからも大きな話題を呼んだようだ。RSA暗号技術はHTTPS、VPN、SSHなどにも使用され、現在のネットのセキュリティにおいて重要な役割を持つことから、仮に論文の内容が正しかった場合は大事になりかねない（未査読の論文、The Daily Swig、heise online）。
結論からいうとおそらくは誤報である可能性が高い。heise onlineの記事によれば、もともとアップロードされた論文がドイツ語の混ざった誤記などがあるものだった上、作者のSchnorr氏が3月3日に最終改訂版としてアップロードしたものも、Googleの暗号研究者であるSophieSchmieg氏などによって多くの数学的矛盾が指摘されている。記事によれば、Schnorr氏は比較的小さな数に対してのみ計算を実行した可能性があるという（SophieSchmieg氏のツイート）。
国内で話題のきっかけになった情報セキュリティの研究者のTsukasa #01氏の関連する新たなツイートでは、
【重要】RSA 破壊を主張する未査読論文ですが、現状再現成功の報告なし (失敗報告あり https://github.com/lducas/SchnorrGate)。また証明内の誤りを指摘する意見 (https://crypto.stackexchange.com/questions/88582/does-schnorrs-2021-factoring-method-show-that-the-rsa-cryptosystem-is-not-secur) もあり。どう少なく見積もっても、未査読論文を不適切なまでにセンセーショナルに扱ってしまいました。申し訳ありません。
としている。なお、同氏の話題のきっかけとなった関連ツイートも一応記載しておくとこちらになる（該当ツイート）。
誤報と間違いは違うのでは (スコア:1)
今回のは間違いだと思われ
Re: (スコア:0)
前半と後半で主語が変わってるんだよ。
本文後半にある
が「ほぼ誤報」と。
nagazouの日本語で文の一部がワープするのはよくあることだから
意味解析までエラー報告してたらキリが無いよ。
Re: (スコア:0)
それでも誤報にはならんし主語が変わったと表現するのも違うと思う
Re: (スコア:0)
本人が続報で訂正してるんだからそれは誤報だろ
暗号を「破壊」？ (スコア:0)
ついでに言うと「RSA cryptography ‘broken’」の「broken」を「破壊された」と訳すのもどうかと。こういうこなれない直訳調の表現はいかがなものか。ふつう「破られた」or「突破された」でしょ。
Re: (スコア:0)
暗号をさらに不可逆に破壊したのかもしれない
Re: (スコア:0)
ついでに言うと、元論文はアブストラクトで「 This destroys the RSA cryptosystem. 」って書いてます。
そのことを知らずにあーだこーだ言うのもどうかと。
Re: (スコア:0)
ふつうは「破られた」だけど、原著論文で「This destroys the RSA cryptosystem」（RSA暗号基盤の破壊）と言ってるので元ツイは「破壊」と言ってる。
The Daily Swigの見出し「RSA cryptography ‘broken’」は「破られた」と「破壊」のダブルミーニングなので「‘broken’」とアポストロフィーで強調してある。
本当に高速で解読できるなら (スコア:0)
発表せずに、悪用して最大限利益を上げるとおもう
Re:本当に高速で解読できるなら (スコア:1)
だから誤報ってことになったんですよ。ﾆﾔﾘ
Re: (スコア:0)
誤報ってことにさせられたのかも、Schnorrさんは、すでに…
Re: (スコア:0)
本当の発見を隠すためにわざと欠陥だらけのバージョンを公開して与太話だと思い込ませたとか
Re: (スコア:0)
法に触れずに稼ぐのはなかなか難しいのでは。
名誉とそれについてくる利益を手にしたほうが。
Re: (スコア:0)
名誉とそれについてくる利益を手にしたほうが。
今回の論文が正しかった場合、内容がドラスティックすぎて、名誉とか利益とか言ってる場合じゃなくなりそうな気もするが。
Re: (スコア:0)
妙な逆恨みの対象になって「タブーを晒したネット社会の悪魔」みたいな扱いされそう
Re: (スコア:0)
ビットコインの採掘でとくにおかしな動きがなかったことからも誤報なのは明らかだな
Re:本当に高速で解読できるなら (スコア:2, すばらしい洞察)
ビットコインに素因数分解問題は使われていない
Re: (スコア:0)
数学者には100万ドルの懸賞金を辞退 [srad.jp]するような変態もいるし
Re: (スコア:0)
と、簡単に言うけど、真面目な数学者には結構難しいと思うよ。何かしら最前線で悪さしてる連中の中でも質の高いのと渡りを付ける方法がぱっと出てくるならともかく。
発表すればどっかの大学教授のポストは固いので、なるべく好条件の所に収まった上、本業ではまとも仕事せずに給与泥棒に徹しつつ、本を書いたり講演したりで小遣いを稼いで定年までのんびり+年金ルートの方が安全確実。
Re: (スコア:0)
それだなぁ。
論文なんて一行も書かなくていいから動くコードで十分。
悪用はしないで欲しいけど。
P=NPの時にも同じこと思ったわ。
理論の前に具体的な問題解け。
まぁ「解読できる！」と宣言しないなら、参考になるかもしれないし論文は便利だろうけど(読める/読む気力のある人には)。
こういう時の為に懸賞問題を用意しておくと良いかもね。
最初の奴は確か力技で解かれてるけど。
Re:本当に高速で解読できるなら (スコア:1)
RSAの危機、と主張してる論文ならそうかも。
たまにちょいちょい、「理論上は速くなる(速くなるところを今の人類の技術では観察できない)」という、「画期的な高速化」があったりするので。
従来手法だと問題のサイズnに対して、n2に比例する時間かかる問題を、n1.9に比例にまで高速化した新手法。ただし、やることが複雑になった分、新手法の方が時間が掛かって、n=1万ぐらいで従来手法では1日で解けるけど、新手法だと地球上の全計算リソースを突っ込んでも1年以上かかります。n=1億ぐらいで逆転しますが、その時に掛かる時間はお察し、みたいなやつ。
そういうのだと、コードを書いてもしょうがなくて論文を書くしかない。
Re:本当に高速で解読できるなら (スコア:1)
AKS素数判定法がそのたぐいだったな。決定的多項式時間の素数判定法だけど多項式の次数が7次と高すぎて、実用的には未だにミラー-ラビンとかの確率的アルゴリズムが使われている。
あとリーマン予想はいまだに証明されていないけど実用的には拡張リーマン予想が正しいと仮定したアルゴリズムが使われているとか
Re: (スコア:0)
ここまで具体的ならともかく、P=NPの場合は「P≠NPと仮定すると矛盾するので背理法によりP=NPが証明されたが、具体的にNP完全問題を多項式時間で解く方法はさっぱりわからない」ということが普通にあり得るので
Re: (スコア:0)
高次でしかも最高次係数が凄まじくデカイ多項式時間だったりすると、具体的アルゴリズムがあったって役にたたんぞ。
Re: (スコア:0)
NSA「せやな」
まあ未査読論文だし (スコア:0)
一部修正で論文通りの結論が得られるかもしれない。
アイデア自体が根本的に間違ってるわけではない、とも言われてるし。
Re:まあ未査読論文だし (スコア:1)
OpenSSHも「RSAやめるやめる無効にする」とずっと言い続けていますし、RSAを捨てなくてはならない日が近づいているのは事実なんでしょう。
ただ、結局RSAじゃないとなんかうまくいかないってことが…
Re:まあ未査読論文だし (スコア:2)
Dropbearとか。
Re: (スコア:0)
ed25519にも対応してますよ: https://github.com/mkj/dropbear/pull/91 [github.com]
Re:まあ未査読論文だし (スコア:2, 参考になる)
それは "ssh-rsa" (RSA/SHA1) をデフォルトで無効にするっていう話で、RSA を無効にするっていう話ではないです。
代替として "rsa-sha2-256" (RSA/SHA256), "rsa-sha2-512" (RSA/SHA512) が挙げられています。
> It is now possible[1] to perform chosen-prefix attacks against the SHA-1 algorithm for less than USD$50K.
ってあるように、SHA-1 の強度の問題ですよ。
https://www.openssh.com/txt/release-8.5 [openssh.com]
Re: (スコア:0)
RSA暗号が捨てられたら「公開鍵暗号は素因数分解の困難性に依拠している」という説明が使えなくなるので困るな
# 実際もう使えないので良い子の皆は真似しちゃダメだよ
きぐか(←なぜか変換できない) (スコア:0)
もしかして: 危殆化(きたいか)
# ログアウトしているとタレコミへのリンクが表示されないバグのせいでACには意味がわからないかもしれない