未知系数的二阶线性同余发生器截位还原

作者：孙宏宇; 朱宣勇; 郑群雄^*

来源：密码学报, 2019, 6(04): 496-511.

DOI：10.13868/j.cnki.jcr.000318

• 二阶线性同余发生器
• 截位序列
• 序列预测
• 格基约化算法

同余发生器的可预测性问题,即能否由一段截位序列还原发生器的参数和初态,进而准确预测后面的序列,是评估发生器安全性的重要研究课题.本文研究在模数m=2k已知,系数a, b未知的条件下,二阶线性同余发生器xi+2=axi+1+bxi mod m的可预测性问题.我们给出一个基于格基约化算法的方法,可以在已知一段连续的高位s比特截位序列的条件下,还原系数a, b和初态x0, x1,实现对序列的预测.实验结果表明,当模数m=232,发生器生成的序列为整数剩余类环Z/m Z上的二阶本原序列时,可以由140拍连续的高位6比特截位序列还原系数a, b和初态x0, x1.本文从逆向还原的角度探究二阶线性同余发生器的抗预测能力,旨在为其在密码上的应用提供参考和指导.

• 单位
  信息安全国家重点实验室; 中国人民解放军战略支援部队信息工程大学; 中国科学院信息工程研究所