編譯 魏劉偉

量子計算機可以破解現在維護互聯網安全的公鑰加密方案

成熟的量子計算機仍然需要數年乃至數十年時間才會出現。但開發(fā)人員始終認為，其殺手級應用程序能在互聯網和其他地方解碼加密信息，無論是國家機密還是個人信息。這種可能性激勵了密碼學家。最近在加州圣巴巴拉舉行的一次會議上，他們將討論20多個加密信息的方案，即使量子計算機也無法將其破解。

此次研討會是美國國家標準與技術研究所（NIST）推動制定所謂后量子密碼學標準的一個努力。這多年的努力聽起來可能為時過早和極端，因為這樣的量子計算機可能永遠不會出現。但密碼學家表示，現在是做好準備的時候了，尤其是因為現在任何人都可以記錄敏感通信，然后再對它們進行解密。荷蘭艾恩德霍芬科技大學的密碼學家坦賈·蘭格（Tanja Lange）說：“如果等到量子計算機出現就太遲了，沒有后量子密碼學的每一天都會遭受數據泄露?！?/p>

高達數千億美元的電子商務都依賴于被稱為公鑰加密術的這種易受攻擊的方案。它們是基于“陷阱門”來計算的，之所以稱之為陷阱門，是因為它們更易于正向計算而非逆向。接收者Alice提供數字公鑰和秘方，發(fā)送者Bob用它來對消息進行加密。竊聽者Eve不可能輕易逆轉Bob的計算來發(fā)現這條信息。然而，Alice還生成了秘密私鑰，它在數學上與公共密鑰相關，這有助于她通過像Bob那樣的計算來解讀信息。

例如，在一個名為RSA的流行公鑰方案中，Bob通過將數字信息本身乘以Alice指定的數字來倍增該數字信息。他將結果除以公鑰（這是由兩個素數相乘而產生的巨大數字）并將余數發(fā)送給Alice。為了重建消息，Alice將余數乘以不同的數字——該數字是她的私鑰——并除以公鑰。就這樣！Bob的原始信息出現了。這就好像Alice告訴Bob如何模糊密碼鎖的設置：通過將刻度盤向前轉許多次，知道如何將刻度盤向前轉以恢復原來的設置。Eve只能努力弄清楚要把撥號盤撥回去多遠。

RSA還說明了量子計算機構成的威脅。如果Eve能夠將公鑰分解為其素數組成，她就可以竊取私鑰并破解密碼。計算大量數字對于傳統(tǒng)計算機來說很難，但對于量子計算機來說會更容易，正如麻省理工學院數學家彼得·肖爾（Peter Shor）在1994年所展示的那樣。運行肖氏算法的量子計算機也可以擊敗新的公鑰方案，因為它擅長于在重復的除法和取余數的操作中找到模式。

為了應對這一風險，密碼專家正在開發(fā)不易受攻擊的陷阱門算法。許多人依賴于被稱為格的幾何結構，即類似于晶體中重復的三維原子圖案的點陣，但它們有數百或數千個維度。格由一組箭頭或向量定義，這些箭頭或向量以不同的組合進行添加而形成模式。對于相同的格，其起初可以由短的、幾乎垂直的、易于處理的矢量組成，也可以由長的、幾乎平行的、很難處理的矢量組成。這些方案中，Alice的私鑰是簡單的格基礎，而她的公

在鑰是定義相同模式的混亂密鑰。為了將每個信息比特傳遞給Alice，Bob可以向她發(fā)送多維空間中點的坐標，該坐標在接近格的點來表示0，在距格點較遠的地方表示1。通過使用雜亂無章的公鑰，即使是量子計算機也無法幫助Eve搞清楚這個點離格有多近。然而，Alice可以很容易做到這一點，因為她持有簡單的私鑰?！案衩艽a學是非?；钴S的領域，因為它是如此的多功能?！钡聡_姆施塔特技術大學的計算機科學家尼娜·賓德爾（Nina Bindel）說。

一些研究人員正在研究更古老的算法。假設您想要在互聯網上傳輸一串字符，但是擔心一些0和1可能會在不經意間翻轉。您可以通過使用有冗余的較長字符串來防止這一點，而這些冗余可以用來更正錯誤。這樣的糾錯碼可以用由0和1組成的網格或矩陣來表示，在20世紀70年代，密碼學家證明了它們可以加密信息。

在這種方案中，Alice的私鑰是糾錯矩陣，而她的公鑰是它的加擾版本。Bob的信息是比特字符串，他將公共矩陣應用于該字符串以獲得不同的字符串。他翻轉幾個隨機的比特以獲得好的度量，并將結果發(fā)送給Alice。即使Eve知道Bob的雜亂無章的矩陣，也無法撤銷他的動作。但是，有了更清晰的矩陣（為了糾正翻轉部分而設計），Alice就能做到。蘭格說，糾錯方案已經進行了比格更多的測試，即使Eve有一臺量子計算機，他也可以應對。多數后量子算法比現有標準需要更大的密鑰或更多的

大計算時間。荷蘭拉德堡德大學的密碼學家西蒙娜·薩馬德吉斯卡（Simona Samardjiska）和他的同事正在開發(fā)一種基于二次方程的靈活的小密鑰方案，它可能更適合于數字簽名而不是發(fā)送秘密信息。

就像任何公開密鑰系統(tǒng)一樣，沒有證據表明后量子方案是不可破解的，甚至在傳統(tǒng)的計算機上也是如此。因此，微軟公司的密碼學家布萊恩·拉麥克奇亞（Brian LaMacchia）表示，新算法不會取代現有的算法，而是很可能與它們一起運行

NIST的數學家達斯汀·穆迪（Dustin Moody）說，最快于2022年，NIST就可以將加密和數字簽名的兩種或三種算法標準化。他表示，該機構希望有選擇。穆迪說：“如果發(fā)現一些新的攻擊破壞了所有的格，我們仍有一些東西可以依靠?！?NIST為聯邦政府設定了標準，但“世界上很多國家都使用NIST標準化的加密技術?！盋loudFlare是加州舊金山的一家互聯網安全和性能公司，為2 000萬的企業(yè)及客戶提供服務。該公司已經開始在網絡瀏覽器中試用其中的一些算法。但Cloudflare的應用密碼學家尼克·沙利文（Nick Sullivan）說，對其全面的采用將需要數年時間。

拉麥克奇亞說，在過去的30年里，他在密碼學方面經歷了4到5次重大變化，包括10年前從RSA轉向與數學相關但更安全的接任者?！斑@個在性質上是不同的，這要復雜得多?！蓖ㄟ^難以察覺的方式，加密用戶——也就是說幾乎每個人——將會知道這一變化進展順利。