低功耗嵌入式平臺(tái)的SM2國(guó)密算法優(yōu)化實(shí)現(xiàn)

劉贛秦，李暉，朱輝，黃煜坤，劉興東

低功耗嵌入式平臺(tái)的SM2國(guó)密算法優(yōu)化實(shí)現(xiàn)

劉贛秦，李暉，朱輝，黃煜坤，劉興東

（西安電子科技大學(xué)網(wǎng)絡(luò)與信息安全學(xué)院，陜西 西安 710071）

隨著無(wú)線通信技術(shù)的發(fā)展和智能終端的普及，越來(lái)越多的密碼算法被應(yīng)用到物聯(lián)網(wǎng)設(shè)備中以保障通信安全和數(shù)據(jù)安全，其中，由國(guó)家密碼管理局提出的SM2橢圓曲線公鑰密碼算法作為我國(guó)自主研發(fā)的橢圓曲線公鑰密碼算法具有安全性高、密鑰短的優(yōu)點(diǎn)，已在通信系統(tǒng)中廣泛部署，應(yīng)用于身份認(rèn)證、密鑰協(xié)商等關(guān)鍵環(huán)節(jié)。然而，由于算法涉及有限域上的大整數(shù)運(yùn)算，計(jì)算開(kāi)銷(xiāo)較大，在低功耗嵌入式平臺(tái)下的執(zhí)行嚴(yán)重影響用戶體驗(yàn)。因此，面向ARM-m系列處理器提出了一種低功耗嵌入式平臺(tái)的SM2算法的高效實(shí)現(xiàn)方案。具體來(lái)說(shuō)，通過(guò)Thumb-2指令集提供的支持處理進(jìn)位和節(jié)省尋址周期，對(duì)大整數(shù)的模加、模減等基礎(chǔ)運(yùn)算進(jìn)行優(yōu)化，并結(jié)合平臺(tái)可用寄存器的數(shù)量構(gòu)建高效的基礎(chǔ)運(yùn)算模塊；基于ARM-m系列處理器乘累加指令周期短的特點(diǎn)，優(yōu)化蒙哥馬利乘法實(shí)現(xiàn)，并結(jié)合CIOS算法設(shè)計(jì)高效的模乘方案，方案不再局限于梅森素?cái)?shù)，極大地提高了模乘計(jì)算的速度和靈活性；在理論分析和實(shí)驗(yàn)測(cè)試的基礎(chǔ)上，給出了嵌入式平臺(tái)上多倍點(diǎn)標(biāo)量乘法wNAF滑動(dòng)窗法的窗長(zhǎng)選取方法。實(shí)驗(yàn)測(cè)試結(jié)果表明，可有效提升資源受限的低功耗嵌入式平臺(tái)中SM2算法的計(jì)算效率，不做預(yù)計(jì)算的情況下在Cortex-M3處理器上測(cè)試簽名速度可達(dá)0.204秒/次，驗(yàn)簽速度0.388秒/次，加密速度0.415秒/次，解密速度0.197秒/次。

信息安全；橢圓曲線密碼體制；SM2；嵌入式平臺(tái)；優(yōu)化

0 引言

物聯(lián)網(wǎng)技術(shù)出現(xiàn)后，因其具有使用成本低、部署難度小的特點(diǎn)，被廣泛應(yīng)用于各種領(lǐng)域，但在技術(shù)迅速得到發(fā)展和應(yīng)用的同時(shí)，其安全問(wèn)題逐漸成為關(guān)注重點(diǎn)。在低功耗嵌入式設(shè)備中， ARM-m系列處理器在包括微控制器、智能汽車(chē)系統(tǒng)、工業(yè)控制系統(tǒng)、智能家居以及無(wú)線網(wǎng)絡(luò)和傳感器等領(lǐng)域應(yīng)用廣泛，其中Cortex-M3處理器部署的IoT設(shè)備數(shù)量可達(dá)數(shù)十億。為保障信息安全，需利用加密技術(shù)對(duì)信息進(jìn)行保護(hù)，而通過(guò)公鑰密碼系統(tǒng)（PKC，public key cryptosystem）對(duì)數(shù)據(jù)信息進(jìn)行加密或簽名保護(hù)是保障網(wǎng)絡(luò)信息安全的主要方法之一。橢圓曲線公鑰密碼（ECC，elliptic curve cryptography）算法的安全性基于橢圓曲線離散對(duì)數(shù)問(wèn)題難以求解，在相同安全程度要求下密鑰規(guī)模小于其他公鑰密碼系統(tǒng)，具有密鑰短、運(yùn)算快、傳輸效率高的特點(diǎn)，更適合各類(lèi)資源受限的IoT設(shè)備。國(guó)家密碼管理局于2010年12月17日提出了SM2橢圓曲線公鑰密碼算法[1]，不僅滿足了各種商用密碼的應(yīng)用需要，也對(duì)我國(guó)信息安全體系建設(shè)有著重大意義。

然而，橢圓曲線底層運(yùn)算較為復(fù)雜，執(zhí)行簽名、加密計(jì)算時(shí)將對(duì)資源受限的IoT設(shè)備產(chǎn)生大量運(yùn)算壓力，設(shè)計(jì)一種高效的橢圓曲線計(jì)算方案可以有效地降低服務(wù)商的設(shè)備部署成本，提升用戶體驗(yàn)。近年來(lái)，研究人員對(duì)SM2算法針對(duì)不同應(yīng)用場(chǎng)景需要提出了許多解決方案，大多側(cè)重于應(yīng)用方面[2-4]，對(duì)于優(yōu)化實(shí)現(xiàn)關(guān)注較少。針對(duì)以上問(wèn)題，本文基于ARM-m系列處理器特點(diǎn)設(shè)計(jì)并實(shí)現(xiàn)了一種SM2國(guó)密算法的高效計(jì)算方案。

SM2算法主要可分為4個(gè)層次，域運(yùn)算層、點(diǎn)運(yùn)算層、多倍點(diǎn)標(biāo)量乘運(yùn)算層、SM2協(xié)議層，如圖1所示，其優(yōu)化手段與傳統(tǒng)ECC算法基本一致。域運(yùn)算的優(yōu)化實(shí)現(xiàn)研究主要針對(duì)計(jì)算量較大的模乘與模逆。數(shù)學(xué)家蒙哥馬利（Montgomery）于1985年提出了蒙哥馬利乘法[5]，極大地提高了大整數(shù)計(jì)算模乘的速度，Koc等[6]在此基礎(chǔ)上對(duì)蒙哥馬利約減算法的步驟進(jìn)行整合，提出了5種優(yōu)化的蒙哥馬利約減算法，進(jìn)一步提高了效率；文獻(xiàn)[7]提出了梅森素?cái)?shù)法，對(duì)于特定素?cái)?shù)效率有所提高。而近年來(lái)對(duì)于模乘的優(yōu)化研究偏重于硬件層面，Aashish等[8]設(shè)計(jì)了Montgomery 乘法器，有效地提高了模乘吞吐量，文獻(xiàn)[9]設(shè)計(jì)了基于硬件的交叉模乘；面向嵌入式平臺(tái)，王騰飛等[10]提出一種基于協(xié)處理器指令的優(yōu)化方案，同樣加快了計(jì)算速度；但基于硬件的方法存在靈活性缺陷，將現(xiàn)有的各類(lèi)嵌入式設(shè)備進(jìn)行硬件升級(jí)成本較大。兩乘數(shù)相等計(jì)算大整數(shù)平方時(shí)，在一些算力較強(qiáng)的平臺(tái)上表現(xiàn)較好的一種思路是利用Karatsuba算法和ToomCook算法[11]對(duì)平方計(jì)算進(jìn)行加速；針對(duì)支持64位運(yùn)算的平臺(tái)，李斌等[12]提出了結(jié)合硬件KOA乘法和梅森素?cái)?shù)法的模乘方案。對(duì)于大整數(shù)模逆的優(yōu)化計(jì)算，Hossain等[13]提出了基于擴(kuò)展Euclid算法的模逆算法，面向GPU等平臺(tái)Zhou等[14]設(shè)計(jì)了利用費(fèi)馬小定理計(jì)算模逆的方案，文獻(xiàn)[15]在此基礎(chǔ)上進(jìn)一步縮短了所需加法鏈。對(duì)于ECC的上層運(yùn)算，文獻(xiàn)[16]針對(duì)ECC的點(diǎn)運(yùn)算進(jìn)行優(yōu)化，分析了各類(lèi)坐標(biāo)系下計(jì)算的優(yōu)劣，取得了約 30%的計(jì)算速度提升?；旌献鴺?biāo)法[17]由Cohen提出，討論了求逆與模乘時(shí)間比不同時(shí)各類(lèi)混合坐標(biāo)系的優(yōu)劣性。文獻(xiàn)[18]提出了ECC標(biāo)量乘法對(duì)使用預(yù)處理及窗口技術(shù)提高點(diǎn)乘計(jì)算效率的思想。由Longa提出的m-DBL算法[19]基于模乘與模平方效率不同，將重復(fù)倍點(diǎn)運(yùn)算中的模乘轉(zhuǎn)化為模平方來(lái)加速運(yùn)算；文獻(xiàn)[20]介紹了用預(yù)計(jì)算的查表法對(duì)固定點(diǎn)標(biāo)量乘法進(jìn)行加速；文獻(xiàn)[21]利用可并行的蒙哥馬利點(diǎn)乘加速了多倍點(diǎn)標(biāo)量乘法運(yùn)算。但此類(lèi)方法大多針對(duì)強(qiáng)算力平臺(tái)，對(duì)于各種資源受限的嵌入式平臺(tái)，由于對(duì)平臺(tái)的一些特點(diǎn)缺乏針對(duì)性，如存儲(chǔ)受限、并行效率差，實(shí)測(cè)時(shí)計(jì)算緩慢，效果欠佳。

圖1 SM2算法層次

Figure 1 Structure of algorithm SM2

本文針對(duì)SM2國(guó)密算法，充分利用低功耗嵌入式平臺(tái)特點(diǎn)，對(duì)橢圓曲線密碼體制的底層運(yùn)算進(jìn)行優(yōu)化實(shí)現(xiàn)研究，對(duì)算法的一些關(guān)鍵步驟進(jìn)行改進(jìn)，主要貢獻(xiàn)包括以下幾個(gè)方面。

1) 結(jié)合ARM-m系列MCU訪存開(kāi)銷(xiāo)大的特點(diǎn)，構(gòu)建了基于Thumb-2指令集的大整數(shù)模加、模減基礎(chǔ)運(yùn)算模塊，結(jié)合平臺(tái)可用寄存器的數(shù)量進(jìn)行高效分配，相比LibTomMath開(kāi)源庫(kù)實(shí)現(xiàn)的模加方案性能提升2.42倍。

2) 考慮平臺(tái)并行效率不高以及訪存較慢的特點(diǎn)，優(yōu)化了蒙哥馬利乘法，并結(jié)合CIOS算法設(shè)計(jì)了高效的模乘方案，效率超過(guò)了在大部分平臺(tái)上表現(xiàn)較好的梅森素?cái)?shù)法和其他各種公開(kāi)算法，同時(shí)避免了梅森素?cái)?shù)法對(duì)于特定素?cái)?shù)的限制問(wèn)題，提高了算法靈活性，簽名效率相比梅森素?cái)?shù)法提升約6.13%。

3) 為存儲(chǔ)受限環(huán)境高效計(jì)算ECC多倍點(diǎn)標(biāo)量乘法提供了解決方案，利用NAF算法計(jì)算多倍點(diǎn)標(biāo)量乘法，分析了使得預(yù)計(jì)算和乘法階段時(shí)間總和最短的窗長(zhǎng)選取，并通過(guò)實(shí)驗(yàn)測(cè)試驗(yàn)證了結(jié)論。

4) 在搭載Cortex-M3處理器的開(kāi)發(fā)板上應(yīng)用優(yōu)化方案實(shí)現(xiàn)了使用256位素域橢圓曲線的SM2簽名、驗(yàn)簽、公鑰生成以及加解密算法，并進(jìn)行了各項(xiàng)對(duì)比測(cè)試。實(shí)驗(yàn)測(cè)試證明提出的優(yōu)化方案效果顯著，達(dá)到了0.205次/秒簽名，0.415次/秒加密速度，相比LibTomMath開(kāi)源庫(kù)實(shí)現(xiàn)的版本簽名性能提升1.62倍，加密性能提升1.59倍。

1 背景知識(shí)

1.1 SM2數(shù)字簽名算法

1.2 SM2加密算法

1.3 橢圓曲線定義及坐標(biāo)表示

1.4 蒙哥馬利乘法

1.5 擴(kuò)展歐幾里得算法

1.6 Cortex-M3及Thumb-2指令集

ARM公司為了更好適應(yīng)微控制器和受限的節(jié)能應(yīng)用需求，設(shè)計(jì)了ARM-m系列處理器，其中Cortex-M3處理器應(yīng)用廣泛，采用ARMv7-M架構(gòu)，包括所有的16位Thumb指令集和基本的32位Thumb-2指令集架構(gòu)。Thumb-2在Thumb指令集架構(gòu)（ISA，instruction set architecture）上進(jìn)行了大量的改進(jìn)，它與Thumb相比，具有更高的代碼密度并提供16/32位指令的更高性能。部分Thumb-2指令集如表1所示。

2 域運(yùn)算優(yōu)化

SM2算法中基礎(chǔ)四則運(yùn)算涉及的操作數(shù)均為256位大整數(shù)，運(yùn)算在有限域中進(jìn)行。根據(jù)Gura等[24]的研究，MCU平臺(tái)開(kāi)銷(xiāo)最大的操作為訪存，因此算法優(yōu)化時(shí)應(yīng)盡可能減少訪存次數(shù)，將常用字段放在寄存器中。本節(jié)介紹面向低功耗嵌入式平臺(tái)的域運(yùn)算構(gòu)建和優(yōu)化方法，對(duì)資源有限的寄存器進(jìn)行合理利用。

表1 部分Thumb-2指令集

2.1 快速模加減

模加減所得結(jié)果為有限域中的元素，在采用標(biāo)準(zhǔn)進(jìn)制表示時(shí)，被存儲(chǔ)在一組機(jī)器字中，以Cortex-M3平臺(tái)的32位架構(gòu)為例，機(jī)器字可表示為16、32位整型或64位浮點(diǎn)型。由文獻(xiàn)[25]可知，浮點(diǎn)型對(duì)字的利用率低，僅有31.25%。而16位及32位帶符號(hào)整型對(duì)字的利用率均不及32位無(wú)符號(hào)整型。因此，本文存儲(chǔ)256位整數(shù)時(shí)均使用32位無(wú)符號(hào)整型。有限域中256位模加計(jì)算過(guò)程如算法1所示。

算法1 256位模加

輸入 加數(shù)，加數(shù)，素域

3) 對(duì)從7到0，重復(fù)執(zhí)行

5) 對(duì)從1到7，重復(fù)執(zhí)行：

圖2 指令集處理256位模加示意

Figure 2 The instruction set handles 256 bit modules plus

圖3 指令集處理256位減法示意

Figure 3 The instruction set handles 256-bit subtraction

表2 通用寄存器的分配

2.2 改進(jìn)的蒙哥馬利模乘

模乘的執(zhí)行過(guò)程通?？煞譃閮蓚€(gè)階段，蒙哥馬利乘法[5]和梅森素?cái)?shù)法[7]。首先計(jì)算256位乘法，再計(jì)算模約減。考慮MCU平臺(tái)通常搭載嵌入式實(shí)時(shí)操作系統(tǒng)，并行效率低；并且，測(cè)試中模平方的按位二次展開(kāi)法效果不佳，因此舍棄了蒙哥馬利乘法中的相關(guān)步驟。由1.4節(jié)介紹的蒙哥馬利乘法，注意到

使用式(11)計(jì)算時(shí)，相比1.4節(jié)中介紹的蒙哥馬利乘法，僅計(jì)算兩次蒙哥馬利約減和兩次256位乘法。進(jìn)一步，可將乘法和約減步驟結(jié)合考慮，本文基于CIOS（coarsely integrated operand scanning）算法[6]對(duì)蒙哥馬利約減算法進(jìn)行優(yōu)化，調(diào)整蒙哥馬利乘法的循環(huán)體和乘法計(jì)算順序，整合了乘法和約減過(guò)程。整個(gè)計(jì)算過(guò)程分為一層外循環(huán)和兩層內(nèi)循環(huán)，基于大整數(shù)運(yùn)算的分段思想，外循環(huán)拆解乘數(shù)至32位，第一層每次取的32位在結(jié)果數(shù)組中乘累加，第二層計(jì)算取約減數(shù)再次乘累加，由于結(jié)果數(shù)組的部分可常駐寄存器，相比先相乘后約減的模乘計(jì)算方式有效降低了訪存次數(shù)。蒙哥馬利約減算法如算法2所示。

算法2 蒙哥馬利約減算法

對(duì)從0到7，重復(fù)執(zhí)行

算法3 改進(jìn)的蒙哥馬利模乘算法

3 多倍點(diǎn)標(biāo)量乘法優(yōu)化

算法4NAF標(biāo)量表示算法

輸入 標(biāo)量

算法5NAF標(biāo)量乘法算法

顯然，算法效率與標(biāo)量的漢明重量（非0元素個(gè)數(shù)）有關(guān)，標(biāo)量表示算法可以有效降低標(biāo)量的漢明重量。其他標(biāo)量乘法算法亦可分為預(yù)計(jì)算和乘法執(zhí)行兩階段，即通過(guò)預(yù)計(jì)算臨時(shí)存儲(chǔ)得到的結(jié)果對(duì)乘法執(zhí)行過(guò)程進(jìn)行加速。一般地，預(yù)計(jì)算得到結(jié)果越多，乘法執(zhí)行時(shí)越快，預(yù)計(jì)算時(shí)間也會(huì)增長(zhǎng)，所以考慮兩階段開(kāi)銷(xiāo)總和作為算法整體性能標(biāo)準(zhǔn)。計(jì)算固定點(diǎn)的乘法時(shí)，預(yù)計(jì)算所得結(jié)果可在多次乘法中重復(fù)使用，此時(shí)預(yù)計(jì)算所耗時(shí)間可忽略不計(jì)?？紤]低功耗嵌入式設(shè)備中存儲(chǔ)資源有限，存儲(chǔ)一張預(yù)計(jì)算的乘法表會(huì)占用較多存儲(chǔ)資源，因此假設(shè)預(yù)計(jì)算結(jié)果僅用于一次乘法。忽略對(duì)點(diǎn)求加法逆的開(kāi)銷(xiāo)，標(biāo)量長(zhǎng)度為256時(shí)，考慮最壞情形下（即標(biāo)量二進(jìn)制表示漢明重量為256）的NAF標(biāo)量乘法計(jì)算量如表3所示。

表3 256位標(biāo)量計(jì)算量

注：A代表點(diǎn)加運(yùn)算，D代表倍點(diǎn)運(yùn)算

預(yù)計(jì)算階段開(kāi)銷(xiāo)隨增大呈指數(shù)型增長(zhǎng)，同時(shí)乘法階段計(jì)算量的減少量逐漸下降。算法實(shí)質(zhì)上是通過(guò)NAF重編碼算法獲得的標(biāo)量中的漢明重量減少，從而減少點(diǎn)加計(jì)算次數(shù)，提高了多倍點(diǎn)標(biāo)量乘法的整體性能。

4 實(shí)驗(yàn)分析

本節(jié)給出優(yōu)化實(shí)現(xiàn)的SM2國(guó)密算法的性能數(shù)據(jù)，使用了基于Tom StDenis編寫(xiě)的LibTomMath開(kāi)源大數(shù)運(yùn)算庫(kù)實(shí)現(xiàn)的SM2國(guó)密算法作為對(duì)比。測(cè)試時(shí)使用橢圓曲線及有限域參數(shù)均為文獻(xiàn)[28]中給定參數(shù)。

本文進(jìn)行測(cè)試的硬件環(huán)境為搭載cortex-M3的STM32F103ZET6開(kāi)發(fā)板和ST-Link下載器，系統(tǒng)時(shí)鐘頻率為72 MHz（STM32F103ZET6有5個(gè)時(shí)鐘源，最大頻率為72 MHz），存儲(chǔ)flash為512 kB；軟件環(huán)境為keil5.0編譯器。編譯參數(shù)使用了-O3、-Otime、--apcs=interwork，用于開(kāi)啟編譯器優(yōu)化和thumb指令集和ARM指令集混合調(diào)用。以運(yùn)行時(shí)間作為評(píng)價(jià)指標(biāo)，將設(shè)計(jì)的方案與一些其他公開(kāi)算法進(jìn)行對(duì)比評(píng)測(cè)。

對(duì)于基礎(chǔ)運(yùn)算模塊，為避免次數(shù)較少、特殊數(shù)據(jù)的影響，通過(guò)重復(fù)執(zhí)行10次公鑰生成過(guò)程在keil5.0中的Simulator對(duì)本文實(shí)現(xiàn)的模加模塊和LibTomMath開(kāi)源大數(shù)運(yùn)算庫(kù)中的模加模塊進(jìn)行對(duì)比測(cè)試，由于庫(kù)中大數(shù)結(jié)構(gòu)體定義較為復(fù)雜，對(duì)其進(jìn)行了精簡(jiǎn)，限定為256位整數(shù)，結(jié)果如表4所示，共執(zhí)行44 200次，可見(jiàn)本文設(shè)計(jì)的基于Thumb-2指令集的優(yōu)化方案使模加算法的執(zhí)行效率提升明顯，性能提升2.42倍。

表4 素?cái)?shù)域模加測(cè)試結(jié)果

同樣地，在開(kāi)發(fā)板上實(shí)現(xiàn)設(shè)計(jì)的模乘方案和一些其他公開(kāi)算法，進(jìn)行對(duì)比評(píng)測(cè)。由于模乘在整個(gè)SM2算法中開(kāi)銷(xiāo)占比約70%，以隨機(jī)生成的相同公私鑰對(duì)整個(gè)SM2協(xié)議運(yùn)行時(shí)間進(jìn)行測(cè)試，通過(guò)JTAG調(diào)試模塊記錄時(shí)間，結(jié)果如表5所示。

表5 不同模乘算法下SM2算法性能測(cè)試結(jié)果

由于平臺(tái)本身不支持模平方的加速算法，同時(shí)結(jié)合MCU平臺(tái)訪存開(kāi)銷(xiāo)大的特點(diǎn)，設(shè)計(jì)的模乘方案優(yōu)于強(qiáng)算力平臺(tái)中表現(xiàn)較好的梅森素?cái)?shù)法，且避免了對(duì)素?cái)?shù)的限定，更廣泛適用于實(shí)際環(huán)境中各種需要更換橢圓曲線參數(shù)來(lái)提高安全性的需求，同時(shí)兼顧SM2國(guó)密算法中的模運(yùn)算和模運(yùn)算，亦可在其他需計(jì)算大整數(shù)模乘的密碼算法中推廣。

為了測(cè)評(píng)多倍點(diǎn)標(biāo)量乘法中的標(biāo)量表示算法，對(duì)1 000次未知點(diǎn)多倍點(diǎn)標(biāo)量乘法計(jì)算時(shí)間進(jìn)行測(cè)試對(duì)比，結(jié)果如圖4所示，其中預(yù)計(jì)算開(kāi)銷(xiāo)如表6所示。

圖4 多倍點(diǎn)標(biāo)量乘法測(cè)試結(jié)果

表6 預(yù)計(jì)算開(kāi)銷(xiāo)分析

結(jié)果表明，取=4時(shí)的NAF算法效果最佳。由表3可知，最壞情形時(shí)取5較取4少計(jì)算一次點(diǎn)加，但實(shí)際情況中標(biāo)量的漢明重量通常少于最壞情形，故考慮預(yù)計(jì)算結(jié)果僅用于一次乘法時(shí)，應(yīng)取=4，適用于未知點(diǎn)乘法，對(duì)于固定點(diǎn)乘法預(yù)計(jì)算時(shí)間可忽略不計(jì)，此時(shí)窗長(zhǎng)取值可視存儲(chǔ)情況而定。

與基于LibTomMath庫(kù)構(gòu)建基礎(chǔ)運(yùn)算的實(shí)現(xiàn)的SM2算法進(jìn)行對(duì)比測(cè)試，同時(shí)對(duì)本文設(shè)計(jì)的SM2國(guó)密算法優(yōu)化方案的整體性能表現(xiàn)進(jìn)行評(píng)估。對(duì)簽名、驗(yàn)簽、公鑰生成、加密、解密運(yùn)算各執(zhí)行1 000次取平均值，結(jié)果如圖5所示，單次簽名速度可達(dá)0.205秒/次，加密速度0.415秒/次，顯著優(yōu)于基于開(kāi)源庫(kù)LibTomMath實(shí)現(xiàn)的SM2國(guó)密算法，簽名性能提升1.62倍，加密性能提升1.59倍。

圖5 SM2算法測(cè)試結(jié)果

5 結(jié)束語(yǔ)

本文面向低功耗嵌入式平臺(tái)設(shè)計(jì)了SM2算法的優(yōu)化實(shí)現(xiàn)方案，其中通過(guò)Thumb-2指令集的支持構(gòu)建了高效的模加減運(yùn)算模塊，對(duì)上層運(yùn)算提供支持；結(jié)合低功耗嵌入式平臺(tái)訪存慢、并行效率低的特點(diǎn)，基于蒙哥馬利乘法進(jìn)行改良，并結(jié)合CIOS算法設(shè)計(jì)了高效的模乘計(jì)算方案，相比梅森素?cái)?shù)法提高了靈活性和效率。實(shí)驗(yàn)結(jié)果表明，本文給出的優(yōu)化實(shí)現(xiàn)能有效地提升SM2算法的計(jì)算速度，實(shí)驗(yàn)測(cè)試中達(dá)到了0.205秒/次簽名，0.415秒/次加密速度，可以更好地滿足在低功耗嵌入式設(shè)備上高效計(jì)算簽名與加密的需求，具有非常高的實(shí)際應(yīng)用價(jià)值。

[1] 國(guó)家密碼管理局. SM2橢圓曲線公鑰密碼算法第1部分: 總則: GM/T 0003.1-2012[S]. 北京:中國(guó)標(biāo)準(zhǔn)出版社, 2012:8.

State Cryptography Administration. SM2 elliptic curve public key cryptography algorithm part 1: general provisions: GM/T 0003.1-2012[S].8 Beijing: China Standard Press, 2012: 8.

[2] 羅玙榕, 曹進(jìn), 李暉, 等. 基于SM2聯(lián)合簽名的電子發(fā)票公開(kāi)驗(yàn)證方案[J]. 網(wǎng)絡(luò)與信息安全學(xué)報(bào), 2022, 8(2): 122-131.

LUO Y R, CAO J, LI H, et al. Electronic invoice public verification scheme based on SM2 joint signature [J]. Journal of Network and Information Security, 2022, 8(2): 122-131.

[3] 陳鋒, 鄒洪, 吳亞楠, 等. 基于SM2密碼體系的電力信息安全監(jiān)控系統(tǒng)設(shè)計(jì)[J]. 電子設(shè)計(jì)工程, 2022, 30(5):100-103, 108.

CHEN F, ZOU H, WU Y N, et al. Design of power information security monitoring system based on sm2 cipher system[J]. Electronic Design Engineering, 2022, 30(5):100-103, 108.

[4] 程朝輝. 基于SM2的無(wú)證書(shū)加密算法[J]. 密碼學(xué)報(bào), 2021, 8(1): 87-95.

CHENG C H. Certificateless encryption algorithm based on SM2 [J]. Journal of Cryptography, 2021, 8(1): 87-95.

[5] MONTGOMERY P L. Modular multiplication without trial division[J]. Mathematics of Computation, 1985, 44(170): 519-521.

[6] KOC C, ACAR T, JR B. Analyzing and comparing montgomery multiplication algorithms[J]. Micro, IEEE, 1996, 16(3): 26-33.

[7] SOLINAS J A. Generalized mersenne numbers[M]. Faculty of Mathematics, University of Waterloo, 1999.

[8] PARIHAR A, NAKHATE S. High-speed high-throughput VLSI Architecture for RSA montgomery modular multiplication with efficient format conversion[J]. Journal of the Institution of Engineers (India) Series B, 2019, 100(2): 217-222.

[9] RAHMAN M S, HOSSAIN M S, RAHAT E H, et al. Efficient hardware implementation of 256-bit ECC processor over prime field[C]//2019 International Conference on Electrical, Computer and Communication Engineering (ECCE). 2019: 1-6.

[10] 王騰飛, 張海峰, 許森. SM2專(zhuān)用指令協(xié)處理器設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)工程與應(yīng)用, 2022, 58(2): 102-109.

WANG T F, ZHANG H F, XU S. Design and implementation of SM2 special instruction coprocessor[J]. Computer Engineering and Applications, 2022, 58(2): 102-109.

[11] DING J N，LI S G，GU Z. High-speed ECC processor over NIST prime fields applied with toom–cook multiplication[J]. IEEE Transactions on Circuits and Systems I, 2019, 66(3): 1003-1016.

[12] 李斌, 周清雷, 陳曉杰, 等. 可重構(gòu)的素域SM2算法優(yōu)化方法[J].通信學(xué)報(bào), 2022, 43(3): 30-41.

LI B, ZHOU Q L, CHEN X J, et al. Optimization of reconfigurable SM2 algorithm over prime field[J]. Journal of Communication, 2022, 43(3): 30-41.

[13] HOSSAIN M S, KONG Y. High-performance FPGA implementation of modular inversion over F_256 for elliptic curve cryptography[C]//2015 IEEE International Conference on Data Science and Data Intensive Systems. 2015: 169-174.

[14] ZHOU L, SU C, HU Z, et al. Lightweight implementations of NIST P-256 and SM2 ECC on 8-bit resource-constraint embedded device[J]. ACM Transactions on Embedded Computing Systems (TECS), 2019, 18(3): 1-13.

[15] 朱輝, 黃煜坤, 王楓為, 等. 一種基于圖形處理器的高吞吐量 SM2 數(shù)字簽名計(jì)算方案[J]. 電子與信息學(xué)報(bào), 2022, 44(10): 1-10.

ZHU H, HUANG Y K, WANG F W, et al. A high throughput SM2 digital signature computing scheme based on graphics processor[J]. Journal of Electronics and Information Technology, 2022, 44(10): 1-10.

[16] LONGA P, GEBOTYS C. Efficient techniques for high-speed elliptic curve cryptography[C]//International Workshop on Cryptographic Hardware and Embedded Systems. Heidelberg, 2010: 80-94.

[17] COHEN H, MIYAJI A, ONO T. Efficient elliptic curve exponentiation using mixed coordinates[C]//International Conference on the Theory and Application of Cryptology and Information Security. 1998: 51-65.

[18] SETIADI I, KISTIJANTORO A I, MIYAJI A. Elliptic curve cryptography: Algorithms and implementation analysis over coordinate systems[C]//2015 2nd International Conference on Advanced Informatics: Concepts, Theory and Applications (ICAICTA). 2015: 1-6.

[19] LONGA P, MIRI A. Fast and flexible elliptic curve point arithmetic over prime fields[J]. IEEE Transactions on Computers, 2008, 57(3): 289-302.

[20] HANKERSON D, MENEZES A J, VANSTONE S. Guide to elliptic curve cryptography[M]. Springer Science & Business Media, 2006.

[21] ISLAM M M, HOSSAIN M S, HASAN M K, et al. FPGA implementation of high-speed area-efficient processor for elliptic curve point multiplication over prime field[J]. IEEE Access, 2019, 7: 178811-178826.

[22] 國(guó)家密碼管理局. SM3 密碼雜湊算法: GMT 0004.4-2012[S]. 北京:中國(guó)標(biāo)準(zhǔn)出版社, 2012:8.

National Cryptography Administration. SM3 password hashing algorithm: GMT 0004.4-2012[S]. Beijing: Standards Press of China, 2012:8.

[23] RIVAIN M. Fast and regular algorithms for scalar multiplication over elliptic curves[J]. Cryptology ePrint Archive, 2011.

[24] GURA N, Patel A, Wander A, et al. Comparing elliptic curve cryptography and RSA on 8-bit CPUs[C]//International Workshop on Cryptographic Hardware and Embedded Systems. 2004: 119-132.

[25] Advanced Micro Devices, Inc. AMD graphic core next[R]. Advanced Micro Devices, Inc, 2011.

[26] DUSSE S R, KALISKI B S. A cryptographic library for the Motorola DSP56000[C]//Workshop on the Theory and Application of Cryptographic Techniques. 1990: 230-244.

[27] MUIR J, STINSON D. Minimality and other properties of the width-𝑤 nonadjacent form[J]. Mathematics of Computation, 2006, 75(253): 369-384.

[28] 國(guó)家密碼管理局. SM2橢圓曲線公鑰密碼算法第5部分:參數(shù)定義: GMT 0003.4-2012[S]. 北京: 中國(guó)標(biāo)準(zhǔn)出版社, 2012.

National Cryptography Administration. SM2 Elliptic curve public key cryptography algorithm Part 5: Parameter definition: GMT 0003.4-2012[S]. Beijing: Standards Press of China, 2012.

[29] 閆閔. 基于GPU的SM2數(shù)字簽名和驗(yàn)證算法的快速實(shí)現(xiàn)與優(yōu)化[D]. 上海: 上海交通大學(xué), 2020.

YAN M. Fast implementation and optimization of SM2 digital signature and verification algorithm based on GPU [D]. Shanghai: Shanghai Jiaotong University, 2020.

Public key cryptographic algorithm SM2 optimized implementation on low power embedded platform

LIU Ganqin, LI Hui, ZHU Hui, HUANG Yukun, LIU Xingdong

School of Cyber Engineering, Xidian University, Xi’an 710071, China

With the development of wireless communication technology and the popularization of intelligent terminals, more and more cryptographic algorithms are applied to IoT devices to ensure the security of communication and data. Among them, the SM2 elliptic curve public key cryptography proposed by the State Cryptography Administration is an elliptic curve public key cryptography algorithm developed domestically, which has the advantages of high security and short key. SM2 has been widely deployed in various communication systems and is used in essential parts such as identity authentication and key negotiation. However, since SM2 involves large integer operations on finite fields, the computational cost is high, and its execution on a low-power embedded platform seriously affects the user experience. Therefore, an efficient implementation scheme of SM2 algorithm for low-power embedded platform was proposed for ARM-m series processors. Specifically, Thumb-2 instruction set was adopted to handle carry and save addressing cycles, basic operations such as modulo addition and sub-traction of large integers were optimized, and the number of available registers on the platform was combined to build efficient basic operations. Besides, based on the short multiplication and accumulation instruction cycle of ARM-m series processors, the implementation of Montgomery multiplication was optimized, and an efficient modular multiplication scheme was designed in combination with the CIOS algorithm. The scheme was no longer limited to Mersenne primes, and greatly improved the speed and flexibility of modular multiplication. Based on the theoretical analysis and experimental test, the window length selection method of the multiple point-scalar multiplication wNAF sliding window method on the embedded platform was given. The experimental test results show that the proposed scheme can effectively improve the computational efficiency of the SM2 algorithm on the resource-constrained low-power embedded platform. Without pre-calculation, the test signature speed can reach 0.204s/time, the signature verification speed is 0.388s/time, the encryption speed is 0.415s/time, and the decryption speed is 0.197s/time.

information security, elliptic curve cryptosystem, SM2, embedded platform, optimization

TP393

A

10.11959/j.issn.2096?109x.2022080

2022?05?16；

2022?07?05

朱輝，zhuhui@xidian.edu.cn

國(guó)家自然科學(xué)基金（61972304, 61932015），陜西省重點(diǎn)產(chǎn)業(yè)創(chuàng)新鏈項(xiàng)目（2020ZDLGY08-04）

The National Natural Science Foundation of China (61972304, 61932015), Natural Science Foundation of Shaanxi Province (2020ZDLGY08-04)

劉贛秦, 李暉, 朱輝, 等. 低功耗嵌入式平臺(tái)的SM2國(guó)密算法優(yōu)化實(shí)現(xiàn)[J]. 網(wǎng)絡(luò)與信息安全學(xué)報(bào), 2022, 8(6): 29-38.

LIU G Q, LI H, ZHU H, et al. Public key cryptographic algorithm SM2 optimized implementation on low power embedded platform [J]. Chinese Journal of Network and Information Security, 2022, 8(6): 29-38.

劉贛秦（1998?），男，江西蓮花人，西安電子科技大學(xué)碩士生，主要研究方向?yàn)槊艽a算法的高性能優(yōu)化。

李暉（1968?），男，河南靈寶人，博士，西安電子科技大學(xué)教授、博士生導(dǎo)師，主要研究方向?yàn)槊艽a學(xué)、無(wú)線網(wǎng)絡(luò)安全、云計(jì)算安全、信息論與編碼理論。

朱輝（1981?），男，河南周口人，博士，西安電子科技大學(xué)教授、博士生導(dǎo)師，主要研究方向?yàn)閿?shù)據(jù)安全與隱私保護(hù)、安全方案及協(xié)議設(shè)計(jì)、網(wǎng)絡(luò)及應(yīng)用安全。

黃煜坤（1998?），男，湖北襄陽(yáng)人，西安電子科技大學(xué)碩士生，主要研究方向?yàn)槊艽a算法的高性能優(yōu)化。

劉興東（1992?），男，湖南衡陽(yáng)人，西安電子科技大學(xué)碩士生，主要研究方向?yàn)榫W(wǎng)絡(luò)空間安全、可信執(zhí)行環(huán)境、密碼算法優(yōu)化。