楊鄧奇，陸正福，左國超

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

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

楊鄧奇1，陸正福2，左國超1

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

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

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

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

1 問題的提出與符號約定

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

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

設(shè)r（x）=xdα+xdα-1+…+xd2+xd（1以非零冪次下降序列表示），M（x）=xn+（rx）。給定字寬w，對于任意的多項式其中deg（a（x））表示a（x）的最高冪次。若δ＝deg（a（x））mod w，L=?deg（a（x））/w」，則多項式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è)計中的一般規(guī)律，先給出一個M（x）＝x163+x7+x6+x3+1，w=8時的算法作為研究樣例。

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

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

2 字歸約算子

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

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

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

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

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

5）在di-δ＜-w時，用替代N，用替代di-δ，可以得到類似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)該取為被歸約項，

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

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

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

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

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

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

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

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

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

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

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

5 實驗結(jié)果

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

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

6 結(jié)束語

模規(guī)約運(yùn)算是代數(shù)算法中有限結(jié)構(gòu)上計算代數(shù)的基礎(chǔ)問題之一，在實際的編碼密碼應(yīng)用中經(jīng)常涉及到的是GF（2m）上的模歸約計算，且可歸為GF（2）上的多項式模歸約。本文運(yùn)用數(shù)學(xué)方法得到了模規(guī)約算法的自動生成算法，并選擇了鏈表數(shù)據(jù)結(jié)構(gòu)對其進(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è)計與實現(xiàn)〔J〕.小型微型計算機(jī)系統(tǒng)，2012，33（3）：577-581.

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

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

〔6〕楊鄧奇，楊健，杜英國，等.ECC點(diǎn)乘運(yùn)算在網(wǎng)絡(luò)并行實現(xiàn)中的裝箱問題〔J〕.大理學(xué)院學(xué)報，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é)報：自然科學(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é)基金資助項目（2010ZC142）

2012-09-07

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

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

10.3969/j.issn.1672-2345.2013.04.005