◆陳思捷 邸紅葉 張金霞

?

SM2公鑰算法中大數(shù)除法的設(shè)計(jì)與硬件實(shí)現(xiàn)

◆陳思捷 邸紅葉 張金霞

(中國(guó)電子科技集團(tuán)公司第十五研究所后勤信息化事業(yè)部 北京 100083)

模運(yùn)算作為SM2橢圓曲線公鑰密碼算法的一種基本運(yùn)算，其前提是除法運(yùn)算，因此大數(shù)除法運(yùn)算速率及硬件實(shí)現(xiàn)是影響公鑰密碼算法性能的一個(gè)關(guān)鍵因素。本文對(duì)大數(shù)除法進(jìn)行了深入研究，提出了一種取位拼接將除法轉(zhuǎn)換為減法的設(shè)計(jì)思想，并給出了該算法在SM2公鑰密碼算法協(xié)處理器中的硬件實(shí)現(xiàn)。

SM2；大數(shù)除法；公鑰密碼；橢圓曲線；模運(yùn)算

0 引言

隨著電子通訊技術(shù)的發(fā)展，網(wǎng)絡(luò)信息的安全存儲(chǔ)、安全傳輸、安全處理的重要性越來(lái)越顯著。作為密碼學(xué)中的重要手段，公鑰密碼體系能夠有效地解決公共信道上的身份認(rèn)證、數(shù)據(jù)私密性、不可否認(rèn)性等問(wèn)題，其中，橢圓曲線密碼[1]由于在安全性、計(jì)算量、處理速度、存儲(chǔ)空間等方面的諸多優(yōu)勢(shì)，已經(jīng)成為繼RSA[2]密碼算法后被高度重視的公鑰密碼算法。國(guó)際上的相關(guān)標(biāo)準(zhǔn)化組織已經(jīng)開始對(duì)其進(jìn)行標(biāo)準(zhǔn)化工作，國(guó)內(nèi)也將SM2橢圓曲線公鑰密碼算法[3]作為密碼行業(yè)標(biāo)準(zhǔn)。在信息安全領(lǐng)域，SM2公鑰密碼算法既可以用于數(shù)據(jù)加解密，又可以用于數(shù)字簽名認(rèn)證，具有廣泛應(yīng)用市場(chǎng)。

為了提高運(yùn)算速度，業(yè)內(nèi)通常采用協(xié)處理器的方式加速運(yùn)算。在SM2公鑰密碼算法協(xié)處理器的硬件實(shí)現(xiàn)過(guò)程中，模運(yùn)算廣泛存在，而大數(shù)除法是其前提。然而，大數(shù)除法在硬件實(shí)現(xiàn)上較為困難且運(yùn)算速度較低，成為影響公鑰密碼算法效率提升的關(guān)鍵因素。因此，對(duì)大數(shù)除法進(jìn)行合理設(shè)計(jì)，在硬件上提高其運(yùn)算效率具有重大意義[4-9]。本文將對(duì)大數(shù)除法的算法進(jìn)行分析，給出一種行之有效的大數(shù)除法器的實(shí)現(xiàn)方法。

1 算法原理

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

（1）點(diǎn)乘中的除法運(yùn)算

此運(yùn)算稱為點(diǎn)乘[11]運(yùn)算，可以通過(guò)多次調(diào)用點(diǎn)加得到運(yùn)算結(jié)果。

可以看出在坐標(biāo)轉(zhuǎn)換過(guò)程中需要調(diào)用大數(shù)除法。

（2）模乘中的除法運(yùn)算

（3）模逆中的除法運(yùn)算

1.2本文算法原理

然而對(duì)于二進(jìn)制數(shù)據(jù)，各位非0即1，因此在除法運(yùn)算中也是非0即1，我們可以直接將除法運(yùn)算簡(jiǎn)化為減法運(yùn)算[14]，而不再需要中間的判斷取位商過(guò)程。

算法流程如下：

START

②區(qū)間判斷，

ENDFOR

END

START

END

1.3優(yōu)化流程

START

②區(qū)間判斷，

ENDFOR

END

在SM2橢圓曲線公鑰密碼算法中，大數(shù)除法主要用于模逆、坐標(biāo)轉(zhuǎn)換、模乘等運(yùn)算，除數(shù)多為較大的素?cái)?shù)，因此增加對(duì)除數(shù)的判斷可以大幅縮減大數(shù)除法運(yùn)算周期，提高SM2運(yùn)算效率。

2 大數(shù)除法硬件實(shí)現(xiàn)

SM2橢圓曲線公鑰密碼算法使用素?cái)?shù)域256位橢圓曲線，我們以256位大數(shù)除法、32位協(xié)處理器為例進(jìn)行詳細(xì)說(shuō)明，若被除數(shù)有效位寬為256，除數(shù)有效位寬為152，即：

圖1 區(qū)間劃分流程

結(jié)合上述大數(shù)除法模塊的硬件實(shí)現(xiàn)方法及256位大數(shù)除法舉例，可知：

3 大數(shù)除法在SM2協(xié)處理器中的實(shí)現(xiàn)及應(yīng)用分析

圖2 SM2協(xié)處理器對(duì)大數(shù)除法器的控制

從1.1節(jié)預(yù)備知識(shí)中我們可以看到，大數(shù)除法在SM2橢圓曲線公鑰密碼算法的具體應(yīng)用中還存在兩種特殊情況：32位除法及大數(shù)冪除法。

3.1 32位除法

32位除法原理同大數(shù)除法相同，區(qū)別在于除了在第一個(gè)周期從RAM中讀取數(shù)據(jù)之外，其余都是利用內(nèi)部32位寄存器直接實(shí)現(xiàn)操作流程，無(wú)需浪費(fèi)多個(gè)周期從RAM中讀數(shù)據(jù)、寫數(shù)據(jù)等，節(jié)省計(jì)算周期。

3.2冪除法

冪除法的原理和大數(shù)除法相同，區(qū)別在于冪除法的被除數(shù)是可以確定的幾個(gè)數(shù)據(jù)，是由數(shù)據(jù)位寬規(guī)格來(lái)選擇的，該被除數(shù)可以不進(jìn)行存儲(chǔ)。這樣在較耗費(fèi)存儲(chǔ)空間的SM2橢圓曲線公鑰密碼算法協(xié)處理器運(yùn)算中，通過(guò)合理規(guī)劃，節(jié)省硬件開銷空間。

由于這兩種特殊狀況的存在，在大數(shù)除法硬件實(shí)現(xiàn)中，可以通過(guò)增加端口控制信號(hào)，對(duì)普通大數(shù)除法、32位除法、冪除法進(jìn)行不同處理，而不是統(tǒng)一按照普通大數(shù)除法的流程進(jìn)行處理。32位除法與普通大數(shù)除法相比，可以節(jié)省從RAM讀寫數(shù)據(jù)所用周期；冪除法與普通大數(shù)除法相比，對(duì)于存儲(chǔ)空間的使用更加合理。

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

本文設(shè)計(jì)了一種可用于公鑰密碼算法中的通用大數(shù)除法器并討論了其在SM2橢圓曲線公鑰密碼算法中的硬件實(shí)現(xiàn)及應(yīng)用。該大數(shù)除法器可以擴(kuò)展至1024位的大數(shù)除法運(yùn)算，通過(guò)優(yōu)化流程、合理設(shè)計(jì)，可以有效縮減大數(shù)除法運(yùn)算周期，合理分配存儲(chǔ)空間，提高SM2橢圓曲線公鑰密碼算法的運(yùn)算效率。

[1]KoblizeN.ElliptlicCurveCryptosystem[J].Mathematicsof Computation, 1987.

[2]Rivest R L, Shamir A, Adleman L. A Method for Obtaining Digital Signatures and Public-key Cryptosystem [J]. Communication of the ACM, 1978.

[3]GM/T 0003.1-2012, SM2橢圓曲線公鑰密碼算法[S].

[4]劉墨德.Newton迭代法及其改進(jìn)[J].三明學(xué)院學(xué)報(bào)， 2007.

[5]章昭輝，王曉蒲，霍劍青.公鑰密碼體制中快速模算法的研究[J].計(jì)算機(jī)工程與應(yīng)用, 2002.

[6]童元滿，戴奎，王志英.基于SD數(shù)據(jù)表示的大數(shù)除法VLSI高速實(shí)現(xiàn)[J].計(jì)算機(jī)工程與科學(xué)，2006.

[7]刑衛(wèi)，宋東平.大數(shù)相除的快速算法[J].密碼與信息，1996.

[8]王劉成，林永才，姜文剛.快速高精度除法算法的FPGA實(shí)現(xiàn)[J].計(jì)算機(jī)工程，2011.

[9]李占才，王許書，涂序彥. RSA快速硬件實(shí)現(xiàn)研究[M]. 計(jì)算機(jī)研究與發(fā)展，2001.

[10]張煥國(guó)譯.D.Hankerson.橢圓曲線密碼學(xué)導(dǎo)論[M].電子工業(yè)出版社，2005.

[11]王慶先.有限域運(yùn)算和橢圓曲線數(shù)乘運(yùn)算研究[D].成都:電子科技大學(xué)，2006.

[12]陳逢林, 蘇厚勤.Montgomery算法的改進(jìn)及其在RSA中的運(yùn)用[J].計(jì)算機(jī)應(yīng)用于軟件, 2006.

[13]王建.橢圓曲線加密體制的雙有限域算法及其硬件實(shí)現(xiàn)[D].北京:北京大學(xué)，2008.

[14]David A. P, John L.H.鄭偉民譯.計(jì)算機(jī)組成與設(shè)計(jì):硬件/軟件接口[M].機(jī)械工業(yè)出版社，2007.