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

發(fā)布時(shí)間:2022-03-08

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

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

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

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

（1）數字摘要

（2）數字摘要+對稱(chēng)密鑰認證

（3）數字摘要+非對稱(chēng)密鑰認證

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

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

1.1 數字摘要

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

具體步驟如下：

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

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

主要優(yōu)點(diǎn)：

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

（2）單向函數：無(wú)法從摘要構造出原文。

主要缺點(diǎn)：

（1）僅僅Hash沒(méi)法保證完整性。

（2）改變這個(gè)消息，重新計算摘要，用改變后的消息+摘要替換原來(lái)的報文。

1.2 數字摘要+對稱(chēng)密鑰認證

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

具體步驟如下：

（1）通過(guò)安全通道，Bob和Alice共享一個(gè)密鑰。

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

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

（4）Bob也用共享密鑰加密隨機數，并對加密結果進(jìn)行HASH運算，計算的結果與接收的HASH進(jìn)行比較，相等則表示是Alice發(fā)送過(guò)來(lái)的。

主要優(yōu)點(diǎn)：

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

（2）分組加密性能快。

主要缺點(diǎn)：

（1）需要通過(guò)安全通道共享密鑰。

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

1.3 數字摘要+非對稱(chēng)密鑰認證

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

具體步驟如下：

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

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

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

主要優(yōu)點(diǎn)：

（1）公鑰可以公開(kāi)，無(wú)需保密。

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

主要缺點(diǎn)：

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

1.4 數字證書(shū)認證

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

· 主題Subject：需要鑒別的個(gè)人Alice

· Alice的公鑰public key

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

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

· 簽名算法Signature Algorithm

具體步驟如下：

（1）Bob申請Alice的證書(shū)公鑰。

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

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

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

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

主要優(yōu)點(diǎn)：

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

主要缺點(diǎn)：

（1）無(wú)法抵抗量子計算機攻擊。

后量子密碼算法概述

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

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

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

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

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

當參數選取適當時(shí)，目前沒(méi)有已知的經(jīng)典和量子算法可以快速求解這些問(wèn)題。

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

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

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

1.1 基于哈希 (Hash-based)

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

1.2 基于編碼 (Code-based)

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

1.3 基于多變量 (Multivariate-based)

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

1.4 基于格 (Lattice-based)

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

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

格密碼算法概述

格（lattice）是一種數學(xué)結構，定義為一組線(xiàn)性無(wú)關(guān)的非0向量（稱(chēng)作格基）的整系數線(xiàn)性組合。具體來(lái)說(shuō)，給定一組格基X1,......,Xn對任意的整數C1,...,Cn，C1X1+...+CnXn都是屬于這個(gè)格的向量，n稱(chēng)為格的維數。例如，下圖表示了一個(gè)二維格和兩組不同的格基：X1

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

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

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

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

1.1 基于格的公鑰加密算法

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

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

(1)首先隨機選取系數較小的多項式 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。當s,e,r,e1,e2均足夠小時(shí)，可以保證br+e2-(ar+e1)s  mod q的系數均不超過(guò)(q-1)/4。故d-cs和m(q-1)/2的每個(gè)系數之差都不超過(guò)(q-1)/4。我們可以通過(guò)這樣的方式從d-cs中還原m;若d-cs的第i個(gè)系數距離0更近，則令m的第i位為0；若 d-cs的第i位系數距離(q-1)/2更近，則令m的第i位系數為1。這樣我們成功通過(guò)私鑰s解密了密文(c,d)，得到消息m。這一算法的安全性由兩個(gè)部分保證：其一是私鑰的安全性，由于公鑰為L(cháng)WE樣本，通過(guò)公鑰不會(huì )泄露私鑰的信息；其二是消息的安全性，由于密文同樣為L(cháng)WE樣本，通過(guò)密文在未知私鑰的前提下，不會(huì )泄露消息。以上描述的簡(jiǎn)單方案是選擇明文安全，而非選擇密文安全的。對于具體的方案，則需要應用密碼學(xué)中著(zhù)名的Fujisaka-Okamoto變換，將以上的基礎方案轉變?yōu)檫x擇密文安全的方案。

1.2 基于格的數字簽名算法

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

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

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

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

（2）驗證者提出挑戰 c。驗證者給出均勻隨機的挑戰c。

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

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

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

下面我們簡(jiǎn)單介紹如何基于LWE問(wèn)題構造∑協(xié)議，進(jìn)而構造數字簽名。和公鑰加密算法類(lèi)似，我們令公鑰為 (a,b=as+e mod q)，私鑰為 s 。

(1)首先隨機選取較小的y

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

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

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

上海航芯ACL16安全芯片

上海航芯自主研發(fā)的ACL16芯片，已通過(guò)AEC-Q100車(chē)規認證、EAL5+認證，是一款高安全、高可靠性的車(chē)載安全芯片。芯片工作溫度達到AEC-Q100 Grade1等級，溫度范圍-40℃~+125℃，其安全性、可靠性等級均超越國產(chǎn)同類(lèi)芯片，是當前車(chē)載終端應用中極具性?xún)r(jià)比優(yōu)勢的一款安全芯片，已適配數十種前裝和后裝產(chǎn)品，為智能網(wǎng)聯(lián)汽車(chē)車(chē)內安全和車(chē)聯(lián)網(wǎng)安全護航。

如需銷(xiāo)售咨詢(xún)，請聯(lián)系：sales@aisinochip.com