文档介绍：-1- 布尔函数的密码学性质及其相互关系摘要: 本文的主要工作是对布尔函数的密码学性质进行简单的介绍以及整理,并将近期密码函数安全性领域里面的主要结论进行归纳和比较,通过各种性质及之间相互关系找出一种构造具有“优秀”密码学性质的函数的方法。本文第一部分为基本概念,主要内容是布尔函数的基本知识以及文章中将会用到的相关符号和语言。这一部分还简单介绍了布尔函数的两个基本性质:均衡性、代数次数。这两个性质对函数的安全性具有十分重要的意义。第二部分介绍了布尔函数的相关免疫性以及弹性的有关内容, 末尾简单地介绍了几种构造具有特定相关免疫阶的布尔函数的方法。第三部分介绍了布尔函数的非线性度以及具有最高非线性度的 Bent 函数的相关内容。这一部分最后还给出了两个完善 Bent 函数以使其均衡的方法。第四部分简单地介绍了布尔函数差分均匀度和 PN 函数的相关内容,并且给出了一个 PN 函数的等价定义。第五部分简单介绍了布尔函数的代数免疫度的概念。第六部分给出了许多重要的结论,这些结论揭示了各种密码函数性质之间的内在联系. 这一部分主要以总结归纳为主,适当加入笔者对结论的一些观点. 第一部分:基本概念定义 设2F 是二元有限域, n 为正整数,称映射 nFFf 22:?为布尔函数. 若记全体 n 维布尔函数的集合为 nB . 使得 nFx 2?且1)(?xf 的x 的个数称为函数 f 的 Hamming 重量,记为)(fW H . 如果一个 n 维布尔函数 f 满足 12)( ?? nHfW , ?, ,f 和g 的 Hamming 距离定义为??)()(),( 2xgxfFxgfd n???其中, A 表示集合 A 中元素的个数. 容易发现:)(),(gfWgfd H??. n 维布尔函数的代数正规型:n nn n nxxxna xxnnaxxaxxa xnaxaxa a xxxfy???????????????????? 21 13121 21 21),,2,1( ),1()3,1()2,1( )()2()1( )0( ),,,( 为了方便书写,记)(NP 表示 N 的幂集,其中?? nN,,2,1??,则 INPI nxIaxxxf????)( 21)(),,,( -2- 其中,),,()( 21kiiiaIa??,),2,1(kjIi j???,??? Ii i Ixx . 这种表示方法称为布尔函数的小项表示.]1[ 在n 维布尔函数的代数正规型中, 系数不为 0 的项的最高次数称为该函数的代数次数,记为) deg( f . 特殊地, 1 代数次数为 1 的布尔函数称为仿射函数. 2 常数项为 0 的仿射函数称为线性函数. 3 含有高于 1 次的项的布尔函数称为非线性函数. 易证: 仿射函数都是均衡的. 从布尔函数的代数正规型中可以发现: 代数次数越低的布尔函数越容易被确定, 这是因为我们可以将)(Ia 看成未知数, 代数次数越低的函数未知数越少, 那么我们就可以用越少的真值对将其确定出来. 因此, 代数次数越低的布尔函数越不适合用作密码函数. 在上面的介绍中,有两个性质对于一个布尔函数能否“胜任”密码函数来说有着十分重要的意义:均衡性、代数次数: 均衡性:序列密码体制产生的密钥流是否具有高的安全强度,取决于它们是否具有良好的伪随机性. 均衡性就是序列伪随机性的一个重要指标. 一条序列称为均衡的是指该序列中不同元素出现的次数至多只相差一个. 代数次数:密码体制中所使用的布尔函数通常具有高的代数次数,低代数次数的密码体制容易遭到 Berlekamp-Massey 算法攻击、插值攻击、代数攻击以及高阶差分攻击.]1[ 以上为第一部分的主要内容,即布尔函数的基本内容. 从第二部分开始,我们将对布尔函数的多种密码性质进行整理、归纳和总结,并将近期密码学界的相关结论呈现出来. 第二部分:布尔函数的相关免疫性这一部分主要介绍了布尔函数相关免疫性的内容,包括相关免疫的定义以及它的一些等价刻画、布尔函数的 Walsh 变换与其相关免疫性的关系、如何构造具有特定阶的相关免疫函数及其记数. 下面先给出相关免疫性的定义: 定义 设有布尔函数 nFFf 22:?. 如果①n 维随机变量),,,( 21nxxx?在nF 2 上均匀分布; ②对下标集?? n,,2,1?中任意 t 个下标?? tjjj,,, 21?, 随机变量),,,( 21nxxxy??与t 个随机变量相互独立, 即对于任意的 mmFaaa 221),,,(??及2Fa?-3- )(),,,|( 21afPaxaxaxafP tjjj???????就称 f 为t 阶相关免疫布尔函数. 如果 f 是t 阶相关免疫布尔函数但不是 1?t 阶相关免疫函数