《布尔函数的密码性质及其相互关系》由会员分享，可在线阅读，更多相关《布尔函数的密码性质及其相互关系（11页珍藏版）》请在金锄头文库上搜索。
1、- 1 - 布尔函数的密码学性质及其相互关系摘要： 本文的主要工作是对布尔函数的密码学性质进行简单的介绍以及整理，并将近期密码函数安全性领域里面的主要结论进行归纳和比较，通过各种性质及之间相互关系找出一种构造具有“优秀”密码学性质的函数的方法。本文第一部分为基本概念，主要内容是布尔函数的基本知识以及文章中将会用到的相关符号和语言。这一部分还简单介绍了布尔函数的两个基本性质：均衡性、代数次数。这两个性质对函数的安全性具有十分重要的意义。第二部分介绍了布尔函数的相关免疫性以及弹性的有关内容， 末尾简单地介绍了几种构造具有特定相关免疫阶的布尔函数的方法。第三部分介绍了布尔函数的非线性度以及具有最高非
2、线性度的Bent函数的相关内容。这一部分最后还给出了两个完善Bent 函数以使其均衡的方法。第四部分简单地介绍了布尔函数差分均匀度和PN函数的相关内容，并且给出了一个PN函数的等价定义。第五部分简单介绍了布尔函数的代数免疫度的概念。第六部分给出了许多重要的结论，这些结论揭示了各种密码函数性质之间的内在联系. 这一部分主要以总结归纳为主，适当加入笔者对结论的一些观点. 第一部分：基本概念定义 1.1 设2F是二元有限域，n为正整数，称映射nFFf22:为布尔函数 . 若记全体n维布尔函数的集合为nB. 使得nFx2且1)(xf的x的个数称为函数f的 Hamming重量 ，记为)( fWH. 如果
3、一个n维布尔函数f满足12)(n HfW，则称这个函数是均衡的 . 设nBgf ,f和g的 Hamming距离 定义为)()(),(2xgxfFxgfdn其中，A表示集合A中元素的个数. 容易发现 :)(),(gfWgfdH. n维布尔函数的代数正规型 ：nnnnnxxxnaxxnnaxxaxxaxnaxaxaaxxxfy21131212121),2, 1(), 1()3 ,1 ()2, 1()()2() 1()0(),(为了方便书写，记)(NP表示N的幂集，其中nN,2 , 1，则INPInxIaxxxf)(21)(),(- 2 - 其中，),()(21kiiiaIa，),2, 1(kjIi
4、j，IiiIxx. 这种表示方法称为布尔函数的 小项表示 . 1在n维布尔函数的代数正规型中，系数不为0 的项的最高次数称为该函数的代数次数 ，记为)deg(f. 特殊地，代数次数为1 的布尔函数称为仿射函数 . 常数项为0 的仿射函数称为线性函数 . 含有高于1 次的项的布尔函数称为非线性函数 . 易证： 仿射函数都是均衡的.从布尔函数的代数正规型中可以发现：代数次数越低的布尔函数越容易被确定，这是因为我们可以将)(Ia看成未知数，代数次数越低的函数未知数越少，那么我们就可以用越少的真值对将其确定出来. 因此， 代数次数越低的布尔函数越不适合用作密码函数 . 在上面的介绍中，有两个性质对于一
5、个布尔函数能否“胜任”密码函数来说有着十分重要的意义：均衡性、代数次数：均衡性 ：序列密码体制产生的密钥流是否具有高的安全强度，取决于它们是否具有良好的伪随机性. 均衡性就是序列伪随机性的一个重要指标. 一条序列称为 均衡的是指该序列中不同元素出现的次数至多只相差一个. 代数次数 ：密码体制中所使用的布尔函数通常具有高的代数次数，低代数次数的密码体制容易遭到Berlekamp-Massey 算法攻击、 插值攻击、 代数攻击以及高阶差分攻击.1以上为第一部分的主要内容，即布尔函数的基本内容. 从第二部分开始，我们将对布尔函数的多种密码性质进行整理、归纳和总结，并将近期密码学界的相关结论呈现出来
6、. 第二部分：布尔函数的相关免疫性这一部分主要介绍了布尔函数相关免疫性的内容，包括相关免疫的定义以及它的一些等价刻画、布尔函数的Walsh 变换与其相关免疫性的关系、如何构造具有特定阶的相关免疫函数及其记数. 下面先给出相关免疫性的定义：定义 2.1 设有布尔函数nFFf22:. 如果n维随机变量),(21nxxx在nF2上均匀分布；对下标集n, 2, 1中任意t个下标tjjj,21，随机变量),(21nxxxy与t个随机变量相互独立,即对于任意的m mFaaa221),(及2Fa- 3 - )(),|(2121afPaxaxaxafPtjjjt就称f为t阶相关免疫布尔函数. 如果f是t阶相关
7、免疫布尔函数但不是1t阶相关免疫函数，则称函数f的相关免疫阶 为t. 下面的结论是n维布尔函数相关免疫性的等价刻画：定理 2.1以下四个叙述等价：n维布尔函数f是t阶相关免疫函数. 对任意的ts，令),(21nxxx的任意s个分量取任意定值，sn维布尔函数f是st阶相关免疫函数. 对任意的),(21ncccc，tcWH)(，随机变量),(21nxxxy与变量xnxcxcxcxc2211相互独立 . 2对任意的),(21ncccc，tcWH)(, 函数xcy是平衡函数 . 以上对于相关免疫性的描述对于理解布这个性质的本质还具有一定的困难. 布尔函数的Walsh 变换对于理解其本质有着至关重要的作
8、用：定义2.2 设)( xf是一个n维布尔函数. 取n nFwwww221),(，令xnxwxwxwxw2211. 称)(wSf为)(xf的循环 Walsh 变换 . 其中，xwxxf fwS)() 1()(定理 2.2 设n维布尔函数f. 若nt1，则f是t阶相关免疫函数的充要条件是对于所有nFw2且twWH)(1，0)(wSf. 上面的定理刻画了t阶相关免疫函数的谱特征，对理解相关免疫性的实质有着非常大的帮助 . 下面介绍具有均衡性的相关免疫函数弹性函数：定义 2.31设n维布尔函数f，若函数f既是一个t阶相关免疫函数又是均衡函数，则称f是一个t阶弹性函数 . 注意到布尔函数f是均衡的当且
9、仅当0)0(fS，于是定理2.31布尔函数f是一个t阶弹性函数的充要条件是对于所有的nFw2且twWH)(0，均有0)(wSf. - 4 - 在密码学研究中，密码函数的均衡性是密码函数的最基本的性质，所以一下讨论都将围绕弹性函数展开. 下面将简单地介绍一下弹性函数的构造. 由于一阶弹性函数的构造方法比较复杂，而且方法种类繁多，这里将省略介绍之. 参考文献 1 中有比较详细的关于一阶弹性函数的构造方法. 这里介绍一下如何通过已知的弹性函数构造新的弹性函数. 定理 2.4设f是n维t阶弹性函数，则)1 ,1 ,1(),(),(),(2121121121nnnnnnxxxfxxxfxxxxfxxxx
10、h是1n维1t阶弹性函数 . 定理 2.5 设f是n维t阶弹性函数，g 是m维s阶弹性函数，则),(),(),(212121mnnnnmnnxxxgxxxfxxxxh是mn维1st阶弹性函数 . 定 理2.63若 函 数)(),(),(321xfxfxf均 是n维t阶 弹 性 函 数 ， 则 函 数)()()()(321xfxfxfxg也是t阶弹性函数的充要条件是)()()()()()()(323121xfxfxfxfxfxfxh是t阶弹性函数 . 这一部分最后将给出几个关于循环Wlash 变换的结论，循环Wlash 变换的定义已经由定义2.2 给出 . 定义 2.4设)(xf是一个n维布尔函
11、数 . 称)(wF为)(xf的线性 Walsh 变换 . 其中，xxwxfwF) 1)()(xw的定义如上 . 称)(xf为)(wF的线性 Walsh 反变换，容易验证，wxw fnwSxf)1)( 21)(线性 Walsh 变换与循环Wlash 变换之间存在着如下关系：0),(220),(2)(wwFwwFwSnf由此可知两种Walsh 变换可以相互唯一确定，所以以后不加说明的话布尔函数的Walsh 变换指的就是循环Walsh 变换 . 容易验证布尔函数)(xf的循环 Walsh 变换有如下性质：- 5 - 定理 2.7若)(wSf为)(xf的循环 Walsh 变换，即xwxxf fwS)(
12、)1()(，那么，)(xf称为)(wSf的循环 Walsh 逆变换，且wxw fnwSxf)1)(21)(. 能量守恒公式：nwfwS222) )(. 卷积公式：对于任意的0a，0)()(awSwSf wf. 第三部分：布尔函数的非线性度布尔函数的非线性度从形象上说指的是布尔函数与仿射函数之间的“距离”. 为了抵抗线性密码攻击，密码体制中所使用的布尔函数应该离所有的仿射函数的“距离”尽可能大. 所以布尔函数f的非线性度定义为f和所有仿射函数的最小Hamming距离 . 定义 3.1设)(xf是一个n维布尔函数，称如下的fN为)(xf的非线性度，),(minlfdNnLlf其中nL表示所有n维仿
13、射函数的集合. 定理 3.1设)(xf是一个n维布尔函数，则)(max2121wSNfwn f其中，)(wSf是)(xf的循环 Walsh 变换 . 这个定理给出了布尔函数非线性度的计算方法，下面的定理给出一个布尔函数的非线性度紧的上界. 定理 3.2 设)(xf是一个n维布尔函数，则它的非线性度满足1 2122n n fN定理 3.2 中的上界是可达的. 定 义3.2设)(xf是 一 个n维 布 尔 函 数 ， 如 果)(xf的 非 线 性 度 达 到1 2122n n fN，那么称)(xf为 Bent 函数定理 3.3 设)(xf是一个n维布尔函数，则)(xf是 Bent 函数当且仅当对任
14、意的nFa2，)(aSf的取值只能是22n. 容易发现， Bent 函数的维数n必定为偶数 . 定义 3.2和定理3.3 都可以作为- 6 - Bent 的定义，其本质是相同的. Bent 函数是非线性度最高的布尔函数，下面给出一些关于 Bent 函数的结论 . 定理 3.4 （存在性） 设mn2为任意正偶数，令mmmmxxxxxxxf22211)(则)(xf是一个n元 Bent 函数 . 定理 3.5设)(xf是n维 Bent 函数，A是2F上的nn阶可逆方阵，nFb2，令)()(bxAfxg，则g也是n维 Bent 函数 . 定理 3.6设)(xf是任意一个n维布尔函数数，则),(),(2
15、1112121nnnnnxxxfyxyxyyyxxxg是n2维 Bent 函数 . 虽然 Bent 函数拥有最高的非线性度，但是Bent 函数却没有作为密码函数最基本的性质均衡性. 下面简单地给出两个构造方式，可以通过对Bent 函数进行改造，使其具有均衡性. 定理 3.7 高非线性度均衡布尔函数构造方法构造方法1.取定k2个n2维 Bent 函数ag，其中ka2. 其中的12k个函数满足nnayxyxyxg11),(另外12k个函数形状为nnayxyxyxg11),(定义nk2维布尔函数),(),(yxgzyxfz，则11222nknk fN且f均衡 . 构造方法2. 设有n2维 Bent
16、函数nnyxyxyxf11),(，定义n2维布尔函数),(yxh如下：0,0),(),(21xyyyxyxfyxhn则112222nnn hN，且h均衡 . 第四部分：布尔函数的差分均匀度以及完全非线性函数差分分布的均匀性是密码函数的一个重要的安全性指标，差分密码分析方法的成功正是通过布尔函数差分分布的不均匀性实现的. 函数的差分均匀性越好，那么- 7 - 函数抵抗差分攻击的能力就越强. 用来刻画布尔函数查分分布均匀性的指标是差分均匀度 . 定义 4.11设f是从有限群A到有限群B的函数，令bxfaxfAx BbAaf)()(|maxmax0则称f为函数f的差分均匀度 . 定理 4.1设f是从有限群A到有限群B的函数，则ABAf由之前的谈论知差分均匀度越小，布尔函数的安全性就越高. 定理 4.1 给出了差分均匀度的一个下界，由此引
