面向后量子時代的密碼技術
?
4月26日，觀眾在第二屆中國（安徽）科技創新成果轉化交易會上拍攝“九章”光量子計算原型機模型
?
后量子密碼學是一個充滿挑戰和機遇的領域，后量子密碼學的研究與應用不但對密碼學，也將對未來的第三代互聯網和元宇宙的發展帶來深遠影響。
文/高承實
編輯/吳美娜
今年1月，國際標準化組織互聯網工程任務組（IETF）啟動了后量子協議使用（PQUIP）工作組，以協調后量子時代加密協議的使用；3 月，抗量子網絡安全供應商 QuSecure 聲稱已率先實現了經由衛星、能抵御量子計算攻擊的端到端加密通信，這也是美國首次采用后量子密碼技術保護衛星數據通信；8 月，美國國家標準與技術研究院（NIST）發布了后量子密碼學（PQC）標準草案，旨在形成一個在未來免受量子網絡攻擊的全球框架……
在全球范圍內，傳統的密碼技術受到了量子技術發展帶來的顯見挑戰，有關量子時代密碼技術的討論日漸增多，相關項目也正在落地。其實，量子計算出現之后，如何確保密碼的安全就開始成為學術界和業界的持續關注焦點。
密碼技術的分類和發展
在量子時代，我們的密碼還安全嗎？回答這一問題，需要考慮密碼技術的類別，因為不同類別密碼技術建立的數學基礎不同，這些密碼算法所能承受的量子“攻擊”程度也不相同。
密碼學的發展經歷了古典密碼學、近代密碼學和現代密碼學。我們現在所說的密碼學一般都是指現代密碼學。從密碼體制上，現代密碼一般被分為對稱密碼和非對稱密碼兩種，此外還有確保通信內容完整性的哈希函數。
根據對明文加密處理方式的不同，對稱密碼又可分為分組密碼和流密碼（也稱序列密碼）。分組密碼是先按一定長度（如64比特、128比特等）對明文進行分組，再以組為單位實施加/解密運算；流密碼則不進行分組，而是按位直接對報文進行加解密運算。
對稱密碼體制要求加密密鑰和解密密鑰相同，或本質上相同，這也是其被稱為對稱密碼的原因。對稱密碼要求密鑰必須被嚴格保密，否則就無法實現加密信息的機密性。因此，密碼通信系統的安全也就完全依賴于密鑰的保密。加密以后的報文可以在不安全的信道上傳輸，但加解密的密鑰卻必須通過安全可靠的信道傳遞。因此，對稱加密體制的最大弱點，就是保密通信的一方必須通過安全可靠的信道把密鑰告訴對方，否則對方無法對接收到的保密信息解密。由此，密鑰的保存和傳遞就成了最頭疼的問題，尤其是在通信參與方比較多，又要求兩兩之間都實現保密通信的情況下就更是如此。
非對稱密碼彌補了對稱密碼體制密鑰管理上的不足。1976年11月，現代密碼學之父、美國學者惠特菲爾德·迪菲和另一位美國密碼學家馬丁·埃爾曼發表了論文《密碼學的新方向》，探討了無需傳輸密鑰的保密通信和簽名認證體系問題，開創了公鑰密碼學，也就是非對稱密碼。在非對稱密碼體制中，每個通信參與方都有兩個密鑰，其中一個密鑰公開，稱為公鑰，另一個密鑰不公開，稱為私鑰。通信時由其中一個密鑰對信息加密，可以用另外一個密鑰解密，而且由公鑰不能推導出私鑰。每一個通信參與方都可以用接收方的公鑰對信息加密，之后只有信息的真正接收方才能夠用自己的私鑰完成對加密信息的解密。同時，信息發送者如果用自己的私鑰對信息簽名，任何接收方也都可以用發送者的公鑰實現對信息發送者身份的驗證。因此，非對稱密碼體制在不需要對密鑰進行保密傳輸的情況下就實現了保密通信。
公鑰密碼學的發展是密碼學發展史上最偉大的一次革命，也許可以說是唯一的一次革命。一般來說，公鑰密碼的安全性由相應數學問題在計算機上的難解性來保證，比如，廣為使用的非對稱密碼算法RSA的安全性就是建立在大整數素因子分解在計算的困難性上的。
哈希函數是一類特殊的函數，它將任意長度的信息輸入，輸出為固定長度的比特串，該輸出稱為哈希值。這種轉換是一種壓縮映射，也就是說，哈希值的空間會遠小于輸入信息的空間，因此不同的輸入會被映射為相同的輸出，但算法的復雜性使得通過這個輸出卻不可能確定到對應的輸入。簡單說，哈希函數就是一種將任意長度的消息壓縮到某一固定長度的消息摘要的函數。哈希函數在密碼學中有廣泛的應用，可以驗證信息的完整性，保證信息的不可篡改性。哈希函數在區塊鏈系統中也得到了廣泛使用。
如何衡量密碼算法的安全性？
密碼算法在安全性上有兩個不同的指標，一是無條件安全，也稱為完善保密性；二是計算安全，又稱實際保密性。
如果利用已知的甚至是未知的最好的算法破譯一個密碼系統需要至少N（某一確定的、很大的數）次運算，就稱該系統為計算上安全的，也就是該算法具有實際保密性。無條件安全是指不論提供的密文有多少，密文中所包含的信息都不足以唯一地確定其對應的明文，即使具有無限計算資源（諸如時間、空間、資金和設備等）的密碼分析者也無法破譯某個密碼系統。1945年美國數學家克勞德·E.香農在其發布的《密碼學的數學原理》中，嚴謹地證明了一次性密碼本（也稱為“弗納姆密碼”，其基本原理是通過將與明文等長、完全隨機，且只使用一次的密鑰與明文進行異或運算來實現加密和解密），具有無條件安全性。但這種絕對安全的加密方式在實際操作中需要消耗大量資源，難以大規模使用。
人們在現實中使用的密碼算法，大部分都是計算安全的。因此，密碼算法在使用時的安全性也需要隨著外部計算能力的提升而不斷被加強。
比如對稱分組加密算法，美國國家標準局最開始采用的是DES算法，其有效密鑰長度是56比特，這也就意味著在算法安全的要求下，破解這個算法需要進行256運算。不過，隨著計算能力的提升，原來用大型機甚至巨型機也難以破解的DES，目前個人電腦已可以輕易將其破解。因此，分組加密算法的標準也由DES進化到了AES，AES 每組的分組長度雖然都是128比特，但其密鑰長度可以是128、192甚至是256比特，這就使得野蠻破解該算法需要更多次的運算。
再比如非對稱密碼算法。原來可能256比特，最多512比特長度密鑰的RSA算法就足夠用了，但由于計算能力的大幅提升，目前1024比特以下的RSA算法已經不再被建議使用了。根據國際標準，目前常用的RSA算法密鑰長度的范圍是1024比特到4096比特，2048比特的密鑰是目前RSA算法中最常用的。
后量子時代的密碼技術路線
如果說以往密碼算法面臨的安全威脅主要來自傳統方式下的計算能力提升，那么當前密碼算法面臨的最大威脅可能就來自量子計算帶來的算力提升了。傳統方式下計算能力的提升，并不會從根本上對原有的密碼加密方式帶來根本性挑戰，但量子力學態疊加原理使得量子計算可以在效率上相比于經典計算機具有更大潛力。
量子計算在一些特定問題上已經顯現出遠優于傳統計算的能力。據Quantum Algorithm Zoo網站統計，目前已有數百個基于量子計算模式的算法被用于對傳統密碼算法的破解，其中對傳統密碼算法有較大影響的量子算法主要有Shor算法、Grover算法、和Simon算法，這些算法對當前廣泛使用的基于傳統數學難題的密碼算法構成了嚴重威脅，導致部分在傳統計算模型下可證明安全的密碼模型在量子時代不再安全。
為了應對量子技術發展帶來的挑戰，后量子密碼學作為一種新興的密碼技術應運而生。后量子密碼學研究的目標，是提供一種能夠在量子計算時代仍然保持安全性的密碼算法和協議。后量子密碼學也是基于量子計算仍難以有效求解的數學難題而建立起來的，目前后量子密碼算法的主要技術路線有基于哈希、編碼、多變量、格和同源等問題的方案。
需要指出的是，對稱密碼算法和哈希函數在量子時代仍能夠保持一定的安全強度，可以通過像上面所說的增加密鑰長度或哈希值長度的方式對抗量子攻擊。
基于哈希算法使用Merkle樹等結構生成數字簽名，是后量子密碼算法的一類，其安全性依賴于哈希函數的安全性，而不是依賴于數學問題的困難性假設。如果所采用的哈希函數算法被攻破，只需將哈希函數更新為更安全的函數算法，就能確保簽名算法的安全性。
基于編碼的算法利用糾錯碼構造單向函數，是后量子密碼算法的第二類，其安全性依賴于編碼理論中的SD（Syndrome Decoding，伴隨式解碼）和LPN（Learning Parity with Noise，帶噪聲的子空間，一個假設問題）等難解問題，可用于構建加密算法、數字簽名和密鑰交換方案等。
基于多變量的密碼算法使用有限域上的多變量二次多項式組構建加密、簽名和密鑰交換，其安全性依賴于求解多變量方程組的困難性。
基于格的密碼算法基于格中的難解問題，可以用于構建加密、數字簽名和密鑰交換等密碼方案。這類方案具有比較快的計算速度和較小的通信開銷，在安全性、公私鑰大小和計算速度方面取得了比較好的平衡，有望成為量子計算時代的標準。
基于同源的密碼算法則利用了超奇異橢圓曲線同源問題構建加密和密鑰交換等密碼方案，這類方案具有較短的公私鑰，但運行效率較低。
目前學術界和業界對抗量子攻擊的對稱密碼研究相對較少，設計方案只有Saturnin等少量方案。
中國在2018年啟動了全國密碼算法設計競賽，其中非對稱算法部分征集到38個算法，經過形式審查、公開評議、檢測評估和專家評選，競賽最終評出14項優勝算法。其中11個密碼算法是基于格困難問題的算法，1個是基于編碼問題的非對稱加密算法，1個是基于超奇異橢圓曲線上同源問題的密鑰交換協議，還有1個是基于置換核問題的數字簽名算法。
總體上，后量子密碼學是一個充滿挑戰和機遇的領域，后量子密碼學的研究與應用不但對密碼學，也將對未來的第三代互聯網和元宇宙的發展帶來深遠影響。
（作者系密碼學博士、中國計算機學會高級會員）
來源：2023年11月29日出版的《環球》雜志 第24期
《環球》雜志授權使用，如需轉載，請與本刊聯系。
更多內容敬請關注《環球》雜志官方微博、微信：“環球雜志”。
