航芯技術(shù)分享 | 一文讀懂什么是量子密碼

被喻為“重要數(shù)據(jù)保險箱”的安全芯片已經(jīng)滲入人們生活的方方面面。隨著5G、物聯(lián)網(wǎng)、車聯(lián)網(wǎng)的迅速發(fā)展，為安全芯片開啟了新的應(yīng)用場景，同時也帶來了新的挑戰(zhàn)。

本文將帶大家深入了解安全芯片的核心，后量子密碼認證技術(shù)。

1、安全認證技術(shù)概述

安全認證技術(shù)是防止信息被篡改、刪除、重放和偽造的一種有效方法。它使接收者能夠識別和確認消息的來源和真?zhèn)?。目前認證技術(shù)主要有4種：

（1）數(shù)字摘要

（2）數(shù)字摘要+對稱密鑰認證

（3）數(shù)字摘要+非對稱密鑰認證

（4）數(shù)字證書認證

不過隨著量子計算機的發(fā)展，現(xiàn)有的絕大多數(shù)公鑰密碼算法（RSA、Diffie-Hellman、橢圓曲線等）能被足夠大和穩(wěn)定的量子計算機攻破，也就是說目前基于非對稱密鑰的認證技術(shù)都不安全，會被攻破。所以需要研究基于后量子密碼的認證技術(shù)。

1.1 數(shù)字摘要

該技術(shù)就是使用單向的HASH函數(shù)將需發(fā)送的消息摘要成為一串固定長度的數(shù)據(jù)，然后發(fā)送給接收方。

具體步驟如下：

（1）使用Hash函數(shù)計算消息的摘要，將其與消息一起發(fā)送。

（2）當(dāng)Bob收到消息，使用同樣算法計算摘要，與收到的摘要進行比較。

主要優(yōu)點：

（1）對消息的任何改變，摘要必然變化。

（2）單向函數(shù)：無法從摘要構(gòu)造出原文。

主要缺點：

（1）僅僅Hash沒法保證完整性。

（2）改變這個消息，重新計算摘要，用改變后的消息+摘要替換原來的報文。

1.2 數(shù)字摘要+對稱密鑰認證

該技術(shù)就是使用共享的對稱密鑰加密隨機數(shù)，再使用HASH函數(shù)將密文信息摘要成為一串固定長度的數(shù)據(jù)，然后發(fā)送給接收方。

具體步驟如下：

（1）通過安全通道，Bob和Alice共享一個密鑰。

（2）Bob發(fā)送一個隨機數(shù)給Alice。

（3）Alice用共享密鑰加密隨機數(shù)，并對加密結(jié)果進行HASH運算，HASH值發(fā)送給Bob。

（4）Bob也用共享密鑰加密隨機數(shù)，并對加密結(jié)果進行HASH運算，計算的結(jié)果與接收的HASH進行比較，相等則表示是Alice發(fā)送過來的。

主要優(yōu)點：

（1）在確保密鑰安全下，可以防止信息被篡改。

（2）分組加密性能快。

主要缺點：

（1）需要通過安全通道共享密鑰。

（2）雙方都保存密鑰，只要一方泄漏密鑰即可破解信息。

1.3 數(shù)字摘要+非對稱密鑰認證

該技術(shù)就是使用自己的私鑰對發(fā)送信息進行簽名，然后接收方使用公鑰驗證這個簽名。

具體步驟如下：

（1）Bob拿到Alice的公鑰，發(fā)送一個隨機數(shù)給Alice。

（2）Alice收到隨機數(shù)后用自己的私鑰進去簽名，簽名結(jié)果發(fā)送給Bob。

（3）Bob使用Alice的公鑰對接收的簽名進行驗簽，如果驗簽通過則確認是Alice發(fā)出來的信息。

主要優(yōu)點：

（1）公鑰可以公開，無需保密。

（2）只需發(fā)送方保存自己的私鑰。

主要缺點：

（1）如何確定公鑰來自Alice？易受中間人攻擊。

1.4 數(shù)字證書認證

該技術(shù)就是需要有一個CA（可信的授權(quán)中心），發(fā)送方Alice從CA申請證書，CA確認Alice確實是Alice，生成和發(fā)布Alice的證書。Alice的證書包含：

· 主題Subject：需要鑒別的個人Alice

· Alice的公鑰public key

· 數(shù)字簽名digital signature：CA對證書的簽名

· 發(fā)布者Issuer：驗證了信息并發(fā)布證書的實體

· 簽名算法Signature Algorithm

具體步驟如下：

（1）Bob申請Alice的證書公鑰。

（2）Alice把自己的證書發(fā)送給Bob，Bob收到后使用CA公鑰驗證證書，并獲取得到Alice的公鑰。

（3）Bob拿到Alice的公鑰后，發(fā)送一個隨機數(shù)給Alice。

（4）Alice收到隨機數(shù)后用自己的私鑰進去簽名，簽名結(jié)果發(fā)送給Bob。

（5）Bob使用Alice的公鑰對接收的簽名進行驗簽，如果驗簽通過則確認是Alice發(fā)出來的信息。

主要優(yōu)點：

（1）可以抵抗中間人攻擊，確認Alice的公鑰。

主要缺點：

（1）無法抵抗量子計算機攻擊。

2、后量子密碼算法概述

后量子密碼是能夠抵抗量子計算機對現(xiàn)有密碼算法攻擊的新一代密碼算法。實現(xiàn)后量子密碼算法主要有以下 4 種途徑 ：

（1）基于哈希 （Hash-based）：最早出現(xiàn)于1979 年，主要用于構(gòu)造數(shù)字簽名。代表算法：Merkle 哈希樹簽名、XMSS、Lamport 簽名等。

（2）基于編碼 （Code-based）：最早出現(xiàn)于1978 年，主要用于構(gòu)造加密算法，代表算法：McEliece。

（3）基于多變量（Multivariate-based）：最早出現(xiàn)于1988年，主要用于構(gòu)造數(shù)字簽名、加密、密鑰交換等。代表方法/算法：HFE （Hidden Field Equations）、Rainbow （Unbalanced Oil and Vinegar （UOV） 方法）、HFEv- 等。

（4）基于格（Lattice-based）：最早出現(xiàn)于1996 年，主要用于構(gòu)造加密、數(shù)字簽名、密鑰交換，以及眾多高級密碼學(xué)應(yīng)用，如：屬性加密 （Attribute-based encryption）、陷門函數(shù) （Trapdoor functions）、偽隨機函數(shù) （Pseudorandom functions）、同態(tài)加密 （Homomorphic Encryption） 等。代表算法：NTRU 系列、NewHope （Google 測試過的）、一系列同態(tài)加密算法 （BGV、GSW、FV 等）。由于其計算速度快、通信開銷較小，且能被用于構(gòu)造各類密碼學(xué)算法和應(yīng)用，因此被認為是最有希望的后量子密碼技術(shù)。

當(dāng)參數(shù)選取適當(dāng)時，目前沒有已知的經(jīng)典和量子算法可以快速求解這些問題。

再次強調(diào)，這些算法的安全性，依賴于有沒有可以快速求解其底層數(shù)學(xué)問題或直接對算法本身的高效攻擊算法。這也正是量子計算機對于公鑰密碼算法有很大威脅的原因。

除這4種問題之外，還有基于超奇異橢圓曲線 （Supersingular elliptic curve isogeny）、量子隨機漫步 （Quantum walk） 等技術(shù)的后量子密碼構(gòu)造方法。另外，對稱密碼算法在密鑰長度較大時 （例如 AES-256），也可被認為是后量子安全的。

為什么上面列的 4 種是最重要的？因為這 4 類途徑是最能構(gòu)造出公鑰密碼學(xué)中已有的各類算法的后量子版本，甚至還能超越（例如基于格的（全）同態(tài)加密）等。

1.1 基于哈希 （Hash-based）

基于哈希的簽名算法由 Ralph Merkel 提出，被認為是傳統(tǒng)數(shù)字簽名 （RSA、DSA、ECDSA 等 ） 的可行代替算法之一?；诠５暮灻惴ㄓ梢淮涡院灻桨秆葑兌鴣?，并使用 Merkle 的哈希樹認證機制。哈希樹的根是公鑰，一次性的認證密鑰是樹中的葉子節(jié)點?；诠５暮灻惴ǖ陌踩砸蕾嚬：瘮?shù)的抗碰撞性。由于沒有有效的量子算法能快速找到哈希函數(shù)的碰撞，因此（輸出長度足夠長的）基于哈希的構(gòu)造可以抵抗量子計算機攻擊。此外，基于哈希的數(shù)字簽名算法的安全性不依賴某一個特定的哈希函數(shù)。即使目前使用的某些哈希函數(shù)被攻破，則可以用更安全的哈希函數(shù)直接代替被攻破的哈希函數(shù)。

1.2 基于編碼 （Code-based）

基于編碼的算法使用錯誤糾正碼對加入的隨機性錯誤進行糾正和計算。一個著名的基于編碼的加密算法是 McEliece 。McEliece使用隨機二進制的不可約 Goppa碼作為私鑰，公鑰是對私鑰進行變換后的一般線性碼。Courtois、Finiasz 和Sendrier 使用 Niederreiter 公鑰加密算法構(gòu)造了基于編碼的簽名方案?；诰幋a的算法（例如 McEliece）的主要問題是公鑰尺寸過大?；诰幋a的算法包括加密、密鑰交換等。

1.3 基于多變量 （Multivariate-based）

基于多變量的算法使用有限域上具有多個變量的二次多項式組構(gòu)造加密、簽名、密鑰交換等算法 。多變量密碼的安全性依賴于求解非線性方程組的困難程度，即多變量二次多項式問題。該問題被證明為非確定性多項式時間困難。目前沒有已知的經(jīng)典和量子算法可以快速求解有限域上的多變量方程組。與經(jīng)典的基于數(shù)論問題的密碼算法相比，基于多變量的算法的計算速度快，但公鑰尺寸較大，因此適用于無需頻繁進行公鑰傳輸?shù)膽?yīng)用場景，例如物聯(lián)網(wǎng)設(shè)備等。

1.4 基于格 （Lattice-based）

基于格的算法由于在安全性、公私鑰尺寸、計算速度上達到了更好的平衡，被認為是最有前景的后量子密碼算法之一。與基于數(shù)論問題的密碼算法構(gòu)造相比，基于格的算法可以實現(xiàn)明顯提升的計算速度、更高的安全強度和略微增加的通信開銷。與其他幾種實現(xiàn)后量子密碼的方式相比，格密碼的公私鑰尺寸更小，并且安全性和計算速度等指標(biāo)更優(yōu)。此外，基于格的算法可以實現(xiàn)加密、數(shù)字簽名、密鑰交換、屬性加密、函數(shù)加密、全同態(tài)加密等各類現(xiàn)有的密碼學(xué)構(gòu)造?；诟竦乃惴ǖ陌踩砸蕾囉谇蠼飧裰袉栴}的困難性。

在達到相同（甚至更高）的安全強度時，基于格的算法的公私鑰尺寸比上述三種構(gòu)造更小，計算速度也更快，且能被用于構(gòu)造多種密碼學(xué)原語，因此更適用于真實世界中的應(yīng)用。近年來，基于LWE （Learning with Errors） 問題 和 RLWE （Ring-LWE） 問題的格密碼學(xué)構(gòu)造發(fā)展迅速，被認為是最有希望被標(biāo)準(zhǔn)化的技術(shù)路線之一。

3、格密碼算法概述

格（lattice）是一種數(shù)學(xué)結(jié)構(gòu)，定義為一組線性無關(guān)的非0向量（稱作格基）的整系數(shù)線性組合。具體來說，給定一組格基X1，。..。..，Xn對任意的整數(shù)C1，。..，Cn，C1X1+.。.+CnXn都是屬于這個格的向量，n稱為格的維數(shù)。例如，下圖表示了一個二維格和兩組不同的格基：X1

一個格的格基可以不是唯一的，例如，（（2，1），（1，1））和（（1，0），（0，1））都是二維整數(shù)格的一組格基。從上圖中可以看到，即使是定義了同樣的格的兩組格基，其長度也可能相差很大。數(shù)學(xué)家和密碼學(xué)家們普遍認為，對于一個維數(shù)足夠高的格，通過一組隨機選取的格基找到一組短格基，或得到一組線性無關(guān)的短格向量是困難的。這個問題稱作最短獨立向量問題（SIVP）。除此之外，還有一些其他的基于格的困難問題，如gap-SVP、BDD等。以上的困難問題通常屬于數(shù)學(xué)上的理論研究范疇。在密碼學(xué)的實際應(yīng)用當(dāng)中，格密碼算法所基于的困難問題更多采用容錯學(xué)習(xí)（LWE）問題。

LWE問題這樣表述：給定隨機矩陣A和向量As+e mod q，其中e是小的誤差項，q是模數(shù)（通常取較大的素數(shù)），從中恢復(fù)隨機的s是困難的。我們稱（A，b=As+e mod q）為LWE樣本，s為LWE秘密。容易看到，如果不存在誤差項e，這一問題即為求解線性方程組，是易解的。然而，當(dāng)引入誤差e之后，LWE問題可歸約到SIVP等格上的困難問題，即求解LWE問題的難度不低于求解格上的困難問題。

在應(yīng)用于密碼算法時，LWE問題存在一個很大的優(yōu)勢：存在“最壞情況到平均情況的歸約”，即求解平均情況下的LWE問題，其難度不低于最難的SIVP問題實例。在一些早期的公鑰密碼算法，如基于背包問題的密碼體制中，由于存在一些易解的背包問題實例，使得當(dāng)參數(shù)選取不恰當(dāng)時，密碼算法的安全性易受攻擊。而對于基于LWE問題的格密碼來說，由于存在最壞情況到平均情況的歸約，因而可以避免這種攻擊的產(chǎn)生。這為基于LWE問題設(shè)計的密碼算法帶來了很大安全性上的優(yōu)勢。

直接通過LWE問題構(gòu)造的密碼學(xué)方案效率并不是很高。更多的時候，我們將整數(shù)向量用多項式代替，得到多項式LWE或稱環(huán)LWE。一個環(huán)LWE樣本為（a，b=as+e mod q），其中a，s，e 均為多項式。環(huán)LWE的安全性建立在理想格中相應(yīng)數(shù)學(xué)問題困難性的基礎(chǔ)之上。盡管這些問題在困難性上面被認為不如格問題更可靠，但目前還沒有發(fā)現(xiàn)可以有效求解這些問題的算法。此外，還有可靠性介于LWE和環(huán)LWE問題之間的模LWE問題，以及這些問題的變種LWR、環(huán)LWR、模LWR問題。格密碼的安全性基本上都依賴于這些問題的困難性。

1.1 基于格的公鑰加密算法

通常，在一個基于LWE問題設(shè)計的密碼算法中，我們將LWE樣本作為公鑰使用，而將LWE秘密作為私鑰使用，這保證了公鑰不會泄露關(guān)于私鑰的信息。我們令公鑰為 （a，b=as+e mod q），私鑰為 s ，這里 a，b，s，e均為多項式，且s，e的系數(shù)相比于q是較小的（理論上s和e的系數(shù)應(yīng)取為離散正態(tài)分布，但在實際應(yīng)用中，出于實現(xiàn)上的效率和安全，s和e通常使用二項分布或均勻分布來模擬）。我們下面描述最基礎(chǔ)的格公鑰加密方案。

對于需要加密的消息，我們將消息記為 0-1 系數(shù)的多項式 m 。

（1）首先隨機選取系數(shù)較小的多項式 r，e1，e2

（2）計算密文c=ar+e1 mod q和 d=br+e2+m（q-1）/2 mod q

容易看到，由于 as≈b mod q，故ars≈br mod q，且 （ar+e1）s≈br+e2 mod q。當(dāng)s，e，r，e1，e2均足夠小時，可以保證br+e2-（ar+e1）s mod q的系數(shù)均不超過（q-1）/4。故d-cs和m（q-1）/2的每個系數(shù)之差都不超過（q-1）/4。我們可以通過這樣的方式從d-cs中還原m;若d-cs的第i個系數(shù)距離0更近，則令m的第i位為0；若 d-cs的第i位系數(shù)距離（q-1）/2更近，則令m的第i位系數(shù)為1。這樣我們成功通過私鑰s解密了密文（c，d），得到消息m。這一算法的安全性由兩個部分保證：其一是私鑰的安全性，由于公鑰為LWE樣本，通過公鑰不會泄露私鑰的信息；其二是消息的安全性，由于密文同樣為LWE樣本，通過密文在未知私鑰的前提下，不會泄露消息。以上描述的簡單方案是選擇明文安全，而非選擇密文安全的。對于具體的方案，則需要應(yīng)用密碼學(xué)中著名的Fujisaka-Okamoto變換，將以上的基礎(chǔ)方案轉(zhuǎn)變?yōu)檫x擇密文安全的方案。

1.2 基于格的數(shù)字簽名算法

對于RSA、橢圓曲線等密碼體制來說，其中的公鑰加密和數(shù)字簽名算法存在一定的對偶性：可通過簡單的交換公私鑰，將公鑰加密算法轉(zhuǎn)化為數(shù)字簽名算法。

然而，對于格密碼而言，這種對偶性并不存在，這意味著我們需要通過新的方式構(gòu)造數(shù)字簽名算法。被密碼學(xué)家廣泛采用的一種方式，即通過零知識證明協(xié)議構(gòu)造數(shù)字簽名。零知識證明可能是密碼學(xué)中最為神奇的一類應(yīng)用。零知識證明解決這樣一個問題：我們是否可以向他人提供對一個命題的證明，但卻不泄露證明這一命題所需要的知識？盡管看起來有些反直覺，但這一點事實上是可以做到的。實現(xiàn)安全的數(shù)字簽名，最基本的需求是令驗證者有能力對簽名者的身份進行認證。而這等價于這樣的一個零知識證明：證明者可證明自己擁有（和對應(yīng)身份的公鑰匹配的）私鑰，但不向驗證者泄露關(guān)于私鑰的信息。這是一類最簡單的零知識證明協(xié)議，通常稱為∑協(xié)議。

∑協(xié)議由以下三個步驟構(gòu)成：

（1）證明者給出承諾w。證明者首先隨機選擇y，并通過y生成承諾w，交給驗證者。

（2）驗證者提出挑戰(zhàn) c。驗證者給出均勻隨機的挑戰(zhàn)c。

（3）證明者給出應(yīng)答z。證明者通過第一步中的y、挑戰(zhàn)c以及用戶私鑰，得到應(yīng)答 z。（我們額外要求z在其值域上是均勻隨機的）驗證者可通過用戶公鑰、挑戰(zhàn)c以及承諾w確認z是否是由證明者合法生成的。

我們將（w，c，z）三元組稱為協(xié)議的抄本（transcript）。在具備零知識性的 ∑ 協(xié)議中，我們通常要求在未知私鑰的情況下（1） 通過w和c得到z是困難的；（2） 通過c和z得到w是容易的。因此，即使在未知私鑰的前提下，（w，c，z）三元組也可以通過這樣的方式生成：首先隨機選取c和z，然后得到w。由于這一生成方式不需要私鑰的參與，故協(xié)議的抄本不包含關(guān)于私鑰的任何知識！這就保證了協(xié)議的零知識性。

由于∑協(xié)議需要證明者和驗證者之間實施交互，故無法直接應(yīng)用于構(gòu)造數(shù)字簽名。但注意到∑協(xié)議要求挑戰(zhàn)c均勻隨機選取，而正如我們所知，一個安全的哈希函數(shù)，其輸出和隨機值是不可區(qū)分的。因此，我們可以將承諾w和需要簽名的消息m輸入哈希函數(shù)H，并用哈希函數(shù)的輸出模擬挑戰(zhàn) c，從而不需要額外的驗證者提出挑戰(zhàn)。與此同時，由于有簽名消息的參與，也實現(xiàn)了消息和∑協(xié)議抄本的綁定。這個方法稱為Fiat-Shamir變換。可以證明，安全的∑協(xié)議通過Fiat-Shamir變換，得到安全的數(shù)字簽名方案。

下面我們簡單介紹如何基于LWE問題構(gòu)造∑協(xié)議，進而構(gòu)造數(shù)字簽名。和公鑰加密算法類似，我們令公鑰為 （a，b=as+e mod q），私鑰為 s 。

（1）首先隨機選取較小的y

（2）令承諾w為ay的高比特位，以排除誤差項的影響

（3）對于挑戰(zhàn)c，令應(yīng)答z = y + cs。（注意到我們要求z均勻隨機，故需要排除一些令z不隨機的邊緣取值：當(dāng)z為邊緣取值時，需要重新選取y并再次計算z。我們這里不展開細節(jié)）

由于ay = az – cas ≈ az – cb mod q，故只需驗證w 是否為 az–cb的高比特位即可。對于需要簽名的消息m和雜湊函數(shù)H，我們令c = H（w||m），即可將這一協(xié)議轉(zhuǎn)化為簽名算法（在驗簽時需要驗證c = H（w||m））。