多重周期二元序列的联合k错2-adic复杂度

《多重周期二元序列的联合k错2-adic复杂度》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、多重周期二元序列的联合k错2-adic复杂度基金资助：国家重点基础研究发展规划项目(973计划)(2007CB311201),国家自然科学基金(60473029,60673072)，国家自然青年科学基金(60503010)联系作者：董丽华，E-mail:lih_dong@mail.xidian.edu.cn董丽华胡予濮曾勇（西安电子科技大学计算机网络与信息安全国家教育部重点实验室,陕西西安,710071）摘要：具有较强密码学性质的序列应该具有较大的2-adic复杂度，以抗击已知的带进位操作反馈移位寄存器综合算法,同时改变较少的几项也不应引起序列的2-adi

2、c复杂度的急剧减小,即k错2-adic复杂度也应尽可能的大。近来，向量化流密码的设计逐渐成为国内外密码学界关注的一个重要方向。对这种类型的流密码的安全性分析需要研究多重序列－有限多个序列的并行流的复杂度。目前对多重序列的复杂度研究多集中于线性复杂度。基于此,本文首先给出了多重二元序列的联合k错2-adic复杂度的定义。随后，借助数论中的中国剩余定理等相关理论给出了联合k错2-adic复杂度的下界，并讨论了具有最大联合2-adic复杂度以及较大联合k错2-adic复杂度的N周期序列的存在性及具有此种性质的序列的数目下界。以此种周期序列作为密钥流序列可以有效抵

3、抗穷举攻击。关键词：密码学；流密码；FCSR；联合2-adic复杂度；k错2-adic复杂度1．引言在新一代的移动通信系统中，巨大的信息吞吐量需要安全快速的信息加密体制，如流密码和分组密码。传统的基于线性反馈移位寄存器(LFSR)的序列密码易受攻击，近年来出现了一些新型的序列密码设计部件，诸如T函数、NLFSR，带进位操作的反馈移位寄存器(FCSR)等等。其中FCSR自Klapper与Goresky于文献[1]中引入之后已引起密码学界的广泛关注。FCSR序列与LFSR序列平行的一些基本性质包括周期、有理表达式、指数表达式和有理近似算法等[2-5]得到了广泛

4、的讨论。最近几年，国内外学者纷纷注意到序列的线性复杂度在极小的扰动下也可能是极不稳定的，因而相继引入了球体复杂度、k错线性复杂度等概念，并作了大量的相关研究工作。特别的文献[6-8]对具有最大线性复杂度以及接近周期的k错线性复杂度的周期序列的存在性进行了研究，给出了此种周期序列的数目下界。在对FCSR序列的研究过程中，文献[9]的作者指出了序列的2-adic复杂度测度具有同样的不稳定性，例如：T周期序列S=(1,0,…,0)∞或(0,1,…,1)∞具有最大的2-adic复杂度log2(2T-1)；然而，若序列S的每个周期改变一个比特，其2-adic复杂度将

5、退化为0。进而只要知道有限个比特就可以有效地重构初始序列。基于此，文献[9]的作者首先给出了k错2-adic复杂度的概念。随后，胡红刚[10]等学者给出了周期序列的k错2-adic复杂度以及k错对称2-adic复杂度的一个下界。在文献[11]中我们给出了计算计算周期为2n的二元序列的2-adic复杂度综合算法，并以该算法为基础，给出了一个计算周期为2n的二元序列的k错2-adic复杂度综合算法。在文献[12]中我们证明了具有最大2-adic复杂度以及较大k错2-adic复杂度的N周期序列的存在性，给出了具有这种性质的周期序列的数目的下界。当前，向量化流密码

6、的设计已逐渐成为国内外密码学界关注的一个重要方向。对这种类型的流密码的安全性分析需要研究多重序列－有限多个序列的并行流的复杂度。在[13]中，Meidl与Niederreiter首先建立了多重序列的k错线性复杂度理论，随后，Niederreiter与Venkateswarlu[14]进一步讨论了具有较大k错线性复杂度的多重序列的存在性以及具有此性质的序列的个数的下界。胡红刚等学者则首先确定了二元周期多重序列的联合2-adic复杂度的期望值并给出了二元周期多重序列的联合对称2-adic复杂度的期望值的一个下界[15]。目前对多重周期序列的k错2-adic复杂

7、度的研究尚未见公开报导，本文将首先给出多重周期二元序列的联合k错2-adic复杂度的一个定义，随后使用数论中的相关理论给出了联合k错2-adic复杂度的下界，并讨论了具有最大联合2-adic复杂度以及较大联合k错2-adic复杂度的N周期序列的存在性及具有此种性质的序列的数目下界。文中的结果对对称密码学[16]中FCSR理论的发展将起到极大的促进作用。这里的代数运算不再是逐比特加而是有限比特串的2-adic加法。由于2j+2j=2j+1，2-adic加法将溢出比特进位到高阶项。2．基本概念任意给定一个二元序列S=s0,s1,s2,…在2-adic整数环Z2

8、中总可以找到与之相匹配的2-adic数α=s0+s12+…+sN－