模歸約算法表達(dá)式自動(dòng)生成算法設(shè)計(jì)與實(shí)現(xiàn)

楊鄧奇，陸正福，左國(guó)超

（1.大理學(xué)院數(shù)學(xué)與計(jì)算機(jī)學(xué)院，云南大理 671003；2.云南大學(xué)數(shù)學(xué)系，昆明 650091）

模歸約算法表達(dá)式自動(dòng)生成算法設(shè)計(jì)與實(shí)現(xiàn)

楊鄧奇1，陸正福2，左國(guó)超1

（1.大理學(xué)院數(shù)學(xué)與計(jì)算機(jī)學(xué)院，云南大理 671003；2.云南大學(xué)數(shù)學(xué)系，昆明 650091）

多項(xiàng)式模歸約算法是計(jì)算機(jī)代數(shù)中的基本問(wèn)題之一，在編碼算法和密碼體制設(shè)計(jì)中有著廣泛應(yīng)用。基于對(duì)模歸約數(shù)學(xué)基礎(chǔ)的分析，設(shè)計(jì)了模歸約算法表達(dá)式自動(dòng)生成算法，只要選擇實(shí)現(xiàn)所需的字寬w和模多項(xiàng)式M（x）的系數(shù)，即可自動(dòng)生成對(duì)應(yīng)的模規(guī)約算法表達(dá)式，為模規(guī)約算法在密碼編碼學(xué)中的應(yīng)用提供了基礎(chǔ)。

模歸約算法；計(jì)算代數(shù)；算法表達(dá)式自動(dòng)生成

代數(shù)算法的設(shè)計(jì)、分析、實(shí)現(xiàn)和應(yīng)用構(gòu)成了計(jì)算代數(shù)的主要研究?jī)?nèi)容，其特征是無(wú)誤差的符號(hào)計(jì)算。有限結(jié)構(gòu)上的代數(shù)算法是計(jì)算代數(shù)的基礎(chǔ)問(wèn)題之一〔1-2〕，普遍涉及模歸約計(jì)算：求一個(gè)多項(xiàng)式（大整數(shù)、代數(shù)結(jié)構(gòu)）關(guān)于另一個(gè)多項(xiàng)式（整數(shù)、代數(shù)結(jié)構(gòu)）的余式（余數(shù)、商結(jié)構(gòu)）等。在實(shí)際應(yīng)用中，循環(huán)碼、對(duì)稱密碼算法AES〔3-4〕、橢圓曲線密碼體制（ECC）〔5-6〕、無(wú)證書(shū)密碼系統(tǒng)（CL-PKC）〔7〕等在軟件實(shí)現(xiàn)中經(jīng)常涉及的則是GF（2m）上的模歸約計(jì)算，可歸為GF（2）上的多項(xiàng)式模歸約。從軟件實(shí)現(xiàn)的角度看，機(jī)器指令不直接支持抽象代數(shù)運(yùn)算，但GF（2m）上的計(jì)算可通過(guò)機(jī)器支持的位運(yùn)算及適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)和算法來(lái)實(shí)現(xiàn)。鑒于上述，本文研究了GF（2m）上的模歸約運(yùn)算的計(jì)算代數(shù)基礎(chǔ)，并據(jù)此設(shè)計(jì)了模規(guī)約算法表達(dá)式自動(dòng)生成的算法。同時(shí)，給出算法實(shí)現(xiàn)的關(guān)鍵數(shù)據(jù)結(jié)構(gòu)，并用C語(yǔ)言實(shí)現(xiàn)了模歸約算法表達(dá)式的自動(dòng)生成，對(duì)GF（2m）上的密碼、編碼計(jì)算具有基礎(chǔ)意義。

1 問(wèn)題的提出與符號(hào)約定

模歸約算法是指：對(duì)于給定的模多項(xiàng)式M（x）和任意的多項(xiàng)式a（x），要求給出算法，求a（x）除以M（x）所得的余式a（x）mod M（x）。

模規(guī)約算法是各類(lèi)密碼系統(tǒng)實(shí)現(xiàn)的基礎(chǔ)，出于效率和安全的考慮，不同的密碼系統(tǒng)對(duì)實(shí)現(xiàn)字寬w和模多項(xiàng)式M（x）有著不同的要求。分析表明，模規(guī)約算法表達(dá)式隨著w和M（x）的變換而呈現(xiàn)不同形式，當(dāng)重新選擇實(shí)現(xiàn)字寬w或模多項(xiàng)式M（x）時(shí)，需要重新推導(dǎo)模規(guī)約算法表達(dá)式，這是一項(xiàng)非常繁瑣的工作。那么，如果選定了模多項(xiàng)式M（x）和字寬w，是否能夠自動(dòng)生成模規(guī)約算法表達(dá)式以便直接應(yīng)用，省去繁瑣的重復(fù)推導(dǎo)過(guò)程？本文通過(guò)對(duì)模規(guī)約算法數(shù)學(xué)基礎(chǔ)的深入分析，探索其一般規(guī)律，提出模規(guī)約算法表達(dá)式自動(dòng)生成算法，對(duì)其用C語(yǔ)言進(jìn)行實(shí)現(xiàn)，給出實(shí)驗(yàn)結(jié)果。

設(shè)r（x）=xdα+xdα-1+…+xd2+xd（1以非零冪次下降序列表示），M（x）=xn+（rx）。給定字寬w，對(duì)于任意的多項(xiàng)式其中deg（a（x））表示a（x）的最高冪次。若δ＝deg（a（x））mod w，L=?deg（a（x））/w」，則多項(xiàng)式a（x）的分段表示（A［L］，A［L-1］，…，A［j］，…，A［1］，A［0］）稱為a（x）的字寬為w的字表示，其中A［j］為xj（wajw+ajw+1x1+…+ajw+w-1xw-1）=xjwt（x）的字表示 ajw+w-1…ajw+1ajw，t（x）＝ajw+ajw+1x1+…+ajw+w-1xw-1；若δ≠0，則A［L］的高w-δ位置0。

為了研究算法設(shè)計(jì)中的一般規(guī)律，先給出一個(gè)M（x）＝x163+x7+x6+x3+1，w=8時(shí)的算法作為研究樣例。

上述算法可參見(jiàn)ECC的各類(lèi)實(shí)現(xiàn)文獻(xiàn)。不難看出，困難的是迭代計(jì)算式的一般形成規(guī)律。在模歸約研究中，給定模多項(xiàng)式，希望研究A［j］對(duì)于A［i］（i

前期針對(duì)情形②和③提出了字歸約算子、半字歸約算子〔9〕。

2 字歸約算子

本節(jié)假定jw≥n。A［j］關(guān)于模多項(xiàng)式M（x）=xn+r（x）的按字歸約表達(dá)為一個(gè)算子，我們將其稱為字歸約算子，記為R（1，A［j］，M（x），w），定義如下：

其中的計(jì)算量涉及2次移位，2次位異或。

3）在di-δ＞w時(shí)，用N+?（di-δ）/w」替代N，用（di-δ）mod w替代di-δ，可以得到類(lèi)似2）的結(jié)論。

4）在-（w-1）＜di-δ＜0時(shí)，表示A［j］先右移N個(gè)字，再右移個(gè)位，因此該項(xiàng)影響A［j-N］和A［j-N-1］，并且有迭代公式：

其中的計(jì)算量涉及2次移位，2次位異或。

5）在di-δ＜-w時(shí)，用替代N，用替代di-δ，可以得到類(lèi)似4）的結(jié)論。

3 半字歸約算子

本節(jié)假定：jw＜n，jw+w-1≥n。由于n=Nw+δ，0＜δ≤w-1，所以j=N，A［N］的0，1，…，δ-1位不在歸約范圍內(nèi)，因此應(yīng)該取為被歸約項(xiàng)，

并且稱S關(guān)于模多項(xiàng)式M（x）=xn+r（x）的歸約為半字歸約，相應(yīng)的算子稱為半字歸約算子（注：此處的“半”并不意味著δ一定是w/2，故筆者將其英文譯為semi-，表達(dá)不完全之意），記為R（δ，S，M（x），w），定義如下：

（1）式與（2）式可以合并成一個(gè)右移δ位的操作。

4 模規(guī)約算法表達(dá)式自動(dòng)生成算法設(shè)計(jì)

對(duì)于上述的描述，設(shè)計(jì)模規(guī)約算法表達(dá)式自動(dòng)生成算法如下。

4.1數(shù)據(jù)結(jié)構(gòu)描述算法采用的數(shù)據(jù)結(jié)構(gòu)描述如下。

圖1給出算法1的數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)示例，將其輸出即可得到對(duì)應(yīng)的模規(guī)約算法表達(dá)式。

圖1 模規(guī)約算法表達(dá)式存儲(chǔ)結(jié)構(gòu)圖

4.2 算法描述算法的輸入為所選擇的字寬w和數(shù)組d，其中d［0］=α，d［1］=deg（M（x）），r（x）的指數(shù)從d［2］開(kāi)始存儲(chǔ)。算法的輸出返回鏈表數(shù)組的首地址。算法中insert（node1變量名）表示在p2-＞next中插入node1類(lèi)型的結(jié)點(diǎn)，insert（node2變量名）表示在p2-＞prior中插入node2類(lèi)型的結(jié)點(diǎn)，結(jié)點(diǎn)中字符串的賦值本算法中不再具體給出。

算法的思想是：先從首地址開(kāi)始查找，若找不到對(duì)應(yīng)的結(jié)點(diǎn)，則申請(qǐng)結(jié)點(diǎn)并插入到鏈表中（若找到相應(yīng)的node2），然后查找node1應(yīng)插入的位置并插入相應(yīng)的node1。

4.3 算法實(shí)現(xiàn)流程圖根據(jù)上述算法，得到其對(duì)應(yīng)的流程。見(jiàn)圖2。

圖2 模規(guī)約算法表達(dá)式自動(dòng)生成算法流程圖

5 實(shí)驗(yàn)結(jié)果

采用C語(yǔ)言對(duì)算法進(jìn)行實(shí)現(xiàn)，程序運(yùn)行結(jié)果如圖3。其中字寬w=32，模多項(xiàng)式M（x）=x163+x7+x6+x3+1。改變字寬w或模多項(xiàng)式M（x），可以得到對(duì)應(yīng)的算法表達(dá)式。

圖3 程序執(zhí)行結(jié)果實(shí)例

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

模規(guī)約運(yùn)算是代數(shù)算法中有限結(jié)構(gòu)上計(jì)算代數(shù)的基礎(chǔ)問(wèn)題之一，在實(shí)際的編碼密碼應(yīng)用中經(jīng)常涉及到的是GF（2m）上的模歸約計(jì)算，且可歸為GF（2）上的多項(xiàng)式模歸約。本文運(yùn)用數(shù)學(xué)方法得到了模規(guī)約算法的自動(dòng)生成算法，并選擇了鏈表數(shù)據(jù)結(jié)構(gòu)對(duì)其進(jìn)行了程序?qū)崿F(xiàn)，為模規(guī)約算法在編碼密碼學(xué)方面的應(yīng)用提供基礎(chǔ)。

〔1〕Joachim Von Zur Gathen，Jürgen Gerhard.Modern Computer Algebra〔M〕.London：Cambridge University Press，1999：1-40.

〔2〕Mishra B.Algorithmic Algebra〔M〕.Berlin：Springer-Verlag，2001：66-78.

〔3〕程桂花，羅永龍，齊學(xué)梅，等.AES算法中基于流水線的可逆S盒設(shè)計(jì)與實(shí)現(xiàn)〔J〕.小型微型計(jì)算機(jī)系統(tǒng)，2012，33（3）：577-581.

〔4〕王韜，趙新杰.針對(duì)AES的Cache計(jì)時(shí)模板攻擊研究〔J〕.計(jì)算機(jī)學(xué)報(bào)，2012，35（2）：235-341.

〔5〕任瑞芳，汪學(xué)明.基于ECC的廣義門(mén)限簽密方案設(shè)計(jì)〔J〕.計(jì)算機(jī)工程與設(shè)計(jì)，2011，32（1）：17-20.

〔6〕楊鄧奇，楊健，杜英國(guó)，等.ECC點(diǎn)乘運(yùn)算在網(wǎng)絡(luò)并行實(shí)現(xiàn)中的裝箱問(wèn)題〔J〕.大理學(xué)院學(xué)報(bào)，2009，8（4）：19-21.

〔7〕Al-Riyami S S，Paterson K G.Certificateless Public Key Cryptography〔M〕.Berlin：Springer-Verlag，2003：452-473.

〔8〕Darrel Hankerson，Julio López Hernandez，Alfred Menezes. Software Implementation of Elliptic Curve Cryptography over Binary Field〔M〕.K.Ko and C.aar（Eds.）：ChES，2000：1-24.

〔9〕陸正福，何英，楊鄧奇，等.模歸約算法的數(shù)學(xué)基礎(chǔ)研究〔J〕.云南大學(xué)學(xué)報(bào)：自然科學(xué)版，2005，27（4）：305-309.

The Design and Implement of Algorithm Expression Auto-generation for Modulo Reduction Operation

YANG Dengqi1，LU Zhengfu2,ZUO Guochao1
（1.College of Mathematics and Computer,Dali University,Dali,Yunnan 671003,China；2.Department of Mathematics,Yunnan University,Kunming 650091,China）

Polynomial modulo reduction operation is one of the fundamental issues of computer algebra,and widely used in coding algorithms and cryptographic system design.Based on the analysis on the mathematic foundation of modulo reduction operation,this paper designs the expression auto-generation algorithm of modulo reduction operation.This algorithm can auto-generate the algorithm expression of modulo reduction operation according to the selected word-width and modulo polynomial.This provides a foundation for the application of modulo reduction algorithm in the areas of cryptography and encode,such as ECC,AES and CL-PKC.

modulo reduction algorithms；computer algebra；algorithm expression auto-generation

O157；TP301.6

A

1672-2345（2013）04-0012-05

云南省自然科學(xué)基金資助項(xiàng)目（2010ZC142）

2012-09-07

楊鄧奇，講師，博士，主要從事網(wǎng)絡(luò)安全、密碼學(xué)和網(wǎng)絡(luò)體系結(jié)構(gòu)研究.

（責(zé)任編輯 袁 霞）

10.3969/j.issn.1672-2345.2013.04.005