二進(jìn)制域滑動(dòng)窗口快速模乘算法

蔣洪波

(黑龍江科技學(xué)院 電氣與信息工程學(xué)院，哈爾濱 150027)

二進(jìn)制域滑動(dòng)窗口快速模乘算法

蔣洪波

(黑龍江科技學(xué)院 電氣與信息工程學(xué)院，哈爾濱 150027)

加速GF(2m)上的模乘運(yùn)算是提高GF(2m)上ECC算法性能的關(guān)鍵。分析了窗口寬度ω的comb多項(xiàng)式乘法和NIST約簡多項(xiàng)式算法，結(jié)合兩種算法提出一種滑動(dòng)窗口的快速模乘算法。該算法彌補(bǔ)了先乘后模方法在時(shí)間上和存儲(chǔ)空間上的缺點(diǎn)，縮短了運(yùn)算時(shí)間，仿真結(jié)果表明快速模算法的運(yùn)算效率比先乘后模的窗口comb多項(xiàng)式乘法和NIST快速約簡速度提高21%左右，預(yù)計(jì)算只需要ω-1個(gè)值。

滑動(dòng)窗口;二進(jìn)制域;快速模乘

0 引言

1976年Diffie和Hellman提出了一種公開密鑰密碼加密解密的新方法?；跈E圓曲線點(diǎn)群上離散對(duì)數(shù)問題(ECDLP)的難解性，橢圓曲線密碼體制具有高度安全性，在同等安全強(qiáng)度下，其計(jì)算量小，存儲(chǔ)量少，帶寬小，軟件和硬件實(shí)現(xiàn)的規(guī)模小，加密和簽字速度高［1］。因此，ECC體制特別適用于計(jì)算能力、集成電路空間、帶寬受限又要求高速實(shí)現(xiàn)的情況，如智能卡和無線通信等領(lǐng)域。

密碼學(xué)中所使用的橢圓曲線最常見的有兩類:質(zhì)數(shù)曲線和二元曲線。二元曲線上的基本運(yùn)算通常叫做二進(jìn)制域上的運(yùn)算。二進(jìn)制域GF(2m)(下文以域代替)上基本運(yùn)算簡單和快速，其模乘算法主要有移位加模2和Montgomery算法［2］。目前最快的乘法算法之一是窗口寬度ω的comb多項(xiàng)式乘法。模乘結(jié)果必須在得到乘法結(jié)果之后再對(duì)其求模，這樣會(huì)耗費(fèi)很多運(yùn)行時(shí)間，同時(shí)也需要存儲(chǔ)2ω-1個(gè)預(yù)計(jì)算值。筆者提出的算法是在目前二進(jìn)制域上從左向右窗口寬度ω的comb多項(xiàng)式乘法和NIST快速約簡算法基礎(chǔ)上，將兩種算法相結(jié)合，實(shí)現(xiàn)減少循環(huán)次數(shù)同時(shí)也節(jié)省存儲(chǔ)單元的目的。

1 comb多項(xiàng)式模乘算法

假設(shè)實(shí)現(xiàn)平臺(tái)是字長W位的系統(tǒng)，其中W是8的整數(shù)倍。一個(gè)字U的W位，分別從0到W-1進(jìn)行標(biāo)記，其中第0位為最高有效位。

設(shè)f(z)是一個(gè)m次的二進(jìn)制既約多項(xiàng)式，記f(z)=zm+r(z)，其中r(z)是一個(gè)次數(shù)最多為m-1的二進(jìn)制多項(xiàng)式，則域的元素是次數(shù)最多為m-1的二進(jìn)制多項(xiàng)式。域元素的加法就是二進(jìn)制多項(xiàng)式的加法，域元素的乘法就是二進(jìn)制多項(xiàng)式相乘并取模f(z)。

算法采用下列符號(hào):C=(C［n］，C［n-1］，…，C［2］，C［1］，C［0］)是一個(gè)數(shù)組，則C{j}表示截短數(shù)組(C［n］，…，C［j+1］，C［j］)。

comb多項(xiàng)式模乘計(jì)算先進(jìn)行comb多項(xiàng)式乘法，然后將結(jié)果作為求模運(yùn)算的輸入來求模。

1.1 窗口寬度ω的comb多項(xiàng)式乘算法

comb算法是López和Dahab在文獻(xiàn)［2］中提出的。對(duì)所有次數(shù)低于ω的多項(xiàng)式u(z)，先計(jì)算出u(z)和域元素b(z)的乘積，并存儲(chǔ)乘積。若ω=4則要有15個(gè)存儲(chǔ)單元來存放預(yù)計(jì)算值。處理時(shí)查表一次計(jì)算出A［j］(t個(gè)ω字的一個(gè)數(shù)組)的ω位，其中a的位處理方向如圖1所示。圖1中的參數(shù)是m=163，W=32，ω=4。

圖1 窗口寬度ω的comb多項(xiàng)式乘法處理過程Fig.1 Process of polynomial multiplication about windows of width ω comb method

算法1 從左向右窗口寬度ω的comb多項(xiàng)式乘法

輸入:次數(shù)低于m的二進(jìn)制多項(xiàng)式a(z)、b(z)。

輸出:二進(jìn)制多項(xiàng)式乘積c(z)=a(z)·b(z)。

(1)計(jì)算Bu=u(z)·b(z)，對(duì)于所有次數(shù)低于ω的多項(xiàng)式u(z)。

(2)數(shù)組C清零。

(3)對(duì)于k從(W/ω)-1到0，重復(fù)執(zhí)行。

①對(duì)于j從0到t-1，重復(fù)執(zhí)行，

令u=(uω-1，…，u1，u0)，其中ui是A［j］的第(ωk+i)位，Bu+C{j}。

②若k≠0，則C←C·zω。

(4)返回(C)。

1.2 NIST快速約減算法

NIST約減多項(xiàng)式是NIST在文獻(xiàn)［3］中推薦的快速模約減方法，字W=32，c(z)的次數(shù)最多為2m-2。

采用一次處理一個(gè)字的方法，例如，設(shè)m=163，W=32(共有6個(gè)字)，考慮c(z)模f(z)=z163+z7+ z6+z3+1的字 C［9］的約減，將字 C［9］表示多項(xiàng)式:

考慮上述同余式右邊的四列，C［9］的約減可以通過把C［9］四次加到C上來實(shí)現(xiàn)(圖2)，而C［9］的最高位四次分別加到C的132、131、128和125位上。同理，計(jì)算233位和283位求模運(yùn)算［3］。

圖2 約減32位字C［9］模f(z)=z163+z7+z6+z3+1Fig.2 Reducing 32-bit word C［9］modulo f(z)=z163+z7+ z6+z3+1

算法2 模f(z)=z163+z7+z6+z3+1的快速約減

輸入:次數(shù)最高位324的二進(jìn)制多項(xiàng)式c(z)。

輸出:c(z)mod f(z)。

2 滑動(dòng)窗口的模乘算法

對(duì)于?a，b∈GF(2m)，a和b為次數(shù)低于m的不可約多項(xiàng)式，采用一次處理a的ω位的窗口方法［4-5］。算法需要進(jìn)行預(yù)計(jì)算并存儲(chǔ)其值，預(yù)計(jì)算的值有B21、B22、…、B2ω-1，共ω-1個(gè)值。寬度為ω的窗口從左向右進(jìn)行滑動(dòng)。ω=4時(shí)的滑動(dòng)窗口如圖3所示。

圖3 ω=4時(shí)的滑動(dòng)窗口Fig.3 Schematic diagram of sliding window for ω=4

圖3中當(dāng)前窗口中的數(shù)值為ai+1、ai、ai-1、ai-2，下一窗口的值為ai-3、ai-4、ai-5、ai-6。以此類推，直到最后的a3、a2、a1、a0。

NIST約減運(yùn)算，先左移ω=4位后得到約減的值，只需運(yùn)行算法2中的2～5步［6］。

由GF(2m)上的二進(jìn)制減法和加法相同，故式(2)中的“-”可以用“+”代替，整理得

經(jīng)上述分析提出算法3。

算法3 計(jì)算模乘的滑動(dòng)窗口方法

輸入:次數(shù)低于m的二進(jìn)制多項(xiàng)式a(z)、b(z)。

輸出:模乘結(jié)果c(z)=a(z)·b(z)mod f(z)。

(1)用文獻(xiàn)［3］中的快速約減算法的第2～5步計(jì)算B21、B22、…、B2ω-1。

(2)數(shù)組c清零。

(3)對(duì)于k從0到(W/ω)-1，重復(fù)執(zhí)行。

對(duì)于j從t-1到0，重復(fù)執(zhí)行

①用文獻(xiàn)［3］中的快速約減算法的第2～5步將c左移ω位，得到次數(shù)低于m的二進(jìn)制多項(xiàng)式。

②令u=(uω-1，…，u1，u0)，其中ui是A［k］的(4j+i)位，利用已知的 B21、B22、…、B2ω-1計(jì)算Bu。

③c=Bu+c。

(3)返回c。

3 結(jié)果與分析

把算法1和文獻(xiàn)［3］中的快速約減算法并用的求模乘的方法稱作方法1，把模乘的滑動(dòng)窗口方法稱作方法2。方法1和方法2都是移位和異或操作。用來衡量時(shí)間效率的因素就只有循環(huán)次數(shù)了。在方法1和方法2中若取ω=4，則方法1的循環(huán)次數(shù)為［(W/ω)+1］·t+算法2中的循環(huán)次數(shù)+1(算法2中的循環(huán)次數(shù)根據(jù)m的不同而不同)，方法2的循環(huán)次數(shù)為(W/ω)·t。從算法的循環(huán)次數(shù)看，方法2要比先乘后模的方法1少些。

從預(yù)計(jì)算的值來看，若ω=4，方法1中的預(yù)計(jì)算是15個(gè)，方法2預(yù)計(jì)算3個(gè)值。方法2比方法1的預(yù)計(jì)算要少12個(gè)，這樣更便于應(yīng)用在存儲(chǔ)受限的設(shè)備上。

對(duì)于方法1和方法2用C建模在Unix平臺(tái)下，用gcc結(jié)果與分析編譯得到的實(shí)驗(yàn)結(jié)果如表1所示。

從實(shí)驗(yàn)結(jié)果可以看到運(yùn)算效率平均提高了21.06%。

表1 ω=4時(shí)方法1和方法2算法運(yùn)行時(shí)間Table 1 Running time of method 1＆method 2 for ω=4

4 結(jié)束語

筆者對(duì)文獻(xiàn)［2］和文獻(xiàn)［3］提出的乘法和求模運(yùn)算進(jìn)行了分析，在此基礎(chǔ)上提出了一種基于滑動(dòng)窗口的模乘運(yùn)算。理論分析和實(shí)驗(yàn)證明，該算法只需要ω-1個(gè)預(yù)計(jì)算，計(jì)算效率比文獻(xiàn)［2］和文獻(xiàn)［3］結(jié)合使用方法的要高21%左右，在存儲(chǔ)單元數(shù)量和計(jì)算時(shí)間上都有很大的改進(jìn)。

［1］NEAL KOBLITZ.Elliptic curve cryptosystems［J］.Mathematics of Computation，1987，48:203-209.

［2］JULIO LOPEZ，RICARDO DAHAB，RICARDO DAHAB.Highspeed software multiplication in［C］.Progress in Cryptology—INDOCRYPT2000，2000:203-212.

［3］National Institute of Standards and Technology.Digital Signature Standard［S］.Washington:Federal Information Processing Standards Publication，2000:186-198.

［4］DARREL HANKERSON，ALFRED MENEZES，SCOTT VANSTONE.Guide to Elliptic Curve Cryptography［M］.New York: Springer-verlag，2004.

［5］李 忠，王 毅，彭代淵.基于滑動(dòng)窗口技術(shù)的有限域GF (2n)乘法算法［J］.通信學(xué)報(bào)，2008，29(7):123-129.

［6］HAN YONGXIANG，BAI GUOQIANG CHEN HONGYI.Efficient VLSI Design and Implementation of an ECC Coprocessor over Binary Field［C］//何大可，黃月江.密碼學(xué)進(jìn)展:中國密碼學(xué)會(huì)2007年會(huì)論文集.成都:西南交通大學(xué)出版社，2007:278-287.

Fast modular multiplication of sliding window based on binary domain

JIANG Hongbo
(College of Electric＆Information Engineering，Heilongjiang Institute of Science＆Technology，Harbin 150027，China)

Speeding up the modular multiplication holds the key to improving the performances of ECC algorithms in GF(2m).This paper presents an analysis of the comb polynomial multiplication(windows of width ω)and NIST reduction polynomials and features a faster modular multiplication algorithm of sliding window by combining the two operations.The algorithm can reduce the computing time by overcoming the shortcomings of modular-after-multiplication in time and storage space.The analysis of mathematic modeling and simulating shows that the new algorithms features computation efficiency about 21 percent greater than former modular-after-multiplication and NIST reduction polynomials and only ω-1 values are needed in pre-computation.

sliding window;binary field;fast modular multiplication

TN918.4

A

1671-0118(2011)05-0414-04

2011-06-16

蔣洪波(1978-)，女，黑龍江省雞西人，講師，碩士，研究方向:SoC、橢圓曲線加密，E-mail:88574099@163.com。

(編輯李德根)