The predictability of multiple recursive generators means one can correctly predict the out-put of generators by recovering the unknown parameters and initial state.It is a crucial aspect of e-valuating the security of generators,as well as a main concern in their design.High-order-truncated sequences have been proved to predict multiple recursive generators,while the low-order case has not been proved yet,and the method of high-order case cannot be trivially generalized to the low-or-der case.Research shows that the low-order-truncated multiple recursive generators can be predicted in three steps.First,lattice reduction algorithms are used to find several polynomials that annihilate the sequences,then their resultant and greatest common divisor are computed to recover the modulus and the coefficients,and finally a lattice is constructed to recover the initial state and estimate the number of truncated digits required.In particular,when the modulus is even,the initial state can al-so be recovered by a lattice-based method with modulo the high-order bits.Extensive experiments have confirmed that the success rate of recovering the initial state can be improved by using two methods above simultaneously when the modulus is even.
multiple recursive generatorssequences over ringslattice reduction algorithmtrun-cated prediction
国家科技期刊平台
NSTL
万方数据
