【作者】 高军涛；

【导师】 胡予濮；

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

【摘要】 本文首先应用错误攻击对两种流密码体制：广义自缩生成器和均衡互缩生成器的安全性进行了分析，为抵抗这种攻击，我们对广义自缩生成器进行了改进，给出了一种新型的广义自缩生成器，并对该生成器的各种伪随机性进行了分析，最后讨论了自相关函数和线性复杂度之间的一个关系，得到如下主要结果： ● 利用错误攻击对广义自缩生成器和均衡互缩生成器这两种流密码体制进行了密码分析，结果表明：对于由60级的线性反馈移位寄存器构成的广义自缩生成器，在反馈多项式已知的条件下，攻击者仅需要4个错误密钥流，结合平均约2⁸个密钥流比特就可以获得生成器的密钥种子；对于均衡互缩生成器，攻击者可以通过改变LFSR若干个时钟来得到错误的输出流，并利用这些输出流得到生成器的密钥种子。 ● 为抵抗错误攻击，设计了一类新型的广义自缩生成器。讨论了该新型序列的各种伪随机性质，包括最小周期，游程长度和序列族的性质，给出了使最小周期达到最大的方法。由我们的方法可以找到2^n-3个周期达到2^n-1的序列。同时证明序列的最大游程长度不超过n²-2.5n+3。 ● 讨论了新型广义自缩生成器的安全性，主要讨论了新型生成器抵抗猜测攻击和相关攻击的能力。关于安全性得到如下结论：当攻击者已知生成器的一个密钥向量G时，攻击的复杂度为O(12n⁴ 2^0.694n)；当攻击者不知道密钥向量G但已知集合C₁={01，10}时，攻击者可以得到序列的一个相关弱点，利用该弱点可以攻击新型广义自缩序列，但当集合C₁发生变化时，该弱点不存在。 ● 研究了新型广义自缩序列线性复杂度的稳定性：当改变序列的奇数个比特时，序列的线性复杂度会增加到最大，即等于序列的最小周期2^n-1；在改变序列偶数个比特且满足一定条件时，序列的线性复杂度会下降，其余情况下，序列的线性复杂度不会下降。 ● 首次指出周期为2ⁿ的伪随机序列的自相关函数和线性复杂度之间存在的一个关系，并讨论了该关系在以下三个方面的应用：1)由序列的线性复杂度来估计／确定序列的自相关函数值；2)通过序列的自相关函数来证明Games-Chan算法；3)由序列的线性复杂度来检验一个序列族的互相关函数值。 ● 针对一类周期为2ⁿ的伪随机序列，指出这类序列的自相关函数值和线性复杂度以及k错线性复杂度存在着关系，即该类序列的自相关函数可以同国线性复杂度和k-错线性复杂度来衡量。更多还原

【Abstract】 This dissertation firstly discusses the ability of the generalized self-shrinking generator and balanced shrinking generator to resist the fault attack. Secondly, a new type of generalized self-shrinking generator is presented to resist the fault attack, and pseudorandomness and security of new sequences are investigated. Finally, the relationship between autocorrelation and linear complexity is discussed. The main results are as follows: The author gives a cryptanalysis of the generalized self-shrinking generator and balanced shrinking generator by using the fault attack technique. The results show that, for the generalized self-shrinking generator given the feedback polynomial, the attacker can obtain the secret keys by 4 faulty keystreams with 60 stages LFSR, where the length of the keystream required is about 2⁸ bits.For the balanced shrinking generator, the attacker can obtain the secret keys by analyzing faulty output sequences which is produced by changing control clock of one of LFSRs. A new type of generalized self-shrinking generator is presented and the least period, run length and the pseudorandom property of sequences family of which are investigated. The results show that, by our method, 2^n-3 sequences with the least period 2^n-1 can be found. Besides, we show that the maximal run length of the new sequences is less than n²-2.5n+3. The security of the new generalized self-shrinking generator is discussed. The results show that, If the vector G is known for the attacker, then he/she can obtain the secret keys with a complexity O(12n⁴2^0.694n). If the vector G is unknown but the C₁={01,10} is known, then the attacker can find a correlation weakness, which can be used to attack the new generalized self-shrinking generator; However, if C₁≠ {01,10}, there does not exist the above correlation weakness. The stability of the linear complexity of the new generalized self-shrinking generator is discussed. The results show that the linear complexity will increase if odd bits are changed in the sequences. If even bits are changed and the situations of bit changed satisfy some conditions, then the linear complexity will decrease, except this, the linear complexity will increase. For the 2ⁿ-periodic pseudorandom sequences, the relationship between autocorrelation and linear complexity is presented and the application of which in three aspects are given, that is: 1)Estimating/Evaluating the value of autocorrelation functions by the linear complexity; 2) A simpler proof of Games-Chan algorithm is given by the autocorrelation; 3) Evaluating the correlation of a given sequence family by the linear complexity. For a sort of sequences with period 2ⁿ, we denote that the autocorrelation is related to linear complexity and k-error linear complexity,that is, the autocrrelation can be estimated by the linear complexity and k-error linear complexity.更多还原