A Lattice-Based Method for Recovering the Unknown Parameters of Truncated Multiple Recursive Generators with Constant  

作　　者：Hanbing YU Qunxiong ZHENG 

机构地区：[1]PLA Strategic Support Force Information Engineering University,Zhengzhou 450001,China

出　　处：《Chinese Journal of Electronics》2024年第6期1458-1467,共10页电子学报（英文版）

基　　金：supported by the National Natural Science Foundation of China(Grant No.61872383)。

摘　　要：Multiple recursive generators with constant,as the high-order extension of linear congruence generators,form an important class of pseudorandom number generators that are widely used in cryptography.The predictability of truncated sequences output by multiple recursive generators with constant that predicts the whole sequences by the truncated high-order bits of the sequences,is a crucial problem in cryptography.This paper studies the predictability of truncated multiple recursive generators with constant.Given a few truncated digits of high-order bits output by a multiple recursive generator with constant,we first convert the multiple recursive generator with constant to multiple recursive generator and then adopt the method we proposed recently to recover the modulus,the coefficients,and the differences of initial state.In particular,we give an estimation of the number of truncated digits required for recovering the differences of initial state by using the expected norm of target vector.We prove by exponential sums that the number of truncated digits required for uniquely determining both the initial state and the constant is finite and give an upper bound.Extensive experiments confirm the correctness of our method.

关 键 词：Multiple recursive generator with constant Lattice reduction Truncated prediction Exponential sums 

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