二次指数发生器截位序列的密码分析

Truncated Sequences Cryptanalysis of Quadratic Generator

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

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 u. 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.