【作者】 朱凤翔；

【导师】 戚文峰；

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

【摘要】 伪随机序列在密码学、通信和计算机等领域有着十分重要的作用.如何评价伪随机序列是序列密码中的重要问题.S.W.Golomb认为“好”的伪随机序列在周期长、易生成的基础上需满足：元素分布均衡、好的游程分布、理想的自相关特性.随着伪随机序列研究的不断深入,对于密码意义下“好”的伪随机序列提出了新的要求.1969年,Massey提出了Berlekamp-Massey综合算法后,线性复杂度便成为评价序列伪随机性的重要指标.然而,线性复杂度高的序列其安全强度未必高.例如序列(110010111001011100100)∞的线性复杂度和周期都达到最大值21,但这是一条极不安全的序列.若改变该序列每周期中的一个比特,则序列线性复杂度降为3.因此,人们提出了另一个衡量序列伪随机性的重要指标：k-错线性复杂度.本文主要研究了周期序列k-错线性复杂度分布,包括k-错线性复杂度值、给定k-错线性复杂度的序列计数、k-错线性复杂度均值以及线性复杂度下降点等问题.主要结果如下：1.对于2n-周期二元序列,当其线性复杂度为2n-1时,计算了该序列2-错(或3-错)线性复杂度的所有可能值以及具有给定2-错(或3-错)线性复杂度序列的条数,由此计算了该序列2-错(或3-错)线性复杂度的均值,即给出了序列2-错(或3-错)线性复杂度的分布情况.2.讨论了任一2n-周期二元序列2-错线性复杂度的分布,具体计算了该序列2-错线性复杂度的所有可能值以及具有给定2-错线性复杂度序列的条数,进一步给出了2n-周期二元序列2-错线性复杂度的均值.3.简单讨论了2n-周期二元平衡序列的2-错线性复杂度的分布.4.给出了Fp上pn-周期序列所有可能的1-错线性复杂度值以及具有给定1-错线性复杂度的序列条数.从而得到了Fp上pn-周期序列1-错线性复杂度均值,更进一步,计算了Fp上pn-周期随机序列k-错线性复杂度均值的界.5.给出了周期为2pn二元序列线性复杂度的第一下降点的上界,并指出了周期为2p的二元序列在大多数情况下达了到该上界.6.给出了Fq上周期为2pn序列线性复杂度第一下降点的上界.7.对分圆多项式Φpq(x)及其因子进行了分析,并给出了周期为pqn二元序列线性复杂度的第一下降点的上界.更多还原

【Abstract】 Pseudorandom sequences are widely used in cryptography, communication and computation, etc. It is an important issue that how to evaluate the pseudorandom sequences.S.W.Golomb considered the good pseudorandom sequences should satisfy:the balanceable distribution of elements、fine runs properties and the ideal auto correlation besides long period and easy generation. With the study of stream cipher, more and more new results appeared and the new requirements about good pseudorandom sequences in cryptography were put forward. The linear complexity became an important standard to estimate the pseudorandom properties after Massey provided the Berlekamp-Massey synthesis algorithm in 1969. However, the sequence having a large linear complexity may not be secure enough. For example, the period and the linear complexity of the sequence (110010111001011100100)∞both reach the maximal value 21, however, it is a quite insecure sequence because altering the last bit of each period will reduce the linear complexity of the sequence to be 3. Therefore, another important standard to scale the pseudorandom properties of the sequences is proposed:k-error linear complexity.In this dissertation, the distribution property of the terror linear complexity is discussed which include the value of k-error linear complexity, the number of the sequences with the given k-error linear complexity, the expected of the k-error linear complexity and the decreasing point of the linear complexity etc. The main results are as follows:1. For the 2n-periodic binary sequence with linear complexity 2n-1, the possible values for the 2-error(or 3-error) linear complexity and the number of sequences with certain 2-error(or 3-error) linear complexity, moreover, the expected of the 2-error(or 3-error) linear complexity is calculated, that is, the distribution of the 2-error(or 3-error) linear complexity are provided.2. For a random 2n-periodic binary sequence, the distribution of the 2-error linear complexity is discussed. That is to say, the possible values for the 2-error linear complexity and the number of sequences with certain 2-error linear complexity are established. Moreover, the expected of the 2-error linear complexity for a random 2n-periodic binary sequence is also given.3. For a random 2n-periodic balanced binary sequence, the distribution of the 2-error linear complexity is discussed simply.4. For a pn-periodic sequence over Fp, the possible values of the 1-error linear complexity and the number of sequences with certain 1-error linear complexity are established. Then the expected of the 1-error linear complexity for a random pn-periodic sequence over Fp is also given. Moreover, the bounds for the expect value of k-error linear complexity are provided.5. The upper bound for the first decreasing point of the linear complexity is given for a binary sequence with period 2p". Furthermore, it is showed that the upper bound can be reached for a binary sequence with period 2p in most condition. 6. The upper bound for the first decreasing point of the linear complexity is given for a sequence with period 2p" over Fq.7. The cyclotomic polynomialΦpq(x) and its factorization are analyzed and the upper bound for the first decreasing point of the linear complexity is given for a binary sequence with period pqn.更多还原