Re: [爆卦] 德國密碼學家宣稱自己摧毀了RSA加密法
※ 引述《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
--
憎めない筋肉馬鹿一直線─────────────────────────────
._ ▎ ▃▅== ▏ ▏▎▊▎ ◤.▃▅ ▄
▄▃▎ ▊ -◢▋‥▋▎ ▋ V.S▅ ▄◢▋▄ ▊▅
◢. ▃ ▃▄︷▃▊ ▃ ▋▂ ▊ ▄ ▁▄=*▊▍
▋◥◣▂▏▄ ▋▊ ▉▊▎▎ ▂ ▊ ▉ ' ◢ ▄ ▅
─────────────────────────最強の男児にして真人のライバル
--
XD
推認真文
應該很多人看不懂 需要更簡單的敘述普通人才知道在幹嘛
嗯嗯,跟我想的一樣(<-完全看不懂
推
你認為這裡會有人懂?
樓下推跟我想的一樣
快跟著推,不然別人以為我不懂XD
為什麼要質因數分解?就不能用質數去相乘不停試誤嗎?
樓下 jserv
難道不能直接拆分微分掉嗎
太認真了吧 是不是博班唸太累來抒發一下
幹人類因為想通了這些 電腦就做出來了
只在演算法課聽過NP
@口@
看這文還以為是@jserv
只知道Nice Play
計算理論剛好上到TM推一個
你在寫什麼,回去重寫!!
太深奧了 我還是等李永樂吧
加鹽加非固定參數,你ㄧ小時破解,我就半小時換
感覺很熱血
快推爆 不然別人以為我們看不懂
還有拆分微分喔?有誰分解質因數要用到微分的?
專業推
推
好厲害!
爆
首PoRSA加密法於1977年由Rivest、Shamir和Adleman提出,因為極大數的質因數分解困難度,此 方法成為世界上應用最廣泛的加密法。目前被破解的RSA密鑰最長紀錄是768個位元,因此 一般認為2048位元的密鑰非常安全可靠。 然而德國密碼學家Claus Peter Schnorr在自己新論文摘要中的最後一句宣稱:本文"摧毀"13
本 : 文宣稱透過晶格密碼學中的SVP法(尋找最接近向量),即使使用傳統電腦,我們也有機 會 : 比二次篩選法和普通數域篩選法(已知最快的傳統因數分解演算法)更快完成分解。 : 這篇論文目前還未通過同行評審。GitHub上已經有人實作文中的算法,但是沒人成功。
爆
[問卦] 幹你娘 勞動部怎麼會變成勞動地獄?爆
[問卦] 12強冠軍台灣要發2億以上大家ok嗎?爆
[問卦] 勞動部霸凌致死案 為何燒不起來?爆
[問卦] 綠鬣蜥 改名成 台灣蜥 問題就解決了吧爆
[問卦] 大巨蛋的功臣現在人在哪裡爆
[問卦] 勞動部霸凌+J爸+發票中獎 會有後續嗎?爆
[問卦] 偷襲小嶋的是中國人!!!爆
[問卦] 這次大巨蛋一致好評是誰的功勞爆
[問卦] 勞動布霸凌比洪仲丘嚴重吧,卻沒上街抗議98
[問卦] 蝦土豆台男吃播影片 都是誰在看的?76
[問卦] 三方詐騙跟台灣廢物法律幹你娘75
[問卦] 星巴克從紙吸管又改回塑膠吸管71
[問卦] 台灣請馬斯克來整頓 哪部門一定會被砍掉61
[問卦] 引進老鷹抓綠鬣蜥 反變老鷹氾濫怎麼辦?52
[問卦] 八卦版是個怎樣的版47
[問卦] 說真的 綠鬣蜥遲早會到北部吧?43
[問卦] 勞動部上吊事件 在2016以前發生會怎樣40
[問卦] 棒球是打完最不喘的運動嗎?31
[問卦] 川普當年說不用戴口罩,其實是對的?35
[問卦] 如果當初核四廠有成功啟用的話會怎樣?42
[地震] 地震?35
[問卦] 現在國小生出國十幾次很正常喔?36
Re: [新聞] 「低碳上學+喝鮮奶」行政爆量 老師好忙39
Re: [問卦] 襲擊小嶋陽菜的人照片一看就是台男25
[問卦] 面試問「什麼布剪不斷」他機智回34
[問卦] 幼教業年薪平均36萬欸你可以37
Re: [新聞] 逼死職員內幕!被許銘春一手拔擢 謝宜容26
Re: [問卦] 說真的 綠鬣蜥遲早會到北部吧?48
[問卦] 當初說大巨蛋不能打棒球的是誰?30
[問卦] 為啥不要儘速研發AI公車?