线性变换移位寄存器序列

王明生，唐再良



线性变换移位寄存器序列

王明生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-），男，四川安岳人，绵阳师范学院教授，主要研究方向为符号计算与应用、信息安全。