線性變換移位寄存器序列

王明生，唐再良

?

線性變換移位寄存器序列

王明生1,2，唐再良1

（1. 綿陽師范學院信息安全研究所，四川綿陽 621006；2. 中國科學院信息工程研究所信息安全國家重點實驗室，北京 100089）

線性變換移位寄存器由Tsaban和Vishne提出，是一個面向字的移位寄存器，每次輸出一個字節。研究了由TSR所生成的序列的基本性質，并且給出了一個新的準則來判定一個線性變換移位寄存器系統的特征多項式是否不可約。利用這個準則，不需要在擴域上做運算來判定一個線性變換移位寄存器系統的特征多項式是否不可約。

密碼學；不可約特征多項式；線性反饋移位寄存器；線性變換移位寄存器

1 引言

有限域中的序列被廣泛應用于密碼學和數字通信。這樣的序列常通過線性反饋移位寄存器（LFSR, linear feedback shifted register）生成[1~3]。

在工程實踐中，一個LFSR一次輸出一個比特使其運算速度緩慢。在1994年的快速軟件加密會議上，Preneel提出了一個問題，這個問題要求設計面向字的LFSR[4]。在文獻[5]中，Tsaban和Vishne提出一個面向字可以產生最大周期序列的LFSR的集合族，這個集合族被稱為線性變換移位寄存器（TSR, linear transformation shift registers）。本文給出了一個新的充分必要條件，來判定TSR的特征多項式是否不可約，這個條件避免在擴域上做運算。

文獻[5]中關于TSR的一些基本結果如下。

尋找不可約特征多項式是尋找本原中最難的部分[6,7]。

由于缺少適當的參考文獻，為了方便進一步研究，在第2節和第3節證明了TSR序列的一些基本結果，這些結果的推導過程和經典的LFSR序列類似。第4節給出了一個判斷TSR系統的多項式是否不可約的新準則，這個準則避免了在擴域上做運算。

2 TSR序列的性質

首先，本文符號定義如下。

令

證明 注意等式

令

由推論2的證明過程可以得到推論3。

3 TSR序列的周期

在這一節中，通過前面的結果來研究TSR的周期。

首先，給出2個簡單的引理。

由上面的討論，可以得到本文的主要結果。

4 f(x)不可約的一個新準則

定義3[5]如果滿足2個條件：1)和互素；2)首一的不可約多項式，則稱()是一個候選。

證明

由于

因此

由定理2可得推論5。

5 結束語

傳統的線性移位寄存器是流密碼算法中的主要部件之一，它每次產生一個新的比特。現代的硬件處理器以字節為單位，因此，有必要研究以字節為單元來移動的新型移位寄存器，線性變換移位寄存器就是這樣的一個模型。為了達到極大周期，需要它的特征多項式是本原多項式。其中，驗證是否不可約是最花費計算量的部分，本文給出了一種驗證不可約的新方式。是否還有其他更為簡單且同時能達到最大周期的移位寄存器模型是值得思考和研究的問題。另外，在公開的文獻中，還沒有基于TSR設計的流密碼算法，如何以此為基礎部件，設計新型的流密碼算法也是值得進一步研究的問題。

[1] BERLEKAMP E R. Algebraic coding theory—revised edition[M]. World Scientific Publishing Company, 2015.

[2] GOLOMB S W. Shift register sequences[M]. Laguna Hills: Aegean Park Press, 1981.

[3] LIDL R, NIEDERREITER H. Finite fields[M]. Cambridge: Cambridge University Press, 1983.

[4] PRENEEL B. Fast software encryption[M]. Lecture Notes in Computer Science, Berlin: Springer, 1995: 1-5.

[5] TSABAN B, VISHE U. Efficient linear feedback shift registers with maximal period[J]. Finite Fields Applications, 2002, 8(2): 256-267.

[6] DEWAR M, PANARIO D. Linear transformation shift registers[J]. IEEE Transactions on Information Theory, 2003, 49(8):2047-2052.

[7] DEWAR M, PANARIO D. Mutual irreducibility of certain polynomials[C]//The 7th International Conference on Finite Fields and Applications. c2003:59-68.

Linear transformation shift register sequences

WANG Ming-sheng1,2, TANG Zai-liang1

(1. Institute of Information Security, Mianyang Normal University, Mianyang 621006, China;2. The State Key Lab of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100089, China)

Linear transformation shift registers (TSR) were introduced by Tsaban and Vishne, which was a word-oriented shift register output a word per step. Some basic properties of sequences generated by the TSR were presented, and a new criterion for deciding if the characteristic polynomial of a TSR system is irreducible was given. This criterion avoids operations in extension fields.

cryptography, irreducible characteristic polynomials, linear feedback shift register, linear transformation shift register

The National Basic Research Program of China (973 Program) (No.2013CB834203), The National Natural Science Foundation of China (No.61379142)

TP309.7

A

10.11959/j.issn.2096-109x.2016.00051

2016-04-03；

2016-05-04。

王明生，wangmingsheng@iie.ac.cn

國家重點基礎研究發展計劃（“973”計劃）基金資助項目（No.2013CB834203）；國家自然科學基金資助項目（No.61379142）

王明生（1967-），男，四川射洪人，博士，中國科學院信息工程研究所研究員、博士生導師，主要研究方向為密碼學、隱私保護、信息安全的數學。

唐再良（1958-），男，四川安岳人，綿陽師范學院教授，主要研究方向為符號計算與應用、信息安全。