论文部分内容阅读
单圈T函数,作为一类密码学基本构件,可应用于序列密码和伪随机数发生器的设计,因此单圈T函数的构造与判定及其密码学性质的研究与分析都成为了T函数研究的重要内容.
首先,作为本文的理论基础和主要工具,我们给出了p-adic整数的加法公式与乘法公式及其证明.继而使用2-adic整数环上的加法与乘法公式,我们讨论了Klimov与Shamir提出的基于f(x)=x+(x2VC)(mod2n)(C≡5or7(mod8))设计的伪随机数发生器的密码学安全性质,讨论了函数f(x)生成的分位序列的游程分布情况.关于发生器的参数C的恢复问题,我们给出了两种判定方法:一种是确定性的判定方法,需要获得输出序列相应分位的1/4周期的分位序列;另一种是概率的判定方法,利用发生器的少量输出就能以较大概率判断C的取值.其次,使用上述的恢复参数的方法,借助于f(x)生成的分位序列在1/4周期中存在的线性关系,我们给出了同时恢复上述伪随机数发生器的内部状态和参数C的算法,其数据复杂度为O(2n/2).此算法对于任意参数C均有效.
对于单圈T函数的构造与判定问题,我们深入发展了“bit-slice”方法.首先,给出了构造T函数所使用的基本运算,尤其是整数剩余类环上的加法,减法和乘法三种运算的分位函数的代数标准型的更为精细的刻画,为研究由上述运算构成的单圈T函数提供了基本工具.在此基础上,我们从代数标准型的角度,给出了在“bit-slice”方法中起关键作用的“参数”概念的等价描述,阐明了“参数”的实质,并给出了已有的使用“参数”证明的定理的简洁证明,证明方法更具可操作性.进一步地,我们使用2-adic整数环上的加法与乘法运算公式,详细讨论并给出了任意次数的单项式的分位函数的代数标准型的刻画,从而克服了从分位函数的代数标准型的角度来判定T函数的单圈性质时所遇到的主要困难.
在上述工作的基础上,我们分三种情况,系统研究了Klimov提出的广义多项式函数(f)(x)=a0(+)a1x(+)…(+)adxd(mod2n),解决了广义多项式函数的单圈判定问题,给出了广义多项式函数单圈的充要条件.对具体形式的单圈广义多项式函数,通过示例,介绍了对函数系数进行细致刻画的方法.同时,对单圈广义多项式函数生成序列的分布性质做了初步地讨论,实验数据显示单圈广义多项式函数的分布性质较普通的多项式函数以及Klimov-Shamir函数更优.此外,从分位函数的代数标准型的角度出发,我们给出了构造多字单圈T函数的一种新方法.