论文部分内容阅读
在eSTREAM计划的推动下,采用非线性驱动序列已经逐步成为序列密码设计的一种主流趋势。由于存在复杂的进位运算,整数剩余类环上的线性递归序列(简称环上序列)在比特层面天然蕴含丰富的非线性结构。将环上序列进行2-adic展开,我们自然可以得到多条二元非线性序列。这些非线性序列具有诸多优良的密码性质,如大周期、良好的元素分布等,恰好迎合了序列密码设计的需求,因此环上序列自然成为当前序列密码领域研究的重要对象。本文从逆向还原的角度探索环上序列的安全性问题。设m是整数,(?)=(at)t≥0是环Z/(m)上的本原序列,整数l ≥2,称(?) mod 2l=(at mod 2l)t≥0为(?)的截(l)位序列。本文研究在已知截位序列(?) mod 2l某些时刻(连续/离散)取值的条件下,如何还原序列(?)的问题,简称为环上序列的截位序列还原问题。截位序列还原问题对于指导基于环上序列的密码算法设计具有重要的意义。我们取得了如下的研究成果:1.基于格基约化算法给出了环上序列的截位序列还原算法。将截位序列还原问题转化为线性同余方程组中小整数解的求解问题,然后通过格基约化的方法进行截位序列还原。进一步,通过变量替换的方法,对于格基约化算法求解线性同余方程组中小整数解的算法进行有效改进。以祖冲之密码的驱动序列进行实验,对于Z/(231-1)上16阶本原序列,在已知递归关系的前提下,由最低的8比特截位序列,长度128拍,可以容易还原其他未知的23比特序列。2.给出了环上序列的截位序列还原所需元素个数的下界估计。将截位序列还原问题转化为格上的最近向量问题。当模数m是素数或互异奇素数之积时,进一步证明:对于Z/(m)上的n阶本原序列(?),当截位比特个数l≥ 2,截位序列(?) mod 2l的元素个数d≥O((n+1)log m/l-1)时,在无穷范数的度量下,如果能够计算d+n维格上的最近向量,则可以以1-1/m的概率还原整体序列a。当格的维数较小时,这个理论结果得到了实验验证。