Aigis密鑰封裝算法多平臺(tái)高效實(shí)現(xiàn)與優(yōu)化

沈詩(shī)羽 何 峰 趙運(yùn)磊

(復(fù)旦大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院 上海 200433)

近年來(lái),為應(yīng)對(duì)大數(shù)據(jù)和互聯(lián)網(wǎng)時(shí)代對(duì)計(jì)算能力的需求,各國(guó)都對(duì)量子計(jì)算研究投入了極大的力度和資源.谷歌、IBM、阿里、騰訊等公司相繼成立了實(shí)驗(yàn)室來(lái)研究量子計(jì)算與后量子安全技術(shù).谷歌于2019年研制出53位量子比特計(jì)算機(jī)[1], 可于3 min 20 s內(nèi)完成世界第一超級(jí)計(jì)算機(jī)Summit一萬(wàn)年才能完成的計(jì)算任務(wù).2020年Yang等人[2]研制出能在超過1 K溫度下運(yùn)作的量子計(jì)算平臺(tái),在實(shí)用性方面取得了巨大的突破.2021年美國(guó)芝加哥大學(xué)和阿貢實(shí)驗(yàn)室研究人員利用超導(dǎo)同軸電纜提高量子態(tài)傳輸保真度,首次實(shí)現(xiàn)確定性多量子比特糾纏,為構(gòu)建大規(guī)模量子計(jì)算機(jī)提供了一種模塊化的方法[3].

量子計(jì)算主要通過利用量子疊加與糾纏兩大量子物理學(xué)特性帶來(lái)的強(qiáng)大并行處理性來(lái)超越經(jīng)典計(jì)算的性能,且其計(jì)算模型中的特殊性質(zhì)也給抗量子密碼算法方案設(shè)計(jì)帶來(lái)了巨大挑戰(zhàn).隨著量子計(jì)算機(jī)的出現(xiàn)與量子計(jì)算技術(shù)的不斷推進(jìn),現(xiàn)代密碼算法面臨著前所未有的挑戰(zhàn).傳統(tǒng)的公鑰密碼設(shè)施大多基于離散對(duì)數(shù)或大整數(shù)分解困難問題,如聯(lián)邦信息處理標(biāo)準(zhǔn)出版物(FIPS)186[4]中規(guī)定的數(shù)字簽名方案和美國(guó)國(guó)家標(biāo)準(zhǔn)與技術(shù)局(NIST)特別出版物(SP)800-56A和(SP)800-56B[5-6]中規(guī)定的密鑰建立機(jī)制. 這些公鑰密碼算法雖然目前尚無(wú)法被傳統(tǒng)計(jì)算機(jī)攻破,但是均可在量子計(jì)算機(jī)中找到多項(xiàng)式時(shí)間的破解方法[7]. 密碼技術(shù)是國(guó)家網(wǎng)絡(luò)空間安全的關(guān)鍵技術(shù),公鑰密碼體制在網(wǎng)絡(luò)、金融、軍事等方面都有著舉足輕重的作用,它被廣泛用于各種網(wǎng)絡(luò)安全協(xié)議中,如IPSEC，TLS等.因此,實(shí)現(xiàn)抵抗量子攻擊的新型密碼體制,即后量子密碼(post-quantum cryptography, PQC),是目前重要的研究方向.

為了應(yīng)對(duì)量子計(jì)算的威脅,2016年美國(guó)國(guó)家標(biāo)準(zhǔn)與技術(shù)局(NIST)開展后量子密碼算法征集,向全球?qū)W者征集后量子密碼算法[8].2019年中國(guó)密碼學(xué)會(huì)也舉辦了全國(guó)密碼算法設(shè)計(jì)競(jìng)賽,旨在為我國(guó)制定后量子算法標(biāo)準(zhǔn)做準(zhǔn)備[9].后量子密碼的構(gòu)造主要包括基于編碼(Code-based)、基于哈希(Hash-based)、基于多變量(Multivariate-based)、基于格(Lattice-based)和基于同源(Isogeny-based)的.近期, NIST宣布了第3輪7個(gè)進(jìn)入決賽(finalists)的算法[10],其中5個(gè)是基于格構(gòu)建的. 相較于其他后量子密碼技術(shù)路線,基于格的密碼方案具有理論上的最壞情況困難保證[11],計(jì)算速度更快,更易于并行,而且通信開銷較小,可用于構(gòu)造多種功能強(qiáng)大的密碼方案,如公鑰加密、數(shù)字簽名、全同態(tài)加密等.我國(guó)密碼算法設(shè)計(jì)競(jìng)賽一等獎(jiǎng)Aigis方案[12-13]即是格上構(gòu)建的基于非對(duì)稱模-LWE(A-MLWE)與非對(duì)稱SIS(A-SIS)困難問題的方案,包含密鑰封裝機(jī)制Aigis-enc與數(shù)字簽名方案Aigis-sig. 對(duì)于密鑰封裝機(jī)制,相比于NIST第3輪中基于MLWE問題的Kyber方案,Aigis密鑰封裝算法(簡(jiǎn)記為Aigis-enc)需要基于額外的假設(shè),但通過壓縮公鑰以及密鑰和噪聲從不同的分布中采樣,Aigis-enc在安全性與錯(cuò)誤率之間取得了更好的權(quán)衡.

為了應(yīng)對(duì)量子攻擊,維護(hù)國(guó)家網(wǎng)絡(luò)空間的長(zhǎng)遠(yuǎn)安全,為未來(lái)國(guó)家后量子密碼算法標(biāo)準(zhǔn)的制定和實(shí)際部署貢獻(xiàn)力量,對(duì)我國(guó)自行研發(fā)的優(yōu)秀后量子密碼算法進(jìn)行優(yōu)化具有重要意義.本文重點(diǎn)關(guān)注Aigis-enc算法在不同平臺(tái)的實(shí)現(xiàn)優(yōu)化,包含高性能平臺(tái)的快速并行實(shí)現(xiàn)與嵌入式低功耗平臺(tái)的緊湊實(shí)現(xiàn).對(duì)此,本文充分利用了單指令多數(shù)據(jù)(single instruction multiple data, SIMD)指令集,如Intel的AVX2指令集和ARM Cortex-M4的數(shù)字信號(hào)處理(DSP)指令集, 對(duì)算法底層多項(xiàng)式運(yùn)算以及算法運(yùn)行所需堆棧與存儲(chǔ)空間進(jìn)行優(yōu)化. 特別地，據(jù)我們所知，本文工作提供了首個(gè)Aigis-enc的ARM Cortex-M4平臺(tái)的輕量級(jí)緊湊實(shí)現(xiàn). 具體而言，本文的主要貢獻(xiàn)有5個(gè)方面:

1) 使用了改進(jìn)版有符號(hào)數(shù)Montgomery約減與Barrett約減,并運(yùn)用乘加指令減少了ARM Cortex-M4平臺(tái)模約減所需指令條數(shù),提升約減效率;

2) 使用了刪減層數(shù)的數(shù)論變換(T-NTT)并提供AVX2與ARM的匯編實(shí)現(xiàn),相比與傳統(tǒng)NTT,刪減了變換的最后一層,極大地減少了預(yù)計(jì)算表存儲(chǔ)需求;

3) 對(duì)多項(xiàng)式壓縮并編碼為字節(jié)流和字節(jié)流解碼并解壓縮這2個(gè)核心多項(xiàng)式序列化與反序列化操作,使用一個(gè)乘法和一個(gè)移位運(yùn)算來(lái)替換耗時(shí)高的除法,并借助AVX2并行處理加快整個(gè)過程;

4) 調(diào)整算式結(jié)構(gòu)以充分適應(yīng)各平臺(tái)指令特性,從而達(dá)到減少總指令數(shù)目與load/store指令開銷的目的;

5) 采用on-the-fly計(jì)算與空間復(fù)用的優(yōu)化方法,大幅減少了運(yùn)行所需堆棧空間、代碼大小以及存儲(chǔ)占用.

實(shí)驗(yàn)結(jié)果表明：綜合本文提及的優(yōu)化技術(shù),在8核Intel Core i7處理器上可將Aigis-enc算法原始AVX2實(shí)現(xiàn)提升25%,且大幅減少了其在ARM Cortex-M4平臺(tái)的預(yù)計(jì)算表存儲(chǔ)、代碼尺寸與運(yùn)行堆棧占用,對(duì)算法實(shí)際應(yīng)用有重要價(jià)值.

1 相關(guān)工作

基于格的密碼體制首先由Ajtai[14]提出.2005年Regev[15]提出的格上基于錯(cuò)誤學(xué)習(xí)(LWE)問題的密碼方案極大提升了格密碼算法的效率,目前格密碼已經(jīng)成為密碼學(xué)領(lǐng)域的研究熱點(diǎn).NIST后量子標(biāo)準(zhǔn)化進(jìn)程中,基于模格的密鑰封裝算法Kyber是第3輪入選算法之一.Zhang等人[12]觀察到MLWE問題的私鑰與噪音分布對(duì)方案安全性與錯(cuò)誤率的影響不對(duì)等,從而提出了A-MLWE與A-SIS問題,并在此基礎(chǔ)上構(gòu)造了Aigis算法.其中,密鑰封裝機(jī)制Aigis-enc可視為Kyber的變體,但能更好地平衡安全性與錯(cuò)誤率.自第2輪算法提交以來(lái),Kyber取消了對(duì)公鑰的壓縮,而Aigis-enc保留了該操作.

算法性能是衡量算法優(yōu)劣的重要指標(biāo)之一,近年來(lái),學(xué)者們提出了很多針對(duì)格密碼算法的軟件優(yōu)化實(shí)現(xiàn)方法[16],包含AVX2并行快速實(shí)現(xiàn)與ARM Cortex-M4平臺(tái)的輕量級(jí)實(shí)現(xiàn).2016年Alkim等人[17]公開了基于RLWE困難問題的NewHope算法,算法參數(shù)設(shè)計(jì)使得其適合使用數(shù)論變換(number theoretic transform, NTT)加速多項(xiàng)式乘法,且使用浮點(diǎn)型NTT進(jìn)行實(shí)現(xiàn).Avanzi等人[18-19]于2018年公開了Kyber第1輪算法實(shí)現(xiàn),包含C參考實(shí)現(xiàn)、C優(yōu)化實(shí)現(xiàn)與AVX2優(yōu)化實(shí)現(xiàn).該實(shí)現(xiàn)中使用了lbq層變換的整型NTT.隨后,在第2輪提交中,該團(tuán)隊(duì)對(duì)算法參數(shù)進(jìn)行了調(diào)整,刪減了NTT層數(shù)以降低q的規(guī)模[20].對(duì)于ARM Cortex-M4平臺(tái)實(shí)現(xiàn),pqm4[21]提供了一個(gè)Cortex-M4微處理器上算法運(yùn)行時(shí)鐘周期與堆棧空間的測(cè)試框架.目前,Kyber算法的M4實(shí)現(xiàn)已被納入該項(xiàng)目.2020年Alkim等人[22]基于其2016年的工作[17],對(duì)NewHope算法的設(shè)計(jì)與ARM實(shí)現(xiàn)進(jìn)行改進(jìn),并使用該技術(shù)優(yōu)化了Kyber的堆棧使用.

目前尚未有針對(duì)7681模數(shù)的匯編指令實(shí)現(xiàn).本文在充分結(jié)合運(yùn)用這些優(yōu)化技術(shù)的基礎(chǔ)上,進(jìn)一步調(diào)整代碼運(yùn)算結(jié)構(gòu),優(yōu)化了多項(xiàng)式序列化、加解密過程,結(jié)合空間復(fù)用等方法,將指令個(gè)數(shù)與存儲(chǔ)降至最低,從而給出了首個(gè)針對(duì)該模數(shù)高效緊湊的優(yōu)化實(shí)現(xiàn)方案.

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

本節(jié)給出了本文工作相關(guān)的預(yù)備知識(shí).首先定義了變量符號(hào)、數(shù)學(xué)運(yùn)算與格上困難問題,接著詳細(xì)描述Aigis-enc算法并介紹了實(shí)現(xiàn)平臺(tái)與優(yōu)化方式.

2.1 基本定義及符號(hào)說(shuō)明

4) 算法參數(shù).算法方案描述中,n為多項(xiàng)式的維度,q為模數(shù),l表示向量的維度,lbm表示消息編碼中1 b可編碼結(jié)果的個(gè)數(shù).此外,η表示噪聲的大小,d(或t)表示Zq域的整數(shù)被壓縮(或刪減)的比特?cái)?shù),g=2d,其下標(biāo)指示操作對(duì)象.pk,sk與ct分別表示公鑰、私鑰與密文,B為通信帶寬,是公鑰和密文長(zhǎng)度的總和(單位為字節(jié)).方案分析中,δ表示解密的錯(cuò)誤率,pq-sec表示后量子安全等級(jí),K表示待封裝密鑰.

2.2 Aigis-enc算法介紹

Aigis-enc方案是基于A-MLWE困難問題的后量子密鑰分裝算法,其核心構(gòu)造為IND-CPA安全的公鑰加密PKE=(KeyGen,Enc,Dec),由密鑰生成、加密和解密3個(gè)部分組成,遵循文獻(xiàn)[23]的設(shè)計(jì)框架.在此框架基礎(chǔ)上,通過FO轉(zhuǎn)換(Fujisaki-Okamoto transformation)[24]可構(gòu)建IND-CCA安全的密鑰封裝機(jī)制KEM=(KeyGen,Encaps,Decaps).由于目前FO轉(zhuǎn)換已有較為統(tǒng)一的模塊化實(shí)現(xiàn)方案,且多為對(duì)PKE所涵蓋函數(shù)接口的調(diào)用,所以本文重點(diǎn)關(guān)注Aigis-enc方案中IND-CPA安全的公鑰加密模塊,進(jìn)而開展對(duì)底層多項(xiàng)式運(yùn)算的優(yōu)化實(shí)現(xiàn).在文獻(xiàn)[23]加密框架的基礎(chǔ)上,私鑰與噪音服從中心二項(xiàng)分布χα,其值在區(qū)間[-α,α]內(nèi).Zhang等人[12]觀察到,α的值對(duì)方案安全性與正確性起著不對(duì)等的作用,換模壓縮技術(shù)的使用也使得秘密向量及其對(duì)應(yīng)的噪音向量在最終噪音項(xiàng)中起著不對(duì)等的作用.由此,Aigis-enc中秘密向量與噪音向量分別從不同的分布χs與χe中采樣,選取了非對(duì)稱體制來(lái)平衡參數(shù)間的影響.

Aigis-enc-PKE的密鑰生成算法如算法1所示.密鑰生成時(shí)首先從n位二進(jìn)制串中均勻采樣出σ和ρ,然后將隨機(jī)種子ρ傳入Sam和Parse函數(shù)以生成NTT域上的矩陣A,接著以σ為參數(shù)通過CBD算法生成私鑰s和噪音向量e,最后計(jì)算As+e后并壓縮,與ρ拼接形成公鑰pk.

算法1.Aigis-enc-PKE密鑰生成算法.

輸出: 公鑰pk(t,ρ),私鑰sks.

① functionAigis-enc.KeyGen( )

②σ,ρ←{0,1}n;

③A～Parse(Sam(ρ));

⑤tCompressq(As+e,dt);

⑥ return (pk(t,ρ),sks).

⑦ end function

算法2.Aigis-enc-PKE加密算法.

輸入:公鑰pk(t,ρ)、待加密消息msg、隨機(jī)數(shù)r;

輸出:密文ct(c1,c2).

① functionAigis-enc.Enc(pk,msg,r)

③A～Parse(Sam(ρ));

⑤uAT·r+e1;

⑥v

⑦vv+Decompressq(msg,dm);

⑧c1Compressq(u,du);

⑨c2Compressq(v,dv);

⑩ returnct(c1,c2).

Aigis-enc-PKE的解密算法如算法3所示.算法傳入?yún)?shù)為密鑰sk和密文ct,通過對(duì)密文ct,即c1和c2進(jìn)行解壓縮,分別得到u和v,最后解碼v-sT·u得到明文msg.

算法3.Aigis-enc-PKE解密算法.

輸入: 私鑰sks、密文ct(c1,c2);

輸出: 解密消息msg.

① functionAigis-enc.Dec( )

②uDecompressq(c1,du);

③vDecompressq(c2,dv);

④msgCompressq(v-sT·u,dm);

⑤ returnmsg.

⑥ end function

2.3 實(shí)現(xiàn)平臺(tái)與SIMD指令

SIMD是一種采用一個(gè)控制器控制多個(gè)平行的處理單元、同時(shí)對(duì)一組向量化數(shù)據(jù)的每個(gè)元素執(zhí)行相同操作的并行技術(shù).相比于多進(jìn)程并發(fā)運(yùn)算,該技術(shù)實(shí)現(xiàn)的是空間上的數(shù)據(jù)級(jí)并行,同一時(shí)刻只有一個(gè)進(jìn)程被執(zhí)行.SIMD技術(shù)多用于實(shí)現(xiàn)一些簡(jiǎn)單的通用運(yùn)算,如算術(shù)運(yùn)算、邏輯運(yùn)算、數(shù)據(jù)排列混合、數(shù)據(jù)批量加載與存儲(chǔ)等.

高級(jí)向量擴(kuò)展(advanced vector extensions, AVX)指令集是x86架構(gòu)微處理器中一種128 b的SIMD指令集,由英特爾提出,隨后也得到了AMD的支持.AVX2指令集是AVX的延伸,將大多數(shù)作用于整數(shù)上的指令擴(kuò)展至256 b,以增加一倍的運(yùn)算效率.另外,三操作數(shù)運(yùn)算指令的支持也減少了操作數(shù)的額外復(fù)制消耗.

ARM Cortex-M4是ARMv7E-M架構(gòu)的數(shù)字信號(hào)控制器,以滿足高性能通用代碼處理以及數(shù)字信號(hào)處理應(yīng)用的需求.其核心通用指令集包含基本的Thumb-1,Thumb-2指令,以及32 b寬乘法.另外,ARM Cortex-M4也提供了SIMD指令,即數(shù)字信號(hào)處理(digital signal processing, DSP)擴(kuò)展指令集.該指令集可在32 b寬的寄存器內(nèi)同時(shí)對(duì)4個(gè)8 b或2個(gè)16 b整數(shù)進(jìn)行操作.

在格密碼算法中,底層操作多為互相獨(dú)立的多項(xiàng)式系數(shù)算術(shù)運(yùn)算與邏輯運(yùn)算,非常適合用SIMD指令進(jìn)行并行優(yōu)化.Aigis-enc算法中多項(xiàng)式系數(shù)規(guī)模為16 b,使用AVX2可實(shí)現(xiàn)16個(gè)數(shù)據(jù)的并行運(yùn)算,DSP可實(shí)現(xiàn)2個(gè)數(shù)據(jù)的并行運(yùn)算,對(duì)多項(xiàng)式算數(shù)運(yùn)算、模約減、數(shù)論變換等模塊效率的提升有明顯的效果.

3 Aigis-enc算法測(cè)試及優(yōu)化函數(shù)選定

本節(jié)給出了gprof與nm工具下Aigis-enc-768實(shí)現(xiàn)的軟件分析測(cè)試結(jié)果,并據(jù)此選定開銷大、調(diào)用頻率高或存儲(chǔ)占用多的模塊以進(jìn)一步優(yōu)化,如離散采樣、多項(xiàng)式乘法、模約減等;對(duì)于尚未并行優(yōu)化的函數(shù),如多項(xiàng)式序列化與反序列化,本文也將其納入優(yōu)化范圍.對(duì)于選定的函數(shù),本節(jié)中給出了相關(guān)理論與算法描述.

3.1 Aigis-enc算法軟件分析

Aigis-enc算法團(tuán)隊(duì)在中國(guó)密碼學(xué)會(huì)官網(wǎng)上提交了Aigis-enc原始實(shí)現(xiàn),作為第2輪算法競(jìng)賽的支撐材料[12].為確定實(shí)現(xiàn)中有待進(jìn)一步優(yōu)化的函數(shù)、從而提升算法整體運(yùn)行效率與空間占用,本文使用gprof與nm工具對(duì)Aigis-enc-768算法實(shí)現(xiàn)進(jìn)行了測(cè)試分析,結(jié)果如圖1所示:

Fig. 1 Test results of the Aigis-enc-768 algorithm圖1 Aigis-enc-768算法測(cè)試分析

結(jié)果顯示,偽隨機(jī)數(shù)擴(kuò)展占用了61.70%的時(shí)間開銷,主要用于噪音采樣與矩陣A的生成,這2項(xiàng)運(yùn)算所需時(shí)長(zhǎng)分別為總體的45.52%與28.65%.一些多項(xiàng)式操作函數(shù)開銷相比較大,如基于NTT的多項(xiàng)式乘法中,前向與逆向NTT共占5.71%,多項(xiàng)式向量的點(diǎn)乘占2.80%.此外,有4.31%的時(shí)間用于多項(xiàng)式序列化與反序列化,包含多項(xiàng)式壓縮與解壓縮、消息編碼與解碼等多項(xiàng)式與字節(jié)流間的轉(zhuǎn)換操作,其中部分函數(shù)目前尚未進(jìn)行并行優(yōu)化.對(duì)于ARM平臺(tái)的輕量級(jí)實(shí)現(xiàn),內(nèi)存與?？臻g占用為算法優(yōu)化的重要指標(biāo)之一.nm工具得到的符號(hào)表顯示,Aigis-enc-768代碼大小為968.304 KB,其中,前向與逆向NTT分別占據(jù)了30 KB.另外,為控制數(shù)據(jù)規(guī)模,模約減函數(shù)在運(yùn)算中調(diào)用頻率較高.原始實(shí)現(xiàn)中模約減并無(wú)顯式調(diào)用,而是實(shí)現(xiàn)在各個(gè)函數(shù)中,這也會(huì)造成代碼冗余.

本文對(duì)Aigis-enc-768算法優(yōu)化主要集中于多項(xiàng)式運(yùn)算處理模塊,對(duì)通用哈希模塊暫不進(jìn)行調(diào)整.對(duì)于結(jié)構(gòu)復(fù)雜的函數(shù),如NTT、模約減、壓縮與序列化等,本文提供了匯編指令優(yōu)化實(shí)現(xiàn).結(jié)合工具分析結(jié)果,本文確定的主要優(yōu)化點(diǎn)有2個(gè)方面:

1) AVX2.使用NTT變體提高多項(xiàng)式乘法計(jì)算效率;對(duì)未優(yōu)化的多項(xiàng)式運(yùn)算函數(shù)進(jìn)行AVX2并行優(yōu)化;提供部分函數(shù)的AVX2匯編指令實(shí)現(xiàn),以優(yōu)化流水調(diào)度;

2) ARM.減少NTT運(yùn)算中預(yù)計(jì)算表大小;運(yùn)用on-the-fly[22]等優(yōu)化思想減少代碼運(yùn)行的?？臻g;使用DSP指令減少運(yùn)算所需時(shí)鐘周期,并提升并行度.

3.2 模約減

多項(xiàng)式系數(shù)為群Zq中的元素,將其規(guī)約為群Zq中的代表元,可以控制系數(shù)規(guī)模,從而減小算法運(yùn)行所需的時(shí)空資源.x86與ARM架構(gòu)的處理器通常使用除法指令來(lái)完成取模運(yùn)算.為此,密碼算法實(shí)現(xiàn)中引入了Barrett約減與Montgomery約減,以減少除法運(yùn)算帶來(lái)的過多消耗,同時(shí)保證約減可以在常數(shù)時(shí)間內(nèi)完成,以抵抗側(cè)信道攻擊.

3.2.1 Barrett約減

以β為基底,Barrett約減可實(shí)現(xiàn)[-β/2,β/2)區(qū)間的整數(shù)a至群Zq的規(guī)約,滿足r=amodq,0≤r

算法4.有符號(hào)數(shù)Barrett約減算法.

輸入: 16 b有符號(hào)整數(shù)a滿足-β/2≤a<β/2、模數(shù)q滿足q<β/2;

輸出:r≡a(modq),其中0≤r≤q.

① functionBarrett(a,q)

④r=a-(tqmodβ);

⑤ returnr.

⑥ end function

3.2.2 Montgomery約減

不同于Barrett約減,Montgomery約減作用于基數(shù)為β的MONT域上.數(shù)據(jù)需從正常域轉(zhuǎn)換到MONT域才可使用Montgomery約減.

Montgomery約減的主要思想是通過對(duì)MONT域內(nèi)的數(shù)加上模數(shù)q的倍數(shù),轉(zhuǎn)換取模時(shí)除法的除數(shù),使得整除運(yùn)算更容易進(jìn)行.約減完成后再轉(zhuǎn)換回正常數(shù)域.對(duì)于無(wú)符號(hào)數(shù),約減結(jié)果在[0,2q)范圍內(nèi),需要與q進(jìn)行比較判斷,以得到[0,q)范圍內(nèi)的輸出.有符號(hào)數(shù)的Montgomery約減在原本的算法上進(jìn)行了一些調(diào)整,輸入范圍為[-βq/2,βq/2),輸出為(-q,q)范圍內(nèi)的有符號(hào)數(shù),見算法5.

算法5.有符號(hào)數(shù)Montgomery約減算法.

輸入:32 b有符號(hào)整數(shù)a滿足-βq/2≤a<βq/2;

輸出:16 b有符號(hào)整數(shù)r′滿足-q

① functionMontgomery(a)

②m=aq-1mod±β;

⑤ returnr′.

⑥ end function

3.3 多項(xiàng)式乘法與數(shù)論變換

數(shù)論變換是快速傅里葉變換(fast Fourier transform, FFT)在有限域上的一種特殊形式,常用于實(shí)現(xiàn)Zq環(huán)上的多項(xiàng)式乘法加速.對(duì)于n長(zhǎng)多項(xiàng)式,其中n為2的冪次,傳統(tǒng)NTT要求參數(shù)q是滿足2n|(q-1)的素?cái)?shù).

c

逆向NTT定義為

且二者滿足f=NTT-1(NTT(f)).給定f,g∈Zq[x]/(xn+1),NTT能夠用來(lái)計(jì)算h=fg∈Zq[x]/(xn+1),矩陣形式的線性變換可表示為

算法6.多項(xiàng)式系數(shù)拒絕采樣算法.

① functionParse(B)

②i,j0;

③ whilej

④dbi+256×bi+1;

⑤d

⑥ ifd

⑧jj+1;

⑨ end if

⑩ii+2;

3.5 多項(xiàng)式壓縮與解壓縮

基于MLWE困難問題構(gòu)造的密鑰封裝方案,在實(shí)現(xiàn)中經(jīng)常使用一些壓縮和解壓縮的方法,一方面,舍棄一些對(duì)正確性影響不大的低階位可節(jié)省帶寬和通信成本;另一方面,在加密和解密過程中執(zhí)行LWE錯(cuò)誤糾正.目前Aigis-enc[11]中使用的函數(shù)定義為

4 Aigis-enc算法AVX2高效實(shí)現(xiàn)方案設(shè)計(jì)

本文提出的針對(duì)Aigis-enc-768算法的AVX2優(yōu)化方案主要包括3個(gè)關(guān)鍵點(diǎn):

1) 模約減.使用匯編指令實(shí)現(xiàn)針對(duì)有符號(hào)數(shù)的改進(jìn)版Barrett約減與Montgomery約減,結(jié)合二者提升約減效率;

2) 多項(xiàng)式乘法.采取刪減一層的NTT,使用匯編指令實(shí)現(xiàn)并優(yōu)化指令流水,以提升效率;

3) 多項(xiàng)式序列化處理.將壓縮與解壓縮中的除法運(yùn)算替換為乘法與移位,從而可使用AVX2指令并行加速.

4.1 模約減

4.1.1 Barrett約減AVX2實(shí)現(xiàn)

Aigis-enc-768算法模數(shù)為q=7681,從而可將系數(shù)規(guī)?？刂圃?6 b有符號(hào)數(shù)范圍內(nèi).設(shè)定β=216,16倍并行的Barrett約減算法可使用4條指令實(shí)現(xiàn),具體見算法7.

算法7.改進(jìn)的Barrett約減算法的AVX2實(shí)現(xiàn).

輸入:向量化的16 b有符號(hào)整數(shù)a、常數(shù)模數(shù)q以及預(yù)計(jì)算的v和x;

輸出:向量化的約減后的值r.

① functionBarrett_AVX2(a,q,v,x)

② vpmulhwt←av;

/*計(jì)算av,取高16 b*/

③ vpsrawt←t?x;/*算術(shù)右移x位*/

④ vpmullwt←tq;

/*計(jì)算tq,取低16 b*/

⑤ vpsubwr←a-t;

/*計(jì)算a-t,得到結(jié)果*/

⑥ returnr.

⑦ end function

4.1.2 Montgomery約減AVX2實(shí)現(xiàn)

在Aigis-enc-768實(shí)現(xiàn)中,Montgomery約減用于規(guī)約Montgomery域內(nèi)2個(gè)16 b數(shù)的乘積,并保持其在Montgomery域內(nèi).根據(jù)模數(shù)設(shè)定β=216,實(shí)現(xiàn)步驟見算法8.

算法8.改進(jìn)的Montgomery約減算法的AVX2實(shí)現(xiàn).

輸入:向量化的32 b有符號(hào)整數(shù)a,記為ahi和alo;

輸出:向量化的16 b有符號(hào)整數(shù)r′.

① functionMontgomery_AVX2(a)

② vpmullwm←aloq-1;

/*m=(aloq-1) mod±β*/

④ vpsubwr′←ahi-t;/*r′=ahi-t*/

⑤ returnr′.

⑥ end function

4.2 多項(xiàng)式數(shù)論變換改進(jìn)

Aigis-enc原始實(shí)現(xiàn)中采用了AVX2接口調(diào)用的形式,實(shí)現(xiàn)了(n,q)=(256,7681)的傳統(tǒng)NTT.相比于API接口調(diào)用,直接使用AVX2指令實(shí)現(xiàn)具有更高的性能及指令調(diào)度安排靈活度,也可省略一些額外的調(diào)用消耗.另外,由于Aigis-enc三組參數(shù)中使用的q不統(tǒng)一,每個(gè)q對(duì)應(yīng)的預(yù)計(jì)算表互不相同,導(dǎo)致算法需要開辟很多額外的存儲(chǔ)空間.使用T-NTT,根的個(gè)數(shù)即可由n降低至n/2,減少了預(yù)計(jì)算表的空間需求.

根據(jù)分析,本文采用T-NTT,刪減NTT運(yùn)算的最后一層,并提供了AVX2指令集形式的匯編實(shí)現(xiàn).AVX2實(shí)現(xiàn)中,先單獨(dú)處理第0層,將系數(shù)a0,a1,…,a63和a128,a129,…,a191分別存入寄存器.通過指令vpmullw和vpmulhw進(jìn)行蝴蝶變換,將系數(shù)與第1個(gè)單位根相乘,再通過指令vpaddw與vpsubw進(jìn)行Montgomery約減,將系數(shù)約減至[-q,q]范圍內(nèi).多項(xiàng)式剩余的128個(gè)系數(shù),即a64,a65,…,a127和a192,a193,…,a255,也進(jìn)行相同的處理.不同于第0層,第1～6層中,256個(gè)系數(shù)統(tǒng)一按序載入處理,乘以對(duì)應(yīng)的單位根.在第4～6層中,需要使用PACK和UNPACK相關(guān)指令調(diào)整系數(shù)順序,將相關(guān)的系數(shù)整合到一起.前向NTT采用了CT蝴蝶變換(Cooley-Tuckey butterflies),輸入為正序多項(xiàng)式系數(shù),輸出為比特反轉(zhuǎn)順序的NTT域元素.逆向NTT采用了GS蝴蝶變換(Gentleman-Sande butterflies),輸入為比特反轉(zhuǎn)順序的NTT域元素,輸出正序多項(xiàng)式系數(shù),其偽代碼見算法9與算法10.通過這2種變換的組合可以省略位反轉(zhuǎn)操作,以提高運(yùn)行效率.

算法9.CT蝴蝶變換AVX2實(shí)現(xiàn).

輸入:向量化的16個(gè)低位系數(shù)rl、高位系數(shù)rh、模數(shù)q與單位根ζ;

輸出:變換后的低位系數(shù)與高位系數(shù)向量rh′與rl′.

① functionCT_Butterfly_AVX2(rl,rh,q,ζ)

② vpmullwζq-1,rh,t1;

/*t1=(rh×ζq-1)(mod 216)*/

③ vpmulhwζ,rh,(rhζ)hi;

⑤ vpsubwt2,(rh×ζ)hi,(rh×ζ)′;

/*(rh×ζ)′=(rh×ζ)hi-t2*/

⑥ vpsubw (rh×ζ)′,rl,rh′;

/*rh′=rl-(rh×ζ)′*/

⑦ vpaddw (rh×ζ)′,rh,rl′;

/*rl′=rh+(rh×ζ)′*/

⑧ return (rh′,rl′).

⑨ end function

算法10.GS蝴蝶變換AVX2實(shí)現(xiàn).

輸入:向量化的16個(gè)低位系數(shù)rl、高位系數(shù)rh、模數(shù)q與單位根ζ;

輸出:變換后的低位系數(shù)與高位系數(shù)向量rh′與rl′.

① functionGS_Butterfly_AVX2(r)

② vpsubwrh,rl,rh′;/*rh′=rl-rh*/

③ vpaddwrh,rl,rl;/*rl=rl+rh*/

④ vpmullwζq-1,rh′,t1;

/*t1=(rh′×ζq-1) mod 216*/

⑤ vpmulhwζ,rh′,rh′;

⑦ vpsubwt2,(rh′×ζ)hi,rh;

/*rh=(rh′×ζ)hi-t2*/

⑧ return (rh′,rl′).

⑨ end function

4.3 多項(xiàng)式序列化與反序列化優(yōu)化

本節(jié)主要說(shuō)明了多項(xiàng)式壓縮并編碼為字節(jié)流、字節(jié)流解碼為多項(xiàng)式并解壓縮這2個(gè)過程的優(yōu)化方案,在算法中用于對(duì)公鑰與密文進(jìn)行處理.優(yōu)化的主要難點(diǎn)在于除法運(yùn)算的處理,由于AVX2指令集中不包含除法指令,Aigis-enc原始實(shí)現(xiàn)中尚未對(duì)其進(jìn)行優(yōu)化,這也造成了該過程較大的開銷.

Barrett在文獻(xiàn)[25]中首次提出可以用一個(gè)乘法和一個(gè)移位運(yùn)算來(lái)代替較為耗時(shí)除法運(yùn)算,即

5 Aigis-enc算法ARM平臺(tái)輕量級(jí)實(shí)現(xiàn)方案設(shè)計(jì)

本節(jié)介紹了針對(duì)Aigis-enc-768算法的ARM Cortex-M4平臺(tái)優(yōu)化方案.設(shè)計(jì)中采取與第4節(jié)相同的改進(jìn)方案,并結(jié)合該平臺(tái)寄存器大小和Thumb與DSP指令集結(jié)構(gòu),對(duì)實(shí)現(xiàn)方案進(jìn)行調(diào)整,從而最優(yōu)化計(jì)算的速度與開銷.另外,輕量級(jí)實(shí)現(xiàn)平臺(tái)還需考慮片上存儲(chǔ),本文采用空間復(fù)用等方法減少了堆棧與存儲(chǔ)資源的占用.

5.1 模約減

5.1.1 Barrett約減ARM實(shí)現(xiàn)

算法11描述了Barrett約減在ARM Cortex-M4上的實(shí)現(xiàn),一次調(diào)用可完成2個(gè)16 b的約減.

算法11.Barrett約減算法ARM實(shí)現(xiàn).

輸入:封裝2個(gè)系數(shù)的32 b寄存器單元a=ahi|alo;

輸出:約減后的32 b寄存器單元r=rhi|rlo.

① functionBarrett_ARM(a)

② smulbbt1,a,v;/*t1←alov*/

③ smultbt2,a,v;/*t2←ahiv*/

⑥ smulbbt1,t1,q;/*t1←t1q*/

⑦ smulbbt2,t2,q;/*t2←t2q*/

⑧ pkhbtt,t1,t2,lsl#16

⑨ usub 16r,a,t;

/*rhi←ahi-thi,rlo←alo-tlo*/

⑩ returnr.

5.1.2 Montgomery約減ARM實(shí)現(xiàn)

ARM Cortex-M4平臺(tái)上多數(shù)指令執(zhí)行時(shí)間均為一個(gè)時(shí)鐘周期.調(diào)整算式結(jié)構(gòu)以結(jié)合乘加運(yùn)算,則可充分利用此特性,將一個(gè)乘法與一個(gè)加法替換為乘加運(yùn)算,從而節(jié)省了一個(gè)周期的時(shí)鐘消耗.

本文應(yīng)用了改進(jìn)后的Montgomery約減[22].算法的輸入為2個(gè)16 b的有符號(hào)數(shù)alo與ahi,分別為2個(gè)32 b乘積的低字.輸出為打包好的2個(gè)(-q,q)區(qū)間內(nèi)的約減結(jié)果.將預(yù)存儲(chǔ)的q-1調(diào)整為-q-1,則r′=ahi-t變更為r′=ahi+t,結(jié)合t計(jì)算中的乘法,即可使用smlabb指令在一個(gè)周期內(nèi)完成2個(gè)16b的乘積與一個(gè)32b的加法.在Aigis-enc-768中,一個(gè)多項(xiàng)式向量由3個(gè)256維多項(xiàng)式構(gòu)成,且2個(gè)多項(xiàng)式的乘法需要執(zhí)行1 856次Montgomery約減(其中2次前向NTT需要896個(gè),一次逆向NTT需要448個(gè),向量點(diǎn)乘需要512個(gè)),改進(jìn)后的方法可以大幅減少乘法所需的總時(shí)鐘周期.

算法12.Montgomery約減算法ARM實(shí)現(xiàn).

輸入:封裝2個(gè)系數(shù)的32 b寄存器單元a=ahi|alo;

輸出:約減后的32 b寄存器單元r=rhi|rlo.

① functionMontgomery_ARM(a)

② smulbbt1,a,v;

③ smulbbr1,t1,-q-1;

/*r1←(t1modβ) (-q-1)*/

④ smlabbr1,r1,q,t1;

⑤ smultbt2,a,v;

⑥ smulbbr2,t2,-q-1;

/*r2←(t2modβ) (-q-1)*/

⑦ smlabbr2,r2,q,t2;

⑧ pkhbtr,r2,r1,asr#16;

/*r←(r2hi|(r1hi?16))*/

⑨ returnr.

⑩ end function

5.2 多項(xiàng)式數(shù)論變換改進(jìn)

本文使用了β=1的T-NTT,即刪減最后一層.該方法大幅減小了預(yù)計(jì)算表存儲(chǔ)空間,利于算法在嵌入式設(shè)備的部署.在AVX2實(shí)現(xiàn)中,由于寄存器存儲(chǔ)空間充足,可加載完整的多項(xiàng)式并逐層變換.而ARM Cortex-M4為32 b架構(gòu),且資源受限(只有16個(gè)32 b寄存器),load與store一次只能存取2個(gè)系數(shù),若采取如AVX2實(shí)現(xiàn)般逐層變換的方法,會(huì)引入過多的load與store指令,所以需要對(duì)NTT結(jié)構(gòu)進(jìn)行調(diào)整以適應(yīng)平臺(tái)特性,調(diào)整后的方案如圖2所示:

Fig. 2 Implementation of NTT on ARM Cortex-M4圖2 ARM平臺(tái)NTT實(shí)現(xiàn)

該方案的主要思想為以固定的距離拆分多項(xiàng)式,每次取16個(gè)系數(shù)存入8個(gè)寄存器,進(jìn)行3層變換后存回原位置.舉例來(lái)說(shuō),第一次循環(huán)存取的系數(shù)為r2={a1‖a0},r3={a33‖a32},r4={a65‖a64},…,r9={a65‖a64}.隨后對(duì)其進(jìn)行前3層數(shù)論變換,一對(duì)變換系數(shù)的距離間隔分別為128,64,32.變換結(jié)束后存回原地址,地址指針前進(jìn)4 B,進(jìn)入下一次循環(huán).T-NTT第4～6層的操作同理進(jìn)行,一對(duì)變換系數(shù)的距離間隔分別為16,8,4,最后統(tǒng)一執(zhí)行系數(shù)間隔為2的第7層變換,得到最終結(jié)果.這里, 一個(gè)寄存器可以存放2個(gè)16 b的系數(shù),相當(dāng)于二并行加速.

5.3 加解密并行優(yōu)化處理

本節(jié)中論述了多項(xiàng)式壓縮與序列化在ARM Cortex-M4上的優(yōu)化方案.優(yōu)化時(shí)考慮的要素主要為:

1) 調(diào)整算式結(jié)構(gòu)以盡可能結(jié)合運(yùn)算過程,減少所需指令的數(shù)目;

2) 盡量在一個(gè)系數(shù)存在于寄存器的整個(gè)生命周期內(nèi)進(jìn)行盡可能多的運(yùn)算操作,以減少load與store指令的開銷.

為了達(dá)成這2個(gè)目標(biāo),需要在效率與寄存器容量2個(gè)指標(biāo)之間權(quán)衡折衷.加密中將秘密消息編碼、多項(xiàng)式壓縮與序列化結(jié)合,即為算法2中的行⑦⑨,c2Compressq(v+Decompressq(msg,dm),dv);在解密中結(jié)合多項(xiàng)式反序列化、解壓縮與消息解碼,即算法3中的行③④,從而得到解密后消息msgCompressq(Decompressq(c2),σ).進(jìn)而,本文結(jié)合除法運(yùn)算轉(zhuǎn)換法,對(duì)該運(yùn)算順序進(jìn)行調(diào)整,使得DSP指令集中一些復(fù)合運(yùn)算指令得以運(yùn)用.優(yōu)化后對(duì)單個(gè)位加密的核心過程見圖3,解密核心過程如圖4所示.

Fig. 3 Implementation of encryption on ARM Cortex-M4圖3 ARM平臺(tái)加密核心步驟實(shí)現(xiàn)

Fig. 4 Implementation of decryption on ARM Cortex-M4圖4 ARM平臺(tái)解密核心步驟實(shí)現(xiàn)

這里加解密實(shí)現(xiàn)中均需對(duì)多項(xiàng)式進(jìn)行預(yù)處理,通過指令pkhbt與pkhtb將σ與k同一索引位的系數(shù)封裝入一個(gè)32 b的寄存器.繼而,在加密中使用指令smuad與mla，解密中使用指令smlsd與mul以完成核心運(yùn)算.此外,實(shí)現(xiàn)中還使用了位運(yùn)算指令bfi與orr,已實(shí)現(xiàn)寄存器中位的提取與比特流的拼接.

5.4 存儲(chǔ)空間及?？臻g優(yōu)化

嵌入式設(shè)備上存儲(chǔ)空間是一重要瓶頸,算法空間使用情況也決定了其能否實(shí)際部署.考慮到這一要素,本文在保持性能盡可能不受影響的情況下,采取on-the-fly[22]計(jì)算與空間復(fù)用等優(yōu)化思想,減小代碼大小以及運(yùn)行所需棧空間.本文對(duì)Aigis-enc-768的優(yōu)化中以堆棧使用和速度為主要指標(biāo),同時(shí)保持代碼大小的合理性.

5.4.1 ?？臻g資源復(fù)用

在Aigis-enc-768原始實(shí)現(xiàn)中,對(duì)方案涉及的所有元素都申請(qǐng)了空間,并且分別對(duì)其進(jìn)行采樣、存儲(chǔ).考慮到該運(yùn)算的線性特性,各對(duì)多項(xiàng)式之間的乘法以及多項(xiàng)式內(nèi)各系數(shù)的乘法均互相獨(dú)立,內(nèi)存中不需要同時(shí)存在多個(gè)多項(xiàng)式.由此,本文在實(shí)現(xiàn)中減少了空間申請(qǐng),通過空間復(fù)用的方式完成多個(gè)多項(xiàng)式運(yùn)算.具體來(lái)說(shuō),對(duì)于密鑰生成和密鑰封裝,申請(qǐng)一個(gè)多項(xiàng)式變量與一個(gè)多項(xiàng)式向量變量,對(duì)于密鑰解封裝,申請(qǐng)2個(gè)多項(xiàng)式變量,每個(gè)多項(xiàng)式的運(yùn)算都在此空間上進(jìn)行,得到結(jié)果后即存入對(duì)應(yīng)的密鑰或密文位置.

基于模格的密鑰封裝方案在密鑰生成與密鑰封裝中都包含A·s的核心運(yùn)算,對(duì)此運(yùn)算進(jìn)行充分優(yōu)化有利于降低代碼運(yùn)行空間需求.如3.3節(jié)所述,經(jīng)過數(shù)論變換后1個(gè)多項(xiàng)式由128個(gè)一次多項(xiàng)式組成,它們之間的點(diǎn)乘互相獨(dú)立,所以執(zhí)行一次點(diǎn)乘僅需要一次多項(xiàng)式ai+ai+1x與si+si+1x相關(guān)的4個(gè)系數(shù)ai,ai+1,si與si+1,這就意味著矩陣A的系數(shù)可以需要時(shí)再采樣,而不用全部生成后再讀取.詳細(xì)地說(shuō),由種子ρ擴(kuò)展得到字節(jié)流后,一次只采樣2個(gè)符合條件的系數(shù),與s中的2個(gè)系數(shù)點(diǎn)乘,并存儲(chǔ)回s的相應(yīng)位置,從而省略了存儲(chǔ)矩陣A所用的空間.

與之相同的還有噪音的采樣.原始實(shí)現(xiàn)中,噪音采樣函數(shù)輸入為字節(jié)流,輸出為服從中心二項(xiàng)分布的多項(xiàng)式.采用on-the-fly計(jì)算優(yōu)化思想[22],噪音采樣函數(shù)輸入調(diào)整為字節(jié)流和多項(xiàng)式,每次采樣噪音后即與輸入多項(xiàng)式對(duì)應(yīng)位置的系數(shù)相加,而不用再進(jìn)行存儲(chǔ).但是這種方法也意味著不能對(duì)噪音多項(xiàng)式進(jìn)行數(shù)論變換(因?yàn)镹TT作用對(duì)象為一個(gè)完整的多項(xiàng)式),從而t′的計(jì)算方式由t′=A°T-NTT(s)+T-NTT(e)調(diào)整為t′=T-NTT(T-NTT-1(A°T-NTT(s))+e).這樣會(huì)引入一個(gè)額外的NTT-1的消耗.在ARM Cortex-M4平臺(tái)上,這意味著需要增加6944時(shí)鐘周期,約占總運(yùn)行時(shí)間的0.3%,但是可以節(jié)省矩陣A與多項(xiàng)式s,e共7 680 B的棧存儲(chǔ)空間,權(quán)衡二者這樣的消耗是值得的.

6 實(shí)驗(yàn)結(jié)果與性能比較

6.1 測(cè)試環(huán)境

本文針對(duì)Aigis-enc密鑰分裝機(jī)制設(shè)計(jì)了AVX2與ARM Cortex-M4的優(yōu)化方案,并于Aigis-enc-768算法上實(shí)現(xiàn)驗(yàn)證.本節(jié)介紹了2個(gè)平臺(tái)的代碼測(cè)試環(huán)境.

1) AVX2測(cè)試環(huán)境:本文進(jìn)行AVX2測(cè)試的硬件環(huán)境為3.6 GHz的八核Intel Core i7-9700K和32 GB內(nèi)存,且關(guān)閉了處理器的睿頻加速技術(shù)(Turbo Boost)和硬件多線程技術(shù)(Hardware Multi-Threading);軟件環(huán)境為macOS Big Sur 11.1操作系統(tǒng)與Apple clang 12.0.0.31.1編譯器.使用的編譯參數(shù)為-Wall -Wextra -Wpedantic -Wmissing-prototypes -Wredundantdecls -Wshadow -Wpointer-arith -mavx2 -mbmi2 -mpopcnt maes -march=native -mtune=native -O0 -fomit-frame-pointer -fno-stack-check.

2) ARM Cortex-M4測(cè)試環(huán)境:本文使用帶有ARMv7E-M 指令集的STM32F4DISCOVERY開發(fā)板為測(cè)試平臺(tái),其內(nèi)存為196 KB,閃存為1 MB,且最大頻率為168 MHz.

本文采用CPU周期數(shù)作為衡量算法效率的標(biāo)準(zhǔn),AVX2代碼測(cè)試的CPU周期數(shù)為對(duì)應(yīng)的函數(shù)執(zhí)行10 000次后所得結(jié)果的中位數(shù),ARM Cortex-M4上的結(jié)果為執(zhí)行100次后的中位數(shù).

6.2 AVX2實(shí)現(xiàn)性能比較

圖5與圖6為Aigis-enc與本文AVX2實(shí)現(xiàn)效率的對(duì)比,其具體數(shù)值分別如表1所示.

Fig. 5 Comparisons of polynomial compression and serialization betweenAigis-enc and our work圖5 多項(xiàng)式壓縮與序列化AVX2實(shí)現(xiàn)對(duì)比

Fig. 6 Comparisons of Aigis-enc and our work in AVX2 implementations圖6 Aigis-enc與本文工作AVX2實(shí)現(xiàn)效率對(duì)比

圖5為多項(xiàng)式壓縮和序列化速度的比較,其中,壓縮位數(shù)d=4的情形用于密文c中第2部分c2的生成,即計(jì)算c2Compressq(v+k,d),d=9用于生成密文的第一部分,即c1Compressq(u,d).本文設(shè)計(jì)中采取的方案性能將原始提升了97.9%和94.7%,相當(dāng)于對(duì)原過程有47倍和19倍的加速.

圖6是Aigis-enc與本文工作AVX2實(shí)現(xiàn)效率對(duì)比.如表1中時(shí)鐘周期數(shù)所示,本文工作將密鑰生成函數(shù)提升23.62%,密鑰封裝函數(shù)提升23.56%,密鑰解封裝函數(shù)提升27.74%,在總性能上體現(xiàn)為25.00%的加速,彰顯了本文優(yōu)化設(shè)計(jì)方案的作用效果.

Table 1 Comparisons of Each Function of Aigis-enc and Our Work in AVX2 Implementations表1 Aigis-enc與本文工作AVX2實(shí)現(xiàn)效率比較

表2為Aigis-enc與本文AVX2實(shí)現(xiàn)NTT預(yù)計(jì)算表存儲(chǔ)量的對(duì)比.在q=7 681下,為了適配AVX2指令實(shí)現(xiàn),Aigis-enc擴(kuò)展的預(yù)計(jì)算表總共需要3 008 B存儲(chǔ)空間,而本文工作僅需1 584 B,減少了47.34%的存儲(chǔ).

Table 2 Comparison of Precomputed Table Storage Between Aigis-enc and Our AVX2 Implementation表2 Aigis-enc與本文AVX2實(shí)現(xiàn)NTT預(yù)計(jì)算表 存儲(chǔ)量對(duì)比

6.3 ARM實(shí)現(xiàn)性能與空間測(cè)試

鑒于目前Aigis-enc僅提供了AVX2實(shí)現(xiàn),且尚未有ARM平臺(tái)或C參考實(shí)現(xiàn)方案,這里僅給出本文優(yōu)化前后STM32F4DISCOVERY開發(fā)板上的實(shí)驗(yàn)測(cè)試結(jié)果來(lái)對(duì)比,如圖7所示,具體數(shù)值如表3所示.其中,優(yōu)化前的算法為根據(jù)Aigis-enc原始實(shí)現(xiàn)自主修改的C實(shí)現(xiàn).

Fig. 7 Comparison of implementation before and after optimization of Aigis-enc on ARM platform圖7 ARM平臺(tái)Aigis-enc優(yōu)化前后實(shí)現(xiàn)效率對(duì)比

Table 3 Comparisons of Each Function of Aigis-enc and Our Work on ARM Cortex-M4 Platform

在棧空間占用上,原始實(shí)現(xiàn)密鑰生成、密鑰封裝及密鑰解封裝分別占據(jù)10.8 KB,14.1 KB與15.3 KB,優(yōu)化后達(dá)到3.3 KB,2.9 KB與3.0 KB,總體上有3.4倍的提升,如表4所示:

Table 4 Menory Evaluation of Aigis-enc and Our Work on ARM Cortex-M4 Platform表4 Aigis-enc與本文工作在ARM Cortex-M4 平臺(tái)上存儲(chǔ)量測(cè)試

可見,采取改進(jìn)的模約減算法、多項(xiàng)式乘法等優(yōu)化方案,可大幅度提高ARM Cortex-M4上的實(shí)現(xiàn)效率.

7 總 結(jié)

本文給出了一種針對(duì)Aigis-enc算法的高效AVX2與ARM Cortex-M4實(shí)現(xiàn)方案,并選用Aigis-enc-768參數(shù)集進(jìn)行實(shí)現(xiàn)驗(yàn)證.該實(shí)現(xiàn)方案在模約減、多項(xiàng)式乘法、序列化與反序列化等方面對(duì)Aigis-enc原始實(shí)現(xiàn)進(jìn)行優(yōu)化,同時(shí)大幅減少了代碼尺寸、運(yùn)行堆?？臻g占用與預(yù)計(jì)算表存儲(chǔ)需求,提升了算法總體性能,使其更易于實(shí)際部署,具有非常大的實(shí)際應(yīng)用價(jià)值.