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

• 作者: 孙宏宇 朱宣勇 郑群雄
• 来源期刊: 密码学报
• 学科: 工学
• 关键词: 二阶线性同余发生器 截位序列 序列预测 格基约化算法
• 年，卷（期）: 2019,（4）
• 页码范围: 496-511
• 页数: 16页
• 分类号: TP309.7
• 字数: 11805字
• 语种: 中文
• 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/mZ上的二阶本原序列时,可以由140拍连续的高位6比特截位序列还原系数a,b和初态x0,x1.本文从逆向还原的角度探究二阶线性同余发生器的抗预测能力,旨在为其在密码上的应用提供参考和指导.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	孙宏宇		1	0	0.0	0.0
2	朱宣勇		1	0	0.0	0.0
3	郑群雄		1	0	0.0	0.0