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

摘要：

同余发生器的可预测性问题,即能否由一段截位序列还原发生器的参数和初态,进而准确预测后面的序列,是评估发生器安全性的重要研究课题.本文研究在模数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.本文从逆向还原的角度探究二阶线性同余发生器的抗预测能力,旨在为其在密码上的应用提供参考和指导.

关键词：二阶线性同余发生器、截位序列、序列预测、格基约化算法

所属期刊栏目：6

分类号：TP309.7(计算技术、计算机技术)

资助基金：国家自然科学基金61872383, 61402524, 61602510;中国科协青年托举工程2016QNRC001;博士后创新人才支持计划BX201600188;博士后面上资助项目2017M611035

在线出版日期：2019-09-19（万方平台首次上网日期，不代表论文的发表时间）

页数：共16页

页码：496-511