Re: [爆卦] 德國密碼學家宣稱自己摧毀了RSA加密法

看板Gossiping作者c910335 (達人)時間3年前 (2021/04/13 18:55)推噓22(23推 1噓 3→)

留言27則, 27人參與討論串3/3 (看更多)

※ 引述《rafe (Out of the hole)》之銘言： : ※ 引述《jackliao1990 (j)》之銘言： : : https://eprint.iacr.org/2021/232.pdf : : 一般認為,我們要等到使用秀爾演算法的量子電腦普及後,RSA加密法才會被破解。然而 : 本 : : 文宣稱透過晶格密碼學中的SVP法(尋找最接近向量)，即使使用傳統電腦，我們也有機 : 會 : : 比二次篩選法和普通數域篩選法(已知最快的傳統因數分解演算法)更快完成分解。 : : 這篇論文目前還未通過同行評審。GitHub上已經有人實作文中的算法,但是沒人成功。 : 也 : : 有人指出論文中的可能漏洞:文中"將整數的指數加倍"這操作在過去被認為需要指數時 : 間 : : ，但作者卻"證明"這需要多項式時間。這表示:過去被認為屬於NP問題的操作，被本文 : 證 : : 明屬於P，這樣豈不就證明P=NP了?(然而質因數分解從沒被證明是NP完全問題) : 解說一下什麼是P=NP : P的意思是polynomial，也就是線性或多項式，NP則指非線性或是指數。 : 這倆個詞是形容問題的複雜度，以玩遊戲來舉例， : 例如說打隻狼破關，你花的時間大致上是線性的， : 如果增加魔王，或是出了dlc你大概只要多花幾個小時就能破關。 : 而NP問題就像是要挑戰無傷破關，你要不斷全破好幾次去熟悉魔王，找出最佳的路徑，道 : 具 : 跟策略。加一個頭目或dlc，代表的是好幾天，幾個月或幾年的訓練。 : 作者證明RSA可被破解，就像是說他找到了方法可以無傷忍殺掉所有魔王， : 讓打倒魔王花的時間變成線性，不論加了多少頭目玩家都只要多花幾個小時就能無傷通關 : ， : 隻狼變成手遊難度，是完全的平衡破壞者。 : 而證明P=NP就比較像是哲學問題，簡單來講就是對於這世上所有的困難問題， : 能不能證明他們都存在一個簡單的解法， : 就像是說不止是隻狼，世上所有的遊戲都存在類似的秘技可以無傷通關，只是還沒被發現 : 而已。 : 衍生來說可以說證明了P=NP，就等於是證明了世上存在著某種真理一樣。前面推文也有提到這件事 NP [1] 是指 non-deterministic polynomial time 並非 non-polynomial time 意思是能夠用非確定性圖靈機在多項式時間內解決的問題現在常用的等價敘述是能夠在多項式時間內驗證是正確的問題而 EXPTIME [2] 這個指的才是指數時間雖然前面兩篇文及推文一直不斷提到 P=NP 然而我認為這篇論文與 P/NP問題 [3] 並沒有太大的相關性理由如下： 1. 該論文所描述的演算法有 heuristic 及 randomized 的部分 heuristic 的部分 worst case 依然是指數時間而 randomized 也不在 P/NP 討論的範圍（我只有大略掃過該論文，並不是很確定我有沒有理解錯誤） 2. 質因數分解本來就不是 NP-hard 的問題（除非 NP=coNP）所以即使質因數分解存在多項式時間的演算法那也無法用來證明 P=NP 只能說明人類已知的 P 問題又變多了類似的事件已經發生過不少次了例如線性規劃 [4] 及質數測試 [5] 關於質因數分解在計算理論一些最近的結果目前有人證明質因數分解可以 randomized reduce 到 PPA [6] 和 PWPP [7] 的交集而且如果廣義黎曼猜想 [8] 是對的那就能證明質因數分解真的在 PPA 和 PWPP 的交集裡 [7:1] 這兩者的複雜度都是比 NP-complete 還簡單的（除非 NP=coNP）另外 SVP 和一些相關問題的複雜度也有人證明是在 PPP [6:1][9] 只不過有些是 Cook reduction [9:1] 所以這些還不能保證真的在 PPP 我想講的大概就這些提供一些計算理論的觀點 [1] NP: https://en.wikipedia.org/wiki/NP_(complexity) [2] EXPTIME: https://en.wikipedia.org/wiki/EXPTIME [3] P/NP問題: https://en.wikipedia.org/wiki/P_versus_NP_problem [4] 線性規劃: https://doi.org/10.1016/0196-6774(80)90002-4 [5] 質數測試: https://www.jstor.org/stable/3597229 [6] PPA, PPP: https://doi.org/10.1016/S0022-0000(05)80063-7 [7] Factoring Complexity: https://doi.org/10.1016/j.jcss.2015.08.001 [8] 廣義黎曼猜想: https://en.wikipedia.org/wiki/Generalized_Riemann_hypothesis [9] SVP Complexity, Cook reduction: https://arxiv.org/abs/1808.06407 -- 憎めない筋肉馬鹿一直線───────────────────────────── ._ ▎ ▃▅== ▏ ▏▎▊▎ ◤.▃▅ ▄ ▄▃▎ ▊ -◢▋‥▋▎ ▋ Ｖ.Ｓ▅ ▄◢▋▄ ▊▅ ◢. ▃ ▃▄︷▃▊ ▃ ▋▂ ▊ ▄ ▁▄=*▊▍ ▋◥◣▂▏▄ ▋▊ ▉▊▎▎ ▂ ▊ ▉ ' ◢ ▄ ▅ ─────────────────────────最強の男児にして真人のライバル -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.113.230.194 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Gossiping/M.1618311343.A.635.html

推

a6234709

04/13 18:56, 3年前 , 1^F

04/13 18:56, 1^F

推

bygonedays

04/13 18:59, 3年前 , 2^F

04/13 18:59, 2^F

→

potionx

04/13 19:00, 3年前 , 3^F

04/13 19:00, 3^F