沈詩羽 何 峰 趙運磊

(復旦大學計算機科學技術學院 上海 200433)

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

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

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

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

1) 使用了改進版有符號數Montgomery約減與Barrett約減,并運用乘加指令減少了ARM Cortex-M4平臺模約減所需指令條數,提升約減效率;

2) 使用了刪減層數的數論變換(T-NTT)并提供AVX2與ARM的匯編實現,相比與傳統NTT,刪減了變換的最后一層,極大地減少了預計算表存儲需求;

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

4) 調整算式結構以充分適應各平臺指令特性,從而達到減少總指令數目與load/store指令開銷的目的;

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

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

1 相關工作

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

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

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

2 預備知識

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

2.1 基本定義及符號說明

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

2.2 Aigis-enc算法介紹

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

Aigis-enc-PKE的密鑰生成算法如算法1所示.密鑰生成時首先從n位二進制串中均勻采樣出σ和ρ,然后將隨機種子ρ傳入Sam和Parse函數以生成NTT域上的矩陣A,接著以σ為參數通過CBD算法生成私鑰s和噪音向量e,最后計算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、隨機數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所示.算法傳入參數為密鑰sk和密文ct,通過對密文ct,即c1和c2進行解壓縮,分別得到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 實現平臺與SIMD指令

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

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

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

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

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

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

3.1 Aigis-enc算法軟件分析

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

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

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

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

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

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

3.2 模約減

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

3.2.1 Barrett約減

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

算法4.有符號數Barrett約減算法.

輸入: 16 b有符號整數a滿足-β/2≤a<β/2、模數q滿足q<β/2;

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

① functionBarrett(a,q)

④r=a-(tqmodβ);

⑤ returnr.

⑥ end function

3.2.2 Montgomery約減

不同于Barrett約減,Montgomery約減作用于基數為β的MONT域上.數據需從正常域轉換到MONT域才可使用Montgomery約減.

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

算法5.有符號數Montgomery約減算法.

輸入:32 b有符號整數a滿足-βq/2≤a<βq/2;

輸出:16 b有符號整數r′滿足-q

① functionMontgomery(a)

②m=aq-1mod±β;

⑤ returnr′.

⑥ end function

3.3 多項式乘法與數論變換

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

c

逆向NTT定義為

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

算法6.多項式系數拒絕采樣算法.

① functionParse(B)

②i,j0;

③ whilej

④dbi+256×bi+1;

⑤d

⑥ ifd

⑧jj+1;

⑨ end if

⑩ii+2;

3.5 多項式壓縮與解壓縮

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

4 Aigis-enc算法AVX2高效實現方案設計

本文提出的針對Aigis-enc-768算法的AVX2優(yōu)化方案主要包括3個關鍵點:

1) 模約減.使用匯編指令實現針對有符號數的改進版Barrett約減與Montgomery約減,結合二者提升約減效率;

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

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

4.1 模約減

4.1.1 Barrett約減AVX2實現

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

算法7.改進的Barrett約減算法的AVX2實現.

輸入:向量化的16 b有符號整數a、常數模數q以及預計算的v和x;

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

① functionBarrett_AVX2(a,q,v,x)

② vpmulhwt←av;

/*計算av,取高16 b*/

③ vpsrawt←t?x;/*算術右移x位*/

④ vpmullwt←tq;

/*計算tq,取低16 b*/

⑤ vpsubwr←a-t;

/*計算a-t,得到結果*/

⑥ returnr.

⑦ end function

4.1.2 Montgomery約減AVX2實現

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

算法8.改進的Montgomery約減算法的AVX2實現.

輸入:向量化的32 b有符號整數a,記為ahi和alo;

輸出:向量化的16 b有符號整數r′.

① functionMontgomery_AVX2(a)

② vpmullwm←aloq-1;

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

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

⑤ returnr′.

⑥ end function

4.2 多項式數論變換改進

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

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

算法9.CT蝴蝶變換AVX2實現.

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

輸出:變換后的低位系數與高位系數向量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實現.

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

輸出:變換后的低位系數與高位系數向量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 多項式序列化與反序列化優(yōu)化

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

Barrett在文獻[25]中首次提出可以用一個乘法和一個移位運算來代替較為耗時除法運算,即

5 Aigis-enc算法ARM平臺輕量級實現方案設計

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

5.1 模約減

5.1.1 Barrett約減ARM實現

算法11描述了Barrett約減在ARM Cortex-M4上的實現,一次調用可完成2個16 b的約減.

算法11.Barrett約減算法ARM實現.

輸入:封裝2個系數的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實現

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

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

算法12.Montgomery約減算法ARM實現.

輸入:封裝2個系數的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 多項式數論變換改進

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

Fig. 2 Implementation of NTT on ARM Cortex-M4圖2 ARM平臺NTT實現

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

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

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

1) 調整算式結構以盡可能結合運算過程,減少所需指令的數目;

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

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

Fig. 3 Implementation of encryption on ARM Cortex-M4圖3 ARM平臺加密核心步驟實現

Fig. 4 Implementation of decryption on ARM Cortex-M4圖4 ARM平臺解密核心步驟實現

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

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

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

5.4.1 ?？臻g資源復用

在Aigis-enc-768原始實現中,對方案涉及的所有元素都申請了空間,并且分別對其進行采樣、存儲.考慮到該運算的線性特性,各對多項式之間的乘法以及多項式內各系數的乘法均互相獨立,內存中不需要同時存在多個多項式.由此,本文在實現中減少了空間申請,通過空間復用的方式完成多個多項式運算.具體來說,對于密鑰生成和密鑰封裝,申請一個多項式變量與一個多項式向量變量,對于密鑰解封裝,申請2個多項式變量,每個多項式的運算都在此空間上進行,得到結果后即存入對應的密鑰或密文位置.

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

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

6 實驗結果與性能比較

6.1 測試環(huán)境

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

1) AVX2測試環(huán)境:本文進行AVX2測試的硬件環(huán)境為3.6 GHz的八核Intel Core i7-9700K和32 GB內存,且關閉了處理器的睿頻加速技術(Turbo Boost)和硬件多線程技術(Hardware Multi-Threading);軟件環(huán)境為macOS Big Sur 11.1操作系統與Apple clang 12.0.0.31.1編譯器.使用的編譯參數為-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測試環(huán)境:本文使用帶有ARMv7E-M 指令集的STM32F4DISCOVERY開發(fā)板為測試平臺,其內存為196 KB,閃存為1 MB,且最大頻率為168 MHz.

本文采用CPU周期數作為衡量算法效率的標準,AVX2代碼測試的CPU周期數為對應的函數執(zhí)行10 000次后所得結果的中位數,ARM Cortex-M4上的結果為執(zhí)行100次后的中位數.

6.2 AVX2實現性能比較

圖5與圖6為Aigis-enc與本文AVX2實現效率的對比,其具體數值分別如表1所示.

Fig. 5 Comparisons of polynomial compression and serialization betweenAigis-enc and our work圖5 多項式壓縮與序列化AVX2實現對比

Fig. 6 Comparisons of Aigis-enc and our work in AVX2 implementations圖6 Aigis-enc與本文工作AVX2實現效率對比

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

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

Table 1 Comparisons of Each Function of Aigis-enc and Our Work in AVX2 Implementations表1 Aigis-enc與本文工作AVX2實現效率比較

表2為Aigis-enc與本文AVX2實現NTT預計算表存儲量的對比.在q=7 681下,為了適配AVX2指令實現,Aigis-enc擴展的預計算表總共需要3 008 B存儲空間,而本文工作僅需1 584 B,減少了47.34%的存儲.

Table 2 Comparison of Precomputed Table Storage Between Aigis-enc and Our AVX2 Implementation表2 Aigis-enc與本文AVX2實現NTT預計算表 存儲量對比

6.3 ARM實現性能與空間測試

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

Fig. 7 Comparison of implementation before and after optimization of Aigis-enc on ARM platform圖7 ARM平臺Aigis-enc優(yōu)化前后實現效率對比

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

在棧空間占用上,原始實現密鑰生成、密鑰封裝及密鑰解封裝分別占據10.8 KB,14.1 KB與15.3 KB,優(yōu)化后達到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 平臺上存儲量測試

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

7 總 結

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