摘要: 二次指数发生器是一种广泛使用的伪随机数发生器。该文指出在已知移位b和模数p的条件下,若已知连续的wn满足| un wn|是一个很小的数时,在多数情况下可以恢复出二次指数发生器的乘子a。说明了若已知连续的wn满足| un wn|是一个很小的数时,在多数情况下可以恢复出二次指数发生器的乘子a和移位b。结论显示了将二次指数发生器直接应用于密码学必须十分慎重。
关键词:
二次指数发生器,
密码分析,
格攻击,
截位序列
Abstract: Quadratic generator is a kind of widely used pseudorandom number generator. This paper studies the cryptanalysis of the quadratic generator. It shows given the shift b, modular p and sufficiently many of the most significant bits of several sets of the form un, un1, un2, how to disclose the multiplier a and the initial value u0, if un does not lie in a small set, where un,un1,un2 are outputs of the quadratic generator. Then it shows that given the modular p and sufficiently many of the most significant bits of several sets of the form un, un1, un2, un3, one may disclose the a, b and the initial value u0 if un does not lie in another small set. The results of this paper show that it should be careful when quadratic generator is used in a cryptosystem
Key words:
quadratic generator,
cryptanalysis,
lattice attack,
truncated sequences
中图分类号:
赵耀东;戚文峰. 二次指数发生器截位序列的密码分析[J]. 计算机工程, 2007, 33(17): 17-19.
ZHAO Yao-dong; QI Wen-feng. Truncated Sequences Cryptanalysis of Quadratic Generator[J]. Computer Engineering, 2007, 33(17): 17-19.