顯示廣告
隱藏 ✕
回列表(←)
Disp BBS guest 註冊 登入(i) 線上人數: 438
首頁(home) 上頁(↑) 下頁(↓) 末頁(end)
※ 本文為 MindOcean 轉寄自 ptt.cc 更新時間: 2021-04-13 09:02:24
看板 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
※ 同主題文章:
● 04-12 21:49 jackliao1990. ■ [爆卦] 德國密碼學家宣稱自己摧毀了RSA加密法
　 04-13 18:55 c910335. ■ Re: [爆卦] 德國密碼學家宣稱自己摧毀了RSA加密法
推 goldman0204: 快推~不然人家以為我看不董!!1F 04/12 21:49
推 P5566: 樓下都直接繞過去2F 04/12 21:49
推 darkbrigher: 繞過去3F 04/12 21:50
噓 algebraic: 跟我昨天睡覺時 神跟我說得差不多4F 04/12 21:50
→ birdy590: 數學上其實不太可能~5F 04/12 21:50
推 SRNOB: 點點手指 從銀行轉一個兆6F 04/12 21:50
推 play714: 我也這樣想7F 04/12 21:50
噓 WolfTeacher: 恩恩 跟我想的一樣8F 04/12 21:50
推 qk3380888: 嗯嗯 對9F 04/12 21:50
推 FiveSix911: 看不懂 先推 裝一下10F 04/12 21:50
→ yulis: 我看幼幼都繞過去就好了啊11F 04/12 21:50
推 calculatortw: Yo叔直接繞過12F 04/12 21:50
推 diabolica: 繞13F 04/12 21:50
推 wonder007: 哇 證明NP= P 惹www14F 04/12 21:51
推 ECZEMA: 怕~15F 04/12 21:51
推 Neisseria: 嫩，yo 叔輕鬆繞16F 04/12 21:51
推 xiaohan: 嗯，我也是這樣想17F 04/12 21:51
推 LeafLu: 看來還有一段路 沒事兒 還是yo叔厲害18F 04/12 21:52
推 gg889g8: THE繞19F 04/12 21:52
推 andy199113: 死定了  他會被暗殺20F 04/12 21:52
推 mathrew: 跟我想的一樣21F 04/12 21:52
噓 wario2014: 快點先破解比特幣啊，直接弄個三億個灌爆交易所22F 04/12 21:53
推 goldman0204: 原本我也是這樣想 不過礙於要上班~23F 04/12 21:53
推 Induction: yoyodiy可以告這個人吧？我好幾年前就在用yo叔的程式24F 04/12 21:53
→ Induction: 繞過rar密碼了，記得要私信他才會給。
推 ethan0419: 果然是這樣26F 04/12 21:53
推 Innofance: RSA真被摧毀銀行還要玩嗎= =27F 04/12 21:54
→ ma4wanderer: 都過超過一個月了  鴿子飛到了28F 04/12 21:54
推 shadowdio: 所以會怎樣29F 04/12 21:54
推 fp737: 住苗栗?30F 04/12 21:54
推 takeda3234:  繞過去~~~31F 04/12 21:54
→ R10K: 太弱了吧，yo叔都直接繞過去32F 04/12 21:54
→ violegrace: yo叔早就繞過去了33F 04/12 21:54
推 rock0807: 這個遊戲有必勝法34F 04/12 21:54
推 asiaking5566: 塊陶阿35F 04/12 21:55
→ darkbrigher: 論文都發出來了 暗殺也沒用了36F 04/12 21:55
推 a94037501: 我早就想過ㄌ37F 04/12 21:55
→ spfy: 現有的加密體系會垮一大半吧38F 04/12 21:56
→ jma306:   我以前不敢公布  因為怕被殺39F 04/12 21:56
推 ljm87: 擔心他的未來40F 04/12 21:56
推 yahe0526: 繞過去就好啦41F 04/12 21:56
推 Vassili242: 跟我想的一樣，只是我懶得打成paper42F 04/12 21:56
推 cka: 嗯我想也是43F 04/12 21:57
→ lianpig5566: 之前做專題就有發現了= =44F 04/12 21:58
推 GaussQQ: 一堆人出來說那論文有問題了 可以update 最新狀況嗎？45F 04/12 21:58
推 jgj12321: 質數的規律就交給你了46F 04/12 21:58
推 Daedolon: p=0或n=147F 04/12 22:00
推 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
推 s9321312: 嗯 跟我的解法差不多52F 04/12 22:03
→ goldman0204: YO叔幼稚園時候我看他寫這個以為他在開玩笑畫圖~哀!!53F 04/12 22:03
推 butten986: 有崩盤啦！54F 04/12 22:05
推 tmwolf: 我岳父的筆名比較調皮一點 不好意思55F 04/12 22:06
推 bestrace: 幹幹幹快賣比特幣 會被盜光光56F 04/12 22:06
推 Busufu: 這理論跟我想的不一樣 應該有漏洞57F 04/12 22:06
推 WeiMinChen: 真。密碼學家目前歸隱苗栗深林 這什麼咖58F 04/12 22:06
推 devilkool: 證明P=NP....59F 04/12 22:07
推 Tattoo: yoyodiy60F 04/12 22:08
推 poseiden: 跟我想的一樣61F 04/12 22:09
推 abadjoke: yoyodiy原來跑到德國去了62F 04/12 22:10
推 suny921: 看不懂啦！民進黨惹火我了！63F 04/12 22:12
推 Justin890820: P=NP64F 04/12 22:12
推 honey4617912: 這念資訊的都看得懂吧==很科普65F 04/12 22:14
推 q456456w: 真破了 還不被管制起來 傻吊= =66F 04/12 22:18
推 PompelmousJ: 確實 跟我所見略同67F 04/12 22:22
噓 BBQ2591: 768被破解 改2048 再破解 改4096 再改 8192 根本沒鳥用68F 04/12 22:24
推 kite6128: 三八兄弟 不是我們一起研究的嗎 發表時也不揪一下的欸69F 04/12 22:24
推 linlaosure: 好欸70F 04/12 22:25
推 diiky: 哇靠，連rsa都不能用了喔71F 04/12 22:25
噓 hanklee66: 但是沒人成功72F 04/12 22:25
推 abd86731: 嗯嗯 我也是這麼想的73F 04/12 22:25
推 richjf: 不是很多都改用ecc了?74F 04/12 22:26
推 hannnnnn: 先推75F 04/12 22:27
推 dnkofe: 快推76F 04/12 22:27
推 amethystboy: yo叔笑而不語77F 04/12 22:31
推 KhePri: 太屌了吧78F 04/12 22:39
推 herculus6502: 差不多是這樣79F 04/12 22:39
推 shadowdio: 永樂老師:最近有小朋友問我...80F 04/12 22:40
推 lyt5566: yo叔：嫩81F 04/12 22:47
推 mdkn35: ∂NP/∂N = P dN82F 04/12 22:52
→ meteor260: P=NP人類直接進化83F 04/12 22:53
推 ashylan: 嗯嗯 英雄所見略同84F 04/12 22:54
推 smb1013: 我都不設密碼85F 04/12 22:54
推 hare1039: RSA 總有一天會被解掉，老早就該換 ECC 惹86F 04/12 22:56
推 tom501062003: 能破但是要看運算時間吧 不過這個突破的話 世界上的87F 04/12 22:57
→ tom501062003: 加密會瘋了
推 heavenlyken: p=np 人族直接躍遷變神族89F 04/12 22:59
推 lolikung: 破了整個世界會瘋掉啊90F 04/12 22:59
→ aisitelu: 無聊 要量子電腦才可以 有量子電腦暴力解都行91F 04/12 22:59
推 wrt: 樓下的RSA密碼是123456被破解好久了92F 04/12 23:01
→ wrt: 裸照已經在網路瘋傳但是沒人看
推 eDrifter: 唉 火星人告訴我的時候 我擔心影響太大沒說 終究被爆出94F 04/12 23:01
推 ll6a: 拜託先不說這種不可能破解，誰破了會發論文出來講，又不是95F 04/12 23:01
推 poison5566: Np 就可以發一篇超猛的了吧96F 04/12 23:01
→ wrt: 改樓樓下97F 04/12 23:01
→ ll6a: 傻子0.0..98F 04/12 23:02
推 kei1823: 早說了就F=MA99F 04/12 23:13
推 j1o2s3e4p5h6: 比特幣要崩了嗎？100F 04/12 23:17
推 rndsulgye: 跟我上個月在思考的問題類似…不過我還不確定，為求謹101F 04/12 23:20
→ rndsulgye: 慎先不發表
→ RicciCurvatu: 這種大定理都是大咖詐胡好幾次都是正常的103F 04/12 23:21
推 pr9558: yo叔:嫩! 我海放你10年104F 04/12 23:22
推 keyman2: 世界末日 天國近了105F 04/12 23:22
推 lee988325: no more secret106F 04/12 23:23
→ waloloo: 嗯嗯，我都去幼幼稚園繞過去107F 04/12 23:24
推 lpoijk: 他漏掉最重要的地方了吧.....108F 04/12 23:25
推 theta4719: 偷改成錯誤資訊 當然測不出來 最後論文確定了才會改成109F 04/12 23:25
→ theta4719: 正確資訊 電影都這樣演
推 pot1234: 一般來說認為svp比因數分解難很多吧 話說哪邊說到作者覺111F 04/12 23:32
→ pot1234: 得多項式時間做的完 我看起來他寫的bound是指數啊？
推 overskyend: 沒錯，我老早就這麼認為的113F 04/12 23:35
噓 hooll111: 又不是只有RSA加密可以用...114F 04/12 23:36
噓 ph4586: 預覽圖勒？115F 04/12 23:38
→ ph4586: http://i.imgur.com/TxZsXJg.jpg
[圖]
推 a4567850: 差不多  跟我想的一樣  只是論文比我早寫好而已117F 04/12 23:40
噓 ECZEMA: 上個月的事情 拿來批踢踢爆卦 都已經被鞭一回了說118F 04/12 23:40
推 sses60802: 恩恩 跟我想的一樣119F 04/12 23:43
推 tatlacz: 嗯嗯 我也是這樣覺得120F 04/12 23:45
推 ee8iqp7x: yo叔屌打121F 04/12 23:48
推 willion003: 所P=NP確定了嗎？122F 04/12 23:48
推 grec: yo叔早就已經繞過去好久了123F 04/12 23:48
噓 unrealstars: 繞過就好解個屁124F 04/12 23:48
推 AdamZheng: 說的很棒125F 04/12 23:49
推 kkwwee: 更快推裝懂126F 04/12 23:51
推 e2ne0: 這不只虛擬貨幣有影響 你各位用https現在也等於裸體上網127F 04/12 23:52
推 Cireiat: 唉，都跟他說不要這麼快submit出去了……多等三天的二次128F 04/12 23:54
→ Cireiat: 驗證這麼難嗎？
推 p72910: rsa被破，aes也不用玩了，所有用數論的密碼學都完了130F 04/12 23:57
推 pilitiger: 天堂2m打密碼的時候我就發現了131F 04/12 23:58
推 mojia: 沒有一個名詞看得懂的 雖然是中文字132F 04/13 00:00
推 youshallnotp: Yo叔10幾年前就破解了133F 04/13 00:02
噓 shortimex: 錯誤的證明，得出錯誤的結論，讓我想起1+2+3+4+... =134F 04/13 00:04
→ shortimex: -1/12
推 xxxrecoil: 傻子才破解吧，我們都繞過去136F 04/13 00:04
推 bigsmile5: @yo叔137F 04/13 00:07
→ xo1100: 破解了會先裝死在社會上大開殺戒誰跟你公開138F 04/13 00:12
推 ter2788: 問題是要多久？139F 04/13 00:13
推 pchunters: 蛤，這些不是小學就知道了？140F 04/13 00:14
推 ds361007: 等高手解答141F 04/13 00:14
推 h3882249: 完了 世界要毀滅了142F 04/13 00:14
推 a0952864901: 加密當然有破解手法 但實務上經常是破完KEY早換了143F 04/13 00:17
→ a0952864901: 但這新聞用"摧毀"感覺有點太吹了XD
推 cygnusx123: YO叔笑而不語145F 04/13 00:18
推 slygun: 比特幣下去146F 04/13 00:18
推 FinallyPeace: NP=P？太神了吧147F 04/13 00:18
推 xiao2chen: 跟我想的一樣148F 04/13 00:21
推 Jokering5566: 跟我猜得差不多149F 04/13 00:21
推 tmuaircat: YO叔比武招親推動人類文明的錯覺150F 04/13 00:26
推 chiahong1227: 真的有可能嗎？151F 04/13 00:26
推 Irelia56: 某人：學這些數學有什麼用？152F 04/13 00:32
推 nenohelios: 如過後段屬實，那他最屌的是解了P=NP欸，這可能嗎153F 04/13 00:33
推 LiaMeow: 嗯嗯 我就說吧154F 04/13 00:35
推 marinsky: 跟我想的一樣155F 04/13 00:39
推 linja: 我竟然都看得懂156F 04/13 00:45
推 sorcxnegi: 消息根本不可能出來啦，不是被滅口就是被當國家級武器157F 04/13 00:47
→ sorcxnegi: 了
→ linzero: 可能是能縮減破解時間，但還是很長吧159F 04/13 00:49
→ linzero: 比方原本解要1萬年，變成5千年，這樣嗎？
噓 aarzbrv: 質因數分解又沒被證明在NPC裡面。161F 04/13 00:51
噓 aarzbrv: 第一頁註明work in progress 08.04.2021所以這篇是廣宣喔
→ cossetannie: 終於有人證明P=NP了163F 04/13 01:09
推 ZooseWu: 括號裡面自己說不是npc 然後前面說p=np是什麼鬼164F 04/13 01:09
推 yillusionwei: 就繞過去理論嘛165F 04/13 01:11
噓 aarzbrv: 這篇最近版本(4/9)宣稱結果比QS,NFS快很多，但都還沒看到166F 04/13 01:14
推 vasia: 他可能是在致敬幼幼167F 04/13 01:16
噓 aarzbrv: 與先前QS,NFS比較跑出來的實驗結果吧？168F 04/13 01:16
推 Thanksbro: 還要破解 我都直接繞過去==169F 04/13 01:16
推 hoo911ver25: 我當年學測寫完無聊解出來九成剛好打鐘被收走170F 04/13 01:17
※ 編輯: jackliao1990 (123.192.157.241 臺灣), 04/13/2021 01:19:26
推 haeiou: 和我想的不太一樣，建議作者再回去想想171F 04/13 01:19
噓 aarzbrv: 還有自認為改良的演算法是根據還沒被證出成立的SA假設…172F 04/13 01:20
噓 aarzbrv: 回p72910：請問AES何時基於RSA？兩個系統差很多耶
推 a000522001: 快推 不然以為我看不懂174F 04/13 01:30
噓 aarzbrv: 所以請教樓上發現哪些具體突破呢？175F 04/13 01:36
噓 vimer: 是喔 阿不就好棒棒176F 04/13 01:39
推 danny409859: 推，優質好文177F 04/13 01:49
推 joemi78: 好像離散學過欸178F 04/13 01:54
推 RLH: 看不懂179F 04/13 01:55
推 rickyshiter: 我早就摧毀了180F 04/13 02:00
推 tn601374: yoyodiy快點拿專利吉他181F 04/13 02:12
推 daye87: 有生之年能看到p=np無憾182F 04/13 02:17
推 ymx3xc: yo叔能繞過RSA 4096183F 04/13 02:30
推 EvilJustice: 2048不夠再加阿，4096，8192？184F 04/13 02:39
推 rnmrn: 我以為大家都知道185F 04/13 02:44
推 iewix: yo叔已經繞過多少年了186F 04/13 02:58
推 llrabel: 看到這種驚天大發現，直接賭他證錯就對了187F 04/13 03:06
推 whatzup1124: NP hArd188F 04/13 03:12
推 jasonchangki: 有人照論文實作但沒成功很大機率出事了吧189F 04/13 03:23
推 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
→ gamania0258: 嗎
推 s12358972: 諾貝爾吧194F 04/13 04:56
推 orze04: 真的證明P=NP要拿自己的名字當獎都可以了195F 04/13 05:36
推 rs6000: 等李永樂 拍片來解答...196F 04/13 05:44
推 xacid: 推 yo 叔197F 04/13 05:49
推 TenGaKu1809: 他如果證明NP=P 他會創另一個諾貝爾獎XD198F 04/13 06:06
推 arue: 也來裝懂一下199F 04/13 06:06
推 DarkHolbach: 德國yo叔200F 04/13 06:10
→ 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
推 chichiliou77: 跟我想的一模一樣205F 04/13 07:12
推 f416720001: 看到離散，我頭髮又掉了兩根206F 04/13 07:19
推 srena: 嗯...長了關於yoyodiy的知識207F 04/13 07:19
推 willy0206: p=np 我到底看了什麼208F 04/13 07:28
→ j07242054: 繞過去就好了啦 yo叔有教209F 04/13 07:35
推 aaron68032: 快破解比特幣讓他崩到沒價值 我想看賤畜礦工跳樓210F 04/13 07:42
推 loveadu: 這我早就知道了211F 04/13 07:48
推 shirleyEchi: 這點問題高中就提過只是沒有深究而已 德國人還真閒212F 04/13 08:03
推 asidy: 乾，看不懂，我要繞過去了213F 04/13 08:06
推 kukuyo: 跟我想的一樣214F 04/13 08:07
推 seio2008: 跟我想的差不多215F 04/13 08:08
推 nevillechao: 應該是只要不是真NP問題，就只是P問題。而非P=NP216F 04/13 08:19
推 Silwez: 可是SVP本身也沒有polynomial time的演算法217F 04/13 08:51

--
※ 看板: Gossiping　文章推薦值: 0 目前人氣: 0 累積人氣: 1882　
分享網址: 複製 已複製
1樓 時間: 2021-04-13 10:40:27 (台灣) 
→
mulder1031
　 04-13 10:40 TW 
真的可以破解，你會詔告天下嗎？正常人都會先海削一票吧？
r)回覆 e)編輯 d)刪除 M)收藏 ^x)轉錄 同主題: =)首篇 [)上篇 ])下篇