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

◆陳思捷 邸紅葉 張金霞

?

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

◆陳思捷 邸紅葉 張金霞

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

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

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

0 引言

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

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

1 算法原理

1.1預(yù)備知識

（1）點乘中的除法運算

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

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

（2）模乘中的除法運算

（3）模逆中的除法運算

1.2本文算法原理

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

算法流程如下：

START

②區(qū)間判斷，

ENDFOR

END

START

END

1.3優(yōu)化流程

START

②區(qū)間判斷，

ENDFOR

END

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

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

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

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

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

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

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

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

3.1 32位除法

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

3.2冪除法

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

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

4 結(jié)束語

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

[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é)報， 2007.

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

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

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

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

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

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

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

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

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

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