國密算法Python工具包的性能優(yōu)化方法

謝振杰 付 偉 羅 芳

1(海軍工程大學(xué)信息安全系 武漢 430033)2(中國人民解放軍78156部隊 重慶 400039)

中國商用密碼標(biāo)準(zhǔn)算法是指國家密碼管理局認(rèn)定的一系列國產(chǎn)商用密碼算法,即國密算法.其中SM2是我國自主設(shè)計的基于橢圓曲線密碼(elliptic curve cryptosystem, ECC)的公鑰密碼算法(以下簡稱“SM2”)[1-5],包含數(shù)字簽名、密鑰交換和公鑰加密,對應(yīng)RSA,ECDSA,DH,ECDH等國際算法.SM3是我國自主設(shè)計的密碼雜湊算法(以下簡稱“SM3”)[6],對應(yīng)MD5,SHA-1,SHA-2等國際算法.SM4是我國自主設(shè)計的分組密碼算法(以下簡稱“SM4”)[7],用于數(shù)據(jù)加解密運算以保證機密性,對應(yīng)DES,AES等國際算法.祖沖之密碼是我國自主設(shè)計的序列密碼算法(以下簡稱“ZUC”)[8],是我國首個成為國際標(biāo)準(zhǔn)的密碼算法,在5G通信領(lǐng)域至關(guān)重要.國密算法作為國家網(wǎng)信自主安全的重要基礎(chǔ)設(shè)施,具備高安全性且自主可控[9],正在各領(lǐng)域加速推廣,其在各平臺的實現(xiàn)性能同樣是一個不容忽視的問題.

Python作為一種解釋型程序設(shè)計語言,其代碼簡潔易學(xué)、第三方資源豐富的特性極大提升了編程效率.但Python的運行效率(指單位時間處理的數(shù)據(jù)量)相比編譯型語言(如C語言)有明顯短板,在運算量大、實時性高的場景下,Python程序可能成為性能瓶頸.隨著國密算法逐步推廣應(yīng)用,國內(nèi)Python程序員(特別是信息安全軟件開發(fā)者)對便捷、穩(wěn)定、高效的國密算法Python工具包有迫切需求.對于國密算法的軟件實現(xiàn)及優(yōu)化,近年來國內(nèi)已有一些研究成果,如:文獻[10]研究了SM4算法快速軟件實現(xiàn)方法;文獻[11-12]研究了ZUC算法快速軟件實現(xiàn)方法;文獻[13]從橢圓曲線計算、有限域上的大整數(shù)計算以及處理器平臺等層面研究了SM2算法的性能優(yōu)化;文獻[14]介紹將國密算法集成到OpenSSL的工作.上述均采用C語言或匯編語言.文獻[15]實現(xiàn)了國密算法JavaScript通用密碼庫.對于在Python環(huán)境下高效實現(xiàn)國密算法,尚未見系統(tǒng)的、效果足夠好的研究成果或開源代碼.

當(dāng)前,采用Python語言編寫的國密算法第三方庫主要是gmssl[16]和snowland-smx(pysmx)[17],二者實現(xiàn)了SM2,SM3,SM4等國密算法.然而,相較于更為成熟的國際密碼算法庫PyCryptodome[18],gmssl或pysmx中同類密碼運算的運行效率低1～3個數(shù)量級.究其原因,gmssl和pysmx使用純Python語言編寫,由Python解釋器逐行解釋執(zhí)行,而PyCryptodome庫的核心算法使用C語言編寫,編譯成鏈接庫后供Python調(diào)用,編譯后的機器代碼在執(zhí)行效率上有顯著優(yōu)勢.此外,gmssl和pysmx尚有諸多細(xì)節(jié)值得改進.因此,當(dāng)系統(tǒng)對密碼運算性能有較高要求時,現(xiàn)有的國密算法Python庫可能難以滿足需要,這在一定程度上阻礙了國密算法在Python環(huán)境下的推廣應(yīng)用.

針對上述問題,本文開發(fā)了高效的國密算法Python工具包,可支持SM2,SM3,SM4,ZUC這4種國密算法,相較于現(xiàn)有的國密算法Python庫gmssl和pysmx,性能有大幅提升,基本與國外成熟的PyCryptodome庫的同類密碼算法性能相當(dāng).開發(fā)過程參考了gmssl,pysmx,PyCryptodome的代碼以及相應(yīng)的國家標(biāo)準(zhǔn)[1-8].

1 性能優(yōu)化

相較于gmssl和pysmx對國密算法的Python實現(xiàn),本工具包采用的性能優(yōu)化方法如下(按照性能提升幅度由高至低排序).

1.1 Numba加速

Numba是一個第三方Python庫[19],用于把Python代碼先編譯成機器代碼再執(zhí)行,對數(shù)值計算和循環(huán)的加速效果尤其明顯,可極大提升代碼運行效率.由于在Python中“一切皆為對象”,變量采用弱類型,而編譯成機器代碼需要明確指定類型,所以使用Numba加速的代碼要犧牲一部分Python語言特性,代碼風(fēng)格介于Python和C之間.Numba只支持部分Python內(nèi)置庫和函數(shù),但對數(shù)值計算常用的第三方庫Numpy[20]有很好的支持.通過cProfile(Python內(nèi)置的性能分析工具)對密碼算法運行過程進行分析,發(fā)現(xiàn)耗時主要來自循環(huán)執(zhí)行的數(shù)值計算,而這正是Numba擅長的部分.參考Numba規(guī)范重寫SM3,SM4,ZUC的核心代碼后,運行效率可提升100倍以上.

1.2 調(diào)用PyCryptodome庫的橢圓曲線運算

SM2的主要耗時來自橢圓曲線點乘,涉及大整數(shù)運算,自主實現(xiàn)大整數(shù)運算并用Numba加速后,運行效率反而不及Python內(nèi)置的大整數(shù)運算.而PyCryptodome庫實現(xiàn)的橢圓曲線運算與SM2是一致的,采用編譯好的C鏈接庫,且允許自定義橢圓曲線參數(shù).因此,調(diào)用PyCryptodome庫的橢圓曲線運算鏈接庫,裝載SM2橢圓曲線參數(shù),運行效率比純Python實現(xiàn)的SM2橢圓曲線運算高5～10倍.

1.3 采用預(yù)計算加速SM2基點點乘

SM2在生成密鑰、簽名、驗證、加密運算中,以及密鑰交換的雙方,均需要運行1次基點點乘(k·G)運算,采用預(yù)計算技術(shù)可顯著提升計算效率[13].標(biāo)量k是一個256b的整數(shù),令其二進制下1的數(shù)量占一半且最高位為1,則采用二進制展開法[1]計算k·G需要進行255+127=382次點加運算.若將k視為32B數(shù)據(jù),對于k上的每個字節(jié)Bi,預(yù)先計算出Bi=1,2,…,255(i∈[0,31])而其他字節(jié)為全0時的k·G坐標(biāo)并保存,則計算任意k·G最多僅需31次點加運算.而每個點坐標(biāo)為512b即64B,預(yù)計算數(shù)據(jù)大小僅為255×32×64B=522240B=510KB.雖然理論上應(yīng)提速12倍,但從1次調(diào)用點乘變?yōu)槎啻握{(diào)用點加,頻繁調(diào)用鏈接庫使開銷增大,所以采用預(yù)計算進行基點點乘的實測效率約為普通點乘的4～5倍.

1.4 并行運算

Numba支持各循環(huán)輪次的并行運算.對于SM4算法,ECB模式下的加密和解密、CBC模式下的解密可并行執(zhí)行,并行運算可使效率提高1～2倍.由于單線程運算量較小,且引入多線程有額外的通信和調(diào)度開銷,線程數(shù)達到4以后,設(shè)置更多的線程數(shù)也不會有明顯提升.

1.5 構(gòu)造雙字節(jié)S盒快表

在SM4和ZUC中,S盒變換是高頻操作,傳統(tǒng)做法是用長度為256B的S盒表逐個字節(jié)轉(zhuǎn)換.初始化階段構(gòu)造雙字節(jié)S盒快表(大小為256×256×2B=131072B=128KB),S盒查表操作可減少一半,“移位”和“按位與”運算也大幅減少.實驗表明,雙字節(jié)S盒快表可使SM4和ZUC的運行效率提高10%～20%.

1.6 減少函數(shù)調(diào)用

函數(shù)調(diào)用使代碼簡潔,但高頻的函數(shù)調(diào)用會引入額外開銷.例如SM3,SM4,ZUC有大量循環(huán)移位運算,將循環(huán)移位的函數(shù)去掉,再盡可能消除“& 0xffffffff”運算(“& 0xffffffff”用于確保值大小為32b,對于64位處理器,運算中間值也可超過32b,僅在最后賦值前再進行“& 0xffffffff”運算;但同一變量連續(xù)2次循環(huán)移位之間不能將其省略,否則會引起計算錯誤),運行效率提高10%～16%.

1.7 避免中間類型轉(zhuǎn)換

在gmssl和pysmx中,各函數(shù)間傳遞的數(shù)據(jù)類型在整數(shù)(int)、字節(jié)串(bytes)、16進制字符串(str)和列表(list)之間反復(fù)轉(zhuǎn)換,這類冗余操作應(yīng)盡可能避免.盡量用同一種數(shù)據(jù)類型完成運算和參數(shù)傳遞,運行效率可提高8%～15%.

1.8 針對Python的專門優(yōu)化

構(gòu)造雙字節(jié)S盒快表、減少函數(shù)調(diào)用和避免中間類型轉(zhuǎn)換對所有編程語言都適用,針對Python語言還可作以下優(yōu)化:一是用類型明確的數(shù)組代替弱類型的列表;二是用生成器表達式代替列表推導(dǎo);三是能在原數(shù)組上修改就不要生成新數(shù)組,等等.通過若干實現(xiàn)細(xì)節(jié)的優(yōu)化,運行效率可提高5%左右.

2 功能擴展

相較于gmssl和pysmx,本工具包還包含以下擴展.

2.1 包含SM2密鑰交換協(xié)議

gmssl和pysmx僅實現(xiàn)了SM2數(shù)字簽名和公鑰加密算法,沒有實現(xiàn)SM2密鑰交換協(xié)議,互聯(lián)網(wǎng)上也未找到實現(xiàn)SM2密鑰交換協(xié)議的開源Python代碼,故本工具包可能是首次在互聯(lián)網(wǎng)上開源SM2密鑰交換協(xié)議的Python代碼.

2.2 SM2實現(xiàn)更完整

gmssl和pysmx實現(xiàn)的SM2數(shù)字簽名算法不包含國標(biāo)[2]規(guī)定的Z值計算和Hash變換,gmssl庫僅能輸入bytes類型消息,而本工具包完整實現(xiàn)了SM2數(shù)字簽名算法的Z值計算和Hash變換,可適配多種類型的輸入(str和bytes).此外,除核心算法外,本工具包還實現(xiàn)了國標(biāo)[1-4]描述的一些重要輔助函數(shù)(如密鑰派生函數(shù)、公鑰驗證、橢圓曲線系統(tǒng)參數(shù)驗證等).

2.3 區(qū)分加速版和未加速版

本工具包同時實現(xiàn)了SM2,SM3,SM4,ZUC這4種國密算法的加速版和未加速版,二者內(nèi)部結(jié)構(gòu)基本一致,功能相同,各算法的代碼文件相互獨立(除SM2需調(diào)用SM3),不設(shè)工具函數(shù)模塊,框架清晰.加速版使用Python第三方庫Numba和PyCryptodome,運行效率明顯提高,便于計算機高效執(zhí)行,但舍棄了部分Python語言特性,犧牲了代碼可讀性.未加速版采用純Python實現(xiàn),不依賴第三方庫,體現(xiàn)了除Numba和PyCryptodome之外的所有優(yōu)化,代碼簡潔、可讀性強,適合初學(xué)者學(xué)習(xí)算法代碼.

3 實驗與分析

本文實驗主要展示國密算法Python工具包加速版和未加速版以及現(xiàn)有國密算法Python庫gmssl和pysmx所實現(xiàn)的SM2,SM3,SM4,ZUC這4種國密算法的運行效率,此外引入ECC-256,MD5,SHA-256,AES-128,RC4這5種國際密碼算法(均來自國際密碼算法庫PyCryptodome)作為對比.

3.1 實驗環(huán)境與參數(shù)

能運行Python 3代碼的處理器和操作系統(tǒng)均可運行本工具包.經(jīng)不同平臺測試,其運行效率的絕對值隨著CPU性能差異而有所浮動,但與其他庫對比的相對值基本穩(wěn)定.實驗計算機的配置如表1所示:

表1 實驗計算機配置

除SM2以外,每輪測試預(yù)先生成100MB隨機數(shù)據(jù),分別以32B,1KB,32KB,1MB這4種大小的數(shù)據(jù)塊讀取,測試各密碼算法對不同長度消息的連續(xù)運算速率.所有實驗均執(zhí)行1000次,取平均值為有效數(shù)據(jù).

3.2 SM2測試

SM2最耗時的環(huán)節(jié)是橢圓曲線點乘運算.隨機生成1000個[1,n-2]范圍內(nèi)的大整數(shù)(n為橢圓曲線基點G的階),由各庫分別執(zhí)行基點點乘運算,速率如圖1所示.其中前7項的橢圓曲線參數(shù)為SM2標(biāo)準(zhǔn)參數(shù)[5],而ECC-256采用美國標(biāo)準(zhǔn)NIST P-256參數(shù)[18].未加速版實現(xiàn)了國標(biāo)[1]描述的3個點乘算法(圖1中標(biāo)注為算法1、算法2和算法3),實測算法2(加減法)最快.加速版調(diào)用了PyCryptodome庫的橢圓曲線運算鏈接庫,達到ECC-256普通點乘的性能,該庫還針對NIST P-256參數(shù)的數(shù)學(xué)特性進行了優(yōu)化,因此ECC-256的基點點乘明顯快于普通點乘.而進一步采用預(yù)計算技術(shù)的SM2基點點乘效率與ECC-256基本一致,約為普通點乘的4.4倍.

圖1 橢圓曲線點乘運算測試

未加速時(指采用算法2點乘的未加速版,下同)點乘運算速率為gmssl的3.0倍、pysmx的1.6倍,預(yù)計算加速后的點乘運算速率為gmssl的49.3倍、pysmx的25.9倍、未加速時的16.4倍.

SM2公鑰加解密、數(shù)字簽名與驗證以及密鑰交換的速率如圖2所示.密鑰交換測試只計雙方的純數(shù)據(jù)計算,不包含網(wǎng)絡(luò)傳輸?shù)绕渌_銷(gmssl和pysmx未實現(xiàn)SM2密鑰交換協(xié)議,故沒有相應(yīng)數(shù)據(jù)).

圖2 SM2算法測試

可見,各版本SM2實際運算的效率基本符合點乘運算測試結(jié)果.加速后運行效率約為gmssl的12～27倍、pysmx的7～16倍、未加速時的4～10倍.作為對比,另測試了ECC-256的簽名/驗證(即ECDSA算法),本實現(xiàn)速率分別為其6倍和1.2倍,PyCryptodome庫目前仍沒有實現(xiàn)ECC加密與解密.

3.3 SM3測試

各密碼雜湊算法的運算速率如圖3所示.

圖3 密碼雜湊算法的運算速率

加速版SM3處理短消息(指32B,下同)的速率為gmssl的73.9倍、pysmx的46.5倍、未加速版的32.6倍,達到PyCryptodome庫SHA-256速率的1.3倍;處理長消息(包含1KB,32KB,1MB,下同)的速率約為gmssl的645倍、pysmx的402倍、未加速版的298倍,達到SHA-256速率的79.3%.

3.4 SM4測試

各分組密碼算法在ECB和CBC這2種分組密碼工作模式下的加解密運算速率分別如圖4、圖5所示(圖中僅標(biāo)注了加密運算速率的數(shù)值).

圖4 分組密碼算法在ECB模式下的運算速率

圖5 分組密碼算法在CBC模式下的運算速率

ECB模式下,加速版SM4加解密短消息的平均速率為pysmx的131倍、gmssl的45.1倍、未加速版的16.7倍,達到PyCryptodome庫AES-128速率的1.2倍;加解密長消息的平均速率約為pysmx的610倍、gmssl的377倍、未加速版的137倍,達到AES-128速率的28.9%.

CBC模式下,加速版SM4加解密短消息的平均速率為pysmx的73.6倍、gmssl的30.0倍、未加速版的10.4倍,達到AES-128速率的2.7倍;加密長消息的速率約為pysmx的257倍、gmssl的167倍、未加速版的57.7倍,達到AES-128速率的48.2%;解密長消息的速率約為pysmx的467倍、gmssl的295倍、未加速版的112倍,達到AES-128速率的85.8%.

可見,與PyCryptodome的AES-128相比,本工具包SM4在ECB模式下加解密長消息、CBC模式下加密長消息的速率相對落后,而在CBC模式下加解密短消息時更快,其余情況下速率基本相當(dāng).

3.5 ZUC測試

各序列密碼算法的運算速率如圖6所示(序列密碼算法的加密和解密是同一種運算).

圖6 序列密碼算法的運算速率

加速版ZUC處理短消息的速率為pysmx的42.7倍、未加速版的24.0倍;處理長消息的速率約為pysmx的106倍、未加速版的61.4倍.本工具包ZUC的運算速率慢于PyCryptodome的RC4,但ZUC的安全性高于RC4.

4 結(jié) 語

綜上,采用Numba編譯核心算法Python代碼,調(diào)用PyCryptodome庫的橢圓曲線運算并采用預(yù)計算加速基點點乘,以及運用其他優(yōu)化后,Python實現(xiàn)的各國密算法的運行效率比現(xiàn)有國密算法Python庫gmssl和pysmx提高1～3個數(shù)量級,基本與PyCryptodome庫的同類密碼算法效率相當(dāng).本工具包大幅提升了國密算法在Python環(huán)境下的數(shù)據(jù)處理能力,一定程度上解決了現(xiàn)有國密算法Python庫性能不足的痛點.本工具包的全部代碼(包含SM2,SM3,SM4,ZUC這4種國密算法的加速版和未加速版,以及上述全部測試代碼)均已在碼云平臺開源(詳見https://gitee.com/basddsa/hggm).