楊亞濤， 王在舟， 曾 萍， 肖 嵩

1. 北京電子科技學院 電子與通信工程系， 北京 100070

2. 西安電子科技大學 通信工程學院， 西安 710071

1 引言

隨著近年來全球?qū)α孔佑嬎慵夹g(shù)的研究深入， 人們對替代現(xiàn)有密碼系統(tǒng)(例如AES、RSA) 的實用化抗量子密碼算法的需求日漸增加. NIST (National Institute of Standards and Technology， 美國國家標準與技術(shù)研究院) 于2017 年11 月征集抗量子密碼算法后， 共有69 個算法進入了第一輪評估. 2020 年7月， NIST 公布了第三輪的7 個候選算法. 其中密鑰封裝機制(key encapsulation mechanism， KEM) 有4個， 分別是Classic McEliece、CRYSTALS-KYBER、NTRU 和SABER. 數(shù)字簽名算法有3 個， 分別是CRYSTALS-DILITHIUM、Falcon 和Rainbow. 另外還有8 種算法進入備選， 其中的KEM 算法分別為BIKE、FrodoKEM、HQC、NTRU Prime 和SIKE. 數(shù)字簽名算法為GeMSS、Picnic 和SPHINCS+.

在NTRU Prime 項目中， SNTRUP(streamlined NTRU Prime)是一個基于格的小型密鑰封裝算法，旨在實現(xiàn)IND-CCA2 安全的標準目標. SNTRUP 基于系統(tǒng)化設(shè)計， 可最大程度減少全面安全評估的復(fù)雜性. 事實證明， SNTRUP 可以低成本消除格上安全性測評的許多復(fù)雜問題， 同時滿足作為基于小格基密鑰封裝算法的嚴格要求. SNTRUP 具有結(jié)構(gòu)簡潔、密鑰密文尺寸小的優(yōu)點， 是比較利于實用化的方案. 在國際上， NTRU (number theory research unit) 密碼體制已成為IEEE P1363.1 標準[1]， 算法的安全性得到多方認同[2].

2 相關(guān)工作

由于格密碼計算速度快， 通信開銷較小， 且能被用于構(gòu)造各類密碼算法和應(yīng)用， 因此被認為是最有希望的抗量子密碼技術(shù). 其代表算法有NTRU 系列、谷歌的NewHope、同態(tài)加密算法BGV、GSW、BFV等. 文獻[3]首次提出了NTRU 公鑰加密(public key encryption，PKE)方案，該方案被稱為經(jīng)典NTRU.隨后研究者基于NTRU 提出了大量的數(shù)字簽名方案. 文獻[4] 中基于NTRU 提出的簽名方案是GGH 簽名方案[5]相對高效的實例化. 文獻[6] 分析指出GGH 簽名方案及NTRU 簽名方案不夠安全， 并指出這類簽名方案的私鑰是較短的格基， 當簽名次數(shù)過多時， 簽名會暴露出格基形成的基本形態(tài)， 從而泄露私鑰.此后， 為避免泄露私鑰信息， 一些學者構(gòu)造了基于格的新型簽名方案. 其中一個方法是2008 年Gentry 等人[7]提出的GPV 簽名方案， 該方案常被稱為hash and sign 設(shè)計， 需要借助單向陷門函數(shù)進行原像采樣. 另一個方法是2009 年Lyubashevsky[8，9]提出的基于Fiat-Shamir 變換的方法， 該方法不使用陷門函數(shù)， 利用拒絕采樣技術(shù)來避免簽名泄露格基形態(tài). 2014 年， Hoffstein 等人[10]基于NTRU 也提出了hash and sign 類型的簽名方案.

近年來NTRU 的使用得到了進一步發(fā)展. 文獻[11] 給出了五種基于NTRU 體制的全同態(tài)加密方案的分析比較， 指出了基于NTRU 加密方案需要優(yōu)化的部分問題. 文獻[12] 提出了一種基于NTRU 的選擇明文攻擊不可區(qū)分性IND-CPA 安全的全同態(tài)加密方案. 文獻[13] 提出了一種新的全同態(tài)掩碼防御方案， 解決了NTRU 算法在實現(xiàn)過程中的側(cè)信道攻擊安全隱患. 文獻[14] 提出了一種T-NTRU 物聯(lián)網(wǎng)動態(tài)安全接入認證算法， 使用動態(tài)變化時間序列通過哈希函數(shù)來產(chǎn)生動態(tài)密鑰， 解決了固定哈希函數(shù)產(chǎn)生固定密鑰的內(nèi)部攻擊安全問題. 文獻[15] 結(jié)合可逆信息隱藏技術(shù)， 提出一種基于NTRU 的密文域可逆信息隱藏算法， 并將該算法應(yīng)用于圖像加密領(lǐng)域. 文獻[16] 使用NTRU 格上高效的參數(shù)生成算法， 構(gòu)建了一個基于NTRU 格的群簽名方案， 縮短了系統(tǒng)公鑰長度. 總之， 上述研究成果都集中在公鑰加密體制和數(shù)字簽名設(shè)計上， 未對基于NTRU 的密鑰封裝機制進行研究， 也沒有進行密鑰協(xié)商協(xié)議的設(shè)計與硬件實現(xiàn).

本文的工作以NTRU Prime 項目為基礎(chǔ). 該項目中眾多研究小組做出了卓有成效的工作. Biasse等人[17]引入了一種快速量子攻擊算法， 破解了分圓多項式下的短生成器問題. Bauch 等人[18]提出了一種更快的基于多元二次函數(shù)的子域?qū)?shù)攻擊方案. Bernstein 等人[19]給出了NTRU Prime 的原始版本. Hao 等人[20]完成了AVR ATmega1284 微控制器上sntrup653 的實現(xiàn)， 他們使用了8160 665 個周期進行封裝， 15 602 748 個周期進行解封裝. Marotzke[21]在Xilinx Zynq Ultrascale+ FPGA 上實現(xiàn)了sntrup761 的硬件加解密， 其時鐘頻率為271 MHz， 分別在4808 μs、524 μs 和958 μs 內(nèi)完成密鑰生成、封裝和解封裝. 在公鑰密碼算法的FPGA 實現(xiàn)方面， Huang 等人[22]實現(xiàn)了改進的RSA 加密算法， 在4 ns 時鐘下加密速度接近40 kb/s. Kamal 等人[23]完成了NTRUEncrypt 的FPGA 實現(xiàn)， 在4 ns 時鐘下加密速度為20.4 kb/s.

本文的主要貢獻如下:

(1) 提出了一種SNTRUP 算法下的雙向認證密鑰協(xié)商協(xié)議(authentication key agreement protocol based on SNTRUP， SNPAKA). 利用SNTRUP 算法， 在只公布公鑰的前提下， 通信雙方利用Hash 函數(shù)和公鑰加密系統(tǒng)進行數(shù)據(jù)封裝和握手通信， 從而在不泄露任何私密信息的情況下完成雙向身份認證和密鑰交換.

(2) 對SNPAKA 協(xié)議進行了運行和測試. 利用Vivado 平臺編寫相關(guān)VHDL 代碼， 經(jīng)過測試和分析，在3 個參數(shù)下本程序均能快速實現(xiàn)密鑰封裝流程， 且能夠得到正確的會話密鑰. 其運算效率相比文獻[22] 中設(shè)計的RSA1024 改進算法的FPGA 硬件實現(xiàn)提升了4.53 倍， 相比文獻[23] 中設(shè)計的NTRU-Encrypt 算法提升了8.83 倍.

3 預(yù)備知識

3.1 格的定義

設(shè)b1，b2，···，bm為Rn的一組線性無關(guān)向量， 取集合L為b1，b2，···，bm的整線性組合， 即

這樣的集合L稱為格， 其中b1，b2，···，bm稱為格L的一組基或簡稱格基.L的每一組基所含向量的個數(shù)相同， 基中所含向量個數(shù)稱為格L的維數(shù)或秩， 記為dim(L)， 它與L所形成的線性子空間的維數(shù)相同.

3.2 格中困難問題

關(guān)于格有三個著名的NP (non-deterministic polynomial) 問題. 以下L代表一個格，d為格L的維數(shù)，‖·‖為2-范數(shù).

3.3 多項式環(huán)與NTRU 格

這里f，g及f×g中所有單項式系數(shù)均為模q操作， 即將f，g及f×g視作Rq=Zq[X]/XN-1上的元素.R中的元素也可以用向量形式來表示:f(x) 可表示為(f0，f1，···，fN-1).

4 SNTRUP 原理

為了說明SNTRUP 的原理， 表1 給出一些參數(shù)定義.

表1 參數(shù)定義Table 1 Parameter definition

在說明SNTRUP 的原理前， 先簡要分析NTRU 公鑰密碼體制的原理.

4.1 經(jīng)典NTRU 公鑰密碼體制

4.1.1 參數(shù)說明

R上多項式元素的加運算與普通多項式加法一致， 用符號“+” 表示; 但乘法運算為卷積運算. 多項式元素模q運算就是把多項式的系數(shù)分別進行modq運算. 可以證明的是(R，+，×) 是一個環(huán)， 即多項式環(huán).p和q在NTRU 中一般作為模數(shù)， 不一定為素數(shù)， 但要求(p，q)=1， 且q ?p.

令R(d1，d2)={F ∈R}， 其中F中有d1個系數(shù)為1，d2個系數(shù)為-1， 余下系數(shù)為0. 則有多項式集合:Rf=R(df，df-1)，Rg=R(dg，dg)，Rφ=R(dφ，dφ)，Rm={m ∈R}， 其中m的系數(shù)在-(p-1)/2到(p-1)/2 之間.

4.1.2 密鑰生成

隨機生成兩個多項式f ∈Rf，g′∈Rg(這里使用g′以區(qū)分SNTRUP 中的私鑰)， 其中f必須在模p和模q下均有乘法逆元， 假設(shè)這兩個逆元分別為Fp和Fq， 則有:Fq×f ≡1 (modq) 和Fp×f ≡1(modp). 然后計算:h ≡Fq×g′(modq)， 則h為公鑰，f為私鑰.

4.1.3 加密與解密算法

設(shè)明文消息為r ∈Rm， 隨機選取多項式φ ∈Rφ， 利用公鑰h， 計算:c ≡pφ×h+m(modq)， 則c為消息r對應(yīng)的密文. 利用密文c和私鑰f以及Fp計算:a ≡f×c(modq) 其中，a的系數(shù)在區(qū)間[-q/2，q/2] 上. 進一步計算:b ≡Fp×a(modp)， 即為解密后的明文. 其解密正確性可以證明如下:

展開并化簡多項式a:

其中pφ×g模p顯然為零， 從而有:a ≡f×r(modp). 又因b ≡Fp×a(modp)， 由乘法逆元的概念，a中的f也被消去， 從而得到明文消息r(modp).

4.2 SNTRUP 密鑰封裝算法

SNTRUP 有兩個層次. 內(nèi)層是SNTRUP Core， 這部分為非對稱加密算法; 外層是SNTRUP， 這部分為密鑰封裝算法. 本節(jié)將分別介紹， 并分析二者的關(guān)系.

4.2.1 SNTRUP 符號說明與相關(guān)定義

素數(shù)p，q， 正整數(shù)w; 其中2p ≥3w，q ≥16w+1. 推薦參數(shù)集如下:

xp-x-1 為多項式環(huán)(Z/q)[x] 上的不可約多項式.

環(huán)Z[x]/(xp-x-1)，(Z/3)[x]/(xp-x-1) 和(Z/q)[x]/(xp-x-1) 分別簡記為R，R/3，R/q.如果R中某元素的所有系數(shù)均在{-1，0，1}上取值， 則稱該元素為小多項式(Small). 如果R中某元素有w個非零元素， 則稱該元素的重量為w.R中所有重量為w的小多項式的集合稱為短小集(Short).

擴展集(Rounded): 指系數(shù)僅在{-(q-1)/2，···，-6，-3，0，3，6，···，(q-1)/2}(其中q ∈1+3Z)或{-(q+1)/2，···，-6，-3，0，3，6，···，(q+1)/2}(其中q ∈2+3Z) 中取值的R的元素的集合.

擴展函數(shù)(Round)R/Rounded: 設(shè)ai ∈{-(q-1)/2，···，(q-1)/2}，ri是3Z(即3 的倍數(shù)集)中最接近ai的元素， 則Round(a0+···+ap-1xp-1)=r0+r1+···+rp-1xp-1. 對于小多項式e ∈R有Round(r)=r+e.

4.2.2 SNTRUP Core 的密鑰生成

定義公鑰集(PublicKeys):P=R/q; 私鑰集(SecretKeys):S=Short×R/3. 算法1 將輸出P×S中的元素.

算法1 KeyGen (密鑰生成)1 生成一個均勻隨機的小多項式g ∈R， 且判斷g 在R/3 上能否被xp -x-1 整除， 能則可逆， 進入下一步， 否則不可逆， 重復(fù)該步驟直到可逆.2 計算g 在R/3 上的逆元g-1.3 生成一個均勻隨機的多項式f ∈Short (f 非零且在R/q 上可逆， 其中w ≥1).4 在R/q 上計算h = g/(3f) (由于假設(shè)了q 是大于3 的素數(shù)， 所以3 在R/q 上是可逆的， 因而3f 在R/q 上也是可逆的).5 輸出(h，(f，g-1))∈P ×S.

4.2.3 SNTRUP Core 的加密與解密算法

定義明文集(Inputs):I=Short; 密文集(Ciphertexts):C=Rounded.

加密算法Encrypt 將I×P映射到C上， 解密算法Decrypt 將C×S映射到I上， 分別見算法2 和算法3.

算法2 Encrypt (加密算法)1 輸入r ∈I，h ∈P.2 在R/q 上計算hr ∈R/q.3 輸出c = Round(hr).

算法3 Decrypt (解密算法)1 輸入c ∈C，(f，v) ∈Short×R/3.2 在R/q 上計算3fc.3 將上一步所得多項式的系數(shù)模3， 得到多項式e ∈R/3.4 在R/3 上計算ev.5 將ev 變換為小多項式r′ ∈R.6 如果r′ 的重量為w， 則輸出r′， 否則輸出(1，··· ，1，0，··· ，0).

4.2.4 經(jīng)典NTRU 算法SNTRUP Core 的比較

SNTRUP Core 在經(jīng)典NTRU 算法上做出了一些改動， 如表2 所示. 相比較而言， SNTRUP Core 的參數(shù)更為具體， 更有利于使用者選取， 所用多項式環(huán)更加多樣且復(fù)雜， 這增強了對于格攻擊的抵抗能力. 加密過程將明文與公鑰直接進行卷積， 相比經(jīng)典算法大幅提高了安全性.

表2 NTRU 與SNTRUP Core 的比較Table 2 Comparison between NTRU and SNTRUP Core

4.2.5 SNTRUP 的參數(shù)空間

SNTRUP 除了SNTRUP Core 的參數(shù)外， 還增加了以下參數(shù):

(1) 通過確定性編碼(Encode) 算法得到的編碼公/私鑰集， 編碼明/密文集:P →Pcode，S →Scode，I →Icode，C →Ccode， 且均為32 字節(jié)的字符串. 確定性解碼(Decode) 算法為編碼算法的逆運算.

(2) 會話密鑰集(SessionKeys): Se 為32 字節(jié)的字符串.

(3) 認證集(Confirm): Cf 為32 字節(jié)的字符串.

(4) 哈希函數(shù)(Hashing): 定義Hash(z) 為SHA-512(z) 雜湊函數(shù)的前32 字節(jié). 定義Hashb為Hash(z) 中z前再加一字節(jié)b ∈{0，1，···，255}， 也記作Hash(b，z).

(5) 確定性哈希認證(HashConfirm) 算法HC:Icode×Pcode→Cf.定義為: HC(r，K) = Hash2(Hash3(r)，Hash4(K))， 其中，rcode∈Icode，Kcode∈Pcode. 該算法能夠保障發(fā)送方發(fā)送的密文確實是使用公鑰對明文進行加密所得.

(6) 確定性哈希會話(HashSession) 算法HS:{0，1}×Icode×Ccode×Cf→Se.定義為: HS(b，y，z)=Hashb(Hash3(y)，z) 其中，b ∈{0，1}，y ∈Icode，z ∈Ccode× Cf. 該算法使得會話密鑰中同時包含了明文和密文的信息， 從而協(xié)商雙方都可以生成該密鑰.

(7) 設(shè)M= (m0，m1，···，mn-1) 和R= (r0，r1，···，rn-1) 是整數(shù)序列， 且假設(shè)對每個i有0≤ri ≤mi ≤214， 則S= Encode(R，M) 是一個字節(jié)序列， 且S的長度只與M有關(guān)，Decode(Encode(R，M)，M)=R. 則編碼(Encode) 算法見算法4.

算法4 Encode (編碼算法)1 如果n = 0 則s 是一個空序列.2 如果n = 1 則S 是r0 的二進制低位在前形式， 且如果m0 ＞28 就截取前2 字節(jié)， 如果28 ≥m0 ＞1 就取前1 字節(jié)， 否則就取0 字節(jié).3 如果n ≥2 則S 是Encode(R′，M′) 的前綴部分， 其中R′ 和M′ 的長度為「n/2■. 而當i 為偶數(shù)時， 對于每對ri mod mi， ri+1 mod mi+1， 可得: r = ri +mirr+1 mod m = mimi+1， 且0 ＜r′ ＜m′ ＜214， 按這種方法就能得到R′ 和M′ 的每一位. 該過程中當m ≥214 時將r mod 28 添加到前綴中， 同時r，m 被替換為■r/28■和■m/28■， 重復(fù)0-2 次可將m 減小到正確范圍中. 如果n 是奇數(shù)則把mn-1，rn-1 也加入R′ 和M′ 中.4 重復(fù)進行第3 步直到n ＜2.

以下給出多種集合元素的編碼方法.(1) 域元素的編碼對于R/q中的元素， 系數(shù)處于{-(q-1)/2，···，-1，0，1，···，(q-1)/2}， 給每個系數(shù)加(q-1)/2使系數(shù)處在{0，1，···，q-1}中. 后使用編碼算法， 其中M=(q，···，q).

(2) 擴展集元素的編碼擴展集中的元素系數(shù)處于{-(q-1)/2，···，-6，-3，0，3，6，···，(q-1)/2}，給每個系數(shù)加(q-1)/2后除以3 ， 從而使系數(shù)處在{0，1，···，(q-1)/3}中， 然后使用編碼算法， 其中M=((q-1)/3+1，···，(q-1)/3+1).

(3) 短小集元素的編碼短小集元素系數(shù)處于{-1，0，1}中， 給每個系數(shù)加1 ， 從而使系數(shù)處于{0，1，2}中. 將每四個元素按低位在前合為一個數(shù)， 從而得到一個字節(jié)， 元素整體長度變?yōu)樵鹊摹竝/4

4.2.6 SNTRUP 的密鑰生成

隨機化算法KeyGen′將輸出Pcode×Se′中的元素， 其中Se′=Scode×Pcode×Icode， 見算法5.

算法5 KeyGen′ (SNTRUP 密鑰生成)1 通過SNTRUP Core 的KeyGen 算法得到(K，k)，K 和k 分別對應(yīng)公鑰和私鑰.2 將K 編碼為Kcode ∈Pcode.3 將k 編碼為kcode ∈Scode.4 生成均勻隨機的ρ ∈Icode.5 輸出(Kcode，(kcode，Kcode，ρ)).

4.2.7 SNTRUP 的封裝與解封裝算法

隨機化算法Encap 通過輸入Pcode中的元素， 輸出C′×Se 中的元素， 其中C′=Ccode×Cf， 見算法6.

算法6 Encap (封裝算法)1 輸入Kcode ∈Pcode， 對Kcode 進行解碼得到K ∈P.2 輸入明文r ∈I， 對r 進行編碼得到rcode ∈Icode.3 計算e = Encrypt(r，K) ∈C， 對e 進行編碼得到ecode ∈Ccode.4 E = (ecode，HC(rcode，Kcode)) ∈Ccode ×Cf.5 輸出(E，HS(1，rcode，E)).

隨機化算法Decap 通過輸入C′×Se′中的元素， 輸出Se 中的元素， 見算法7.

算法7 Decap (解封裝算法)1 輸入E = (ecode，γ) ∈Ccode ×Cf 和(kcode，Kcode，ρ) ∈Scode ×Pcode ×Icode.2 對ecode 進行解碼得到e ∈C.3 對kcode 進行解碼得到k ∈S.4 計算r′ = Decrypt(e，k) ∈I.5 按照Encap 的步驟計算r′code， 最后重新求出一個密文E′.6 如果E′ = E 則輸出HS(1，rcode，E)， 否則輸出HS(0，ρ，E).code、e′、e′

4.2.8 SNTRUP 兩層次的關(guān)系

SNTRUP 兩個層次之間關(guān)系密切， 如圖1 所示. 可以看出， 任何信息在封裝與解封裝模塊外均為編碼狀態(tài)， 而SNTRUP Core 加解密模塊可以看作其子模塊， 該子模塊的輸入和輸出信息都是未經(jīng)編碼的. 編碼后由于信息長度被固定為32 字節(jié)， 因此E共有64 字節(jié)， 前32 字節(jié)為編碼后的密文e′code， 后32 字節(jié)為哈希認證值HC， 而其他的輸入輸出則均為32 字節(jié)， 這極大方便了通信雙方對信息的接收與輸出.

圖1 SNTRUP 兩層次關(guān)系圖Figure 1 Relations between two hierarchies of SNTRUP

4.3 雙向認證密鑰協(xié)商協(xié)議SNPAKA 設(shè)計

設(shè)計的SNPAKA 協(xié)議說明如下:

第一階段: 參數(shù)與密鑰生成

(1) 密鑰Kcode: 32 字節(jié)公鑰字符串， 通過上文KeyGen′算法生成.kcode: 32 字節(jié)私鑰字符串， 通過上文KeyGen′算法生成.

(2) 參數(shù)ρ: 32 字節(jié)反饋信息字符串， 包含了Alice 與Bob 事先約定好的Alice 的認證信息.rcode: 32 字節(jié)身份信息字符串， 包含了Alice 與Bob 事先約定好的Bob 的認證信息.

第二階段: AKA 協(xié)議執(zhí)行

SNPAKA 協(xié)議交互流程如圖2 所示.

圖2 雙向認證密鑰協(xié)商流程Figure 2 Two-directional authentication key agreement process

(1) Alice 作為密鑰協(xié)商過程發(fā)起方， 首先生成密鑰(Kcode，(kcode，Kcode，ρ))， 其中Kcode作為公鑰由他人使用， (kcode，Kcode，ρ) 包含公/私鑰對與反饋信息ρ， 由Alice 謹慎保管. 監(jiān)聽者在該步驟僅能獲得公鑰Kcode.

(2) Bob 接收公鑰Kcode并利用上文Encap 算法求出(E，HS(1，rcode，E)). 其中rcode∈Icode為Bob 的身份信息， HS(1，rcode，E) 為會話密鑰. 這里的E= (ecode，HC(rcode，Kcode)) 包含了密文和認證密鑰兩部分， 后者表明密文e是使用公鑰對明文加密后求得. 使用哈希函數(shù)保證了無法由E反推得到rcode，Kcode. 之后， 將密文E傳送給Alice. 監(jiān)聽者在該步驟僅能獲得無法解密的密文E.

(3) Alice 利用上文Decap 算法求出rcode和E′， 并判斷E′=E是否成立， 以此來判斷Bob 是否是會話密鑰的持有者. 如果是， 則通過E和rcode求出HS(1，rcode，E)， 并利用該哈希值將反饋信息ρ進行對稱加密得到ρ′并輸出. 監(jiān)聽者在該步驟僅能獲得無法解密的ρ′.

(4) Bob 接收到Alice 發(fā)出的加密后的反饋信息ρ′， 并利用自己的會話密鑰HS(1，rcode，E) 對其進行解密. 至此雙方都知道了對方的身份以及擁有會話密鑰的事實.

此后雙方使用該會話密鑰進行對稱加密通信， 從而實現(xiàn)了雙向的認證與密鑰協(xié)商. 整個過程中監(jiān)聽者未能獲得任何敏感信息， 從而保證了協(xié)議的安全性. 與一般密鑰協(xié)商協(xié)議相比， 本協(xié)議核心為SNTRUP算法， 因而可以更快地進行大量加解密和密鑰封裝操作， 極大提高了密鑰協(xié)商的效率.

5 FPGA 實現(xiàn)及性能測試

FPGA(現(xiàn)場可編程邏輯門陣列， field programmable gate array)，是一種可以根據(jù)需求對底層電路結(jié)構(gòu)進行設(shè)計與更新的芯片， 通過使用FPGA 內(nèi)部邏輯資源構(gòu)建計算電路、例化大量計算引擎， 可以提高計算并行度，實現(xiàn)對指定算法的加速計算. SNPAKA 的FPGA 實現(xiàn)基于SNTRUP 密鑰封裝算法，在Xilinx Vivado 平臺下編寫代碼測試程序， 進行行為級仿真， 對SNTRUP 密鑰封裝算法進行測試. 以參數(shù)857 為例， 通過輸入公鑰、隨機數(shù)與密文， 將程序輸出的密鑰、密文和哈希值與預(yù)先計算的結(jié)果進行比較. 之后運行參數(shù)653 和參數(shù)761， 分析并比較其運算性能. 測試環(huán)境為: Windows 10 操作系統(tǒng)， Vivado 2020.1.1 工程平臺. 依照上述算法， 本程序共設(shè)計了10 個模塊， 如表3 所示. 在具體實現(xiàn)時， 使用了Karatsuba 快速乘法算法[24]進行大數(shù)相乘， 極大降低了算法復(fù)雜度.

表3 設(shè)計的FPGA 程序模塊Table 3 Modules in FPGA implementation

5.1 測試結(jié)果與分析

私鑰生成部分結(jié)果如圖3 所示.

圖3 私鑰生成結(jié)果Figure 3 Private key generating result

圖3 中， private_key_out_valid 為私鑰輸出指示信號; private_key_out 為私鑰輸出; private_key_out_tb 為讀取測試文件中的私鑰. 可見私鑰生成與預(yù)先計算的結(jié)果一致.

公鑰生成部分結(jié)果如圖4 所示.

圖4 公鑰生成結(jié)果Figure 4 Public key generating result

圖4 中， public_key_out_valid 為公鑰輸出指示信號; public_key_out 為公鑰輸出; private_key_out_tb 含義同圖3. 可見公鑰生成與預(yù)先計算的結(jié)果一致.

密文部分結(jié)果如圖5 所示.

圖5 密文結(jié)果Figure 5 Ciphertext result

圖5 中， cipher_output_valid 為密文輸出指示信號; cipher_output 為封裝后的密文輸出; output_tb 為讀取測試文件中的密文. 可見密文與預(yù)先計算的結(jié)果一致.

解封裝哈希輸出如圖6 所示.

圖6 解封裝結(jié)果Figure 6 Decapsulation result

5.2 算法性能分析

5.2.1 三種參數(shù)下的運算性能

(1) 參數(shù)857 下的運算測試

通過實際測試， SNTRUP 密鑰封裝算法在參數(shù)857 下運算速度如表4 所示.

表4 參數(shù)857 下的運算速度Table 4 Computing speed under parameter 857

(2) 參數(shù)761 下的運算測試

通過實際測試， SNTRUP 密鑰封裝算法在參數(shù)761 下運算速度如表5 所示.

表5 參數(shù)761 下的運算速度Table 5 Computing speed under parameter 761

(3) 參數(shù)653 下的運算測試

通過實際測試， SNTRUP 密鑰封裝算法在參數(shù)653 下運算速度如表6 所示.

表6 參數(shù)653 下的運算速度Table 6 Computing speed under parameter 653

通過圖7， 可以看到三種參數(shù)下的運算性能， 隨著參數(shù)逐漸增大， 運算速度呈現(xiàn)平緩下降趨勢.

圖7 三種參數(shù)下運算速度比較(kb/s)Figure 7 Comparison of computing speed among three parameters (kb/s)

5.2.2 資源占用情況分析

經(jīng)過FPGA 實際仿真測試， 可以得到資源使用情況如表7 所示. 可以看出， 隨著參數(shù)逐漸增大， 查找表(LUT) 使用數(shù)量呈遞增趨勢. 這是由于輸入長度的增加導(dǎo)致了程序?qū)Ω鞣NRAM 的需求增多. FF 與LUTRAM 使用量僅有小幅波動. BRAM、DSP、IO、BUFG 均不隨參數(shù)變化而變化. 雖然參數(shù)增大提升了SNTRUP 的安全性， 但代價是運算速度隨之降低. 因而選擇參數(shù)時既要考慮安全性也要考慮實際應(yīng)用場合. 可以看到， 本測試程序所用資源遠遠小于FPGA 芯片中所含資源; 可見SNTRUP 密鑰封裝算法十分輕巧， 便于使用.

表7 硬件資源使用情況Table 7 Hardware resource usage

5.3 與其他公鑰加密算法的對比

選擇同樣使用FPGA 實現(xiàn)的改進的RSA1024 公鑰加密算法和基于NTRU 的NTRUEncrypt 公鑰加密算法作為比較對象， 可得表8. 可以看出， 與改進的RSA1024 公鑰加密算法相比， SNTRUP 算法運算速度是其4.53 倍. 而與同樣基于NTRU 的NTRUEncrypt 公鑰加密算法相比， SNTRUP 算法速度為其8.83 倍.

表8 三種算法運算速度對比Table 8 Comparison of computing speed among three algorithms

6 安全性分析

本節(jié)將從SNTRUP 本身和FPGA 實現(xiàn)兩方面對安全性進行分析. 目前針對SNTRUP 算法的攻擊方式主要為格攻擊和中間相遇攻擊.

6.1 格攻擊

6.2 中間相遇攻擊

NTRU 分析中通常取E= 2p. Wunderer 等人[36]歸納了Schanck 的建議， 將傳統(tǒng)的中間相遇攻擊替換為了量子搜索， 這將增加了L的循環(huán)次數(shù)， 又節(jié)約了大量存儲空間. 另一方面，L次循環(huán)應(yīng)該是連續(xù)的， 在限定時間T內(nèi)要求完成(L/T)2次并行量子搜索， 這也大大增加了實際計算開銷.到目前為止， 還沒有出現(xiàn)能夠有效解決格中困難問題的量子算法， SNTRUP 算法能夠很好抵抗格攻擊和中間相遇攻擊， 它也是學者公認安全性較好的基于格問題的公鑰加密方案.

6.3 對硬件的分析攻擊

分析攻擊是指密碼分析者從FPGA 芯片本身通過能量分析或直接讀取的方式來直接獲取密鑰信息.本實現(xiàn)方案采用每次開始加密或上電時隨機生成密鑰存入bram， 使用完成后直接擦除bram 的方式， 保證分析者無法直接讀取密鑰信息. 另外， 由于密鑰生成的隨機性， 對同一個明文即使反復(fù)加密， 對芯片探測所得能量譜也有巨大差異， 分析者很難通過對硬件進行分析而獲取密鑰信息.

7 總結(jié)

在NIST 開展的抗量子密碼算法征集與標準化過程中， 格密碼因其優(yōu)異的性能而備受關(guān)注. NTRU和NTRU Prime 作為格密碼的典型代表具有重要的研究意義. 本文給出了SNTRUP Core 加密/解密模塊與SNTRUP 封裝/解封裝模塊的層次關(guān)系， 利用SNTRUP 的密鑰封裝特性， 設(shè)計了雙向認證密鑰協(xié)商協(xié)議SNPAKA， 通過四步握手實現(xiàn)了快速認證密鑰協(xié)商過程， 并進行了FPGA 實際測試. 經(jīng)過測試和分析， 該方案密鑰生成速度為198.22 kb/s， 封裝速度為1983.27 kb/s， 解封裝速度為919.84 kb/s， 相比經(jīng)典NTRU 算法NTRUEncrypt 提升了8.83 倍， 相比RSA1024 公鑰加密方案提升近了4.53 倍. 最后分析了SNTRUP 的安全性， 給出兩種攻擊下對SNTRUP 安全性的分析. 下一步我們將繼續(xù)對SNPAKA 進行完善， 對其硬件快速實現(xiàn)做進一步優(yōu)化.