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

• 作者: 朱宣勇 杨建斌
• 来源期刊: 密码学报
• 学科: 工学
• 关键词: 线性递归序列 整数剩余类环 截位序列 序列还原 最近向量问题
• 年，卷（期）: 2017,（2）
• 页码范围: 133-150
• 页数: 18页
• 分类号: TP309.7
• 字数: 9877字
• 语种: 中文
• DOI: 10.13868/j.cnki.jcr.000169

摘要

整数剩余类环上线性递归序列(简称环上序列)是一类重要的伪随机序列,在密码学中有广泛的应用.截取环上序列的部分比特序列得到的截位序列是其常见的应用形式.环上截位序列还原问题,即由截位序列还原整体序列,是环上序列安全性评估的重要研究课题.设m是奇素数或不同奇素数之积,f(x)是(Z)/(m)上的n次本原多项式,(a)是由f(x)生成的本原序列,若已知序列(a)的最低(l)比特序列,序列元素个数为d,如何还原整体序列?将问题转化为格上的最近向量的计算问题,进一步证明:对于截位比特个数(l)大于等于2,截位序列元素个数d大于等于O((n+1)logm/l-1)在无穷范数的度量下,如果能够计算d+n维格上的最近向量,则可以以1-1/m的概率还原整体序列.以ZUC密码标准的驱动序列进行实验,由长度大约100拍的6比特截位序列,可以还原出整体序列,恢复未知的25比特序列.根据5比特的截位序列,若已知序列元素个数达到150左右,能够成功还原的实验次数超过一半.对截位比特个数(l)等于2的情形,当本原多项式的次数小于4时,(Z)/(231-1)和(Z)/(232-1)上的本原序列可以由最低2比特截位序列还原整体序列.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	朱宣勇	信息工程大学数学工程与先进计算国家重点实验室	8	17	2.0	4.0
2	杨建斌	信息工程大学数学工程与先进计算国家重点实验室	1	1	1.0	1.0