不要別的,只要科學

頗有潛力的後量子加密算法僅1小時就被完全破解


2022年08月29日

新浪科技

近期,兩位研究人員在1個小時內使用一台10年「高齡」台式計算機成功破解後量子加密算法。

新浪科技訊

如果最新的加密算法被破解,則意味著網絡安全存在威脅性,尤其是發送機密信息、金融安全交易、驗證數據等,任何人的私密信息將不再保密,網絡上木馬程序和惡意攻擊軟件肆虐橫行,未來的數字網絡經濟將面臨崩潰。

如果人們使用功能先進的量子計算機系統時,網絡將面臨著安全危機,因此,2017年美國政府和國家標准與技術研究所(NIST)發起了一項國際比賽,用於尋找實現「後量子加密(post-quantum

今年7月份,美國政府和國家標准與技術研究所選出了第一批獲獎者——四個加密算法,它們經過一系列修正後,將作為量子盾部署的四項加密算法,同時,該機構還宣布了四項正在考慮中的候選算法。

7月30日,兩位研究人員披露稱,他們在1個小時內使用一台計算機就能破解其中一款加密算法(之後其他研究員也開始破解安全算法,並且破解時間更快,有時僅用幾分鐘時間),值得注意的是,該記錄並非由某台先進計算機創造的,而是來自一台具有10年「高齡」CPU的台式計算機,而且是單核運行,這次破解加密算法讓研究人員意識到後量子密碼學在被采用之前需要克服許多障礙。

新西蘭奧克蘭大學數學家和計算機科學家史蒂文·加爾布雷斯(Steven

美國密歇根大學密碼學家克裏斯托弗·佩科特(Christopher

美國政府和國家標准與技術研究所標准化工作負責人達斯汀·穆迪(Dustin

  「秘密曲線」

加拿大滑鐵盧大學數學家戴維·饒(David

戴維說:「從數學角度上講,橢圓是非常優雅的曲線,應用橢圓曲線作為定理的加密算法是非常不錯的。」

如果有兩條橢圓曲線(E1和E2),我們能夠創建一個函數,將E1曲線上的點P映射到E2曲線上的點Q,這個函數被稱為同源函數,如果我們能映射這個函數,E1曲線每一個點都可以映射到E2曲線,秘密密鑰是同源的,公開密源是橢圓曲線。之後假設兩個密鑰交換當事人分別為愛麗絲和鮑勃,他們希望秘密交換一條信息,即使是在潛在攻擊者的監視之下,對於密鑰交換,愛麗絲和鮑勃互相將同源曲線混合,從而生成一條「秘密曲線」。

愛麗絲和鮑勃的密鑰交換從一組點開始,這些點由叫做「圖表」的邊線連接起來,每個點代表一條不同的橢圓曲線,如果你能以一種特定方法將一條曲線轉換成另一條曲線(通過同源地圖),在兩個點之間畫一條邊線,由此產生的「圖表」非常大且複雜,如果沿著邊線前行一段相對較短的路程,將會在一個看似完全隨機的地點結束。

愛麗絲和鮑勃的圖表都有相同的點,但是邊線是不同的,該情況被定義為非同源,愛麗絲和鮑勃的交換密鑰從同一個點開始,沿著各自的圖表上的隨機邊線跳躍,跟蹤從一個點到另一個點的路徑,之後愛麗絲和鮑勃都公布了密鑰的結束位置,但對相關路徑保密。

現在愛麗絲和鮑勃交換位置:愛麗絲到鮑勃的最終點,鮑勃到愛麗絲的最終點,每次都重複「秘密曲線」,這樣他們最終會在同一點結束。這個點位已被破解,所以愛麗絲和鮑勃可以用該點位作為秘密密鑰——允許安全地加密和解密彼此的信息,即使網絡攻擊者看到他們發送給彼此的中間點,也不會知道他們的「秘密步數」,因此網絡攻擊者無法算出最終端點。

但是為了運行SIDH算法,愛麗絲到鮑勃還需要交換關於「秘密曲線」的額外信息,這些額外信息導致了SIDH算法被破解。

  傳統數學理論的「新轉折」

研究員托馬斯·德克魯(Thomas

他們偶然發現了數學家恩斯特·卡尼(Ernst

最終,為了恢複愛麗絲的「秘密步數」,以及共享密鑰,卡斯特裏克和德克魯檢查了兩條橢圓曲線的運地結果——愛麗絲的起始曲線,以及她公開發送給鮑勃的曲線,該組合產生了一種叫做「交換面」的曲面,之後他們使用「交換面」、Kani定理(與「交換面」相關的橢圓曲線定理)以及愛麗絲給鮑勃的額外信息,從而揭曉愛麗絲所走的每一步。

Meta

目前,德克魯和卡斯特裏克在62分鐘內破解了SIDH算法的最低安全等級的算法,並在不足1天的時間內破解了最高安全等級的算法。隨後不久,另一位安全專家對網絡攻擊進行了調整,僅需10分鐘便能破解最低安全等級的算法,幾個小時就能破解了最高安全等級的算法。在過去幾周的時間裏,更多一般性網絡攻擊使得SIDH算法接近崩潰。

  一個分水嶺

美國布朗大學數學家傑弗裏·霍夫斯坦(Jeffrey

因此,像美國政府和國家標准技術研究所舉辦此類競賽是非常重要的,在上一輪比賽中,IBM公司密碼學家沃德·伯倫斯(Ward

初創公司PQShield密碼破譯專家托馬斯·普雷斯特(Thomas


熱門內容

友善連結