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

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

二次指数发生器

文章构造了有限域Fq上一种基于二次指数方法的伪随机数发生器,即数位二次指数伪随机数发生器,并且考虑了由它产生的序列的分布情况。由这种发生器产生的序列的分布情况是通过偏差来刻划的,本文利用特征和这种工具给出了其偏差的部分结果。设t是由这种发生器产生的序列的周期,对任意的ε>0,当t≥q1/2+2ε时,我们给出这条序列分布偏差的上界为O(t-1/4q1/8+εlogq),从而说明序列是渐进等分布的。

椭圆曲线上二次发生器序列分布的一致性

讨论了二次指数发生器在椭圆曲线上模拟所生成的序列的分布情况,证明了此类椭圆曲线序列是渐近一致分布序列。主要的理论工具为椭圆曲线有理点群的指数和估计。