※ 本文為 MindOcean 轉寄自 ptt.cc 更新時間: 2021-04-13 09:02:24
看板 Gossiping
作者 標題 [爆卦] 德國密碼學家宣稱自己摧毀了RSA加密法
時間 Mon Apr 12 21:49:06 2021
https://eprint.iacr.org/2021/232.pdf
RSA加密法於1977年由Rivest、Shamir和Adleman提出,因為極大數的質因數分解困難度,此
方法成為世界上應用最廣泛的加密法。目前被破解的RSA密鑰最長紀錄是768個位元,因此
一般認為2048位元的密鑰非常安全可靠。
方法成為世界上應用最廣泛的加密法。目前被破解的RSA密鑰最長紀錄是768個位元,因此
一般認為2048位元的密鑰非常安全可靠。
然而德國密碼學家Claus Peter Schnorr在自己新論文摘要中的最後一句宣稱:本文"摧毀"
了世界各大機構都在用的RSA加密法。此文一放上網就引起轟動。
如果這篇論文出自無名小卒,大家只會當成笑話。但是這篇作者Claus Peter Schnorr是知
名密碼學家,他提出的Schnorr簽章在加密貨幣如比特幣中被廣泛應用,他還是RSA數學卓越
獎和萊布尼茲獎得主。
名密碼學家,他提出的Schnorr簽章在加密貨幣如比特幣中被廣泛應用,他還是RSA數學卓越
獎和萊布尼茲獎得主。
一般認為,我們要等到使用秀爾演算法的量子電腦普及後,RSA加密法才會被破解。然而本
文宣稱透過晶格密碼學中的SVP法(尋找最接近向量)，即使使用傳統電腦，我們也有機會
比二次篩選法和普通數域篩選法(已知最快的傳統因數分解演算法)更快完成分解。
文宣稱透過晶格密碼學中的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
推 : 快推~不然人家以為我看不董!!1F 04/12 21:49
推 : 樓下都直接繞過去2F 04/12 21:49
推 : 繞過去3F 04/12 21:50
噓 : 跟我昨天睡覺時 神跟我說得差不多4F 04/12 21:50
→ : 數學上其實不太可能~5F 04/12 21:50
推 : 點點手指 從銀行轉一個兆6F 04/12 21:50
推 : 我也這樣想7F 04/12 21:50
噓 : 恩恩 跟我想的一樣8F 04/12 21:50
推 : 嗯嗯 對9F 04/12 21:50
推 : 看不懂 先推 裝一下10F 04/12 21:50
→ : 我看幼幼都繞過去就好了啊11F 04/12 21:50
推 : Yo叔直接繞過12F 04/12 21:50
推 : 繞13F 04/12 21:50
推 : 哇 證明NP= P 惹www14F 04/12 21:51
推 : 怕~15F 04/12 21:51
推 : 嫩，yo 叔輕鬆繞16F 04/12 21:51
推 : 嗯，我也是這樣想17F 04/12 21:51
推 : 看來還有一段路 沒事兒 還是yo叔厲害18F 04/12 21:52
推 : THE繞19F 04/12 21:52
→ andy199113 …
推 : 跟我想的一樣21F 04/12 21:52
噓 : 快點先破解比特幣啊，直接弄個三億個灌爆交易所22F 04/12 21:53
推 : 原本我也是這樣想 不過礙於要上班~23F 04/12 21:53
推 : yoyodiy可以告這個人吧？我好幾年前就在用yo叔的程式24F 04/12 21:53
→ : 繞過rar密碼了，記得要私信他才會給。
→ : 繞過rar密碼了，記得要私信他才會給。
推 : 果然是這樣26F 04/12 21:53
推 : RSA真被摧毀銀行還要玩嗎= =27F 04/12 21:54
→ : 都過超過一個月了 鴿子飛到了28F 04/12 21:54
推 : 所以會怎樣29F 04/12 21:54
推 : 住苗栗?30F 04/12 21:54
推 : 繞過去~~~31F 04/12 21:54
→ : 太弱了吧，yo叔都直接繞過去32F 04/12 21:54
→ : yo叔早就繞過去了33F 04/12 21:54
推 : 這個遊戲有必勝法34F 04/12 21:54
推 : 塊陶阿35F 04/12 21:55
→ : 論文都發出來了 暗殺也沒用了36F 04/12 21:55
推 : 我早就想過ㄌ37F 04/12 21:55
→ : 現有的加密體系會垮一大半吧38F 04/12 21:56
→ : 我以前不敢公布 因為怕被殺39F 04/12 21:56
推 : 擔心他的未來40F 04/12 21:56
推 : 繞過去就好啦41F 04/12 21:56
推 : 跟我想的一樣，只是我懶得打成paper42F 04/12 21:56
推 : 嗯我想也是43F 04/12 21:57
→ : 之前做專題就有發現了= =44F 04/12 21:58
推 : 一堆人出來說那論文有問題了 可以update 最新狀況嗎？45F 04/12 21:58
推 : 質數的規律就交給你了46F 04/12 21:58
推 : p=0或n=147F 04/12 22:00
推 : 國中在學質因數分解時 就想過了 果然有人跟我一樣解法48F 04/12 22:00
推 : 我高中時就知道了49F 04/12 22:01
→ : 終於有其他人想到啦？那我就能省功夫了50F 04/12 22:01
→ : yo叔表示: 還算可以啦 你終於邁出我十年前的第一步啦51F 04/12 22:02
推 : 嗯 跟我的解法差不多52F 04/12 22:03
→ : YO叔幼稚園時候我看他寫這個以為他在開玩笑畫圖~哀!!53F 04/12 22:03
推 : 有崩盤啦！54F 04/12 22:05
推 : 我岳父的筆名比較調皮一點 不好意思55F 04/12 22:06
推 : 幹幹幹快賣比特幣 會被盜光光56F 04/12 22:06
推 : 這理論跟我想的不一樣 應該有漏洞57F 04/12 22:06
推 : 真。密碼學家目前歸隱苗栗深林 這什麼咖58F 04/12 22:06
推 : 證明P=NP....59F 04/12 22:07
推 : yoyodiy60F 04/12 22:08
推 : 跟我想的一樣61F 04/12 22:09
推 : yoyodiy原來跑到德國去了62F 04/12 22:10
推 : 看不懂啦！民進黨惹火我了！63F 04/12 22:12
推 : P=NP64F 04/12 22:12
推 : 這念資訊的都看得懂吧==很科普65F 04/12 22:14
推 : 真破了 還不被管制起來 傻吊= =66F 04/12 22:18
推 : 確實 跟我所見略同67F 04/12 22:22
噓 : 768被破解 改2048 再破解 改4096 再改 8192 根本沒鳥用68F 04/12 22:24
推 : 三八兄弟 不是我們一起研究的嗎 發表時也不揪一下的欸69F 04/12 22:24
推 : 好欸70F 04/12 22:25
推 : 哇靠，連rsa都不能用了喔71F 04/12 22:25
噓 : 但是沒人成功72F 04/12 22:25
推 : 嗯嗯 我也是這麼想的73F 04/12 22:25
推 : 不是很多都改用ecc了?74F 04/12 22:26
推 : 先推75F 04/12 22:27
推 : 快推76F 04/12 22:27
推 : yo叔笑而不語77F 04/12 22:31
推 : 太屌了吧78F 04/12 22:39
推 : 差不多是這樣79F 04/12 22:39
推 : 永樂老師:最近有小朋友問我...80F 04/12 22:40
推 : yo叔：嫩81F 04/12 22:47
推 : ∂NP/∂N = P dN82F 04/12 22:52
→ : P=NP人類直接進化83F 04/12 22:53
推 : 嗯嗯 英雄所見略同84F 04/12 22:54
推 : 我都不設密碼85F 04/12 22:54
推 : RSA 總有一天會被解掉，老早就該換 ECC 惹86F 04/12 22:56
推 : 能破但是要看運算時間吧 不過這個突破的話 世界上的87F 04/12 22:57
→ : 加密會瘋了
→ : 加密會瘋了
推 : p=np 人族直接躍遷變神族89F 04/12 22:59
推 : 破了整個世界會瘋掉啊90F 04/12 22:59
→ : 無聊 要量子電腦才可以 有量子電腦暴力解都行91F 04/12 22:59
推 : 樓下的RSA密碼是123456被破解好久了92F 04/12 23:01
→ : 裸照已經在網路瘋傳但是沒人看
→ : 裸照已經在網路瘋傳但是沒人看
推 : 唉 火星人告訴我的時候 我擔心影響太大沒說 終究被爆出94F 04/12 23:01
推 : 拜託先不說這種不可能破解，誰破了會發論文出來講，又不是95F 04/12 23:01
推 : Np 就可以發一篇超猛的了吧96F 04/12 23:01
→ : 改樓樓下97F 04/12 23:01
→ : 傻子0.0..98F 04/12 23:02
推 : 早說了就F=MA99F 04/12 23:13
推 : 比特幣要崩了嗎？100F 04/12 23:17
推 : 跟我上個月在思考的問題類似…不過我還不確定，為求謹101F 04/12 23:20
→ : 慎先不發表
→ : 慎先不發表
→ : 這種大定理都是大咖詐胡好幾次都是正常的103F 04/12 23:21
推 : yo叔:嫩! 我海放你10年104F 04/12 23:22
推 : 世界末日 天國近了105F 04/12 23:22
推 : no more secret106F 04/12 23:23
→ : 嗯嗯，我都去幼幼稚園繞過去107F 04/12 23:24
推 : 他漏掉最重要的地方了吧.....108F 04/12 23:25
推 : 偷改成錯誤資訊 當然測不出來 最後論文確定了才會改成109F 04/12 23:25
→ : 正確資訊 電影都這樣演
→ : 正確資訊 電影都這樣演
推 : 一般來說認為svp比因數分解難很多吧 話說哪邊說到作者覺111F 04/12 23:32
→ : 得多項式時間做的完 我看起來他寫的bound是指數啊？
→ : 得多項式時間做的完 我看起來他寫的bound是指數啊？
推 : 沒錯，我老早就這麼認為的113F 04/12 23:35
噓 : 又不是只有RSA加密可以用...114F 04/12 23:36
![[圖]](https://i4.disp.cc/imgur/TxZsXJgh.jpg)
推 : 差不多 跟我想的一樣 只是論文比我早寫好而已117F 04/12 23:40
噓 : 上個月的事情 拿來批踢踢爆卦 都已經被鞭一回了說118F 04/12 23:40
推 : 恩恩 跟我想的一樣119F 04/12 23:43
推 : 嗯嗯 我也是這樣覺得120F 04/12 23:45
推 : yo叔屌打121F 04/12 23:48
推 : 所P=NP確定了嗎？122F 04/12 23:48
推 : yo叔早就已經繞過去好久了123F 04/12 23:48
噓 : 繞過就好解個屁124F 04/12 23:48
推 : 說的很棒125F 04/12 23:49
推 : 更快推裝懂126F 04/12 23:51
推 : 這不只虛擬貨幣有影響 你各位用https現在也等於裸體上網127F 04/12 23:52
推 : 唉，都跟他說不要這麼快submit出去了……多等三天的二次128F 04/12 23:54
→ : 驗證這麼難嗎？
→ : 驗證這麼難嗎？
推 : rsa被破，aes也不用玩了，所有用數論的密碼學都完了130F 04/12 23:57
推 : 天堂2m打密碼的時候我就發現了131F 04/12 23:58
推 : 沒有一個名詞看得懂的 雖然是中文字132F 04/13 00:00
推 : Yo叔10幾年前就破解了133F 04/13 00:02
噓 : 錯誤的證明，得出錯誤的結論，讓我想起1+2+3+4+... =134F 04/13 00:04
→ : -1/12
→ : -1/12
推 : 傻子才破解吧，我們都繞過去136F 04/13 00:04
推 : @yo叔137F 04/13 00:07
→ : 破解了會先裝死在社會上大開殺戒誰跟你公開138F 04/13 00:12
推 : 問題是要多久？139F 04/13 00:13
推 : 蛤，這些不是小學就知道了？140F 04/13 00:14
推 : 等高手解答141F 04/13 00:14
推 : 完了 世界要毀滅了142F 04/13 00:14
推 : 加密當然有破解手法 但實務上經常是破完KEY早換了143F 04/13 00:17
→ : 但這新聞用"摧毀"感覺有點太吹了XD
→ : 但這新聞用"摧毀"感覺有點太吹了XD
推 : YO叔笑而不語145F 04/13 00:18
推 : 比特幣下去146F 04/13 00:18
推 : NP=P？太神了吧147F 04/13 00:18
推 : 跟我想的一樣148F 04/13 00:21
推 : 跟我猜得差不多149F 04/13 00:21
推 : YO叔比武招親推動人類文明的錯覺150F 04/13 00:26
推 : 真的有可能嗎？151F 04/13 00:26
推 : 某人：學這些數學有什麼用？152F 04/13 00:32
推 : 如過後段屬實，那他最屌的是解了P=NP欸，這可能嗎153F 04/13 00:33
推 : 嗯嗯 我就說吧154F 04/13 00:35
推 : 跟我想的一樣155F 04/13 00:39
推 : 我竟然都看得懂156F 04/13 00:45
推 : 消息根本不可能出來啦，不是被滅口就是被當國家級武器157F 04/13 00:47
→ : 了
→ : 了
→ : 可能是能縮減破解時間，但還是很長吧159F 04/13 00:49
→ : 比方原本解要1萬年，變成5千年，這樣嗎？
→ : 比方原本解要1萬年，變成5千年，這樣嗎？
噓 : 質因數分解又沒被證明在NPC裡面。161F 04/13 00:51
噓 : 第一頁註明work in progress 08.04.2021所以這篇是廣宣喔
噓 : 第一頁註明work in progress 08.04.2021所以這篇是廣宣喔
→ : 終於有人證明P=NP了163F 04/13 01:09
推 : 括號裡面自己說不是npc 然後前面說p=np是什麼鬼164F 04/13 01:09
推 : 就繞過去理論嘛165F 04/13 01:11
噓 : 這篇最近版本(4/9)宣稱結果比QS,NFS快很多，但都還沒看到166F 04/13 01:14
推 : 他可能是在致敬幼幼167F 04/13 01:16
噓 : 與先前QS,NFS比較跑出來的實驗結果吧？168F 04/13 01:16
推 : 還要破解 我都直接繞過去==169F 04/13 01:16
推 : 我當年學測寫完無聊解出來九成剛好打鐘被收走170F 04/13 01:17
※ 編輯: jackliao1990 (123.192.157.241 臺灣), 04/13/2021 01:19:26推 : 和我想的不太一樣，建議作者再回去想想171F 04/13 01:19
噓 : 還有自認為改良的演算法是根據還沒被證出成立的SA假設…172F 04/13 01:20
噓 : 回p72910：請問AES何時基於RSA？兩個系統差很多耶
噓 : 回p72910：請問AES何時基於RSA？兩個系統差很多耶
推 : 快推 不然以為我看不懂174F 04/13 01:30
噓 : 所以請教樓上發現哪些具體突破呢？175F 04/13 01:36
噓 : 是喔 阿不就好棒棒176F 04/13 01:39
推 : 推，優質好文177F 04/13 01:49
推 : 好像離散學過欸178F 04/13 01:54
推 : 看不懂179F 04/13 01:55
推 : 我早就摧毀了180F 04/13 02:00
推 : yoyodiy快點拿專利吉他181F 04/13 02:12
推 : 有生之年能看到p=np無憾182F 04/13 02:17
推 : yo叔能繞過RSA 4096183F 04/13 02:30
推 : 2048不夠再加阿，4096，8192？184F 04/13 02:39
推 : 我以為大家都知道185F 04/13 02:44
推 : yo叔已經繞過多少年了186F 04/13 02:58
推 : 看到這種驚天大發現，直接賭他證錯就對了187F 04/13 03:06
推 : NP hArd188F 04/13 03:12
推 : 有人照論文實作但沒成功很大機率出事了吧189F 04/13 03:23
推 : P=NP？Turin award 得主出現了190F 04/13 03:52
推 : 也就是說,這篇論文被實作出來還能順便證明P=Np191F 04/13 04:40
推 : RSA可以被破解該拿圖靈 證明N=NP有更高的榮譽可以頒192F 04/13 04:52
→ : 嗎
→ : 嗎
推 : 諾貝爾吧194F 04/13 04:56
推 : 真的證明P=NP要拿自己的名字當獎都可以了195F 04/13 05:36
推 : 等李永樂 拍片來解答...196F 04/13 05:44
推 : 推 yo 叔197F 04/13 05:49
推 : 他如果證明NP=P 他會創另一個諾貝爾獎XD198F 04/13 06:06
推 : 也來裝懂一下199F 04/13 06:06
推 : 德國yo叔200F 04/13 06:10
→ : 的確如此201F 04/13 06:17
→ : YO叔早就破解了202F 04/13 06:24
→ : 看到第一頁就放棄了= =203F 04/13 06:36
推 : 菜雞問問yo叔是什麼204F 04/13 06:38
推 : 跟我想的一模一樣205F 04/13 07:12
推 : 看到離散，我頭髮又掉了兩根206F 04/13 07:19
推 : 嗯...長了關於yoyodiy的知識207F 04/13 07:19
推 : p=np 我到底看了什麼208F 04/13 07:28
→ : 繞過去就好了啦 yo叔有教209F 04/13 07:35
推 : 快破解比特幣讓他崩到沒價值 我想看賤畜礦工跳樓210F 04/13 07:42
推 : 這我早就知道了211F 04/13 07:48
推 : 這點問題高中就提過只是沒有深究而已 德國人還真閒212F 04/13 08:03
推 : 乾，看不懂，我要繞過去了213F 04/13 08:06
推 : 跟我想的一樣214F 04/13 08:07
推 : 跟我想的差不多215F 04/13 08:08
推 : 應該是只要不是真NP問題，就只是P問題。而非P=NP216F 04/13 08:19
推 : 可是SVP本身也沒有polynomial time的演算法217F 04/13 08:51
--
※ 看板: Gossiping 文章推薦值: 0 目前人氣: 0 累積人氣: 1858
回列表(←)
分享