01
RSA算法要被破解了？！
這幾天一篇文章引起了密碼學界的廣泛關注，
《Fast Factoring Integers by SVP Algorithms》
作者聲稱自己破解了RSA算法
其正是Claus Peter Schnorr
Claus Peter Schnorr何許人也？
德國最有名的密碼學家之一、
法蘭克福歌德大學數學和信息學系教授、
Schnorr 簽名算法發明人。
以他的名字命名的「Schnorr數字簽名方案」，
今天全世界都在應用。
而其可以構建更高效和隱私性更強的區塊鏈系統，
一直備受區塊鏈開發者們的關注。
一個詞總結那就是
正是這樣一位大佬
提出自己破解了RSA算法
但很多人還是持質疑態度的
一開始，有人懷疑「標題党」
有人猜測是別人假冒Schnorr發布的「舊文」
（馬上Schnorr自己出面認領了 ……）
但Schnorr本人也鬧了個「烏龍」
一開始將文章錯發成了2019年的版本
經人提醒後更新為3月3日的最新版本
並且摘要包含了
「This destroys the RSA cryptosystem。」
GitHub上也有人開始嘗試進行算法實現，
不過，結果都顯示不可行。
人們對於這篇「天降文章」還有很多疑惑：
Schnorr為何要發布這樣一篇文章？
文章中的問題是不小心的遺漏還是有意為之？
RSA算法真的要被破解了嗎？
……
對於這些問題，我們只能讓子彈再飛一會
但這篇文章的出現再次提出一個問題：
我們距離RSA算法不再可信任的那天
還有多遠？
02
RSA算法是什麼？
如果要解釋RSA的重要性：
「地球上最重要的算法之一」
「所有密碼的根基」
覺得誇張？
那了解了RSA算法後你可能就不這麼想了。
1977年，三位數學家
Rivest、Shamir 和 Adleman 設計了一種算法，
可以實現非對稱加密。
算法用他們三個人的名字命名，
叫做 RSA 算法。
這種算法非常可靠，
它運用了數學「兩個大的質數相乘，
難以在短時間內將其因式分解」
這樣一套看似簡單
事實上真的非常非常非常困難的數學難題。。。。。。
且密鑰越長，它就越難被破解。
近40年過去，
RSA 算法經曆了各種攻擊的考驗。
根據已經披露的文獻，
目前被破解的最長RSA密鑰是768個二進制位。
也就是說，長度超過768位的密鑰，
還無法破解，至少沒人公開宣布。
（Schnorr大佬這不就來了嘛）
因此。目前一般認為，
1024位的RSA密鑰基本安全，
2048位的密鑰極其安全。
而RSA算法作為被研究得最廣泛的公鑰算法，
被普遍認為是目前最優秀的公鑰方案之一。
也是最廣泛使用的「非對稱加密算法」：
HTTPS協議中就使用了RSA加密算法，
金融、互聯網、電子商務……
我們生活中的各個領域都有RSA算法的身影，
毫不誇張地說，
只要有計算機網絡的地方，
就有 RSA 算法。
而在1982年，
RSA算法的發明者創立了RSA公司。
2013年左右，RSA在全球擁有8000萬客戶，
客戶基礎遍及各行各業，
包括銀行、政府機構、電信、宇航業、大學等。
超過7000家企業，逾800萬用戶
使用RSA SecurID認證產品保護企業資料，
（包括財富雜志排行前百家企業的80%）
而超過500家公司在逾1000種應用軟件
安裝有RSA Bsafe軟件。
現在你是否理解，
為何密碼學家Schnorr說自己破解了RSA算法
會引起如此大的轟動了吧？
03
密碼攻防會有盡頭嗎 ？
幾千年來，
人們追求的信息安全一直藏在無盡的密碼攻防裏，
不斷升級的密碼算法和不斷提升的計算算力 。
對於人們來說，
RSA
真的足夠安全了麼？
2012年國家互聯網應急中心發布
「關於 RSA1024 算法存在被破譯風險的通報」
美國國家標准與技術研究所（NIST） 在 07 年 3 月就要求在 2010 年 12 月 31 日之前停止使用 1024 位RSA 算法。
RSA 公司相關負責人也明確表示，雖然沒有證據表明 RSA1024 算法已經被破譯，但是破譯只是時間問題。
RSA1024 算法被破譯可能引發加密信息被破譯、數字簽名被偽造、通信過程被竊聽等安全事件。
2013年「棱鏡門」事件爆發，
據路透社報道，
美國國安局（NSA）曾與加密技術公司RSA
達成了1000萬美元的協議，
要求在移動終端廣泛使用的加密技術中放置後門。
RSA SecurID密鑰卡
此舉將讓NSA通過隨機數生成算法Bsafe的後門程序
輕易破解各種加密數據。
RSA否認了相關的內容，
聲稱自己的加密算法只使用了國家認證的協議。
而NSA則拒絕發表評論。
曾有互聯網安全專家在接受采訪時表示，
「美國國安局在RSA中設置後門意味著，
密碼動態密碼部分已經被美國政府掌握。」
彼時，RSA在中國有很多客戶
包括中國電信、中國移動、中國銀行、中國農業銀行、
中國工商銀行、中國建設銀行、華為、海爾等。。。。。
另一個「不安全」因素，在於算力和算法的發展
在1994 年，
美國數學家 Peter Shor 就發現了一種量子算法，
其性能優於經典算法。
在此之前因數分解確實被認為是很難的數學題，
計算機科學家認為經典計算機
幾乎不可能分解出大於 2048 位的數字，
（2048位正是目前RSA加密最常用的基礎形式）
Shor卻證明了，
只要量子計算機有足夠的邏輯量子比特來執行操作，
該算法就可以完全破壞基於RSA
和橢圓曲線密碼學的加密機制。
還有一種稱為Grover的算法，
可以將AES加密從128位徹底削弱至64位，
然後就能通過普通計算機算法來破解了。
越來越多的專家認為，
大規模量子計算機將在未來十年問世。
人們對於破解 2048 位 RSA 加密信息時間的預估
也在不斷縮短。
在達沃斯舉行的世界經濟論壇上，
穀歌首席執行官皮查伊（Sundar Pichai）曾預言：
在5到10年的時間周期，量子計算將會打破我們今天所知道的加密技術。
Shor也曾在接受采訪時表示：
我認為用安全的後量子密碼系統取代RSA的唯一阻礙是意志和編程時間。我認為我們已經知道要如何做到這一點，只是不清楚是否能及時做到。
不論是通過算力的提升，
還是後門的植入，
圍繞保密與破解的鬥爭，似乎永遠不會停止。
04
不怕量子計算的密碼？有！
或許是厭惡了你來我往無休止的攻防
也或許是出於防患於未然的謹慎
學界及產業界已經將目光
投向了量子保密通信和抗量子算法。
美國國家標准與技術研究所（NIST）
正在制定一套抗量子算法（QRA）標准，
希望在2024年前完成。
綜合考慮量子計算機建造時間、
信息需要保護的時間、
升級基礎設施需要的時間等因素，
在重要領域及環節盡早布局量子安全
正逐漸成為各界共識。
One more question：
理論上，
任何以計算複雜度為基礎的密碼算法及其應用
都是可以被攻破的。
有沒有完全不怕算力破解的密碼？
有！量子密碼！
比如我國正在大力發展的
量子密鑰分發（QKD）技術：
用量子力學物理原理實現共享密鑰在線生成，
密鑰的安全性依賴於基本的物理原理，
而不是具體的數學假設。
因此，結合信息論安全的對稱加密算法，
能保證用量子密鑰加密的內容不可破譯。
而且，《量子安全技術白皮書》中提出：
在當前以及近未來的技術條件下，可以將 QKD 與後量子密碼相結合。
後量子密碼能應用於 QKD 網絡中實現設備間的簽名認證……QKD 技術能夠為後量子密碼系統生成所需要的成對臨時密鑰或工作密鑰，通過QKD不斷更換加密密鑰，可獲得很強的前向安全性。
這種「QKD + PQC」類型的應用方案使密碼系統整體能夠應 對量子攻擊。
從「陰符」、「陰書」到凱撒密碼，
從密碼機到生活中無處不在的RSA……
人們對於信息安全的追求永無止境，
我們也期待隨著科學的發展、技術的普及，
會有真正的「無條件安全」 出現。
