【作者】 徐洪；

【导师】 戚文峰；

【作者基本信息】 解放军信息工程大学 ， 密码学， 2007， 博士

【摘要】 带进位反馈移位寄存器(FCSR)是由美国学者Klapper和Goresky提出的一种新的密钥流发生器.产生的方式决定了FCSR序列天然蕴含了较高的复杂性,它不同于线性移位寄存器序列需要再用其它装置加以改造.由FCSR生成达到最大周期的序列称为l-序列,它有许多类似于m-序列的伪随机性质,如0、1分布均衡,游程分布好等.序列的2-adic复杂度衡量了能产生该序列的最短FCSR的规模.类似于BM算法,存在相应的有理逼近算法可以方便计算序列的2-adic复杂度.FCSR序列,如l-序列,由于2-adic复杂度不高,并不能直接用作密钥流序列,FCSR的线性过滤(F-FCSR)是目前最有效的基于FCSR的序列密码体制.本文继续深入研究了l-序列的其它伪随机性质,这些研究可以为基于FCSR的序列密码设计提供重要参考.设a是以q=pe为连接数,周期T=pe-1(p-1)的l-序列或其采样,再设其指数表示为an=(A·g(mod q))(mod 2),其中g为模q的原根,gcd(A,q)=1.本文第一部分利用剩余类环上的指数和估计研究了l-序列及其采样的自相关性质,结果表明l-序列及其采样具有较好的自相关特性.具体结果如下：1.证明了当位移τ取遍[0,T-1]时,l-序列或其采样序列旦的自相关函数Ca(τ)的均值为0,方差Var,(Ca(τ)=O(q 1n4q).由Chebyshev不等式知,当连接数q适当大时,l-序列及其采样的绝大多数自相关值都是很理想的.2.当连接数为素数p时,证明了l-序列或其采样序列旦的自相关函数Ca(τ)满足：通过计算该三角和,容易给出Ca(τ)的估计值.特别,当位移τ满足gτ(mod p)|=2,(p-1)/2时,序列旦的自相关函数值Ca(τ=O(1n2 p),当p适当大时,该值也较小3.当连接数为素数方幂pe(e≥2)时,证明了对任意正整数i,1≤i≤e/2,当位移τ=kT(2pi)时,l-序列或其采样序列a的自相关函数值为其中1≤k≤2pi-1,gcd(k,p)=1.此结论说明,确实存在某些位移,使得l-序列及其采样的自相关值较大.本文第二部分利用环上本原权位序列的性质研究了l-序列采样的平移不等价性质.具体结果为：4.证明了当连接数为素数方幂时l-序列的采样不平移等价,从而说明在素数方幂情形下,Goresky和Klapper提出多年的猜想(猜想1.1)也是正确的.设丝是环Z/(pe)上由n次本原多项式f(x)生成的本原序列,则称序列：a=u(mod 2)为f(x)导出的n级广义l-序列,简称广义l-序列.它可以看成l-序列的自然推广本文第三部分利用环上本原权位序列的性质进一步研究了广义l-序列的平移不等价性质.设f(x), g(x)为环Z/(pe)上不同的n次本原多项式,得到的具体结果如下：5.当e=1时,在已有结论的基础上,证明了几乎对所有奇素数p,由f(x),g(x)导出的广义l-序列都不平移等价.6.当e≥2时,证明了若f(x)(?) g(x) (mod p),则由f(x), g(x)导出的广义l-序列都不平移等价；而当f(x)(?)g(x)(mod p)时,也几乎对所有本原多项式f(x), g(x),相应的广义l-序列都不平移等价.特别,广义l-序列的任意采样都不平移等价.更多还原

【Abstract】 Feedback with carry shift register (FCSR) is a new kind of keystream generators proposed by Klapper and Goresky. The architecture determines that FCSR sequences possess high linear complexity naturally, while for linear feedback shift register (LFSR) sequences, some modifications, such as nonlinear filtering and clock-controlling, must be done to obtain high linear complexity. The maximal period sequence generated by an FCSR is called an l-sequence. Such sequences have many fine pseudorandom properties similar to m-sequences, such as 0、1 balanceness, and fine run properties etc.The 2-adic complexity of a binary sequence characterizes the size of the shortest FCSR that generates the sequence. Similar to BM algorithm, there also exists a corresponding 2-adic rational approximation algorithm, which can efficiently compute the 2-adic complexity of binary sequences. The FCSR sequences, such as l-sequences, cannot be used directly as keystream sequences because of their comparatively low 2-adic complexity. Up to now, the linear filter of FCSR (F-FCSR) is the most efficient stream cipher based on FCSR. In this dissertation, we make a further study on some other pseudorandom properties of l-sequences, which can be a valuable reference for the design of the FCSR-based stream ciphers.Let a be an l-sequence or its decimation with period T= pe-1(p-1) generated by an FCSR with connection integer q=pe,and let an= (A·gn (mod q)) (mod 2) be its exponential representation, where g is a primitive root modulo q, and gcd(A, q)=1.In the first part of this dissertation, with the help of estimate of exponential sums over residue rings, we discuss the autocorrelation property of l-sequences and their decimations. Our results show that such sequences have fine autocorrelation properties. The main results are as follows:1. We show that when the shiftτruns through all integers between 1 and T-1, the expected autocorrelation value of the l-sequence or its decimation a is 0, and the variance is Var(Ca(τ))= O(q ln4q). From Chebyshev’s inequality we know that, when the connection integer q is a little larger, most autocorrelations of l-sequences and their decimations are low.2. When the connection integer is a prime number p, we show that the autocorrelation function Ca(τ) of the l-sequence or its decimation a satisfies Thus by calculating such triangular sum, we can easily obtain an estimate of Ca(τ). Especially, letτbe the shift such that |gτ(mod p)|= 2 or (p-1)/2, then the corresponding autocorrelation value of a is Ca(τ)= O(ln2p), which is also very low when p is a little larger.3. When the connection integer is a prime power pe (e≥2), we show that for any positive integer i,1≤i≤e/2, when the shift isτ= kT/(2pi), the corresponding autocorrelation value of the l-sequence or its decimation a is where 1≤k≤2pi-1, and gcd(k, p)= 1. This result shows that there do exist some shifts, such that the corresponding autocorrelation values of the l-sequence or its decimation are high.In the second part of this dissertation, using the fine properties of the level sequences of primitive sequences over residue rings, we analyze the distinctness of decimations of l-sequences, and obtain the following result:4. When the connection integer is a prime power, we show that the decimations of any l-sequences are cyclically distinct, which verifies the conjecture (Conjecture 1.1) proposed by Goresky and Klapper several years ago in the case of prime powers.Let u be a primitive sequences over ring Z/(pe), generated by a primitive polynomial f(x) of degree n. Then call the sequence a= u (mod 2) a generalized l-sequence of order n derived by f(x), or call it a generalized l-sequence for simplicity. Such sequences can be seen as a natural generalization of l-sequences.In the third part of this dissertation, using the fine properties of the level sequences of primitive sequences over residue rings, we further analyze the distinctness of generalized l-sequences. Let f(x), g(x) be two different primitive polynomials of degree n over Z/(pe). The main results are as follows:5. On the basis of some existing result, we show that when e=1, almost for all odd prime numberp, the generalized l-sequences derived by f(x), g(x) are cyclically distinct.6. When e≥2, we show that if f(x) (?) g(x)(mod p), then the generalized l-sequences derived by fix), g(x) are cyclically distinct. Furthermore, when f(x)(?) g(x) (mod p), almost for all such primitive polynomials, the corresponding generalized l-sequences are cyclically distinct. Particularly, the decimations of any generalized l-sequence are cyclically distinct.更多还原