科學大家|保護信息安全的密碼 背後的原理你真懂嗎？

　　2019年03月01日 09:15 科學大家

　　

　　出品| 新浪科技《科學大家》

　　撰文| 王明生 中國科學院信息工程研究所研究員

　　密碼學（Cryptography）是一門古老而年輕的科學，它的起源可以追溯到古羅馬時代約公元110年的愷撒（Caesar）加密。然而，直到1949年Claude Elwood Shannon發表了《保密系統的通信理論》這篇劃時代的論文，才標誌著現代密碼學的誕生。經典密碼學所使用的密碼設計和分析方法不是基於數學推理而是依賴密碼學家的直覺和靈感。

　　

　　凱撒密碼盤

　　1976 年，Diffie 和Hellman 發表了一篇影響力巨大的「密碼學新方向」的文章。它標誌著公鑰密碼學的誕生，從此密碼學走出秘密領域，進入公開研究領域。在此之前，人們完全依靠彼此共享的秘密密鑰來實現秘密通信，而公鑰密碼技術使得通信雙方在沒有事先共享任何秘密信息的情況下能夠通信。在對稱密鑰加密情況下，兩方同意共享一個可同時用於（任何一方）加密和解密的秘密密鑰k。公鑰加密在這個意義上是非對稱的，具體來說，接收方產生一對密鑰（pk，sk），被分別稱為公鑰和私鑰，發送方用公鑰將消息加密后發送給接收方，接收方用自己的私鑰解密收到的密文。

　　

　　公鑰pk可以是通信發生之前，接收方以明文形式發給發送方。需要強調的是：兩方之間的通信通道可以是公開的，但假設是認證的，即敵手無法修改接收方發給發送方的公鑰（特別是敵手不能用自己產生的密鑰去替換），這個問題可以用數字簽名解決；也可以是接收方廣泛地傳播它的公鑰pk，比方說通過她的個人網頁，將公鑰放置在她的名片中，公布在報紙上面，或者是放在某個公共目錄使得任何想和接收方秘密通信的人都可以查到她的公鑰。這種應用模型中，所有通信中多個發送方可以利用同樣的pk與接收方多次通信。

　　由於公鑰pk是公開的，因此公鑰加密的安全不依賴於公鑰的安全性，而僅僅依賴於私鑰的安全性。與之相比，對稱密鑰加密假設了所有密鑰的完全保密性，即通信雙方必須共享密鑰，並且不允許第三方獲得此密鑰。公鑰加密方案可使多個發送者與單個接受者秘密通信，與之不同的是，依靠雙方共享密鑰的對稱密鑰加密只能讓兩方進行秘密通信。公鑰加密體制的最主要的缺點是較對稱密鑰加密而言要慢至少2~3個數量級，因此，如果對稱密鑰加密是一種選擇（換言之，如果雙方能夠事先安全地共享一個密鑰），它就應當被使用。

　　

　　公鑰加密體制

　　不同種類的公鑰加密演演算法

　　自公鑰密碼體制問世以來，密碼學家們提出了多種公鑰加密方案，它們的安全性都是基於數學基礎問題的計算困難性。對於這些數學問題，如果利用已知的求解演演算法由公開信息計算出私鑰的時間越長，那麼基於這一數學問題的公鑰加密系統被認為是越安全。

　　傳統的公鑰加密演演算法，根據所基於的數學困難問題來分類，有以下三類系統目前被認為是安全高效的（不考慮具有量子計算能力的敵手）：1。大整數分解系統（代表性的有RSA）；2。離散對數系統（代表性的有DSA）；3。橢圓曲線離散對數系統（ECC）。

　　自從1978年RSA體制提出來以後，人們對大整數分解問題的研究產生了強烈的興趣，並取得了豐富的成果。在1985年，ElGamal型公鑰密碼體制提出以後，學術界又對有限域上離散對數的計算問題產生了濃厚的興趣。值得注意的是，大整數分解問題的求解和有限域上離散對數問題的求解在本質上具有某種一致性，因而基於RSA假設的RSA和基於有限域上離散對數假設的DSA的安全強度幾乎一致。

　　

　　經過人們的不斷努力，隨著計算機運算效率的迅速提升，目前人們對於這兩類問題的求解能力大大地提高，使得基於大整數分解的RSA體制受到很大的衝擊，密鑰長度為512比特的RSA不再認為是安全的（對於DSA也是如此），這就迫使RSA體制中使用的模數和基於有限域上離散對數問題的公鑰密碼體制中有限域的規模越來越大，同時需要更長的密鑰來保證系統安全，這造成運算速度的降低，如DSA體制的運算速度隨著其密鑰長度的增加將以指數級下降。

　　橢圓曲線密碼體制（Elliptic Curve Cryptography，ECC）是1985年由Koblitz和Miller分別提出的，利用基於有限域上橢圓曲線上點組成的加法群構造基於橢圓曲線離散對數問題的密碼體制，二十多年來人們對橢圓曲線離散對數問題的經典求解演演算法的研究幾乎沒有本質進展。

　　橢圓曲線密碼體制的安全性是建立在求橢圓曲線離散對數問題（Elliptic Curve Discrete Logarithm Problem，ECDLP）難解的基礎上。ECC與RSA、DSA相比有很多技術優點：橢圓曲線離散對數問題目前只存在指數時間的經典演演算法，而大整數分解和有限域上離散對數問題存在亞指數級的經典演演算法，這就體現在ECC比RSA的每比特密鑰的安全性能更高，密鑰長度160比特的ECC與1024比特的RSA、DSA有相同的安全強度，而210比特ECC與2048比特的 RSA、DSA具有相同的安全強度，即達到相同安全強度的ECC的密鑰大小和系統參數與RSA、DSA相比要小得多，意味著它所佔的存儲空間較小，且ECC的運算速率比RSA、DSA快得多。ECC的上述特點使得它在許多領域已經取代RSA，成為通用的公鑰加密演演算法，包括作為輕量密碼演演算法模塊和應用於網路傳輸層協議TLS等。

　　必須注意實際工程中實現的密碼不同於教科書式密碼。下面我們將介紹「教科書式RSA」加密和「教科書式ElGamal」加密，並分析其不安全性。

　　「教科書式RSA」加密方案

　　KeyGen：輸入1^n，隨機選擇兩個n比特的素數p，q，N=pq，∅（N）=（p-1）（q-1），選擇滿足gcd（e，∅（N））=1的e，計算d=e^（-1） mod∅（N），輸出公鑰pk=（N，e），私鑰sk=（N，d）。

　　

　　「教科書式ElGamal」加密方案

　　KeyGen：輸入1^n，執行多項式時間演演算法輸出一個循環群G，其階為q（其中‖q‖=n），生成元為g。然後選擇隨機的x←Z_q並且計算h≔g^x。公鑰是（G，q，g，h），私鑰是（G，q，g，x）。

　　

　　

　　上述兩個演演算法加解密的正確性能夠簡單地驗證。在分析它們的安全性之前，我們必須明確攻擊場景。根據敵手的能力，主要有以下幾種攻擊類型：

　　（1）唯密文攻擊（Ciphertext-only attack），這是最基本的攻擊方式，表示敵手只能觀察到密文，並且試圖確定相應的明文；

　　（2）已知明文攻擊（Known-plaintext attack），這裡敵手學習一個或者多個使用相同密鑰加密的明密文對，目標是確定其它密文對應的明文；

　　（3）選擇明文攻擊（Chosen-plaintext attack，CPA），這種攻擊中，敵手能夠選擇明文，並得到相應的密文，試圖確定其它密文對應的明文；

　　（4）選擇密文攻擊（Chosen-ciphertext attack，CCA），這最後一種攻擊類型是指敵手甚至可以選擇密文並得到相應的明文，目標依然是確定其他密文的明文。

　　前兩種攻擊類型是被動的，符合實際場景的，唯密文攻擊在實踐中最容易實現，敵手唯一要做的就是竊聽傳輸密文的公共通道；而已知明文攻擊符合實際是因為不是所有加密的消息都是保密的，至少不是無限期的保密，舉個例子，通信開始是雙方可能通常加密「hello」消息，又或者加密可用來保證某機密直到公開的那一天，任何竊聽並獲得密文的人，將在後來獲得相應的明文。

　　相對而言，后兩種攻擊類型是主動的，敵手能夠適應性地有選擇地請求加密和解密，這是否代表了一個真正值得關注的現實的敵對威脅？針對選擇明文攻擊（CPA），有個二戰時期的軍事歷史說明了這一點。

　　在1942年的5月，美國海軍的密碼專家截獲了一份通信消息，該消息中包含了一份密文欄位「AF」，他們相信這對應著明文「中途島」，認為日軍正計劃對中途島發動攻擊，然而華盛頓的指揮者並不相信，通常認為中途島不可能成為攻擊的目標。於是海軍密碼專家命令在中途島的美軍軍隊發送一個明文消息，說他們的淡水供給不足。日軍截獲了該消息，立刻報告給其上級「AF」淡水不足。於是確信「AF」的確就是中途島，美軍迅速派三架運輸機抵達該位置，結局就是中途島被解救了，日軍受到了重創，這裡海軍密碼專家就完成了一次經典的選擇明文攻擊。

　　至於選擇密文攻擊（CCA），我們可以設想一個用戶和他們的銀行通信的場景，其中所有的通信都是經過加密的。如果該通信沒有被認證，則敵手能夠代表用戶發送特定密文，銀行將解密這些密文，敵手可能能夠從結果中掌握某些信息。此外，加密經常在高級別的協議中使用；比如，一個加密方案可能被作為認證協議的一部分來使用，其中一方發送一份密文給對方，對方解密返回結果。在這種情況下，一個誠實方可能正好扮演了一個解密預言機的角色，所以該方案必須是CCA安全的。

　　公式詳解「教科書式RSA加密」方案

　　明顯可以看出「教科書式RSA加密」方案是確定性加密，因此不是CPA安全的。儘管「教科書式ElGamal加密「在判定Diffie-Hellman（DDH）假設下被嚴格證明是CPA安全的，卻容易受到選擇密文攻擊。選擇密文攻擊（CCA）安全的一個密切的相關問題就是密文的可延展性，直觀上來解釋，即一個加密方案擁有這樣一個屬性：給定未知消息m的密文c，可以得到未知消息m_1的密文c_1，其中m和m_1具有某種已知的關聯。「教科書式RSA」加密就容易出現上面的攻擊，比方說敵手觀察到使用公鑰〈N，e〉加密的密文c=m^e mod N，則有密文c_1=2^e c mod N，解密為2m mod N，因為〖c_1〗^d≡〖（2^e m^e ） 〗^d≡2^ed m^ed≡2m mod N。對於「教科書式ElGamal加密」，比如說敵手A攔截了使用公鑰pk=（G，q，g，h）加密消息m的密文c=〈c_1，c_2 〉，這意味著c_1=g^y，c_2=h^y∙m。一些隨機選擇的y←Z_q對敵手來說是未知的，但敵手可以計算〖c_2〗^/=c_2∙m^/，則很容易知道密文c^/=〈c_1，〖c_2〗^/ 〉是消息m∙m^/的密文，這個觀察結果就容易引起選擇密文攻擊。有人可能會反對：如果接收者收到兩個密文c、c^/，並且密文的前一個元素相同，將產生懷疑（確實，對於正常生成的密文，密文的第一個元素相同的概率是可忽略的）。然而，敵手很容易避免其發生，令c_1，c_2，m，m^/如上面所述，敵手可以選擇隨機的y^/←Z_q，並且設〖c_1〗^（（2））=c_1∙g^（y^/ ），〖c_2〗^（（2））=c_2∙h^（y^/ ）∙m^/，容易驗證c^（（2））=〈〖c_1〗^（（2）），〖c_2〗^（（2）） 〉是消息m∙m^/的密文，且密文的第一個元素是完全隨機的。

　　

　　依據上述分析，「教科書式RSA加密」形式簡單高效，但是不滿足密碼的安全要求。事實上，RSA實驗室公鑰加密標準PKCS#1v1.5版本，利用了填充加密的原理，對於一個常見形式的公鑰pk=〈N，e〉，令k為N的位元組長度，即k是一個滿足2^8（k-1） ≤N

　　儘管至今還沒有基於RSA假設的證明，PKCS#1v1.5仍然被認為是CPA安全的，但是對該方案的選擇密文攻擊已被證實。因為標準中的填充部分是以特別的方式完成（且不由任意比特組成），如果密文沒有正確的格式，將會返回一個錯誤消息，這些錯誤消息的存在足以發起選擇密文攻擊：給定一個正確生成的密文c，攻擊者可以恢復出明文m，方法是通過提交多個密文並且觀察哪個密文能成功解密，哪個會產生錯誤。由於這類信息可以來源於當接收到不正確格式的消息時，發出錯誤消息的伺服器，因此在實踐中是可行的。

　　也就是說，基於RSA假設的高效且CCA安全的方案還不存在。密碼學家們為了提高現有方案的效率，提出新的假設，並且探索使用現有的假設，能夠達到的最高效率上界。在實際中獲得很大成功的一種方法，是在「完全嚴格的安全性證明」和「沒有證明」之間提供一個「中間地帶」。該方法就是在證明密碼學方案的安全性中，引入了一個理想模型，最流行的例子就是隨機預言機（Random Oracle，RO）模型。

　　依此，密碼學家們構造了隨機預言機模型下的CCA安全的RSA加密，進一步，為了消除最初版本方案中密文比Z_N^*中的單個元素要長（即使是加密一個短消息時）的缺陷，結合最優非對稱填充（OAEP）技術，構造了RSA-OAEP加密方案，修訂了之前的PKCS#1v1.5標準。儘管舊版本由於兼容性仍然被廣泛使用，但現在新的實現系統應該傾向於這個更新后的版本。

　　相對來說，「教科書式ElGamal」加密方案不僅有效並且能夠基於DDH假設證明是安全的，卻沒有在實踐中得到廣泛採用，或許因為有限域上存在亞指數演演算法求解離散對數問題。而工程實現ElGamal式加密時，出於安全和效率的考慮，現在廣泛使用ECC，至於實現的標準可以參考商用密碼演演算法標準-SM2橢圓曲線公鑰密碼演演算法或者美國國家標準與技術研究所（National Institute of Standards and Technology，NIST）頒布的ECC標準。

　　

　　抗量子計算機攻擊的公鑰密碼方案提上日程？

　　前面介紹了網路時代為了保護被傳輸數據的機密性（Confidentiality）而廣泛使用的公鑰加密體制，它們的安全性或者基於大整數分解問題的困難性，或者基於離散對數問題的困難性。然而，1994年美國數學家Peter Shor在量子計算模型下提出一個演演算法使得解決以上數學困難問題成為可能。Shor演演算法在量子計算機上可以在多項式時間內解決大整數分解與離散對數問題。這意味著，一旦量子計算機或者針對大整數分解問題或者離散對數問題的專用量子計算機被製造出來，將會完全破解基於這些困難問題的公鑰加密演演算法。二零一七年三月三日，谷歌量子AI實驗室三名科學家Mohseni、Read和Neven在《自然》雜誌上宣稱「量子計算機五年內將實現商用化」。雖然文章同時指出，真正的量子計算機所需要的技術還需要十年左右的時間才能完成，但這已經使得傳統的公鑰密碼系統的安全性存在巨大的風險。因此，迫切需要設計下一代的抗量子計算機攻擊的公鑰密碼方案。

　　對於某些問題，經研究表明量子演演算法相對於傳統演演算法並沒有明顯的優勢。目前，主要的抗量子計算機攻擊的公鑰密碼方案的候選有基於格的、基於編碼的、基於哈希函數的、基於多變數的密碼系統等。其中，格上的若干困難問題，如最短向量問題（Shortest Vector Problem，SVP）、獨立最短向量問題（Shortest Independent Vector Problem，SIVP）等，還沒有發現能夠在多項式時間內解決的量子演演算法，因此被認為其可以抵抗量子計算攻擊。

　　另一方面，格上的困難問題之間存在平均情形困難性（Average-case Hardness）與最差情形困難性（Worst-case Hardness）之間的歸約關係（簡單來說，Worst-case Hardness屬於計算複雜性理論範疇，密碼方案直接使用的密碼學原語（cryptographic Primitive）我們希望是Average-case Hardness），且在格上的數學運算主要是矩陣向量乘法，計算簡單高效，可并行實現。此外，相比於基於編碼、哈希函數、多變數等其他的抗量子計算攻擊的公鑰方案，以格為基礎的數學結構，不僅可以構造加密方案，也可以構造簽名方案、密鑰協商方案。這意味著，基於格的公鑰系統可以部署多個公鑰密碼方案模塊，有利於整個公鑰密碼系統在通信網路系統上的功能整合。綜合上述諸多優勢，基於格的加密方案已經成為抗量子計算攻擊的最有希望的候選演演算法之一。

　　

目前，已有的基於格的加密方案主要分為兩大類，一類是NTRU密碼系統，其方案的實現效率較高，但缺乏可證明安全性。另一類是基於格上平均情形下的困難問題如帶誤差學習問題（Learning with Errors， LWE），環上帶誤差學習問題（Ring Learning with Errors， RLWE）等的加密方案，也是基於格的加密體制的一個熱門研究領域。基於平均情形下困難問題的主要加密方案包括基於一般格的最早的Regev 加密方案、對偶Regev（dual-Regev）加密方案以及基於理想格的RLWE的加密方案等。在這裡，我們就不深入介紹了。

　　

　　截止2017年11月30日，NIST已經完成了第一輪后量子密碼（Post-Quantum Cryptography，PQC）（也被稱為是抗量子的或量子安全的密碼）演演算法的徵集。到目前為止，23個PKE/KEM的格密碼提案，有3個方案（Compact-LWE，HILA5，Odd Mantattan）已經被攻破，4個方案被攻擊候已提出解決辦法，還有2個方案存在其它問題；5個Signature的格簽名提案的Comments較少，目前沒有被攻破。

　　正如NIST所說：「后量子標準化的發展過程不應該被視為競爭，某些情況下，也許不可能作出一個候選方案優於另一個方案的具有良好支撐的判斷。相反，NIST將以公開和透明的方式對提交的演演算法進行深入全面的分析，並鼓勵密碼團隊共同進行分析和評估。這種結合的分析方式將影響NIST對后量子標準化的後續發展的決策。

　　NIST預計將進行多輪評估，為期3至5年，而且由於目前科學對於量子計算能力的認知還遠遠不夠全面，這個評估過程將比SHA-3和AES的評選更為複雜。此外，一些候選后量子密碼系統可能有完全不同的設計屬性和數學基礎，不同類型之間的候選演演算法的比較將是困難甚至不可能的。雖然距離大規模地應用量子計算機還有一段路要走，但由於從傳統公鑰密碼體制到后量子密碼的過渡不太可能是一個簡單的「drop in」，開發、規範和部署新的后量子密碼系統將需要付出極大的努力。因此，應當及早地進行這個過渡。」

　　現在到未來幾年時間，正是后量子密碼標準化的黃金階段，感興趣的研究人員應當抓住這個機遇，踴躍地參與其中！（圖片由編輯所加，來源於網路）

想想都不錯