布尔函数的密码性质及其相互关系资料.doc

PAGE  PAGE - 12 - 布尔函数的密码学性质及其相互关系 摘要：本文的主要工作是对布尔函数的密码学性质进行简单的介绍以及整理，并将近期密码函数安全性领域里面的主要结论进行归纳和比较，通过各种性质及之间相互关系找出一种构造具有“优秀”密码学性质的函数的方法。本文第一部分为基本概念，主要内容是布尔函数的基本知识以及文章中将会用到的相关符号和语言。这一部分还简单介绍了布尔函数的两个基本性质：均衡性、代数次数。这两个性质对函数的安全性具有十分重要的意义。第二部分介绍了布尔函数的相关免疫性以及弹性的有关内容，末尾简单地介绍了几种构造具有特定相关免疫阶的布尔函数的方法。第三部分介绍了布尔函数的非线性度以及具有最高非线性度的Bent函数的相关内容。这一部分最后还给出了两个完善Bent函数以使其均衡的方法。第四部分简单地介绍了布尔函数差分均匀度和PN函数的相关内容，并且给出了一个PN函数的等价定义。第五部分简单介绍了布尔函数的代数免疫度的概念。第六部分给出了许多重要的结论，这些结论揭示了各种密码函数性质之间的内在联系. 这一部分主要以总结归纳为主，适当加入笔者对结论的一些观点. 第一部分：基本概念 定义1.1 设是二元有限域，为正整数，称映射为布尔函数. 若记全体维布尔函数的集合为. 使得且的的个数称为函数的Hamming重量，记为. 如果一个维布尔函数满足，则称这个函数是均衡的. 设,和的Hamming距离定义为 其中，表示集合中元素的个数. 容易发现:. 维布尔函数的代数正规型： 为了方便书写，记表示的幂集，其中，则 其中，，，.这种表示方法称为布尔函数的小项表示.在维布尔函数的代数正规型中，系数不为0的项的最高次数称为该函数的代数次数，记为. 特殊地， 代数次数为1的布尔函数称为仿射函数. 常数项为0的仿射函数称为线性函数. 含有高于1次的项的布尔函数称为非线性函数. 易证：仿射函数都是均衡的. 从布尔函数的代数正规型中可以发现：代数次数越低的布尔函数越容易被确定，这是因为我们可以将看成未知数，代数次数越低的函数未知数越少，那么我们就可以用越少的真值对将其确定出来. 因此，代数次数越低的布尔函数越不适合用作密码函数. 在上面的介绍中，有两个性质对于一个布尔函数能否“胜任”密码函数来说有着十分重要的意义：均衡性、代数次数： 均衡性：序列密码体制产生的密钥流是否具有高的安全强度，取决于它们是否具有良好的伪随机性. 均衡性就是序列伪随机性的一个重要指标. 一条序列称为均衡的是指该序列中不同元素出现的次数至多只相差一个. 代数次数：密码体制中所使用的布尔函数通常具有高的代数次数，低代数次数的密码体制容易遭到Berlekamp-Massey算法攻击、插值攻击、代数攻击以及高阶差分攻击. 以上为第一部分的主要内容，即布尔函数的基本内容. 从第二部分开始，我们将对布尔函数的多种密码性质进行整理、归纳和总结，并将近期密码学界的相关结论呈现出来. 第二部分：布尔函数的相关免疫性 这一部分主要介绍了布尔函数相关免疫性的内容，包括相关免疫的定义以及它的一些等价刻画、布尔函数的Walsh变换与其相关免疫性的关系、如何构造具有特定阶的相关免疫函数及其记数. 下面先给出相关免疫性的定义： 定义2.1 设有布尔函数. 如果 ①维随机变量在上均匀分布； ②对下标集中任意个下标，随机变量与个随机变量相互独立,即对于任意的及 就称为阶相关免疫布尔函数. 如果是阶相关免疫布尔函数但不是阶相关免疫函数，则称函数的相关免疫阶为. 下面的结论是维布尔函数相关免疫性的等价刻画： 定理2.1 以下四个叙述等价： ①维布尔函数是阶相关免疫函数. ②对任意的，令的任意个分量取任意定值，维布尔函数是阶相关免疫函数. ③对任意的，，随机变量与变量相互独立. ④对任意的，, 函数是平衡函数. 以上对于相关免疫性的描述对于理解布这个性质的本质还具有一定的困难. 布尔函数的Walsh变换对于理解其本质有着至关重要的作用： 定义2.2 设是一个维布尔函数. 取，令. 称为的循环Walsh变换. 其中， 定理2.2 设维布尔函数. 若，则是阶相关免疫函数的充要条件是对于所有且，. 上面的定理刻画了阶相关免疫函数的谱特征，对理解相关免疫性的实质有着非常大的帮助. 下面介绍具有均衡性的相关免疫函数——弹性函数： 定义2.3 设维布尔函数，若函数既是一个阶相关免疫函数又是均衡函数，则称是一个阶弹性函数. 注意到布尔函数是均衡的当且仅当，于是 定理2.3 布尔函数是一个阶弹性函数的充要条件是对于所有的且，均有. 在密码学研究中，密码函数的均衡性是密码函数的最基本的性质，所以一下讨论都将围绕弹性函