关杰;周琮伟
【摘 要】M序列反馈函数的构造一直是序列密码理论的研究热点.基于由m序列构造M序列反馈函数的结构特性,结合函数变换和函数派生的方式得到一类M序列反馈函数的快速构造方法,并给出了该类M序列反馈函数的多项式表示、计数以及重量性质.%The construction of M-sequence feedback functions has always been a hotspot in the theory of stream cipher. Based on the structural properties of the M-sequence feedback function constructed by the m-sequence, the method of fast construction of a class M-sequence feedback functions was proposed by combining the function transformation and func-tion derivative. Meanwhile, polynomial representation, amount and weight property of the class M-sequence feedback functions were considered.
【期刊名称】《通信学报》
【年(卷),期】2018(039)004
【总页数】7页(P84-90)
【关键词】川端康成M序列反馈函数;多项式表示;函数变换;函数派生
【作 者】关杰;周琮伟
【作者单位】解放军信息工程大学三院,河南 郑州 450001;解放军信息工程大学三院,河南 郑州 450001
【正文语种】中 文
【中图分类】TN918.2
1 引言
胡幼桃一个n级移位寄存器至多产生周期为2n的序列，通常称达到最大周期2n的序列为M序列，又叫De Bruijn序列。关于LFSR的圈结构已经可以完全刻画，并且知道最大周期的2n-1的序列由其特征多项式为二元域上的本原多项式产生，此时，称周期为2n-1的序列为m序列。相较于m序列，M序列有着更好的线性复杂度和自相关性质，一直以来其构造问题是
序列密码理论的研究热点。由于NFSR的圈结构没有较好的刻画手段，故其构造的经典方法一直以来局限于图论的反树和因子关联图法[1]，小项表示的圈剪接筛法[2]和由一个M序列通过对称[3]、派生[4]和递归[5]等得到一类M序列。近期，国外学者关于M序列的构造主要有“改进版”的Martin算法[6]以及关于D-同态递归构造的最新研究成果[7]。而国内学者关于M序列构造的新思路和研究主要有“编织法”[8]，利用复合函数所代表的寄存器因子关联图的研究构造M序列[9～13]以及针对大级数的并圈构造[14]。以上这些构造方法大致可以分为两类，即同级直接生成的“并圈法”以及小级数递归生成大级数的“递归法”。但是“并圈法”生成的M序列往往需要大量的统计、判断和检验，并且得到的M序列往往是以小项表示；而“递归法”往往得到的M序列个数较少且M序列往往与小级数的初始序列具有较大相关性。
因此，针对以上M序列在实际构造中存在的问题，本文提出了一类可以实际应用，且以多项式表示的M序列反馈函数的快速构造方法。
2 预备知识
解剖以下是本文用到的定义和符号说明。
冯天瑜Gf：以f为反馈函数的n级移位寄存器的状态图。
对偶变换D：设为f产生的GF(2)上任意一条周期为T的序列，令“+”为GF(2)上的加法运算，则aT+1,…)。
对称变换R：
组合变换RD：a1+1,… )。
Ai：f0(x2,…,xn)中所有i(0 ≤i≤n-1)次项的集合为Ai，特别地，零次项为 1以及最高次项为x2…xn。
常见的反馈函数有2种表示方法，即小项表示和多项式表示。在实际应用中，更实用的是用多项式表示的反馈函数，因为利用多项式表示的反馈函数其构造M序列无论从软件和硬件实现的角度都更为方便快捷。文献[15]给出了圈结构不含枝即非奇异的n级反馈函数，其用多项式表示3种函数变换的对应表达式。
定理 1[15]设非奇异n级反馈函数的多项式表示为f=x1+f0(x2,… ,xn)，若分别用Df、Rf和RDf表示以D(Gf)、R(Gf)和RD(Gf)为状态图的n级移位寄存器反馈反馈函数，则
1946年，De Bruijn从图论的角度证明了产生M序列的非线性移位寄存器的个数等于而非奇异移位寄存器的个数恰好等于但是至今人们都无法证明M序列的非线性移位寄存器以2n的长度划分了整个非奇异移位寄存器，即猜想若将整个非奇异移位寄存器对应的反馈函数看作一个，而M序列的反馈函数可以看作是个数为2n的陪集的代表元。20世纪80年代，高鸿勋[16]在以圈剪接筛法的基础上提出了一个非奇异反馈函数为M序列反馈函数的充要条件，但对于生成全部n(n≥ 5)级M序列来讲没有实际意义。
本文直接引用文献[15]中关于M序列反馈函数多项式表示的一个必要条件来说明随机寻到一个M序列反馈函数的数据复杂度。
引理 1[15]在M序列反馈函数f0的多项式表示中，有以下性质。
1) 最高次项x2…xn这一项一定出现。
2) 项数一定是奇数。
奥修书
3) 1这一项一定出现。
4) 一次项x2,…,xn不能全部出现。
由于考虑将1和x2…xn这2项排除，则剩余可能出现的项的个数即为 2n-1- 2 。在此基础上将2n-1- 2 种可能出现的项进行一个分类，即定义Ai(1 ≤i≤n-2)，则可能产生M序列反馈函数的个数为 2 2n-1-2。又因为项数一定是奇数，则可能产生M序列的反馈函数的个数可以降到 2 2n-1-3。如果从线性项x2,…,xn不能全部出现的角度考虑，则可能产生M序列反馈函数的个数为假设M序列的反馈函数服从均匀分布，则实际利用引理 1寻到一个M序列反馈函数的数据复杂度约为O(2n- 3)。
文献[15]给出了利用对偶变换D、对称变换R和组合变换RD构造M序列的结论。如引理2所示。
引理2[15]f是M序列的反馈函数，则Df、Rf和RDf也是M序列的反馈函数。当n≥ 3 时，f≠Df、f≠Rf；当n为偶数时，f、Df、Rf、RDf这4个函数两两互异。
由于在实际应用中并不需要生成全部的M序列反馈函数，更多的时候是需要生成具有某些构造特点的多项式表示的反馈函数。本文的工作即是利用由m序列构造M序列反馈函数的结构特性，经上述 3种函数变换得到一类M序列反馈函数多项式表示的快速构造方法，为了更好地说明对偶变换D、对称变换R以及组合变换RD在构造M序列反馈函数中的应用，
接下来，给出2个关于m序列的结论。
3 由函数变换证明的2个结论
本文由函数变换发现了m序列个数及其特征多项式的一些性质，并从另外一个角度证明了如下结论。
引理3 [17]当n≥ 3 ，总为偶数。
证明 当n≥ 3 时，由引理 2知，Rf形成的必然是一条新的m序列，则f≠Rf，因此，由Rf形成的特征多项式必然异于f的本原多项式，而二元域上的本原多项式的总数为因此，当必然为偶数，证毕。
定理2 当n为偶数且n≥ 3 时，不存在形式为的本原三项式。
证明 当n为偶数且n≥ 3 时，对于特征多项式
为的m序列，其反馈函数的形式为由定理1可知，Rf=f，但是由引理2可知，Rf形成的必然是一条新的m序列，因此，Rf、f两者的特征多项式不相等，这与Rf=f矛盾，则此时不存在
形式为的本原三项式，证毕。
4 函数变换及函数派生在构造M序列反馈函数中的应用
4.1 函数变换在构造M序列反馈函数中的应用
在实际构造M序列的过程中，人们很自然地考虑从m序列出发，即考虑在m序列长度为n-1的0游程中添加一个0得到M序列，这也符合对M序列的游程统计。这种情况构造的M序列反馈函数其实是在m序列的反馈函数表达式中添加一个小项当然将小项表示转化为多项式表示中，发现得到的M序列反馈函数满足引理1的性质，考虑该M序列反馈函数的对偶函数时，其对偶函数也应该为M序列的反馈函数，据此给出了一类M序列反馈函数f快速构造的多项式表示的形式，即形式1。
腐蚀速率
形式 1 在m序列的反馈函数q的基础上添加这2项，即
容易看出，具有形式1的多项式表示的反馈函数f满足引理1，从而可以推出m序列的项数为偶数项，否则与f中出现1这一项相矛盾。
同时考虑对称函数Rf和RDf，当n≥ 3 ，由f对称所形成的必然是新的一条M序列，所以势必由f可以得到一个新的满足M序列的反馈函数Rf，观察其结构可知，仍然是在m序列的反馈函数上添加 1,x2…xn这2项，其与引理3的结论是相对应的，同理可得RDf与Df具有相同结构。据此，可以快速构造个M序列反馈函数。
如果本文将x1, 1,x2…xn这3项单列，指出任意由形式1构造的M序列反馈函数的对偶函数Df具有定理3的形式。
定理3 任意由形式1构造的M序列反馈函数f的对偶函数Df具有以下形式。
1) 包含x1,1,x2…xn这3项。
2) 包含f在集合Ai(1 ≤i≤n-2)中所有未出现的项。
证明 由于f=q+1+x2…xn=x1+f0(x2,…,xn)，则由定理1知，Df包含项，其多项式展开式中包含f0(x2,…,xn)中所有i(1 ≤i≤n-2)次项的集合为Ai以及 1,x2…xn。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议