【作者】 董丽华；

【导师】 胡予濮；

【作者基本信息】 西安电子科技大学 ， 密码学， 2006， 博士

【摘要】 本文主要研究了广义自缩（GSS）序列的伪随机性--线性复杂度的稳定性、线性组合向量的选取、GSS序列生成器的安全性，设计出求周期为2ⁿ与pⁿ序列的k错2-adic复杂度算法以及周期为pⁿ序列的k错N-adic复杂度算法，得到如下主要结果： 1、给出了GSS序列族中周期为N=2^n-1的这类GSS序列的线性复杂度的下界；分析了该类序列的线性复杂度的稳定性。 2、设计出一个选取GSS序列生成器的线性组合向量G的简单算法，得到了大量能够最大化GSS序列最小周期的线性组合向量G。 3、对GSS序列生成器在三种情形下的安全性进行了分析，即：仅LFSR的初始状态未知、线性组合向量和LFSR的初始状态皆未知，以及LFSR的联结多项式与初始状态皆未知。 4、具体分析了第五类和第六类GSS序列生成器的安全性。 5、针对GSS序列的周期为2ⁿ（n为正整数）这样一个事实，集中对周期为2ⁿ（n为正整数）序列的2-adic复杂度与k错2-adic复杂度进行了研究。得到以下结果：首先证明了具有最大2-adic复杂度N以及k错2-adic复杂度接近N的N周期序列的存在性，同时给出了具有此种性质的周期序列数目的下界；其次给出了两个求k错2-adic复杂度的算法以及一个求k错N-adic复杂度的算法，使用这三个算法可以分别求得周期为pⁿ与2ⁿ的二元序列的k错2-adic复杂度的上界以及周期为pⁿ的二元序列的k错N-adic复杂度的上界。更多还原

【Abstract】 This dissertation focuses on the pseudo-random properties of the Generalized Self-Shrinking (GSS) sequences-the stability of the linear complexity, the selection of the linear combining vectors, the security of the GSS sequence generators, designs the algorithms for computing the k-error 2-adic complexity of the 2~n and p~n periodic binary sequences and the algorithm for determining the k-error N-adic complexity of the p~n periodic binary sequences. The author obtains main results as follows:1. A lower bound of the linear complexity of the GSS sequences is presented, and the stability of the GSS sequences is discussed.2. A simple algorithm is proposed for selecting the linear combing vectors G of the GSS sequence generators. The number of the vectors G obtained is large and all of the vectors G can maximize the least period of the GSS sequences.3. The security of the GSS sequence generators is investigated under three cases in which the initial state of the LFSR is unknown, both the initial state of the LFSR and linear combing vector are unknown, and both the initial state and feedback polynomial of the LFSR are unknown.4. The security of the fifth class and the sixth class of the GSS sequence generators is discussed concretely.5. Note the period of the GSS sequences is 2~n, where n is a positive integer. The 2-adic complexity and the k-error 2-adic complexity are mainly investigated for the 2"-periodic sequences. Firstly, the existence of N-periodic sequences, which simultaneously achieve the maximum value of the 2-adic complexity and the k-error 2-adic complexity is established, and the number of the N-periodic sequences of such properties is given. Then two algorithms for computing the k-error 2-adic complexity and an algorithm for computing the k-error N-adic complexity are proposed, by which we can determine the upper bound of the k-error 2-adic complexity of the p~n and 2~n periodic sequence and the upper bound of the k-error N-adic complexity of the p~n periodic sequence respectively.更多还原