整数剩余类环上的截位序列还原研究  

Reconstructing Truncated Sequences Derived from Primitive Sequences over Integer Residue Rings

作　　者：杨建斌 朱宣勇[1] 

机构地区：[1]信息工程大学数学工程与先进计算国家重点实验室,郑州450001

出　　处：《密码学报》2017年第2期133-150,共18页Journal of Cryptologic Research

基　　金：国家863计划重点项目(2015AA01A708);国家自然科学基金项目(61170235)

摘　　要：整数剩余类环上线性递归序列(简称环上序列)是一类重要的伪随机序列,在密码学中有广泛的应用.截取环上序列的部分比特序列得到的截位序列是其常见的应用形式.环上截位序列还原问题,即由截位序列还原整体序列,是环上序列安全性评估的重要研究课题.设m是奇素数或不同奇素数之积,f(x)是Z/(m)上的n次本原多项式,a是由f(x)生成的本原序列,若已知序列a的最低l比特序列,序列元素个数为d,如何还原整体序列?将问题转化为格上的最近向量的计算问题,进一步证明:对于截位比特个数大于等于2,截位序列元素个数d大于等于O((n+1)logm/-1)在无穷范数的度量下,如果能够计算d+n维格上的最近向量,则可以以1-1/m的概率还原整体序列.以ZUC密码标准的驱动序列进行实验,由长度大约100拍的6比特截位序列,可以还原出整体序列,恢复未知的25比特序列.根据5比特的截位序列,若已知序列元素个数达到150左右,能够成功还原的实验次数超过一半.对截位比特个数等于2的情形,当本原多项式的次数小于4时,Z/(2^(31)-1)和Z/(2^(32)-1)上的本原序列可以由最低2比特截位序列还原整体序列.As a very important pseudorandom sequences, linear recurring sequences over integer residue rings is widely used in cryptology. The common application form is to obtain a truncated sequences by truncating some bits of a linear recurring sequences over integer residue rings. Recovering original sequences over integer residue rings from its truncated sequences is an important research topic in the area of safety evaluation. Let m be a square-free odd integer, and let f(x) be a primitive polynomial of degree n over Z/(m), and let a be a primitive sequence generated by f(x). In this paper, we study how to recover the original sequence a from its  leastsignificant bits. This problem is reduced to the lattice closest vector problem. We prove that the original sequence can be uniquely reconstructed by d elements of its  least significant bits with the probability at least 1-1/m if ≥2 and d≥O((n+1)logm/-1)The above result is obtained under the assumption that one can access to an oracle forthe lattice closest vector problem for the infinity norm. The correctness of the above reconstruction has been validated in experiment, by recovering the primitive sequences of order 16 over Z/(2^(31)-1) of the ZUC algorithm from its 6 least significant bits with about 100 elements. Moreover, we have successfully reconstructed the primitive sequences for 54 times by about 150 elements of its given 5 least significant bits in 100 experiments. As for the situation of sequences with 2 least significant bits, the original primitive sequences over Z/(2^(31)-1) and Z/(2^(32)-1) can be successfully reconstructed when the degree n of the primitive polynomial is less than 4.

关 键 词：线性递归序列 整数剩余类环 截位序列 序列还原 最近向量问题 

分 类 号：TP309.7[自动化与计算机技术—计算机系统结构]