模歸約算法表達式自動生成算法設計與實現

楊鄧奇，陸正福，左國超

（1.大理學院數學與計算機學院，云南大理 671003；2.云南大學數學系，昆明 650091）

模歸約算法表達式自動生成算法設計與實現

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

（1.大理學院數學與計算機學院，云南大理 671003；2.云南大學數學系，昆明 650091）

多項式模歸約算法是計算機代數中的基本問題之一，在編碼算法和密碼體制設計中有著廣泛應用。基于對模歸約數學基礎的分析，設計了模歸約算法表達式自動生成算法，只要選擇實現所需的字寬w和模多項式M（x）的系數，即可自動生成對應的模規約算法表達式，為模規約算法在密碼編碼學中的應用提供了基礎。

模歸約算法；計算代數；算法表達式自動生成

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

1 問題的提出與符號約定

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

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

設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。

為了研究算法設計中的一般規律，先給出一個M（x）＝x163+x7+x6+x3+1，w=8時的算法作為研究樣例。

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

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

2 字歸約算子

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

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

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

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

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

5）在di-δ＜-w時，用替代N，用替代di-δ，可以得到類似4）的結論。

3 半字歸約算子

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

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

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

4 模規約算法表達式自動生成算法設計

對于上述的描述，設計模規約算法表達式自動生成算法如下。

4.1數據結構描述算法采用的數據結構描述如下。

圖1給出算法1的數據結構存儲示例，將其輸出即可得到對應的模規約算法表達式。

圖1 模規約算法表達式存儲結構圖

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

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

4.3 算法實現流程圖根據上述算法，得到其對應的流程。見圖2。

圖2 模規約算法表達式自動生成算法流程圖

5 實驗結果

采用C語言對算法進行實現，程序運行結果如圖3。其中字寬w=32，模多項式M（x）=x163+x7+x6+x3+1。改變字寬w或模多項式M（x），可以得到對應的算法表達式。

圖3 程序執行結果實例

6 結束語

模規約運算是代數算法中有限結構上計算代數的基礎問題之一，在實際的編碼密碼應用中經常涉及到的是GF（2m）上的模歸約計算，且可歸為GF（2）上的多項式模歸約。本文運用數學方法得到了模規約算法的自動生成算法，并選擇了鏈表數據結構對其進行了程序實現，為模規約算法在編碼密碼學方面的應用提供基礎。

〔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〕程桂花，羅永龍，齊學梅，等.AES算法中基于流水線的可逆S盒設計與實現〔J〕.小型微型計算機系統，2012，33（3）：577-581.

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

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

〔6〕楊鄧奇，楊健，杜英國，等.ECC點乘運算在網絡并行實現中的裝箱問題〔J〕.大理學院學報，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〕陸正福，何英，楊鄧奇，等.模歸約算法的數學基礎研究〔J〕.云南大學學報：自然科學版，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

云南省自然科學基金資助項目（2010ZC142）

2012-09-07

楊鄧奇，講師，博士，主要從事網絡安全、密碼學和網絡體系結構研究.

（責任編輯 袁 霞）

10.3969/j.issn.1672-2345.2013.04.005