论文部分内容阅读
近年来,代数攻击已经获得了密码学界的广泛关注。为了抵制各种攻击,布尔函数必须具有好的密码性质:平衡,高的代数免疫,高的代数次数,高的非线性度以及好的抵制快速代数攻击的能力。本文研究了具有好的密码性质的布尔函数构造与代数攻击,主要贡献如下:第一,提出了利用本原多项式来构造密码上重要的布尔函数的方法,并构造了三类布尔函数具有非常好的密码性质:平衡,最优代数次数,最优代数免疫和高的非线性度。在08年Asiacrypt上,Carlet和Feng研究了一类具有好的密码性质的布尔函数,其非线性度好于之前提出的所有无限类布尔函数,而我们导出的非线性度的界比他们的还要好。第二,提出了一种新方法来研究布尔函数的非线性等价,讨论了在每一个等价类中布尔函数的个数,进一步研究了等价类的一些性质,包括代数次数,代数免疫和非线性度,并给出了它们的界。我们发现有很多等价类具有最优代数次数,最优代数免疫和好的非线性度,并讨论了如何来构造具有特定性质的等价类,进而证明构造布尔函数使得其所在等价类具有好的密码性质是可能的。第三,研究了布尔函数抵制快速代数攻击的能力,给出了快速代数免疫和高阶非线性度之间的一个界(这是首次有人给出这两个密码性质之间的界),接着证明了下面两类布尔函数的快速代数免疫是不好的:(a) Carlet提出的Tu-Deng函数的修复函数。Tu-Deng函数具有最优代数次数,最优代数免疫和非常好的非线性度,但它抵制快速代数攻击的能力非常弱,Carlet发现了这个弱点并试图修复它。(b) Tang等人提出的一类函数,具有最优代数次数,最优代数免疫和非常好的非线性度。第四,提出了代数攻击的一个改进版本,并将其应用于流密码分析,新的攻击方法在许多情形下都有效,其时间复杂度要比经典的代数攻击小得多。特别地,我们考察了流密码Trivium和E0,发现针对它们的经典代数攻击可以被极大地加速。第五,提出了一种新的代数攻击,称之为高阶代数攻击,并将其应用于流密码分析,其效率通过新概念r阶代数免疫来描述。我们证明了下面两类布尔函数的2阶代数免疫为1,从而给出了针对它们的极其有效的攻击(极大地超过了已知的所有攻击):(a) Carlet-Feng函数,具有最优代数次数,最优代数免疫,好的非线性度以及好的抵制快速代数攻击的能力。(b)旋转对称布尔函数,一类非常有趣且已被很好研究的布尔函数,可以被有效地实现。