看板 Gossiping作者 jackliao1990 (j)標題 [爆卦] 德國密碼學家宣稱自己摧毀了RSA加密法時間 Mon Apr 12 21:49:06 2021
https://eprint.iacr.org/2021/232.pdf
RSA加密法於1977年由Rivest、Shamir和Adleman提出,因為極大數的質因數分解困難度,此
方法成為世界上應用最廣泛的加密法。目前被破解的RSA密鑰最長紀錄是768個位元,因此
一般認為2048位元的密鑰非常安全可靠。
然而德國密碼學家Claus Peter Schnorr在自己新論文摘要中的最後一句宣稱:本文"摧毀"
了世界各大機構都在用的RSA加密法。此文一放上網就引起轟動。
如果這篇論文出自無名小卒,大家只會當成笑話。但是這篇作者Claus Peter Schnorr是知
名密碼學家,他提出的Schnorr簽章在加密貨幣如比特幣中被廣泛應用,他還是RSA數學卓越
獎和萊布尼茲獎得主。
一般認為,我們要等到使用秀爾演算法的量子電腦普及後,RSA加密法才會被破解。然而本
文宣稱透過晶格密碼學中的SVP法(尋找最接近向量),即使使用傳統電腦,我們也有機會
比二次篩選法和普通數域篩選法(已知最快的傳統因數分解演算法)更快完成分解。
這篇論文目前還未通過同行評審。GitHub上已經有人實作文中的算法,但是沒人成功。也
有人指出論文中的可能漏洞:作者宣稱如果使用新算法,"將整數的指數大小加倍"只會讓操
作數增加一個數量級。這表示:過去被認為屬於NP問題的操作,被本文證明屬於P,這樣豈不就證明P=NP了?(然而質因數分解從沒被證明是NP完全問題)
--
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.192.157.241 (臺灣)
※ 文章代碼(AID): #1WT4_MO4 (Gossiping)
※ 文章網址: https://www.ptt.cc/bbs/Gossiping/M.1618235350.A.604.html
※ 同主題文章:
[爆卦] 德國密碼學家宣稱自己摧毀了RSA加密法
04-12 21:49 jackliao1990.
推 P5566: 樓下都直接繞過去2F 04/12 21:49
推 SRNOB: 點點手指 從銀行轉一個兆6F 04/12 21:50
→ yulis: 我看幼幼都繞過去就好了啊11F 04/12 21:50
推 LeafLu: 看來還有一段路 沒事兒 還是yo叔厲害18F 04/12 21:52
噓 wario2014: 快點先破解比特幣啊,直接弄個三億個灌爆交易所22F 04/12 21:53
推 Induction: yoyodiy可以告這個人吧?我好幾年前就在用yo叔的程式繞過rar密碼了,記得要私信他才會給。24F 04/12 21:53
推 fp737: 住苗栗?30F 04/12 21:54
→ R10K: 太弱了吧,yo叔都直接繞過去32F 04/12 21:54
→ spfy: 現有的加密體系會垮一大半吧38F 04/12 21:56
→ jma306: 我以前不敢公布 因為怕被殺39F 04/12 21:56
推 ljm87: 擔心他的未來40F 04/12 21:56
推 cka: 嗯我想也是43F 04/12 21:57
推 GaussQQ: 一堆人出來說那論文有問題了 可以update 最新狀況嗎?45F 04/12 21:58
推 rodney92: 國中在學質因數分解時 就想過了 果然有人跟我一樣解法48F 04/12 22:00
推 kenndy: 我高中時就知道了49F 04/12 22:01
→ leamaSTC: 終於有其他人想到啦?那我就能省功夫了50F 04/12 22:01
→ saladim: yo叔表示: 還算可以啦 你終於邁出我十年前的第一步啦51F 04/12 22:02
→ goldman0204: YO叔幼稚園時候我看他寫這個以為他在開玩笑畫圖~哀!!53F 04/12 22:03
推 tmwolf: 我岳父的筆名比較調皮一點 不好意思55F 04/12 22:06
推 bestrace: 幹幹幹快賣比特幣 會被盜光光56F 04/12 22:06
推 Busufu: 這理論跟我想的不一樣 應該有漏洞57F 04/12 22:06
推 Tattoo: yoyodiy60F 04/12 22:08
推 abadjoke: yoyodiy原來跑到德國去了62F 04/12 22:10
推 suny921: 看不懂啦!民進黨惹火我了!63F 04/12 22:12
推 q456456w: 真破了 還不被管制起來 傻吊= =66F 04/12 22:18
噓 BBQ2591: 768被破解 改2048 再破解 改4096 再改 8192 根本沒鳥用68F 04/12 22:24
推 kite6128: 三八兄弟 不是我們一起研究的嗎 發表時也不揪一下的欸69F 04/12 22:24
推 diiky: 哇靠,連rsa都不能用了喔71F 04/12 22:25
推 richjf: 不是很多都改用ecc了?74F 04/12 22:26
推 mdkn35: ∂NP/∂N = P dN82F 04/12 22:52
推 ashylan: 嗯嗯 英雄所見略同84F 04/12 22:54
推 hare1039: RSA 總有一天會被解掉,老早就該換 ECC 惹86F 04/12 22:56
推 tom501062003: 能破但是要看運算時間吧 不過這個突破的話 世界上的加密會瘋了87F 04/12 22:57
→ aisitelu: 無聊 要量子電腦才可以 有量子電腦暴力解都行91F 04/12 22:59
推 wrt: 樓下的RSA密碼是123456被破解好久了
裸照已經在網路瘋傳但是沒人看92F 04/12 23:01
推 eDrifter: 唉 火星人告訴我的時候 我擔心影響太大沒說 終究被爆出94F 04/12 23:01
推 ll6a: 拜託先不說這種不可能破解,誰破了會發論文出來講,又不是95F 04/12 23:01
→ wrt: 改樓樓下97F 04/12 23:01
→ ll6a: 傻子0.0..98F 04/12 23:02
推 rndsulgye: 跟我上個月在思考的問題類似…不過我還不確定,為求謹慎先不發表101F 04/12 23:20
推 pr9558: yo叔:嫩! 我海放你10年104F 04/12 23:22
推 keyman2: 世界末日 天國近了105F 04/12 23:22
→ waloloo: 嗯嗯,我都去幼幼稚園繞過去107F 04/12 23:24
推 lpoijk: 他漏掉最重要的地方了吧.....108F 04/12 23:25
推 theta4719: 偷改成錯誤資訊 當然測不出來 最後論文確定了才會改成正確資訊 電影都這樣演109F 04/12 23:25
推 pot1234: 一般來說認為svp比因數分解難很多吧 話說哪邊說到作者覺得多項式時間做的完 我看起來他寫的bound是指數啊?111F 04/12 23:32
噓 hooll111: 又不是只有RSA加密可以用...114F 04/12 23:36
推 a4567850: 差不多 跟我想的一樣 只是論文比我早寫好而已117F 04/12 23:40
噓 ECZEMA: 上個月的事情 拿來批踢踢爆卦 都已經被鞭一回了說118F 04/12 23:40
推 tatlacz: 嗯嗯 我也是這樣覺得120F 04/12 23:45
推 grec: yo叔早就已經繞過去好久了123F 04/12 23:48
推 kkwwee: 更快推裝懂126F 04/12 23:51
推 e2ne0: 這不只虛擬貨幣有影響 你各位用https現在也等於裸體上網127F 04/12 23:52
推 Cireiat: 唉,都跟他說不要這麼快submit出去了……多等三天的二次驗證這麼難嗎?128F 04/12 23:54
推 p72910: rsa被破,aes也不用玩了,所有用數論的密碼學都完了130F 04/12 23:57
推 mojia: 沒有一個名詞看得懂的 雖然是中文字132F 04/13 00:00
噓 shortimex: 錯誤的證明,得出錯誤的結論,讓我想起1+2+3+4+... =-1/12134F 04/13 00:04
→ xo1100: 破解了會先裝死在社會上大開殺戒誰跟你公開138F 04/13 00:12
推 a0952864901: 加密當然有破解手法 但實務上經常是破完KEY早換了
但這新聞用"摧毀"感覺有點太吹了XD143F 04/13 00:17
推 slygun: 比特幣下去146F 04/13 00:18
推 tmuaircat: YO叔比武招親推動人類文明的錯覺150F 04/13 00:26
推 Irelia56: 某人:學這些數學有什麼用?152F 04/13 00:32
推 nenohelios: 如過後段屬實,那他最屌的是解了P=NP欸,這可能嗎153F 04/13 00:33
推 linja: 我竟然都看得懂156F 04/13 00:45
推 sorcxnegi: 消息根本不可能出來啦,不是被滅口就是被當國家級武器了157F 04/13 00:47
→ linzero: 可能是能縮減破解時間,但還是很長吧
比方原本解要1萬年,變成5千年,這樣嗎?159F 04/13 00:49
噓 aarzbrv: 質因數分解又沒被證明在NPC裡面。
第一頁註明work in progress 08.04.2021所以這篇是廣宣喔161F 04/13 00:51
推 ZooseWu: 括號裡面自己說不是npc 然後前面說p=np是什麼鬼164F 04/13 01:09
噓 aarzbrv: 這篇最近版本(4/9)宣稱結果比QS,NFS快很多,但都還沒看到166F 04/13 01:14
推 vasia: 他可能是在致敬幼幼167F 04/13 01:16
噓 aarzbrv: 與先前QS,NFS比較跑出來的實驗結果吧?168F 04/13 01:16
※ 編輯: jackliao1990 (123.192.157.241 臺灣), 04/13/2021 01:19:26
推 haeiou: 和我想的不太一樣,建議作者再回去想想171F 04/13 01:19
噓 aarzbrv: 還有自認為改良的演算法是根據還沒被證出成立的SA假設…回p72910:請問AES何時基於RSA?兩個系統差很多耶172F 04/13 01:20
噓 aarzbrv: 所以請教樓上發現哪些具體突破呢?175F 04/13 01:36
噓 vimer: 是喔 阿不就好棒棒176F 04/13 01:39
推 RLH: 看不懂179F 04/13 01:55
推 tn601374: yoyodiy快點拿專利吉他181F 04/13 02:12
推 daye87: 有生之年能看到p=np無憾182F 04/13 02:17
推 ymx3xc: yo叔能繞過RSA 4096183F 04/13 02:30
推 rnmrn: 我以為大家都知道185F 04/13 02:44
推 iewix: yo叔已經繞過多少年了186F 04/13 02:58
推 llrabel: 看到這種驚天大發現,直接賭他證錯就對了187F 04/13 03:06
推 HHH555JJJ: P=NP?Turin award 得主出現了190F 04/13 03:52
推 s12358972: 也就是說,這篇論文被實作出來還能順便證明P=Np191F 04/13 04:40
推 gamania0258: RSA可以被破解該拿圖靈 證明N=NP有更高的榮譽可以頒嗎192F 04/13 04:52
推 orze04: 真的證明P=NP要拿自己的名字當獎都可以了195F 04/13 05:36
推 rs6000: 等李永樂 拍片來解答...196F 04/13 05:44
推 xacid: 推 yo 叔197F 04/13 05:49
推 arue: 也來裝懂一下199F 04/13 06:06
→ ewjfd: 的確如此201F 04/13 06:17
→ sanpf: YO叔早就破解了202F 04/13 06:24
→ oxlittle: 看到第一頁就放棄了= =203F 04/13 06:36
推 REDF: 菜雞問問yo叔是什麼204F 04/13 06:38
推 srena: 嗯...長了關於yoyodiy的知識207F 04/13 07:19
推 aaron68032: 快破解比特幣讓他崩到沒價值 我想看賤畜礦工跳樓210F 04/13 07:42
推 shirleyEchi: 這點問題高中就提過只是沒有深究而已 德國人還真閒212F 04/13 08:03
推 asidy: 乾,看不懂,我要繞過去了213F 04/13 08:06
推 kukuyo: 跟我想的一樣214F 04/13 08:07
推 nevillechao: 應該是只要不是真NP問題,就只是P問題。而非P=NP216F 04/13 08:19
推 Silwez: 可是SVP本身也沒有polynomial time的演算法217F 04/13 08:51
--