近期，兩位研究人員在1個(gè)小時(shí)內(nèi)使用一臺(tái)10年“高齡”臺(tái)式計(jì)算機(jī)成功破解后量子加密算法。

　　新浪科技訊 北京時(shí)間8月29日上午消息，據(jù)報(bào)道，目前，兩位研究員成功破解一種加密算法，該加密算法曾被科學(xué)界寄予厚望，認(rèn)為能夠抵御量子計(jì)算的威脅。

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

　　如果人們使用功能先進(jìn)的量子計(jì)算機(jī)系統(tǒng)時(shí)，網(wǎng)絡(luò)將面臨著安全危機(jī)，因此，2017年美國(guó)政府和國(guó)家標(biāo)準(zhǔn)與技術(shù)研究所(NIST)發(fā)起了一項(xiàng)國(guó)際比賽，用于尋找實(shí)現(xiàn)“后量子加密(post-quantum cryptography)”的最佳方式。

　　今年7月份，美國(guó)政府和國(guó)家標(biāo)準(zhǔn)與技術(shù)研究所選出了第一批獲獎(jiǎng)?wù)摺膫€(gè)加密算法，它們經(jīng)過一系列修正后，將作為量子盾部署的四項(xiàng)加密算法，同時(shí)，該機(jī)構(gòu)還宣布了四項(xiàng)正在考慮中的候選算法。

　　7月30日，兩位研究人員披露稱，他們?cè)?個(gè)小時(shí)內(nèi)使用一臺(tái)計(jì)算機(jī)就能破解其中一款加密算法(之后其他研究員也開始破解安全算法，并且破解時(shí)間更快，有時(shí)僅用幾分鐘時(shí)間)，值得注意的是，該記錄并非由某臺(tái)先進(jìn)計(jì)算機(jī)創(chuàng)造的，而是來自一臺(tái)具有10年“高齡”CPU的臺(tái)式計(jì)算機(jī)，而且是單核運(yùn)行，這次破解加密算法讓研究人員意識(shí)到后量子密碼學(xué)在被采用之前需要克服許多障礙。

　　新西蘭奧克蘭大學(xué)數(shù)學(xué)家和計(jì)算機(jī)科學(xué)家史蒂文·加爾布雷斯(Steven Galbraith)說:“一次如此戲劇性和強(qiáng)大的攻擊……是相當(dāng)令人震驚的，這不僅是因?yàn)槠平獍踩惴ㄋ捎玫臄?shù)學(xué)原理令人感到驚奇，而且還減少了后量子密碼學(xué)的多樣性，消除了一種與NIST競(jìng)賽中絕大多數(shù)方案工作方式差異很大的加密算法。”

　　美國(guó)密歇根大學(xué)密碼學(xué)家克里斯托弗·佩科特(Christopher Peikert)說：“這有點(diǎn)令人感到失望，該研究結(jié)果讓后量子密碼學(xué)界既感到震驚，又感到振奮，震驚是因?yàn)檫@次破解出乎預(yù)料，突然將一個(gè)看起來像數(shù)字鐵門的事物變成了濕報(bào)紙。”

　　美國(guó)政府和國(guó)家標(biāo)準(zhǔn)與技術(shù)研究所標(biāo)準(zhǔn)化工作負(fù)責(zé)人達(dá)斯汀·穆迪(Dustin Moody)說：“研究人員僅用1個(gè)小時(shí)就破解加密算法，這太難以置信，如果一個(gè)密碼系統(tǒng)方案要被破解，最好是在它投入廣泛應(yīng)用之前就被破解，否則將面臨重大損失。”

　　“秘密曲線”

　　加拿大滑鐵盧大學(xué)數(shù)學(xué)家戴維·饒(David Jao)和同事開始關(guān)注加密系統(tǒng)破解，他們的密碼系統(tǒng)既類似于眾所周知的常規(guī)性算法，又有適當(dāng)?shù)牟町悾撍惴ǚ桨副环Q為“超奇異同源迪菲-赫爾曼算法(SIDH)”，主要是處理橢圓曲線，同樣的數(shù)學(xué)對(duì)象被用于現(xiàn)今最廣泛的密碼學(xué)類型。據(jù)悉，SIDH算法最初于2011年提出，設(shè)計(jì)者從超奇異同源橢圓曲線的角度提出一種抵御量子攻擊的密碼系統(tǒng)，該密碼系統(tǒng)依賴于計(jì)算超奇異橢圓曲線之間同源的困難性問題，而且密鑰長(zhǎng)度明顯要比其他后量子密碼長(zhǎng)度短。

　　戴維說：“從數(shù)學(xué)角度上講，橢圓是非常優(yōu)雅的曲線，應(yīng)用橢圓曲線作為定理的加密算法是非常不錯(cuò)的。”

　　如果有兩條橢圓曲線(E1和E2)，我們能夠創(chuàng)建一個(gè)函數(shù)，將E1曲線上的點(diǎn)P映射到E2曲線上的點(diǎn)Q，這個(gè)函數(shù)被稱為同源函數(shù)，如果我們能映射這個(gè)函數(shù)，E1曲線每一個(gè)點(diǎn)都可以映射到E2曲線，秘密密鑰是同源的，公開密源是橢圓曲線。之后假設(shè)兩個(gè)密鑰交換當(dāng)事人分別為愛麗絲和鮑勃，他們希望秘密交換一條信息，即使是在潛在攻擊者的監(jiān)視之下，對(duì)于密鑰交換，愛麗絲和鮑勃互相將同源曲線混合，從而生成一條“秘密曲線”。

　　愛麗絲和鮑勃的密鑰交換從一組點(diǎn)開始，這些點(diǎn)由叫做“圖表”的邊線連接起來，每個(gè)點(diǎn)代表一條不同的橢圓曲線，如果你能以一種特定方法將一條曲線轉(zhuǎn)換成另一條曲線(通過同源地圖)，在兩個(gè)點(diǎn)之間畫一條邊線，由此產(chǎn)生的“圖表”非常大且復(fù)雜，如果沿著邊線前行一段相對(duì)較短的路程，將會(huì)在一個(gè)看似完全隨機(jī)的地點(diǎn)結(jié)束。

　　愛麗絲和鮑勃的圖表都有相同的點(diǎn)，但是邊線是不同的，該情況被定義為非同源，愛麗絲和鮑勃的交換密鑰從同一個(gè)點(diǎn)開始，沿著各自的圖表上的隨機(jī)邊線跳躍，跟蹤從一個(gè)點(diǎn)到另一個(gè)點(diǎn)的路徑，之后愛麗絲和鮑勃都公布了密鑰的結(jié)束位置，但對(duì)相關(guān)路徑保密。

　　現(xiàn)在愛麗絲和鮑勃交換位置：愛麗絲到鮑勃的最終點(diǎn)，鮑勃到愛麗絲的最終點(diǎn)，每次都重復(fù)“秘密曲線”，這樣他們最終會(huì)在同一點(diǎn)結(jié)束。這個(gè)點(diǎn)位已被破解，所以愛麗絲和鮑勃可以用該點(diǎn)位作為秘密密鑰——允許安全地加密和解密彼此的信息，即使網(wǎng)絡(luò)攻擊者看到他們發(fā)送給彼此的中間點(diǎn)，也不會(huì)知道他們的“秘密步數(shù)”，因此網(wǎng)絡(luò)攻擊者無法算出最終端點(diǎn)。

　　但是為了運(yùn)行SIDH算法，愛麗絲到鮑勃還需要交換關(guān)于“秘密曲線”的額外信息，這些額外信息導(dǎo)致了SIDH算法被破解。

　　傳統(tǒng)數(shù)學(xué)理論的“新轉(zhuǎn)折”

　　研究員托馬斯·德克魯(Thomas Decru)并未打算破壞SIDH算法，他試圖在此基礎(chǔ)上進(jìn)一步應(yīng)用該方法增強(qiáng)另一種類型密碼學(xué)，并未成功，卻激發(fā)了一個(gè)新想法，該方法可能對(duì)攻擊SIDH算法有效。于是，他找到了比利時(shí)魯汶大學(xué)同事沃特·卡斯特里克(Wouter Castryck)，他們開始鉆研相關(guān)文獻(xiàn)資料。

　　他們偶然發(fā)現(xiàn)了數(shù)學(xué)家恩斯特·卡尼(Ernst Kani)于1997年發(fā)表的一篇論文，其中有一個(gè)定理“幾乎能適用于SIDH算法”，卡斯特里克說：“我們?cè)J(rèn)為它破解加密算法非常快，可能需要1-2天時(shí)間。”

　　最終，為了恢復(fù)愛麗絲的“秘密步數(shù)”，以及共享密鑰，卡斯特里克和德克魯檢查了兩條橢圓曲線的運(yùn)地結(jié)果——愛麗絲的起始曲線，以及她公開發(fā)送給鮑勃的曲線，該組合產(chǎn)生了一種叫做“交換面”的曲面，之后他們使用“交換面”、Kani定理(與“交換面”相關(guān)的橢圓曲線定理)以及愛麗絲給鮑勃的額外信息，從而揭曉愛麗絲所走的每一步。

　　Meta AI Research公司的數(shù)學(xué)家和密碼學(xué)家克里斯汀·勞特爾(Kristin Lauter)說：“看到該技術(shù)被使用，我感到非常興奮！它不僅有助于開發(fā)基于同活的密碼學(xué)，還研究了交換面，因此我對(duì)自己未將該算法作為破解加密算法的解決方案，而感到羞愧。”

　　目前，德克魯和卡斯特里克在62分鐘內(nèi)破解了SIDH算法的最低安全等級(jí)的算法，并在不足1天的時(shí)間內(nèi)破解了最高安全等級(jí)的算法。隨后不久，另一位安全專家對(duì)網(wǎng)絡(luò)攻擊進(jìn)行了調(diào)整，僅需10分鐘便能破解最低安全等級(jí)的算法，幾個(gè)小時(shí)就能破解了最高安全等級(jí)的算法。在過去幾周的時(shí)間里，更多一般性網(wǎng)絡(luò)攻擊使得SIDH算法接近崩潰。

　　一個(gè)分水嶺

　　美國(guó)布朗大學(xué)數(shù)學(xué)家杰弗里·霍夫斯坦(Jeffrey Hoffstein)說:“我們不可能保證某個(gè)加密系統(tǒng)是無條件安全的，相反，密碼學(xué)家依靠充足的時(shí)間和人力試圖破解來產(chǎn)生自信，這意味著當(dāng)明天早上一覺醒來時(shí)，你無法保證不會(huì)有人能采用某種新算法破解該加密系統(tǒng)。”

　　因此，像美國(guó)政府和國(guó)家標(biāo)準(zhǔn)技術(shù)研究所舉辦此類競(jìng)賽是非常重要的，在上一輪比賽中，IBM公司密碼學(xué)家沃德·伯倫斯(Ward Beullens)設(shè)計(jì)了一次網(wǎng)絡(luò)攻擊，破壞了彩虹簽名算法，與卡斯特里克和德克魯一樣，伯倫斯只有從不同角度分析潛在的數(shù)學(xué)問題后，才對(duì)該加密算法攻擊奏效。就像對(duì)SIDH算法的攻擊一樣，此次攻擊破壞了一個(gè)依賴不同于多數(shù)提議后量子算法的數(shù)學(xué)系統(tǒng)。

　　初創(chuàng)公司PQShield密碼破譯專家托馬斯·普雷斯特(Thomas Prest)說：“最近發(fā)生的加密算法破解是一個(gè)分水嶺，研究后量子密碼學(xué)難度很大，同時(shí)分析各種算法系統(tǒng)的安全性并非簡(jiǎn)單的事情，一個(gè)數(shù)學(xué)對(duì)象可能在某個(gè)角度上沒有明顯結(jié)構(gòu)，但在另一個(gè)角度上則有開發(fā)結(jié)構(gòu)，最難的部分就是尋找正確的新視角。”