基于格的后量子密碼系統(tǒng)研究

張 賀，王 鵬，李思照

(哈爾濱工程大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱 150001)

0 引言

后量子密碼(Post-Quantum Cryptography，PQC)又稱抗量子密碼，是能夠抵抗量子計(jì)算機(jī)對(duì)現(xiàn)有密碼算法攻擊的新一代密碼算法。因?yàn)榱孔佑?jì)算機(jī)的出現(xiàn)，現(xiàn)有的絕大多數(shù)公鑰密碼算法(RSA，Diffie-Hellman和橢圓曲線等)能被足夠大且穩(wěn)定的量子計(jì)算機(jī)攻破[1]，可以抵抗這種攻擊的密碼算法能夠在量子計(jì)算和其之后時(shí)代存活下來，所以被稱為“后”量子密碼。

密碼學(xué)的發(fā)展經(jīng)過了4個(gè)階段：古典密碼學(xué)、近代密碼學(xué)、現(xiàn)代密碼學(xué)和新興的量子密碼學(xué)。其中，古典密碼學(xué)的經(jīng)典算法主要有凱撒加密和換位加密[2]等；近代密碼學(xué)則是以DES為代表的對(duì)稱密碼學(xué)，隨后非對(duì)稱加密算法標(biāo)志著公鑰加密成為新的主流[3]。公鑰加密的原理一般是基于對(duì)應(yīng)數(shù)學(xué)的問題在計(jì)算機(jī)上的難解性進(jìn)行的，但是，量子計(jì)算機(jī)的出現(xiàn)使得這一難解的過程可以在有限的時(shí)間內(nèi)得到解決。因此，量子密碼學(xué)應(yīng)運(yùn)而生，它利用了單光子的量子性質(zhì)[4]，保證了數(shù)據(jù)傳輸?shù)目勺C性安全。

標(biāo)志著密碼學(xué)進(jìn)入量子密碼學(xué)新時(shí)期的算法主要是1994年彼得·秀爾[5]提出的Shor算法和1996年Lov Grover[6]提出的Grover算法。Shor算法可以以多項(xiàng)式時(shí)間求解周期函數(shù)的周期，而RSA、橢圓曲線等密碼體制基于的大整數(shù)分解問題和離散對(duì)數(shù)求解問題，都可以轉(zhuǎn)化為周期函數(shù)求解周期的問題，因此Shor算法可以在有限時(shí)間內(nèi)破解現(xiàn)有的RSA方案等公鑰加密方案。Grover算法又稱為量子搜索算法，是一種用于非結(jié)構(gòu)化搜索的算法。

PQC按照其數(shù)學(xué)原理主要可以分為4種[7]：基于格的PQC體制、基于編碼的PQC體制、基于哈希的PQC體制和基于多變量多項(xiàng)式的PQC體制。其中，基于格的PQC算法在安全性、公私鑰尺寸和計(jì)算速度上有著更好的平衡，主要表現(xiàn)在：第一，Ajtai等人[8]在數(shù)學(xué)層面上證明了格中一般的困難問題與NP困難問題的難度等價(jià)，有著較強(qiáng)的安全性；第二，基于格的PQC的應(yīng)用場景豐富，在傳統(tǒng)的公鑰加密、數(shù)字簽名和密鑰交換等領(lǐng)域都有著優(yōu)秀的表現(xiàn)；第三，基于格的密碼體制在硬件上的實(shí)現(xiàn)很靈活，可部署場景廣泛，在資源受限和資源豐富的場合都可以應(yīng)用[9]。因此，基于格的PQC體制被很多人認(rèn)為是最有前景的PQC算法。

與常規(guī)的把復(fù)雜問題轉(zhuǎn)換為簡單問題再求解不同，密碼算法的安全性完全要依賴于難解的數(shù)學(xué)問題，在有限的時(shí)間內(nèi)無法求出解。與在軟件上執(zhí)行的PQC算法相比，硬件執(zhí)行的效率是軟件上的數(shù)十倍，甚至上百倍。在一些軍方和醫(yī)療等復(fù)雜的應(yīng)用場合[10]，需要高速的執(zhí)行來縮短加解密時(shí)間，因此關(guān)于PQC算法在硬件上的研究就顯得十分必要。

1 基于格的PQC體制發(fā)展現(xiàn)狀

量子計(jì)算機(jī)的出現(xiàn)對(duì)于目前的密碼體制造成了巨大的沖擊，各個(gè)國家都開始積極地推動(dòng)PQC標(biāo)準(zhǔn)的制定。最具代表性的是美國國家標(biāo)準(zhǔn)與技術(shù)研究所(National Institute of Standards and Technology，NIST)。早在2009年，NIST就啟動(dòng)了PQC計(jì)劃來標(biāo)準(zhǔn)化一個(gè)或多個(gè)PQC方案。2015年4月，NIST舉辦了“后量子世界的網(wǎng)絡(luò)安全”研討會(huì)，對(duì)未來的標(biāo)準(zhǔn)化進(jìn)行了討論[11]。在2016年，NIST正式宣布進(jìn)行NIST PQC算法征集[12]，邀請(qǐng)世界各國學(xué)者提交PQC方案，再經(jīng)由評(píng)定選出適合標(biāo)準(zhǔn)化的算法。

1.1 評(píng)估標(biāo)準(zhǔn)

NIST的標(biāo)準(zhǔn)化評(píng)定對(duì)于算法的評(píng)估主要分為3個(gè)方面，包括安全性、成本和性能以及算法和實(shí)現(xiàn)特征[13]。具體來說，安全性是評(píng)估PQC算法最為重要的因素，需要遵循傳輸層安全協(xié)議(Transport Layer Security，TLS)、安全外殼協(xié)議(Secure Shell，SSH)和網(wǎng)絡(luò)密鑰交換協(xié)議(Internet Key Exchange，IKE)等一系列互聯(lián)網(wǎng)協(xié)議。NIST對(duì)算法的安全強(qiáng)度定義了5種安全級(jí)別[14]，如表1所示，以更好地比較提交算法的安全強(qiáng)度等級(jí)。成本是評(píng)估候選算法時(shí)的第二重要標(biāo)準(zhǔn)，包括計(jì)算效率和內(nèi)存需求，具體包括公鑰、密文和簽名的大小，密鑰生成，公鑰和私鑰的計(jì)算效率以及解密的成功率，所有提交算法的提交者需要提供NIST參考平臺(tái)的性能評(píng)估。NIST更希望接受靈活性大的候選算法，這有利于在各種平臺(tái)上高效地運(yùn)行，同時(shí)可以通過指令集的擴(kuò)展來提高算法性能。

表1 NIST規(guī)定的算法安全級(jí)別Tab.1 Algorithm security levels specified by NIST

1.2 算法征集情況

截止現(xiàn)在，NIST已經(jīng)進(jìn)行了3輪對(duì)廣泛征集的PQC算法的評(píng)估，提交的算法分為公鑰加密、密鑰封裝方案和數(shù)字簽名方案。在2017年12月，NIST對(duì)征集到的69份PQC算法方案進(jìn)行了評(píng)估，其中包括20份數(shù)字簽名方案和49份公鑰加密或密鑰封裝方案[15]。經(jīng)過第1輪評(píng)估，有26個(gè)候選方案進(jìn)入了第2輪評(píng)估，包括17份公鑰加密或密鑰封裝方案和9份數(shù)字簽名方案[16]，其中12份加密方案是基于格的PQC方案，占據(jù)了所有加密方案的一半。

在2020年10月，NIST公布了第3輪征集的密碼方案[17]，具體方案如表2所示。其中，CRYSTALS-KYBER，NTRU和SABER是基于格的公鑰加密或密鑰封裝方案，CRYSTALS-Dilithium和FALCON是基于格的數(shù)字簽名方案?；诟竦募用荏w制成為了最有可能PQC標(biāo)準(zhǔn)化的方案。

表2 NIST第3輪提交算法Tab.2 Submitted algorithms in NIST round 3

NIST預(yù)計(jì)在2024年之前完成對(duì)PQC最終入選算法的標(biāo)準(zhǔn)制定，公布PQC的標(biāo)準(zhǔn)化草案。屆時(shí)，新的密碼體系將取代現(xiàn)有的密碼體系，來應(yīng)對(duì)日益突出的量子威脅，為保密信息、數(shù)字簽名和信息訪問等應(yīng)用保證其安全性和授權(quán)控制。

2 基于格的幾種PQC算法

2.1 Saber算法

Saber算法是一種基于格的密鑰封裝機(jī)制(KEM)算法，在安全性級(jí)別的發(fā)展上，首先是一個(gè)基于2個(gè)模p和q的冪的選擇明文攻擊(Chosen Plaintext Attack，CPA)的安全公鑰加密(PKE)方案，然后經(jīng)過Fujisaki-Okamoto的改造為隨機(jī)選擇密文攻擊(IND-CCA)安全的KEM[18]。其安全性基于帶舍入的學(xué)習(xí)(Learning-with-Rounding，LWR)的變體MLWR，MLWR問題是基于模塊矩陣的LWR問題。LWR是LWE問題的一種變體，其中誤差項(xiàng)是通過舍入操作引入的，而不是從隨機(jī)分布中獲得的。

Saber通過不同參數(shù)的設(shè)置決定了Saber的不同安全級(jí)別，但是三者的多項(xiàng)式的次數(shù)N都為256，模q=213，p=210，具體如表3所示。

表3 Saber算法的不同分支Tab.3 Different branches of Saber algorithm

Saber公鑰加密方案包括3個(gè)階段：密鑰生成、加密和解密。

算法1:Saber密鑰生成輸入:種子 (0,1)256,常數(shù)向量h輸出:公鑰pk,私鑰sk1.從 (0,1)256均勻生成l×l階多項(xiàng)式矩陣A,A=gen(seedA)∈ l×lp2.均勻生成r= ({0,1}256),從二項(xiàng)分布中隨機(jī)生成s=βμ( l×1q;r)3.縮放生成向量b,b=((ATs+h)modq)4.對(duì)向量b舍入,b?(εq-εp)∈ l×1p5.得到公鑰pk,pk=(seedA,b)6.對(duì)pk進(jìn)行哈希變換,pkh= (pk)7.均勻生成向量z1= ({0,1}256)8.得到私鑰sk,sk=(s,z1,pkh)

在密鑰生成階段中，函數(shù)gen是基于SHAKE-128的偽隨機(jī)數(shù)生成器，用于從種子中獲取矩陣，生成了多項(xiàng)式的公共矩陣A和多項(xiàng)式的秘密向量s。同時(shí)，對(duì)乘積As進(jìn)行縮放和舍入得到向量b，其中公鑰由A和b組成，密鑰為向量s。

算法2:Saber加密操作輸入:公鑰pk,種子 (0,1)256,向量r輸出:密文c,共享密鑰K1.均勻選取生成消息m= ({0,1}256)2.如果r未被指定,則均勻生成r= ({0,1}256)3.從二項(xiàng)分布中隨機(jī)生成s′=βμ( l×1q;r)4.縮放生成向量b′,b′=((As′+h)modq)5.對(duì)向量b′舍入,b′?(εq-εp)∈ l×1p6.加密向量v′1=bT(s′modp)∈ p7.縮放生成cm,cm=(v′1+h1-2εp-1mmodp)8.對(duì)向量cm舍入,cm?(εp-εT)∈ T9.得到密文c=(cm,b′)10.通過哈希函數(shù)生成(K^,c)= (F(pk),m)11.通過哈希函數(shù)生成K= (K^,c)

在加密階段中，消息由v′1=s′bT(s′是專門為加密生成的向量)加密。生成的密文涉及到向量b′，b′由As′產(chǎn)生。

算法3:Saber解密操作輸入:公鑰pk,私鑰sk,密文c,向量z1輸出:共享密鑰K1.解密向量v1=b′T(smodp)∈ p2.解密生成原文消息m′,縮放m′=((v1-2εp-εTcm+b2)modp)舍入m′?(εp-1)∈ 23.調(diào)用加密操作生成m′的密文c′4.如果c=c′,則返回共享密鑰K= (K^,c)5.否則返回共享密鑰K= (z1,c)

在解密階段中，通過來自sb′的v1的近似來恢復(fù)消息，然后再加密與已有的密文消息對(duì)比，如果相同，則接受，否則拒絕。

2.2 CRYSTALS-KYBER算法

數(shù)論變換(Number Theoretic Transform，NTT)操作將傳統(tǒng)的多項(xiàng)式乘法運(yùn)算轉(zhuǎn)化為系數(shù)式乘法運(yùn)算，降低了多項(xiàng)式乘法運(yùn)算的復(fù)雜度。INTT操作是NTT操作的逆操作，將系數(shù)式乘法運(yùn)算轉(zhuǎn)化回多項(xiàng)式乘法運(yùn)算。CWM算法是將2個(gè)二次多項(xiàng)式在q[x]/(x2-ωi)中相乘，其中i隨系數(shù)的指標(biāo)變化[20]。

Kyber是由公鑰加密方案轉(zhuǎn)化而來的KEM，是NIST后量子標(biāo)準(zhǔn)中提出的算法。Kyber算法適用于多項(xiàng)式環(huán)Rq，其中φ(x),q,n分別為xn+1，3 329，256。Kyber算法的密鑰生成、加密和解密操作如下。

算法4:Kyber密鑰生成輸入:字節(jié)數(shù)組(0,1)256輸出:公鑰pk,私鑰sk1.從Rk×kq中均勻采樣生成多項(xiàng)式矩陣A-2.從Rkq中中心二項(xiàng)分布采樣生成向量s,e3.公鑰pk=A-s+e4.均勻生成32位字節(jié)數(shù)組z5.私鑰sk=(s,pk, (pk),z)

密鑰生成操作需要2k次NTT操作和k2次系數(shù)式乘法運(yùn)算(CWM)操作。

算法5:Kyber加密操作輸入:公鑰pk,消息m輸出:密文c,共享密鑰K1.消息m是均勻生成的32位字節(jié)數(shù)組2.m= (m)3.(K-,r)= (m, (pk))4.從Rk×kq中均勻采樣生成多項(xiàng)式矩陣A-5.中心二項(xiàng)分布采樣生成向量r,e1←＄Rkq6.中心二項(xiàng)分布采樣生成向量e2←＄Rq7.計(jì)算u=ATr+e18.生成密文c,c=(u,v)=(ATr+e1,pkTr+e2+m)9.共享密鑰K=(K-, (c))

加密操作需要k次NTT，k2+k次CWM和k+1次INTT操作。

算法6:Kyber解密操作輸入:私鑰sk,密文c,向量z輸出:共享密鑰K1.解密生成原文消息m′,m′=v-skTu2.加密操作的常數(shù)向量h3.哈希變換得到(K-′,r′)= (m′,h)4.利用加密操作生成m′的密文c′5.如果c=c′,則返回共享密鑰K=(K-′, (c))6.否則返回共享密鑰K=(z, (c))

Kyber算法中k取值為{2,3,4}，通過改變參數(shù)k可以調(diào)整其安全級(jí)別。

2.3 CRYSTALS-Dilithium算法

CRYSTALS-Dilithium是NIST第3輪后量子數(shù)字簽名候選方案中的一種，是一種基于晶格的數(shù)字簽名方案，屬于代數(shù)格加密套件(CRYSTALS)及密鑰封裝機(jī)制中的一種。Dilithium算法的核心運(yùn)算是多項(xiàng)式矩陣和向量的運(yùn)算，安全性基于模塊化帶錯(cuò)誤學(xué)習(xí)(M-LWE)和最短整數(shù)解(SIS)問題，但是不同的是所有多項(xiàng)式的采樣都是均勻采樣，多項(xiàng)式的生成比較簡約[21]。Dilithium算法中n=256，q=223-213+1。Dilithium數(shù)字簽名方案的安全級(jí)別可通過表4中的參數(shù)進(jìn)行調(diào)整。

表4 Dilithium算法不同安全級(jí)別下的參數(shù)設(shè)置Tab.4 Parameter settings of Dilithium algorithm at different security levels

Dilithium數(shù)字簽名方案的3個(gè)核心算法是密鑰生成、簽名生成和簽名驗(yàn)證，具體算法如下。

算法7:Dilithium密鑰生成輸入:種子ζ∈{0,1}256輸出:公鑰pk和私鑰sk1.從多項(xiàng)式環(huán)Rq均勻生成k×?階多項(xiàng)式矩陣A∈ k×lp2.從多項(xiàng)式環(huán)Rq均勻生成多項(xiàng)式向量s1和s23.計(jì)算t=As1+s24.將t拆解為t=t0+bt15.生成公鑰pk=(A,t1)6.生成私鑰sk=(A,t0,s1,s2)

在Dilithium數(shù)字簽名方案的密鑰生成中，為了保持公鑰大小較小，矩陣A被種子ρ替換，種子ρ生成確定性密鑰，這是基于晶格的密碼學(xué)中廣泛使用的技術(shù)。此外，將t中每個(gè)系數(shù)的較低d位放在密鑰中，來進(jìn)一步降低公鑰大小。

算法8:Dilithium簽名生成輸入:私鑰sk,消息M∈{0,1}?,常數(shù)向量h輸出:三元組 σ=(z,h,c)1.初始化(z,h)為無效2.當(dāng)(z,h)無效時(shí)執(zhí)行循環(huán)3.生成隱蔽向量y←S?γ14.計(jì)算w=Ay,使w=w1·2γ2+w05.c=哈希(M‖w1)∈Bτ,使多項(xiàng)式c的τ個(gè)系數(shù)為±1,其他系數(shù)為06.生成潛在簽名z=y+cs17.w-cs2=w2·2γ2+w38.如果‖z‖∞≥γ1-β或者‖w2‖∞≥γ2-β 則返回(z,h)無效9.否則計(jì)算由t中的未知部分產(chǎn)生的進(jìn)位向量h,h由-ct0和w-cs2+ct0的高位產(chǎn)生10.如果‖ct0‖∞≥γ2或者h(yuǎn)≥ω則11.返回(z,h)無效12.結(jié)束循環(huán)

在簽名生成中，簽名算法選擇一個(gè)掩蔽向量y，其中的系數(shù)來自[-γ1,γ1)，來計(jì)算后續(xù)w=Ay。檢查多項(xiàng)式的最大范數(shù)是否在可接受的預(yù)定義范圍和向量的最大范數(shù)，來檢查簽名是否泄漏有關(guān)該秘密值的信息。額外增加的一個(gè)拒絕條件是提示h驗(yàn)證算法期間t的哪些系數(shù)需要進(jìn)位。根據(jù)安全級(jí)別的不同，平均需要嘗試3～5次才能生成有效的簽名。

算法9:Dilithium簽名驗(yàn)證輸入:公鑰pk,消息M∈{0,1}?,三元組σ=(z,h,c)輸出:有效或無效1.Az-ct1結(jié)果的四舍五入的高位為w′1,w′1=(h,Az-ct1·2d,2γ2)2.如果‖z‖∞<γ1-β且c= (M‖w′1) 且h≤ω,則返回有效3.否則返回?zé)o效

在簽名驗(yàn)證過程中，由于t中每個(gè)系數(shù)的低位不包含在公鑰中，因此驗(yàn)證器利用提示h來執(zhí)行該操作。隨后，根據(jù)消息和w′1重新計(jì)算質(zhì)詢c，并將其與簽名中提供的質(zhì)詢c進(jìn)行比較。此外，檢查z是否具有有效范數(shù)(即每個(gè)系數(shù)是否具有簽名生成期間檢查的最大值)。

3 硬件實(shí)現(xiàn)

目前，對(duì)于基于格的密碼體制的高效硬件實(shí)現(xiàn)是當(dāng)期研究的熱點(diǎn)，大量的研究者們不但提出了PQC方案，也提供了硬件上實(shí)現(xiàn)的結(jié)果。格基密碼體制易于在硬件中高效實(shí)現(xiàn)，主要優(yōu)勢在于格基密碼體制中的運(yùn)算主要是多項(xiàng)式計(jì)算，可以利用NTT算法實(shí)現(xiàn)高效快速乘法，在硬件中極大地提高了格基密碼方案的吞吐量[22]。同時(shí)，硬件實(shí)現(xiàn)相比于軟件有著高效并行處理的優(yōu)勢，加速處理多項(xiàng)式中的復(fù)雜計(jì)算，而且性能與資源上的權(quán)衡十分出色，應(yīng)用場景廣泛。

硬件上的開發(fā)方法主要可以分為軟硬件協(xié)同設(shè)計(jì)(RTL)和高級(jí)綜合(High Level Synthesis，HLS)2種方法，在硬件上的實(shí)現(xiàn)平臺(tái)主要有Xilinx FPGA上的Virtex-7，UltraScale+和Artix-7等平臺(tái)，完成對(duì)格基密碼體制的硬件實(shí)現(xiàn)。

3.1 Saber算法的硬件實(shí)現(xiàn)

Saber算法是NIST第3輪評(píng)估中的候選算法之一，研究者們對(duì)于Saber算法在硬件上的實(shí)現(xiàn)的研究很多。Roy等人[23]設(shè)計(jì)了一個(gè)指令集協(xié)處理器架構(gòu)，可以提供指令級(jí)的靈活性和模塊化，易于添加或修改新的指令。在多項(xiàng)式的乘法優(yōu)化上，對(duì)絕對(duì)值進(jìn)行乘法運(yùn)算，然后累加器通過系數(shù)符號(hào)位決定是加法還是減法，這樣將乘法轉(zhuǎn)化為移位和相加操作，優(yōu)化了架構(gòu)，減少周期、邏輯和寄存器數(shù)量，具體的多項(xiàng)式乘法器結(jié)構(gòu)如圖1所示。同時(shí)，乘法器是大規(guī)模并行的，不會(huì)受到內(nèi)存訪問瓶頸的影響。多項(xiàng)式的結(jié)構(gòu)易于擴(kuò)展，可以滿足不同性能的需求，支持Saber算法的幾種變體。

圖1 多項(xiàng)式乘法器結(jié)構(gòu)Fig.1 Polynomial multiplier structure

文獻(xiàn)[24]基于多項(xiàng)式乘法產(chǎn)生的乘法輸出是并行的，但需要的輸出是串行的問題，提出了一種新的循環(huán)面向行處理(CROP)策略，把乘法器的輸出放到下一個(gè)寄存器中存儲(chǔ)，進(jìn)行N步后，把所有寄存器中的輸出進(jìn)行循環(huán)累積，進(jìn)而很容易地實(shí)現(xiàn)串行操作。具體來說，把N步操作拆為了r×t步，即每個(gè)t子累積需要r步循環(huán)，從而更高速地實(shí)現(xiàn)多項(xiàng)式乘法的輸出操作。使用了2個(gè)移位寄存器(SR)和N個(gè)處理元件(PE)，實(shí)現(xiàn)了CROP策略在硬件上的實(shí)現(xiàn)。

Zhu等人[25]對(duì)之前的分層Karatsuba框架進(jìn)行了優(yōu)化，之前的這一框架實(shí)現(xiàn)了多項(xiàng)式乘法的分步操作，分為了預(yù)加、乘法和后加3步，但是沒有考慮輸入端加法器和寄存器的復(fù)用。通過調(diào)度層實(shí)現(xiàn)了寄存器和加法器的重用，資源上節(jié)約了90%。同時(shí)，權(quán)衡了調(diào)度層和內(nèi)核層，使得預(yù)加和后加操作變得更加緊湊，均衡了計(jì)算速度和延遲面積。Saber算法中的多項(xiàng)式可以通過流水線方式生成，且與乘法硬件并行生成，減少了延遲開銷和多項(xiàng)式的內(nèi)存。同時(shí)，引入了截?cái)喑俗觼韺?shí)現(xiàn)細(xì)粒度處理。

多項(xiàng)式乘法時(shí)，一個(gè)多項(xiàng)式的系數(shù)較小(-4～+4)，另一個(gè)多項(xiàng)式的系數(shù)為10位或13位。因此，Basso等人[26]采取集中式乘法器結(jié)構(gòu)，使用預(yù)計(jì)算的方法，把乘法結(jié)果預(yù)先計(jì)算好，這樣MAC內(nèi)部的乘法變成了簡單的選擇操作，顯著減少了MAC單元的面積。數(shù)字信號(hào)處理模塊(DSP)負(fù)責(zé)處理這種系數(shù)乘法，一個(gè)DSP包含2個(gè)公共多項(xiàng)式系數(shù)和2個(gè)秘密系數(shù)，一個(gè)DSP就可以計(jì)算4個(gè)系數(shù)乘法，通過128組DSP可以實(shí)現(xiàn)128個(gè)周期內(nèi)計(jì)算256系數(shù)多項(xiàng)式的乘法。通過使用多路復(fù)用器(MUX)將多項(xiàng)式乘法的并行輸出變?yōu)榇休敵龃鎯?chǔ)到外存中。

He等人[27]通過可伸縮矩陣源處理(SMOP)，把多項(xiàng)式乘法中的系數(shù)相乘轉(zhuǎn)換為矩陣形式。建立了一套完整的體系結(jié)構(gòu)，將算術(shù)運(yùn)算與信號(hào)控制流均集成到硬件上，得到緊湊的協(xié)處理器結(jié)構(gòu)。整個(gè)系統(tǒng)包括數(shù)據(jù)流和控制流，其中重點(diǎn)的多項(xiàng)式乘法部分，將SMOP的算法做到硬件上，通過循環(huán)移位寄存器(CSR)、乘法和加法器(MAA)和累加器(AC)來實(shí)現(xiàn)多項(xiàng)式乘法和并行輸入串行輸出(PISO)。He等人還展示了2個(gè)或4個(gè)CSR分組下，整個(gè)處理器的不同流程。這些實(shí)驗(yàn)的具體對(duì)比如表5所示[23-27]，Saber算法為標(biāo)準(zhǔn)的Saber算法。

表5 Saber算法硬件實(shí)現(xiàn)的對(duì)比Tab.5 Comparison of Saber algorithm hardware implementation

Xie等人的設(shè)計(jì)與Basso等人的設(shè)計(jì)相比，在性能無差距下，設(shè)計(jì)的面積延遲積(ADP)降低了10%。

從表5中可以看到，Zhu等人針對(duì)分層Karatsuba框架的優(yōu)化，在性能上的表現(xiàn)最好，但是其需要的資源也最多，尤其是DSP和BRAM，因此，比較適合追求性能不注重成本的應(yīng)用場合。He等人的可伸縮矩陣源處理需要的硬件資源最少，因此性能表現(xiàn)較差，適合輕量化的場景。Roy等人對(duì)多項(xiàng)式乘法器進(jìn)行優(yōu)化，將乘法轉(zhuǎn)化為移位和相加操作，在綜合的性能和資源上的表現(xiàn)最優(yōu)。

3.2 CRYSTALS-KYBER算法的硬件實(shí)現(xiàn)

KYBER體系結(jié)構(gòu)分為3個(gè)主要核心：Keccak(哈希和采樣)、NTT和Control(控制器和所有其他所需函數(shù))。Huang等人[28]發(fā)現(xiàn)在算法的整體階段中，尤其是加密和解密階段，存在很多可以重復(fù)使用的單元，且加密和解密過程一般并不沖突，可以復(fù)用這些單元來節(jié)省硬件成本。因此，他們將所有哈希函數(shù)集成為一個(gè)哈希模塊，同時(shí)引入BRAM來存儲(chǔ)中間數(shù)據(jù)，盡可能地利用FPGA，在一個(gè)時(shí)鐘周期內(nèi)實(shí)現(xiàn)Keccak置換過程。在使用Montgomery Reduction時(shí)，其中的3次乘法和1次減法，通過在硬件中使用流水線的方法，算法的時(shí)鐘周期變?yōu)樵瓉淼?/4。

Bisheh-Niasar等人[29]利用KRED和KRED-2X算法來實(shí)現(xiàn)多項(xiàng)式的?；s減，且只需要移位和加法操作，但是只能輸出16位數(shù)據(jù)，為了輸出32位數(shù)據(jù)，提出了K2-RED算法，減少了移位和加法操作，且12位的輸出也意味著占用的內(nèi)存更少。為了避免多項(xiàng)式乘法中的位反轉(zhuǎn)成本，提出了2×2的可重構(gòu)蝶形結(jié)構(gòu)，支持CT和GS操作，來合并2層NTT，且每層執(zhí)行2個(gè)蝶形操作，減少硬件資源。

Yarman等人[30]在模約減單元采用了滑動(dòng)遞歸的方法，組合相同的位來消除冗余操作，同時(shí)簡化操作，實(shí)現(xiàn)了一個(gè)時(shí)鐘周期的延遲。設(shè)計(jì)的蝶形單元可以用于NTT和INTT操作，每個(gè)蝶形單元包括4個(gè)雙端口的BRAM，其中2個(gè)BRAM存儲(chǔ)第1個(gè)輸入多項(xiàng)式和輸出多項(xiàng)式，另外2個(gè)存儲(chǔ)第2個(gè)輸入多項(xiàng)式，同時(shí)還擁有一個(gè)BROM，用于存儲(chǔ)預(yù)計(jì)算和加載的旋轉(zhuǎn)因子冪，通過多路復(fù)用器進(jìn)行多項(xiàng)式的傳輸操作。還設(shè)計(jì)了輕量級(jí)、平衡和高性能的硬件架構(gòu)，分別使用1個(gè)、4個(gè)和16個(gè)蝶形單元，來應(yīng)對(duì)不同的使用場景。

Xing等人[31]實(shí)現(xiàn)了CRYSTALS-KYBER算法的純手動(dòng)設(shè)計(jì)硬件，不需要借助ARM Cortex等硬連線處理器和RISC-V等可重構(gòu)邏輯。系統(tǒng)中設(shè)計(jì)使用了2個(gè)蝶形單元，分別用于處理KYBER中的一個(gè)256項(xiàng)NTT，NTT分解為2個(gè)獨(dú)立的偶數(shù)索引和奇數(shù)索引，具體的NTT操作(上方)和INTT操作(下方)如圖2所示。

圖2 NTT和INTT中的蝶形單元Fig.2 Butterfly units in NTT and INTT

在逐點(diǎn)乘法中，采用了Karatsuba算法，降低了乘法操作的次數(shù)。同時(shí),使用Barrett的模約減操作降低了DSP等資源的消耗。將減少系統(tǒng)資源消耗的關(guān)鍵放在了內(nèi)存占用上，主要包括數(shù)據(jù)在RAM上的即時(shí)存儲(chǔ)、解決讀寫速率不匹配而靈活多變的FIFO存儲(chǔ)器以及重新加密階段充分利用FIFO存儲(chǔ)器等方法。這些實(shí)驗(yàn)的具體對(duì)比如表6所示[28-31]，KYBER算法為Kyber-512。

表6 KYBER算法硬件實(shí)現(xiàn)的對(duì)比Tab.6 Comparison of hardware implementation of Kyber algorithm

從表6中可以看出，Xing等人的純手動(dòng)設(shè)計(jì)硬件實(shí)現(xiàn)，由于不需要ARM Cortex等硬連線處理器和RISC-V等可重構(gòu)邏輯，因此在綜合的性能與資源上的表現(xiàn)最為優(yōu)秀。Bisheh-Niasar等人提出的K2-RED算法從算法層次減少了移位和加法操作，根本上降低了硬件上的資源使用。

3.3 CRYSTALS-Dilithium算法的硬件實(shí)現(xiàn)

Beckwith等人[32]實(shí)現(xiàn)了對(duì)Dilithium的不同安全級(jí)別下不同的相關(guān)參數(shù)的高性能硬件實(shí)現(xiàn)，算法中很多操作存在大量的數(shù)據(jù)依賴性，使得通過高度并行化來提升效率變得很難。提高性能的方向主要是優(yōu)化多項(xiàng)式運(yùn)算單元和優(yōu)化操作調(diào)度。在多項(xiàng)式運(yùn)算單元上，使用了2×2的蝶形單元、地址解析單元和FIFO存儲(chǔ)器，一次處理2層來降低NTT中的內(nèi)存訪問成本，同時(shí)也不會(huì)占用過多的資源。Dilithium算法中的多項(xiàng)式采樣需要大量的偽隨機(jī)數(shù)據(jù)，使用了3個(gè)Keccak核，為向量和矩陣添加了多條拒絕通道，并行處理偽隨機(jī)數(shù)據(jù)，提升了吞吐量。在優(yōu)化操作調(diào)度上，將簽名生成單元中的拒絕循環(huán)拆分為2級(jí)管道，加速單個(gè)操作的性能來加速整體的性能。

Land等人[33]利用DSP模塊中的動(dòng)態(tài)配置、預(yù)加法和單指令多數(shù)據(jù)(SIMD)的功能實(shí)現(xiàn)了NTT，MACC等所有的具體功能模塊，減少了內(nèi)存占用，省去了多項(xiàng)式重新采樣，模塊間又執(zhí)行流水線處理，加快了算法實(shí)現(xiàn)。在NTT模塊中，之前的NTT結(jié)構(gòu)一般只使用DSP進(jìn)行低延遲乘法，充分利用了DSP中的移位寄存器、多路復(fù)用器等單元，通過預(yù)計(jì)算蝶形單元中的旋轉(zhuǎn)因子，加快了INTT操作，給NTT等所有相關(guān)的算術(shù)操作都實(shí)現(xiàn)了低延遲。這里同樣使用BRAM來存儲(chǔ)多項(xiàng)式，不同的是系數(shù)存放的間接地址，使讀寫沖突的數(shù)量降到了最低。在模約簡模塊中，利用模運(yùn)算的數(shù)學(xué)關(guān)系對(duì)46位值的s進(jìn)行了簡化。整個(gè)架構(gòu)的算術(shù)操作由NTT，MACC和矩陣向量乘法執(zhí)行，檢查模塊會(huì)對(duì)多項(xiàng)式的范數(shù)進(jìn)行檢查，采樣模塊和Keccak模塊負(fù)責(zé)多項(xiàng)式的隨機(jī)生成，共同受控制單元的調(diào)度。

Ricci等人[34]用VHDL語言設(shè)計(jì)和實(shí)現(xiàn)了Dilithium算法中的所有底層功能，包括SHAKE-128，SHAKE-256，NTT和ExpandAq等函數(shù)，而且針對(duì)硬件環(huán)境對(duì)這些函數(shù)做了進(jìn)一步的優(yōu)化，然后將這些函數(shù)集成到了Dilithium算法的密鑰生成、簽名和驗(yàn)證3個(gè)階段，來提升算法的處理速度。

Zhao等人[35]提出了一種分段流水線處理方法，將算法中的操作分成多個(gè)段，硬件以流水線方式一次處理一個(gè)段。這種方法大大減少了中間結(jié)果的存儲(chǔ)需求，并隱藏了許多操作的執(zhí)行時(shí)間。優(yōu)化模塊，包括高速流水線NTT模塊、基于BRAM的采樣模塊、緊湊分解模塊和3個(gè)定制的模塊化簡模塊。整體的系統(tǒng)結(jié)構(gòu)如圖3所示。

圖3 系統(tǒng)結(jié)構(gòu)Fig.3 System structure diagram

本文將整個(gè)系統(tǒng)分為了NTT、頭部、尾部等多個(gè)模塊組件，因此采用了分段流水線的處理方法，將數(shù)字簽名算法中的操作分為多個(gè)段，以流水線的方式一次處理一個(gè)段，每段通過對(duì)應(yīng)模塊分別執(zhí)行多項(xiàng)式生成和采樣以及NTT操作，大大減少了中間結(jié)果的存儲(chǔ)需求，并隱藏了許多操作的執(zhí)行時(shí)間。根據(jù)模數(shù)q和BRAM的位寬關(guān)系，將3個(gè)陣列為一組存儲(chǔ)多項(xiàng)式的4個(gè)系數(shù)，提高BRAM存儲(chǔ)空間的利用率。同時(shí)，多項(xiàng)式矩陣是實(shí)時(shí)計(jì)算，而非預(yù)先計(jì)算，從而避免在BRAM中的無效存儲(chǔ)。通過利用BRAM的空閑區(qū)域，來替換移位寄存器，折疊變換蝶形單元，提高了資源利用率，優(yōu)化了NTT模塊。

這些實(shí)驗(yàn)的具體對(duì)比如表7所示[32-35]，Dilithium算法為安全級(jí)別2下的算法。

表7 Dilithium算法硬件實(shí)現(xiàn)的對(duì)比Tab.7 Comparison of hardware implementation of Dilithium algorithm

Ricci等人使用VHDL語言重新設(shè)計(jì)了所有底層功能，極大地降低了Dilithium算法的密鑰生成、簽名和驗(yàn)證時(shí)間，但是占用的資源也極多。Zhao等人提出的分段流水線處理，一方面極大地降低了資源消耗，同時(shí)時(shí)間上表現(xiàn)的差距不大，綜合性能表現(xiàn)上最好。

4 側(cè)信道攻擊分析

格基密碼體制通過格中難解數(shù)學(xué)問題保證了其算法的安全性，但是硬件的具體實(shí)現(xiàn)往往會(huì)面臨側(cè)信道攻擊，進(jìn)而影響算法的安全性和性能[36]，例如芯片的瞬時(shí)功耗，以提取由實(shí)現(xiàn)處理的密鑰[37]。側(cè)信道攻擊一般通過檢測目標(biāo)設(shè)備泄露的物理信息進(jìn)行分析，如執(zhí)行算法每一步時(shí)需要的時(shí)間或者功率軌跡、消耗的能量、發(fā)射的電磁波和產(chǎn)生的錯(cuò)誤輸出等，從而提取出算法的密鑰。典型的側(cè)信道攻擊分為冷啟動(dòng)攻擊[38]、故障攻擊[39]、定時(shí)攻擊[40]和功率分析[41]等。因此，需要對(duì)這些格基密碼算法對(duì)側(cè)信道攻擊進(jìn)行分析，從而找到解決對(duì)策。

物理安全性有限或沒有物理安全性的輕量級(jí)應(yīng)用程序更容易受到此類攻擊，因?yàn)閷?duì)手可以輕松收集旁道信息。不同平臺(tái)的泄漏模式不同。例如，源于處理器架構(gòu)的泄漏可能會(huì)影響軟件，而依賴于基本組合和時(shí)序電路構(gòu)建塊的小故障會(huì)影響硬件實(shí)現(xiàn)。針對(duì)基于晶格密碼體制的第1種側(cè)通道攻擊是對(duì)NTRUEncrypt實(shí)現(xiàn)的定時(shí)攻擊[42]，該攻擊利用的是解密過程中哈希函數(shù)的執(zhí)行時(shí)間取決于密文這一過程。

在Saber算法去封裝的過程中，一般會(huì)長期使用私鑰，這會(huì)導(dǎo)致容易受到側(cè)信道分析，解決這一問題的方法是對(duì)密鑰操作進(jìn)行隱藏處理。有效的掩模設(shè)計(jì)分為2個(gè)模的冪和舍入學(xué)習(xí)的有限噪聲采樣，面臨的主要挑戰(zhàn)是將逐位運(yùn)算與算術(shù)掩蔽相結(jié)合，要求算法在掩蔽表示之間進(jìn)行安全轉(zhuǎn)換。所描述的設(shè)計(jì)包括一個(gè)用于算術(shù)共享上的屏蔽邏輯移位的新原語，以及對(duì)現(xiàn)有的Saber屏蔽二項(xiàng)式采樣器進(jìn)行調(diào)整。

Abdulgadir等人[43]采用寄存器—傳輸層(RTL)的方法來構(gòu)建硬件，對(duì)使用私鑰操作的每一單元都進(jìn)行了隱藏處理。在多項(xiàng)式運(yùn)算單元上，將多項(xiàng)式生成為2個(gè)多項(xiàng)式，使得乘積為另一個(gè)多項(xiàng)式與這2個(gè)多項(xiàng)式乘積的和。在SHA3單元，使用不相關(guān)的狀態(tài)來提供非線性運(yùn)算所需的隨機(jī)性。中心二項(xiàng)分布(CBD)取樣器單元上，使用了Goubin布爾型轉(zhuǎn)向算術(shù)型的方法，轉(zhuǎn)換采樣中的幾位。同時(shí)，還設(shè)計(jì)了高效的屏蔽邏輯移位單元方法實(shí)現(xiàn)了邏輯移位單元的隱藏。實(shí)驗(yàn)表明，抗CSA攻擊下，系統(tǒng)使用的LUT和延遲分別是不抗CSA攻擊的2.9倍和1.4倍。

對(duì)于CRYSTALS-KYBER算法的抗側(cè)信道攻擊防護(hù)，Jati等人[44]在整體的硬件架構(gòu)上使用了廣泛的資源共享，包括算術(shù)運(yùn)算、控制信號(hào)及FSM，同時(shí)實(shí)現(xiàn)了更小的SHA-3內(nèi)核，LUT和FF的數(shù)量減少了70%和50%，在具有高性能的同時(shí)有著最小的開銷，同時(shí)提供了良好的抗故障性。實(shí)現(xiàn)抗側(cè)信道攻擊的策略有3種：隨機(jī)延遲，由基于TRNG的環(huán)形振蕩器的真隨機(jī)數(shù)生成器生成；地址隨機(jī)化，在系統(tǒng)啟動(dòng)/重置時(shí)使用隨機(jī)數(shù)據(jù)和fisher-yates-shuffle技術(shù)[45]創(chuàng)建的地址隨機(jī)化，在每條指令結(jié)束后隨機(jī)更新排列；指令隨機(jī)化，引入一條名為INSTRND的指令使接下來的N條指令以隨機(jī)順序執(zhí)行。同時(shí)，設(shè)計(jì)了一種基于替代置換網(wǎng)絡(luò)(SPN)結(jié)構(gòu)的良好微分偏差的16×8哈希來保護(hù)指令指針和內(nèi)存。

Karabulut等人[46]發(fā)現(xiàn)CRYSTALS-Dilitium算法中的ω-小多項(xiàng)式采樣過程會(huì)泄漏有關(guān)系數(shù)的-1，0或+1賦值的信息，進(jìn)一步證明，這一采樣過程可以在單個(gè)功率測量中找到，并且可以恢復(fù)會(huì)話密鑰，針對(duì)這一問題的攻擊恢復(fù)系數(shù)符號(hào)的成功率超過99.99%，將被拒絕的挑戰(zhàn)多項(xiàng)式的熵降低到39～60位。

Chen等人[47]針對(duì)CRYSTALS-Dilithium算法提出了一個(gè)保守的方案和一個(gè)快速的兩階段攻擊策略。對(duì)手可以將這2種方案結(jié)合起來，通過高效的混合CPA(相關(guān)功率分析)攻擊，可以分析出p的最低有效位，進(jìn)而恢復(fù)相關(guān)候選序列，恢復(fù)完整的秘密系數(shù)。實(shí)驗(yàn)表明，在合理的功率跟蹤量下，該算法的置信度可達(dá)99.99%。得益于這一策略，對(duì)手可以以7.77倍的加速度恢復(fù)密鑰。這項(xiàng)工作指出，基于非保護(hù)NTT的多項(xiàng)式乘法是脆弱的。

針對(duì)不同類型的攻擊和不同應(yīng)用應(yīng)當(dāng)采取不同的對(duì)策，對(duì)于輕量級(jí)的硬件實(shí)現(xiàn)，這些設(shè)備往往布置在受約束的環(huán)境和移動(dòng)設(shè)備上，攻擊者的攻擊一般是在設(shè)備的正常操作期間進(jìn)行攻擊，因此，主要需要進(jìn)行電磁攻擊的額外防護(hù)。而在其他任何嵌入式的設(shè)備當(dāng)中，尤其是針對(duì)多個(gè)用戶共享的平臺(tái)，需要防止緩存泄露。大多數(shù)的PQC算法仍在開發(fā)和實(shí)驗(yàn)驗(yàn)證階段，實(shí)驗(yàn)框架一直處于大量修改和擴(kuò)展階段，提出的一些針對(duì)側(cè)信道攻擊的防御對(duì)策往往只使用于特定算法，具有局限性。

5 結(jié)束語

通過對(duì)Saber算法、CRYSTALS-KYBER算法和CRYSTALS-Dilithium算法的詳細(xì)算法介紹和相關(guān)的硬件實(shí)現(xiàn)介紹，展示了格基量子密碼學(xué)相關(guān)的背景、基礎(chǔ)知識(shí)和發(fā)展現(xiàn)狀。著重介紹了格基密碼的硬件實(shí)現(xiàn)部分，對(duì)于算法中的多項(xiàng)式采樣模塊和多項(xiàng)式乘法模塊的具體實(shí)現(xiàn)進(jìn)行了總結(jié)分析，尤其是NTT算法在多項(xiàng)式乘法器模塊中的應(yīng)用，通過蝶形單元大大降低了NTT操作時(shí)間，借由實(shí)驗(yàn)數(shù)據(jù)對(duì)比展現(xiàn)了不同改進(jìn)型密碼系統(tǒng)的架構(gòu)和優(yōu)劣。最后，對(duì)硬件實(shí)現(xiàn)中可能面臨的側(cè)信道攻擊進(jìn)行了總結(jié)分析，介紹了抗側(cè)信道攻擊的硬件設(shè)計(jì)思路。

在后量子時(shí)代，基于格的PQC體制以其強(qiáng)大的安全性、平衡性和靈活性成為了PQC學(xué)中最為活躍的部分，其與硬件的高效結(jié)合充分展示了其靈活性和廣闊的實(shí)用場景，推動(dòng)著密碼學(xué)與實(shí)際應(yīng)用的不斷結(jié)合。