王明生，唐再良

?

線性變換移位寄存器序列

王明生1,2，唐再良1

（1. 綿陽(yáng)師范學(xué)院信息安全研究所，四川綿陽(yáng) 621006；2. 中國(guó)科學(xué)院信息工程研究所信息安全國(guó)家重點(diǎn)實(shí)驗(yàn)室，北京 100089）

線性變換移位寄存器由Tsaban和Vishne提出，是一個(gè)面向字的移位寄存器，每次輸出一個(gè)字節(jié)。研究了由TSR所生成的序列的基本性質(zhì)，并且給出了一個(gè)新的準(zhǔn)則來(lái)判定一個(gè)線性變換移位寄存器系統(tǒng)的特征多項(xiàng)式是否不可約。利用這個(gè)準(zhǔn)則，不需要在擴(kuò)域上做運(yùn)算來(lái)判定一個(gè)線性變換移位寄存器系統(tǒng)的特征多項(xiàng)式是否不可約。

密碼學(xué)；不可約特征多項(xiàng)式；線性反饋移位寄存器；線性變換移位寄存器

1 引言

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

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

文獻(xiàn)[5]中關(guān)于TSR的一些基本結(jié)果如下。

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

由于缺少適當(dāng)?shù)膮⒖嘉墨I(xiàn)，為了方便進(jìn)一步研究，在第2節(jié)和第3節(jié)證明了TSR序列的一些基本結(jié)果，這些結(jié)果的推導(dǎo)過(guò)程和經(jīng)典的LFSR序列類似。第4節(jié)給出了一個(gè)判斷TSR系統(tǒng)的多項(xiàng)式是否不可約的新準(zhǔn)則，這個(gè)準(zhǔn)則避免了在擴(kuò)域上做運(yùn)算。

2 TSR序列的性質(zhì)

首先，本文符號(hào)定義如下。

令

證明 注意等式

令

由推論2的證明過(guò)程可以得到推論3。

3 TSR序列的周期

在這一節(jié)中，通過(guò)前面的結(jié)果來(lái)研究TSR的周期。

首先，給出2個(gè)簡(jiǎn)單的引理。

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

4 f(x)不可約的一個(gè)新準(zhǔn)則

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

證明

由于

因此

由定理2可得推論5。

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

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

[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

國(guó)家重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃（“973”計(jì)劃）基金資助項(xiàng)目（No.2013CB834203）；國(guó)家自然科學(xué)基金資助項(xiàng)目（No.61379142）

王明生（1967-），男，四川射洪人，博士，中國(guó)科學(xué)院信息工程研究所研究員、博士生導(dǎo)師，主要研究方向?yàn)槊艽a學(xué)、隱私保護(hù)、信息安全的數(shù)學(xué)。

唐再良（1958-），男，四川安岳人，綿陽(yáng)師范學(xué)院教授，主要研究方向?yàn)榉?hào)計(jì)算與應(yīng)用、信息安全。