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

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

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

1 引言

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

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

2 相關(guān)工作

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

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

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

本文的主要貢獻(xiàn)如下:

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

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

3 預(yù)備知識(shí)

3.1 格的定義

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

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

3.2 格中困難問題

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

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

這里f，g及f×g中所有單項(xiàng)式系數(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 的原理前， 先簡(jiǎn)要分析NTRU 公鑰密碼體制的原理.

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

4.1.1 參數(shù)說明

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

令R(d1，d2)={F ∈R}， 其中F中有d1個(gè)系數(shù)為1，d2個(gè)系數(shù)為-1， 余下系數(shù)為0. 則有多項(xiàng)式集合: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 密鑰生成

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

4.1.3 加密與解密算法

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

展開并化簡(jiǎn)多項(xiàng)式a:

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

4.2 SNTRUP 密鑰封裝算法

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

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

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

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

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

擴(kuò)展集(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的元素的集合.

擴(kuò)展函數(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. 對(duì)于小多項(xiàng)式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è)均勻隨機(jī)的小多項(xiàng)式g ∈R， 且判斷g 在R/3 上能否被xp -x-1 整除， 能則可逆， 進(jìn)入下一步， 否則不可逆， 重復(fù)該步驟直到可逆.2 計(jì)算g 在R/3 上的逆元g-1.3 生成一個(gè)均勻隨機(jī)的多項(xiàng)式f ∈Short (f 非零且在R/q 上可逆， 其中w ≥1).4 在R/q 上計(jì)算h = g/(3f) (由于假設(shè)了q 是大于3 的素?cái)?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 上計(jì)算hr ∈R/q.3 輸出c = Round(hr).

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

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

SNTRUP Core 在經(jīng)典NTRU 算法上做出了一些改動(dòng)， 如表2 所示. 相比較而言， SNTRUP Core 的參數(shù)更為具體， 更有利于使用者選取， 所用多項(xiàng)式環(huán)更加多樣且復(fù)雜， 這增強(qiáng)了對(duì)于格攻擊的抵抗能力. 加密過程將明文與公鑰直接進(jìn)行卷積， 相比經(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) 算法為編碼算法的逆運(yùn)算.

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

(3) 認(rèn)證集(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) 確定性哈希認(rèn)證(HashConfirm) 算法HC:Icode×Pcode→Cf.定義為: HC(r，K) = Hash2(Hash3(r)，Hash4(K))， 其中，rcode∈Icode，Kcode∈Pcode. 該算法能夠保障發(fā)送方發(fā)送的密文確實(shí)是使用公鑰對(duì)明文進(jìn)行加密所得.

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

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

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

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

(2) 擴(kuò)展集元素的編碼擴(kuò)展集中的元素系數(shù)處于{-(q-1)/2，···，-6，-3，0，3，6，···，(q-1)/2}，給每個(gè)系數(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}中， 給每個(gè)系數(shù)加1 ， 從而使系數(shù)處于{0，1，2}中. 將每四個(gè)元素按低位在前合為一個(gè)數(shù)， 從而得到一個(gè)字節(jié)， 元素整體長(zhǎng)度變?yōu)樵鹊摹竝/4

4.2.6 SNTRUP 的密鑰生成

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

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

4.2.7 SNTRUP 的封裝與解封裝算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 FPGA 實(shí)現(xiàn)及性能測(cè)試

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5.2 算法性能分析

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

(1) 參數(shù)857 下的運(yùn)算測(cè)試

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

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

(2) 參數(shù)761 下的運(yùn)算測(cè)試

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

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

(3) 參數(shù)653 下的運(yùn)算測(cè)試

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

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

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

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

5.2.2 資源占用情況分析

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

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

5.3 與其他公鑰加密算法的對(duì)比

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

表8 三種算法運(yùn)算速度對(duì)比Table 8 Comparison of computing speed among three algorithms

6 安全性分析

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

6.1 格攻擊

6.2 中間相遇攻擊

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

6.3 對(duì)硬件的分析攻擊

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

7 總結(jié)

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