线性变换移位寄存器序列
2016-10-13王明生唐再良
王明生,唐再良
线性变换移位寄存器序列
王明生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系统的多项式是否不可约的新准则,这个准则避免了在扩域上做运算。……
