基于格基约化算法的环上截位序列还原
|
摘要
研究由序列a-的最低l比特序列还原整体序列的问题。将该问题转化为使用格基约化算法求解线性同余方程组的问题。实验结果表明,对ZUC密码算法的驱动序列,即对于■/(2~(31)-1)上的16阶本原序列,当已知整体序列的最低8比特序列,长度为110拍,则可以还原整体序列。
In this paper,we study how to recover the original sequences a-from its l least significant bits.This problem can be reduced to the problem of systems of linear congruence,and can be solved by lattice basis reduction algorithm.Moreover,the correctness of the above reconstruction has been validated in experiment.We have successfully reconstructed the primitive sequences of order 16 over ■/(2~(31)-1) of the ZUC algorithm by 110 elements of its 8 least significant bits.
In this paper,we study how to recover the original sequences a-from its l least significant bits.This problem can be reduced to the problem of systems of linear congruence,and can be solved by lattice basis reduction algorithm.Moreover,the correctness of the above reconstruction has been validated in experiment.We have successfully reconstructed the primitive sequences of order 16 over ■/(2~(31)-1) of the ZUC algorithm by 110 elements of its 8 least significant bits.
引文
[1]Kurakin V L,Kuzmin A S,Mikhalev A V,et al.Linear recurring sequences over rings and modules[J].J.Math.Sci,1995,76(6):2793-2915.
[2]Reeds J A,Sloane N J A.Shift-register synthesis(modulo m)[J].SIAM Journal of computing,1985,14(3):505-513.
[3]祝跃飞.环导出序列的唯一性及还原算法[J].数学学报,2001,44:103-110.
[4]Huang M Q,Dai Z D.Projective maps of linear recurring sequences with maximal p-adic periods[J].Fibonacci Quart,1992,30(2):139-143.
[5]Kuzmin A S,Nechaev A A.Linear recurring sequences over Galois ring[J].Russian Mathmatical Surveys,1993,48:171-172.
[6]Zhu X Y,Qi W F.On the distinctness of modular reductions of maximal length sequences module odd prime powers[J].mathmatics of computatlon,2008,77(263):1623-1637.
[7]郑群雄.整数剩余类环上本原序列压缩导出序列的保熵性[D].郑州:信息工程大学,2013.
[8]ETSI/SAGE.Specification of the 3GPP confidentialityand integrity algorithms 128-EEA3&128-EIA3.Document 4:design and evalutation report,version:2.0[EB/OL].[2011-09-11].http:∥zuc.dacas.cn/thread.aspxl ID=2304.
[9]黄民强.环上本原序列的分析及其密码学评价[D].合肥:中国科学技术大学,1988.
[10]刘峰.剩余类环上一类保熵映射还原问题[D].郑州:信息工程大学,1999.
[11]毛竟.环Z/(2e-1)上本原序列还原算法及平移不等价性研究[D].郑州:信息工程大学,2013.
[12]Frieze A M,Hastad J,Kannan R,et al.Reconstructing truncated integer variables satisfying linear congruences[J].SIAM J.Comput,1988,17:262-280.
[13]Lenstra A,Lenstra H,Lovasz L.Factoring polynomial with ratioiial coefficients[J].Mathematiche Annalen,1982,261:515-534.
[14]Gama N,Nguyen P Q.Predicting lattice reduction[C]∥eurocrypt 2008.2008:31-51.
[15]Chen Y,Nguyen P Q.BKZ 2.0:better lattice security estimates[C]∥ASIACRYPT 2011.2011:1-20.
[16]Kannan R,Bachem A.Polynomial algorithms for computing the Smith and Hermite normal forms of an integer matrix[J].siam J.comput,1979,8:499-507.
[17]Shoup V.Number Theory C++Library(NTL)version 9.6.2.[EB/OL].[2015-15-14]http:∥www.shoup.net/ntl/.
[18]Schnorr C P,Euchner M.Lattice basis reduction:improved practical algorithms and solving subset sum problems[J].Mathematical Programming,1994,66(1-3):181-199.
[19]戚文峰.环Z/(2e)上本原序列的压缩映射及其导出序列的分析[D].郑州:信息工程大学,2001.
[20]朱宣勇.环上本原序列保熵压缩映射的研究[D].郑州:信息工程大学,2004.
[2]Reeds J A,Sloane N J A.Shift-register synthesis(modulo m)[J].SIAM Journal of computing,1985,14(3):505-513.
[3]祝跃飞.环导出序列的唯一性及还原算法[J].数学学报,2001,44:103-110.
[4]Huang M Q,Dai Z D.Projective maps of linear recurring sequences with maximal p-adic periods[J].Fibonacci Quart,1992,30(2):139-143.
[5]Kuzmin A S,Nechaev A A.Linear recurring sequences over Galois ring[J].Russian Mathmatical Surveys,1993,48:171-172.
[6]Zhu X Y,Qi W F.On the distinctness of modular reductions of maximal length sequences module odd prime powers[J].mathmatics of computatlon,2008,77(263):1623-1637.
[7]郑群雄.整数剩余类环上本原序列压缩导出序列的保熵性[D].郑州:信息工程大学,2013.
[8]ETSI/SAGE.Specification of the 3GPP confidentialityand integrity algorithms 128-EEA3&128-EIA3.Document 4:design and evalutation report,version:2.0[EB/OL].[2011-09-11].http:∥zuc.dacas.cn/thread.aspxl ID=2304.
[9]黄民强.环上本原序列的分析及其密码学评价[D].合肥:中国科学技术大学,1988.
[10]刘峰.剩余类环上一类保熵映射还原问题[D].郑州:信息工程大学,1999.
[11]毛竟.环Z/(2e-1)上本原序列还原算法及平移不等价性研究[D].郑州:信息工程大学,2013.
[12]Frieze A M,Hastad J,Kannan R,et al.Reconstructing truncated integer variables satisfying linear congruences[J].SIAM J.Comput,1988,17:262-280.
[13]Lenstra A,Lenstra H,Lovasz L.Factoring polynomial with ratioiial coefficients[J].Mathematiche Annalen,1982,261:515-534.
[14]Gama N,Nguyen P Q.Predicting lattice reduction[C]∥eurocrypt 2008.2008:31-51.
[15]Chen Y,Nguyen P Q.BKZ 2.0:better lattice security estimates[C]∥ASIACRYPT 2011.2011:1-20.
[16]Kannan R,Bachem A.Polynomial algorithms for computing the Smith and Hermite normal forms of an integer matrix[J].siam J.comput,1979,8:499-507.
[17]Shoup V.Number Theory C++Library(NTL)version 9.6.2.[EB/OL].[2015-15-14]http:∥www.shoup.net/ntl/.
[18]Schnorr C P,Euchner M.Lattice basis reduction:improved practical algorithms and solving subset sum problems[J].Mathematical Programming,1994,66(1-3):181-199.
[19]戚文峰.环Z/(2e)上本原序列的压缩映射及其导出序列的分析[D].郑州:信息工程大学,2001.
[20]朱宣勇.环上本原序列保熵压缩映射的研究[D].郑州:信息工程大学,2004.