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, un1, un2, how to disclose the multiplier a and the initial value u0, if un does not lie in a small set, where un,un1,un2 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, un1, un2, un3, 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

摘要： 二次指数发生器是一种广泛使用的伪随机数发生器。该文指出在已知移位b和模数p的条件下，若已知连续的wn满足| un wn|是一个很小的数时，在多数情况下可以恢复出二次指数发生器的乘子a。说明了若已知连续的wn满足| un  wn|是一个很小的数时，在多数情况下可以恢复出二次指数发生器的乘子a和移位b。结论显示了将二次指数发生器直接应用于密码学必须十分慎重。

关键词: 二次指数发生器, 密码分析, 格攻击, 截位序列

CLC Number: 

• TP309