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

整数剩余类环上线性递归序列(简称环上序列)是一类重要的伪随机序列, 在密码学中有广泛的应用. 截取环上序列的部分比特序列得到的截位序列是其常见的应用形式. 环上截位序列还原问题, 即由截位序列还原整体序列, 是环上序列安全性评估的重要研究课题. 设m是奇素数或不同奇素数之积, f(x)是Z/(m)上的n次本原多项式, 是由 f(x)生成的本原序列, 若已知序列的最低l比特序列, 序列元素个数为d, 如何还原整体序列？将问题转化为格上的最近向量的计算问题, 进一步证明：对于截位比特个数l大于等于2, 截位序列元素个数d大于等于在无穷范数的度量下, 如果能够计算d+n维格上的最近向量, 则可以以1...

Full description

Saved in:
Bibliographic Details
Published in:Journal of Cryptologic Research 2017-04, Vol.4 (2), p.133
Main Authors: Jian-Bin, YANG, Xuan-Yong, ZHU, 杨建斌, 朱宣勇
Format: Article
Language:Chinese
Subjects:
Algorithms
Integers
Polynomials
Pseudorandom sequences
Residues
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:整数剩余类环上线性递归序列(简称环上序列)是一类重要的伪随机序列, 在密码学中有广泛的应用. 截取环上序列的部分比特序列得到的截位序列是其常见的应用形式. 环上截位序列还原问题, 即由截位序列还原整体序列, 是环上序列安全性评估的重要研究课题. 设m是奇素数或不同奇素数之积, f(x)是Z/(m)上的n次本原多项式, 是由 f(x)生成的本原序列, 若已知序列的最低l比特序列, 序列元素个数为d, 如何还原整体序列？将问题转化为格上的最近向量的计算问题, 进一步证明：对于截位比特个数l大于等于2, 截位序列元素个数d大于等于在无穷范数的度量下, 如果能够计算d+n维格上的最近向量, 则可以以1-1/m的概率还原整体序列. 以ZUC密码标准的驱动序列进行实验, 由长度大约100拍的6比特截位序列, 可以还原出整体序列, 恢复未知的25比特序列. 根据5比特的截位序列, 若已知序列元素个数达到150左右, 能够成功还原的实验次数超过一半. 对截位比特个数l等于2的情形, 当本原多项式的次数小于4时, Z/(231-1)和 Z/(232-1)上的本原序列可以由最低2比特截位序列还原整体序列.
ISSN:2097-4116
DOI:10.13868/j.cnki.jcr.000169