信息工程大学学报2024，Vol.25Issue(2)：181-188,8.DOI:10.3969/j.issn.1671-0673.2024.02.009
未知参数多重递归发生器的截低位还原
Predicting Low-Order-Truncated Multiple Recursive Generators with Unknown Parameters
摘要
Abstract
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.关键词
多重递归发生器/环上序列/格基约化算法/截位还原Key words
multiple recursive generators/sequences over rings/lattice reduction algorithm/trun-cated prediction分类
信息技术与安全科学引用本文复制引用
于寒冰,郑群雄..未知参数多重递归发生器的截低位还原[J].信息工程大学学报,2024,25(2):181-188,8.基金项目
国家自然科学基金资助项目(61872383) （61872383）
