逆同余发生器的密码分析  

On Cryptanalysis of the Inversive Generator

作　　者：赵耀东[1] 戚文峰[1] 

机构地区：[1]郑州信息工程大学信息工程学院,河南郑州450002

出　　处：《武汉大学学报（理学版）》2007年第3期279-282,共4页Journal of Wuhan University:Natural Science Edition

基　　金：国家自然科学基金资助项目(60373081);国家高技术研究发展计划(863)资助项目(2006AA01Z417)

摘　　要：使用格中的最短向量对未知向量进行逼近的方法,证明了在已知乘子a和模数p的条件下,若连续的wi满足|ui-wi|是一个很小的数时,在多项式时间内可以恢复出逆同余发生器的移位b.本文的结论表明将逆同余发生器直接应用于密码学必须十分慎重.In this paper, we prove that given the multiplier a, modular p and sufficiently many of the most significant bits of three consecutive outputs of the inversive generator, one can disclose the shift b and the initial value if those outputs do not lie in a small set, by the method of using the shortest vector in the lattice to approximate the unknown vector. The result of this paper shows that we should be careful when we use the inversive generator in a cryptosystem.

关 键 词：逆同余发生器 密码分析 格攻击 

分 类 号：TN918.1[电子电信—通信与信息系统]