布尔函数的密码学性质的研究(可编辑)

布尔函数的密码学性质的研究(可编辑) 布尔函数的密码学性质的研究 西安电子科技大学 博士学位论文 布尔函数的密码学性质研究 姓名:周宇 申请学位级别:博士 专业:密码学 指导教师:肖国镇 20090901 摘 要 布尔函数在密码学和通信领域有广泛的应用(论文研究了布尔函数的一 些性质(取 得以下主要结果: 重量的布尔函数，从布尔函数的汉明角度给出了平方和指标的下界 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 达式，同时得 到了布尔函数的非线性度上界的汉明重量表达式:从Bent函数角度构造了两类平 方和指标和绝对值指标较小的布尔函数( 2 (基于一个布尔函数的全局雪崩准则 GAC ，提出了两个不同布尔函数的互相关函 数所对应的全局雪崩准则:平方和指标和绝对值指标，给出了这两个指标的上下界( Walsh谱与互相关函数的一些性质( 3 (通过研究具有线性结构的布尔函数的性质，利用Walsh谱和汉明重量得到了布尔 函数不具有k维线性结构的充分条件，进而给出了具有线性结构的弹性布尔函数 新的非线性度上界( 4 (基于代数厚度的定义，研究了一些布尔函数代数厚的关系式，得到仿射函数、相 关免疫函数、部分Bent和Bent函数的代数厚度上界是2?1，在此基础上改进了 k 2?k?孚 次基本对称布尔函数代数厚度的上界( 5 (基于线性子空间理论给出了一个布尔函数在给定仿射空间上是k一正规的充要条 件，同时给出布尔函数满足k一正规时k和其的汉明重量的关系，进而给出了判断 一个布尔函数是否是k(正规的算法，经分析此算法较对所有的k维空间进行搜索 计算量小，易于实现( 6 (利用Krawtchouk多项式和组合数学讨论了等重对称布尔函数的密码学性质，给 出了等重对称布尔函数?以s^谱的表达式，利用此表达式给出了等重对称布尔函 数的非线性度，相关免疫性，扩散性，平衡性等，结果表明这类函数不 具有较好的密 码学性质( 关键词:布尔函数全局雪崩准则代数厚度正规布尔函数等重对称布尔函 数 Krawtchouk多项式 Abstract Booleanfunctionshavewide instream andblock Cryptographic applicationciphers dissertation thebasic ofBoolean ciphers(This investigatestheory some Theauthorobtainsmainresultsasfollows: ofBooleanfunctions( properties is is Oilthe resultofGACwhichderivedSon lowerbound by 1 (The analyzed(A of Booleanfunctionswith concluded(the weight七is sum-of-squaresany Hamming with is of boundon k nonlinearityHammingweightgiven(The expressionupper hasthelowerabsolutecriterionandthelowersumof twoconstructionswhich square isobtained( criterionfromBentfunctions measurethecorrelativebetweentwoBoolean on degree functions， basedGAC， 2 (To the indicatorandtheabsoluteindicatorofcross-correlationare 8UrTb-of-squares pro- twoindicatorstheGAC X(M( posed(The improve criterion whichproposedby and and boundsonthetwoindicatorsareob- ZhangY(L(Zheng (Lowerupper some betweenWalsh andcross―correlationfunc- tained，andproperties spectrum tionsare given( the Some ofBooleanfunctionswithlinearstructureare 3 ( properties presented(By methodsofWalshtransformandthe sufficientconditionOila Hammingweight，a Booleanfunctionwithoutklinearstructureisderived(Anboundonnonlin- upper with theseresults( ofaresilientfunctionlinearstructureisdeduced by earity of of onthedefinition algebraicthickness， somerelationshipsalgebraic 4 (Based boundon thicknessofaffineBoolean thicknessarederived(The upper algebraic functions，correlation Bentfunctionsand immunity，Bentfunctions，partially functionsareatmost tothisfactan boundon plateaued 2“,(According upper thicknessof Booleanfunctionsof佗 variableswith algebraic elementarysymmetric algebraicdegree improved( k 2?k?孚 is Basedonthe of sufficientand conditiononwhether a necessary theorysubspace， aBooleanfunctionisnormalornotisobtained(A betweentheHam- relationship ofBooleanfunctionandthedimensionkofa affme is given subspace ruingweight tocheckwhethera Booleanfunctionis discussed(Furthermore，all given algorithm forthe k-normalis isbetterthanthemethodwhichisused given，this algorithm enumerationofallk―dimensionalaffine subspaces( Krawtchouk combinatorial of and By polynomial Mathematics， someproperties 6 ( the Booleanfunctionsarediscussed(TheWalsh of equal-weightsymmetric spectra is Booleanfunctions cryptographicprop- the given(Some symmetric equal((weight and obtained， balanced are immunity，PC nonlinearity,correlative erties including functionisbadfor Boolean thatthe theseresults symmetric implies equal―weight properties( cryptographic characteristics for avalanche functionthecriterion global Keywords:Boolean Booleanfunctions normalBooleanfunctions thickness equal??weightsymmetric algebraic Krawtchouk polynomial 符号说明 符号 意义 符号 意义 马 二元域 二元域上亿维向量空间 + 实数域上加法 二元域上加法 玩 佗元布尔函数全体 毋。A 佗元仿射布尔函数全体 L。 亿元线性布尔函数全体 ，扛 的非线性度 deg f ，@ 的代数次数 ， z 的支撑集 wt y 布尔函数f z 的汉明重量 向量Q的汉明重量 F fo妒。 ， z 在Q处的Walsh谱 ，@ 的绝对值指标 o ， z 的平方和指标 ，扛 和9 z 的绝对值指标 of，g ，@ 和9@ 的平方和指标 亿元k重对称布尔函数 佗元i次对称布尔函数 吼 z 次数为i的Krawtchouk多项式 集合A的元素个数 IAI ，@ 的代数厚度 k阶扩散准则 M泐唰今?川?瑚泖 PC k 严格雪崩准则 Q 毋上可逆n×n矩阵 实数t取下整 线性空间U的维数 dim U ，@ 的线性结构空间 U上 线性空间U的对偶空间 空间直和 0 训,。1 曰上的全0向量 曰上的全1向量 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果( 尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人已 经发表或撰写过的研究成果;也不包含为获得西安电子科技大学或其它教育机构的学位 或证书而使用过的材料(与我一同工作的同志对本研究所做的任何贡献均已在论文中做 了明确的说明并表示了谢意( 申请学位论文与资料若有不实之处，本人承担一切相关责任( 本人签名:脚 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即:研究生在校 攻读学位期间论文工作的知识产权单位属西安电子科技大学(本人保证毕业离校后，发 表论文或使用论文工作成果时署名单位仍然为西安电子科技大学(学校有权保留送交论 文的复印件，允许查阅和借阅论文;学校可以公布论文的全部或部分内容，可以允许采用 保密的论文在解密后遵守此规定 影印、缩印或其它复制手段保存论文( 本学位论文属于保密在一年解密后适用本授权书( 本人签名: 日期 导师签名:堑垫 第一章绪论 第一章 绪论 密码函数在通信和密码学中有着广泛的应用(特别是在分组密码和流密码的算法设 计与分析中占用极其重要的地位(而密码函数的性质分析是基于密码函数的各种密 码体制的研究热点(本篇论文的研究内容是布尔函数的各种密码学性质(如全局雪崩 准则，非线性度，代数厚度，正规性和对称性等( 研究背景与意义 ?1(1 密码技术应用于军事和外交通信的历史可追溯道四千年前，但是直到1949年 Shannon发表了“保密系统的通信理论”f1161一文后，密码学才真正成为一门的科学( 上世纪七十年代中期，在密码学的研究中出现了两个引人注目的事件:一是1976年， Di伍e和HeUman发表的“密码学的新方向”f531开创了公钥密码学的新纪元，为解决 通信网络中的信息安全提供了新的理论和技术基础(另一个事件是1977年 美国国家标 准局 NBS 正式公布实施数据加密 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 DES (这两个事件标志着现代密码学的诞生( 随着计算机网络的迅速发展，各个国家从政府到民间对密码技术的研究越来越多，密码 从私钥密码到公钥密码实现了密码体制理论与技术以惊人的速度得到发展( 的突破，从 DES到AES的过程使密码算法越来越受到人们的重视( 密码函数主要用在流密码体制中，而流密码又称序列密码(序列密码的加密是用一 个序列与明文序列进行叠加来产生密文，解密用同一个序列与密文叠加来恢复明文(这 个序列一般称为密钥流序列，它决定着流密码的安全(如果产生的密钥流序列有某种规 律性或者能暴露某种特性，这对攻击者来说有很大的好处，所以怎样产生安全性高的密 钥流序列是流密码安全的关键(这里的安全性主要指随机性，确定性和可操作性，所以一 般采用伪随机序列f61】( 而密钥流的产生可以利用密钥流生成器来实现，而布尔函数正好能实现这个功能， 线性反馈移位寄存器 三FS可以将布尔函数作为密钥流生成器的主要部件( 兄 因其实现 简单，速率快，便于分析等优点而被广泛地用与各类数字电路中，也是构造密钥流生成器 的最重要部件之一(Rueppel【103】将这类密钥流生成器分解成两部分，其中LFSR部分 称为驱动部分，密码函数所在部分称为非线性组合部分(它们的任务分别是:驱动部分 控制存储器的状态转移，负责提供若干周期大，统计特性好的序列供组合部分使用，而非 线性部分则将由驱动部分提供的序列组合成满足 要求 对教师党员的评价套管和固井爆破片与爆破装置仓库管理基本要求三甲医院都需要复审吗 的，性质良好的密钥流序列，非线 性组合部分对线性部分产生的序列进行混淆和扩散( 易上礼级LFSR是由他个二元存储器与若干个岛上的乘法器和加法器连接而成， 其中ci，of?F2(每一存储器称为LFSR的一级，n为三FS尺的级数或长度(在第歹个移 送出,作为输出序列的一位(初始状态 ao，a1，„，a肛1 可由用户指定，而补入末端存 布尔函数的密码学性质研究 图1(1线性反馈移位寄存器 储器的aj+n之值由反馈函数或线性递归关系: aj押 0ciaj+n-i,J?0 t+1 确定(这样产生的一系列,经过一个布尔函数f x 的作用后就是密钥流序列，实现过 程为下图所示 图1(2组合生成器 同步流密码生成器的工作模式可以用方程式表示如下: bo ， n0，al，„，an-1 bl f L ao，al，„，an-1 1-1 ao，a1，„，?一1 b2 f L2 bm一1 f Lm-1 ao，al，„，an-1 多个输出的密文数字中，以便隐藏明文数字的统计特性;混淆是将密文和明文的统计特 性之间的关系复杂化(为此对布尔函数有很强的要求，例如，平衡性，非线性性，相关免 疫性，扩散性，全局雪崩准则，代数厚度，正规性，代数免疫等( 布尔函数不仅在序列密码体制的设计和分析中扮演着重要的角色，它也被用于分组 密码的设计中(DES是分组密码的一个最经典的例子，它的安全性取决于S盒密码学性 而S盒可以用多输出布尔函数来描述(分组密码中用到的各种置质的好坏， 换也可以看 第一章绪论 3 作多输出密码函数(可以看出，构造密码学性质优良的多输出密码函数是设计较高安全 性的分组密码体制的关键( ?1(2布尔函数的发展历史与现状 随着计算机的发展，人们对密码系统中的布尔函数的研究更加深入，出现了许多衡 量密码函数的指标， 总结 初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf 起来，主要有以下一些: 1，非线性度 为偶数，称达到最高非线性度的密码函数为Bent函数(这类密码函数的优点是能有效抵 抗线性攻击『56]和最佳仿射逼近 BAA 攻击(但这类函数的缺点是非平衡的，由于要是 产生的密钥流序列尽可能达到随机，就要是尽可能平衡，这限制了它在密码学中的广泛 应用(为了保留Bent函数的这种高非线性度，又要克服它的非平衡性，人们研究如何构 造平衡的高非线性布尔函数f56，59，107，112]( 2，相关免疫函数和弹性函数 了相关免疫函数『119](紧接着证明了布尔函数的相关免疫阶数，变元数和代数次数的 也提出了几种构造办法(这个概念受到国内外的广泛关注(特别制约关系， 是国内学者 文献【2l】中改进了上述结果得到m阶弹性函数Walsh谱的特点:F fo妒口 三0 mod 2m+2+【2学J，其中d为n元布尔函数f x 的代数次数(在S盒的设计中也用到弹 ，65，69，75，135](随着这个结果出现了大量关于相关免疫函性函数f41 数的研究文献 数的构造f35，41，66，69，75，96，135]( 68】( 3，扩散准则 1985年，Webster在研究如何设计S盒时，将“完全性”和“雪崩效应”这两个 了这个概念:高阶雪崩准则[1]和扩散准则 PC [100](这两个概念的思想完全体现了 Shannon所提出的混淆和扩散准则，研究的是布尔函数与其移位布尔函数的程度(这些 指标，如相关免疫性，高非线性度等【10，25，36，66，110-112，134]( 4 布尔函数的密码学性质研究 为了克服扩散准则在某些点 局部性 上的自相关值，使得布尔函数在整体上达到最 Zhang和Zheng发现了扩散性只能用来刻画布尔函数优(紧接着1995年， 在某些点的自 相关值，对于其他的点没有描述，所以为了克服扩散准则的这个缺点，使得布尔函数在整 体上达到最优，提出密码函数的全局雪崩准则 GAC f136]:绝对值指标和平方和指标( GAC告诫我们要从整体上把握布尔函数，受到密码学界的广泛青睐，产生一系列的相关 文献【42，62，87-89，120-124，126，133，140，142]( 4，代数厚度 在流密码和分组密码中除了研究布尔函数的非线性度外，还得考虑其它两个指标: 代数次数和代数正规型中单项式 非零的系数 的个数，Knudsen[72】和Laif76]分别提出 而由非线性布尔函数组合的多个线性反馈移位寄存器 LFSR 生成的序列中，其线性复 个数和代数次数来决定的，次杂度是由这个布尔函数代数正规型中单项式的 数低的布尔 寄存器 LFSR 的非线性布尔函数选取中，必须考虑高的代数次数和多的单项式( 而在密码攻击中使用的布尔函数常常用仿射等价的布尔函数来代替，这意味者代数 正规型中单项式的个数在仿射变换下可能会改变(所以在2003年Cadet提出代数厚度 Algebraic 规型中单项式的个数问题，在利用组合理论的基础上研究了代数厚度满足一 定条件的布 尔函数的个数界，提出了关于任意元布尔函数代数厚度的公开问题(这个指标的提出，对 衡量密码函数的复杂性有重要参考价值，对构造复杂性好的密码函数也有指导意义( 5，正规性 密码函数的正规性是近年来受到关注的一个密码学性质[12]，[23】，[30]，【37]，[52】'【57】( 尔函数在一个k o?k?n 维仿射子空间上为常数，则称之为k正规的(正规性反映了 布尔函数在一个仿射子空间上的局部特性，如果k越大，则会暴露布尔函数的较多信息， 所以布尔函数必须要求其正规性的仿射子空间的维数较低(但受到人们重视是2001年 后，出现了许多结果[12]，[23]，[30]，[37】，【52】'【57】(Dobbertin曾猜想所有的Bent函数都是 个给出了判定布尔函数正规性的算法【52】，文献【4，13】中也给出判定布尔函数正规性的 算法( 6，代数免疫 2003年后代数攻击成为一种有效而有趣的攻击方法【2，3，44，45，77】:通过建立初 XL算法[117]、GrobnerBases算法等 来求解超定的多元高次方程组方法、 以获得初始 密钥(代数攻击被成功地应用于一些基于LFSR的流密码系统中(为了抵抗代数攻击， 第一章绪论 Immunity :也 Meier等[93】引入一个布尔函数的新的密码学性质:代数免疫 Algebraic 就是在方程 1(1 中用f x 的零化子代替，@ ，得到一个新的方程组，零化子的代数次数 越低，新方程组所含的变元个数越少，代数攻击的复杂度越低(代数攻击的 数学描述为: f x 1的点Lij ao，al，„，an-1 O 1，2，„ (有 l |I 。 O ? 跏 一 2 ll 口(俨 口 ? 0 肌一 3 2 II 驴 口 O ? 骱 “从“ 一 ( 一 ， 咖 o 0 咖 跏 “ 一 元个数(所以代数免疫就定义为布尔函数零化子的代数次数最小 值(Courtois和Meier 『441证明了n元布尔函数的代数免疫阶的上界是『等1(代数攻击的出现给密码函数的分 析和设计提出新的课题f2v]，[31】，【45]，【51】(具有最大 优 的代数免疫阶的布尔函数成为人 们感兴趣的研究课题f5，49，51，7s]( 由于人们对非线性理论知之甚少，加之密码体制本身的缺陷，构造具有优良密码学 性质的密码函数不是一件容易的事( 内容安排及主要结果 ?1(3 论文共分五章(第一章介绍密码函数的研究背景、发展历史与现状;第二章介绍本。 第三章介绍布尔函数的文研究所涉及到的数学理论和布尔函数的相关知识: 全局雪崩准 则和非线性度;第四章介绍布尔函数的两个密码学指标:代收厚度和正规性;第五、六章 介绍了等重对称布尔函数的密码学性质( 第二章介绍了本文研究所涉及到的数学理论和密码函数相关背景知识，在数学理 有限域和线性空间和仿射子空间等;在密码函数方面主要论方面主要包括: 包括:布尔 函数的表示和布尔函数的各种安全度量指标( 第三章介绍了布尔函数的全局雪崩准则的概念和自相关函数的一些性质;利用 Son在文献f120]中的不等式得到了仅从布尔函数的汉明重量角度给出的平方和指标的 下界表达式，紧接着构造了一类平方和指标和绝对值指标较小的布尔函数:然后推广了 一个布尔函数的全局雪崩准则，得到两个不同布尔函数的互相关的全局雪崩准则，并且 给出了这个指标的上下界;最后讨论了具有线性结构的布尔函数的性质，并得到此时弹 性函数的新的非线性度( 第四章利用矩阵理论研究了Carlet提出的布尔函数代数厚度，得到了一些代数厚 数的代数厚度的上界，特别是改进了对称布尔函数代数厚度的上界: 6 布尔函数的密码学性质研究 第五章介绍了布尔函数的正规性定义，基于线性空间的理论给出了布尔函数在一个 给定空间上是否为正规性的判断条件，提出了判断布尔函数是否正规性的算法;最后，研 究了三谱值函数的一些性质( 第六章介绍了对称布尔函数的两大类:等重对称布尔函数和基本对称布尔函数， 并给出了两者的联系;重点给出了等重对称布尔函数的一些密码学性质:相关免疫性，非 线性度，平衡性，代数次数，扩散性等，也给出了Krawtchouk多项式的一些性质( 主要研究结果: 1 (分析了Son关于n元平衡布尔函数的全局雪崩准则 GAC 的结果推广到了任意 汉明重量的布尔函数，得到了任意汉明重量的布尔函数的平方和指标的下界表达 式，使得仅从汉明重量角度就能给出其对应的布尔函数的非线性度;从Bent函数 角度构造了两类平方和指标和绝对值指标较小的布尔函数( 2 (基于布尔函数的全局雪崩准则 GAC ，提出了两个不同布尔函数的互相关所对应 的全局雪崩准则:平方和指标和绝对值指标，给出了这两个指标的上下 界，同时也 得到了布尔函数Walsh谱与互相关函数的一些性质( 3 (通过研究具有线性结构的布尔函数的性质，利用Walsh谱和汉明重量得到了布尔 函数不具有k维线性结构的充分条件，进而给出了具有线性结构的弹性布尔函数 新的非线性度上界( 4 (在对一般布尔函数代数厚度的研究基础上，得到仿射函数、相关免疫函数、Bent 函数、部分Bent函数和plateaued函数的代数厚度的上界不超过2铲1，在此基础上 改进了k 2?k?孚 次基本对称布尔函数代数厚度的上界( 5 (基于线性子空间理论给出了一个布尔函数在给定的空间上是k(正规的充要条件， 同时给出布尔函数满足k(正规时k和I x 的汉明重量的关系，进而给出了判断一 个布尔函数是否是k一正规的算法，经分析此算法较对所有的k维空间 进行搜索计 算量小，易于实现( 6 (利用Krawtchouk多项式和组合数学讨论了等重对称布尔函数的密码学性质，给 出了等重对称布尔函数?oZs危谱的表达式，利用此表达式给出了等重对称布尔函 数的非线性度，相关免疫性，扩散性，平衡性等，结果表明这类函数不 具有较好的密 码学性质( 7 第二章基础知识 第二章 基础知识 本文的许多研究结果都是建立在数学理论的基础上的(本章第一部分介绍代数和有 限域等相关数学知识(第二部分介绍布尔函数的基本概念，基础理论 以及密码函数的 各种度量指标( 有限域 ?2(1 这里我们将主要介绍群，环，域等概念( 定义2(1 设G是非空集合，并在G中定义了一种代数运算“o"，若满 足下述条 o b?G( 1 封闭性(对任意a，b?G，恒有a o 2 结合律(对任意的a，b?G，有 ab oC a。 b。c ( o o e ea a( 3 G中有一恒等元e存在，对任意a?G，有e?G，使a oa e( 4 对任意a?G，存在a的逆元a-1?G，使a。a一1 a一1 则称G构成一个群( 上述定义中，G的运算“o”可以是通常的乘法或者加法(若为乘法，则恒等元称为 单位元;若为加法，则恒等元记为0;a的逆元记为一口( G 群G中所含元素的个数称为群G的阶，记作I1(若群中元素个数有限，称为有限 群;否则，称无限群(如果群G的运算满足交换律，则称它是交换群或Abel群(把运算表 示成加法形式的Abel群称为加群(如果群G的所有元素都可由其中的一个元素来生成， 则称它是循环群(循环群必然是Abel群( 有了群作为基础，下面我们给出环和域的概念和性质( 定义2(2 交换环 R，+，?? 是一个具有两种二元运算“+’’和“(”的代数系统， 它满足性质: 1 R，+，?? 关于其加法是一个加群，即Abel加法群( 2 R，+，?? 的全体非零元关于其乘法构成一个可交换半群( 定义2(3 模佗剩余类环 磊，+，?? 简记作磊 是由整数集的亿个模n剩余类所构 成的交换环(它保留了整数的加法和乘法运算( 布尔函数的密码学性质研究 但是需要注意的是，如果佗为合数，磊的乘法幺半群是有零因子的，即存在非零元 a，b?磊，使得ab 0( 定义2(4 F是一个非空集合，若在F中定义了两种运算:“+’’ 加法 和“??” 乘 法 ，且满足以下性质: 1 F关于加法元算构成Abel群(加法单位元记为0( 2 F中所有非零元素关于乘法构成Abel群(乘法的单位元记为1( 3 对任意的8，b，C?F，加法和乘法之间存在如下的分配律: a?? b+C a??b+a??c; b+C ??a b??a+C??a( 则称F是一个域( 可以看出域是环的特例( 由有限个元素所构成的域称为有限域，或称为伽罗瓦 Galois 域(域中的元素个数 称为该有限域的阶(B表示q阶有限域( 设F是任意一个域，而e是它的单位元素(如果对于任意正整数m，都 ?0，我 有me 们就说F的特征是0，或F是特征0的域(如果存在正整数m使me 0，那么就说F的 特征不等于O，而适合条件pe 0的最小正整数P就叫做F的特征，或者说F是特征P 的域(所以我们就知道任意一个域F的特征或者是0，或者是一个素数P(进而有 定理2(1 设F是任意的域，用n表示F的素域 F的最小子域 ，那么当F的特 征是一个素数P时，?就与域磊同构;而当F的特征是0时，n就与Q同构( 而对于特征为P的域F有下面性质( 定理2(2 设F是特征为P的域，a和b是F中任意两个元素，而n是任意非负整 数，那么一定有 o+6 矿 ap”+bp“( 有了域的基础，可给出域上多项式的概念( 定义2(5 含有一个未定元数z的域R上的多项式定义为 ，@ nnzn+n仉一1zn一1+„+alx+ao， 其中ai?fp，i 0，1，2，„，’2，且用昂九表示系数取自域B上的一切多项式集合( 有了上面的基础我们可以给出多个变量的多项式(设z1，X2，„，zn是域日上的n 个符号，设kl，k2，„，?是非负数，ak，乜„k?局，称 m-，X2„，zn ?aklk2(((kz 1xk22„z争， kl，k2，„，Jk 为域R上的亿元多项式( 9 第二章基础知识 线性空间和仿射子空问 ?2(2 首先介绍线性空间和子空间( 定义2(6 如果域F上的扎重元素集合y满足下述条件时: 1 V关-3 力n法元算构成Abel群( 2 对y中任何元素V和F中任何元素c，满足CV?V，我们称y中元素 V为矢量 或者向量，F中的元素C为纯量或者标量，称乘c运算为数乘( 3 分配律成立，对任何札，u?V，c，d?F恒有: C?? 乱+V C??t正+c??秽; C+d ??V C??V+d??V( 4 若c，d?F，V?V，有: cd v c 如 ;1??V V，1?只 则称y是域F上的一个佗维线性空间或者矢量空间( 定义2(7 若子集??V，且满足线性空间的条件，则称?是y的一个子空间( 域F上的矢量V1，v2，„，仇的线性组合定义为 让 bxvl+b2v2+„+kVk，bi?F 1?i?七 ( 则我们有 定理2(3 线性空间y中矢量Vl，V2，„，V七的所有线性组合所构成的集合S是y 的子空间( 定义2(8 设V1，V2，„，讥是线性空间y中的一组非零矢量，当且仅当存在有一组 不全为零的纯量C1，C2，„，ck ci?F，i 1，2，„，k 使 0 ClVl+C2V2+„+cku知2 成立时，则称这组矢量线性相关，否则，称这组矢量线性无关 或者线性独立 ( 根据线性相关的定义可知:非零矢量V。，V2，„，毗为线性相关的充要条件是:存在 有一个矢量vi 1?i?七 ，它可以表示成其余矢量的线性组合( 定义2(9 在任何线性空间中，能张成该空间的线性独立矢量的集合称为该线性空 间的基底，而称这组线性独立矢量的数目为该线性空间的维数，若基底中矢量的个数为 有限，则称为有限维线性空间，否则称无限维数线性空间( 如果线性空间y中存在k个线性独立的元素，并且在y中不存在多于k个元素所 构成的线性独立元素组，则称线性空间y的维数为k，并称y为k维线性空间，记作 dim V k( 10 布尔函数的密码学性质研究 同时两个n维向量a，b的内积 或点积 表示为: a??b al，a2，„，an ?? bl，52„，k 口16l+a262+„+?k ai，bi?F 是一个纯量( a，b矢量互为正交， 定义2(10 设E为线性空间霹的一个子空间(如果E7为与E中所有向量都正交 的曰的全体向量所构成的集合，即 El o?露la??b o，Vb?E ， 则E7也是曰的线性子空间，并称之为E的零化空间，或者对偶空间，记为‖ E上( 下面给出空间直和概念( 定义2(11 设E，E7是线性空间曰的子空间，所有能表示成011+O,2 O,1?E，Ol? E7 的向量组成的集合，称为E与E7的和，记为E+F(如果E+E’中的每个 向量Q的 分解式 口 Q1+Q2，Or'1?E，a2?EI E7( 是唯一的，这个和称为直和，记为叼 E0 在线性空间和其子空间的基础上，我们可给出仿射子空间的概念( 定义2(12 o 如果V是曰上的一个k维子空间，b?叼，则yb称为叼上的 k维 仿射子空间( 可见子空间是仿射子空间的一个特例( ?2(3布尔函数理论 在许许多多复杂的现代化设备中都少不了一个基本的元器件，即逻辑电 路(这是一 种在其输入和输出之间有一定逻辑关系的电路(这种电路的输入和输出间通常都是用脉 冲的有无或电位的高底来表示的(然后运用数学中的一些基本的公理及定理对其进行数 便可得到合乎逻辑的结果(在此基础上发展出了一门重要学科，称学运算， 为布尔代数 学( 作为表示逻辑运算的函数，布尔函数是研究数字逻辑电路的重要数学工具，也是研 究以此为基础的一切科学技术的重要工具，从而也是研究密码学和密码技术的重要工具( 无论在流密码还是分组密码中，无论在私钥还是公钥密码中，布尔函数都有很重要的应 用(尤其在流密码中，所使用的主要数学工具之一就是布尔函数(本节我们介绍布尔函 数的基本概念和研究方法( 第二章基础知识 2(3(1布尔函数的表示 n元布尔函数y x1定义为: ， z :露_马， 其中X Xl，X2，„，X几 ?曰( 为了方便我们用鼠表示曰上的n元布尔函数的全体(用0表示局，曰， Bn上的 加法( 布尔函数的表示方法有很多种，这里我们主要介绍真值表，小项表示， 多项式表示， Walsh谱表示( 1，真值表 布尔函数由于其定义域和值域都是有限集，自然可以用列表法表示( 例如，下表定义一个二元布尔函数y x y z1，z2 :表中左列是X的 值，右列是相应 表2(1布尔函数y z y x1，X2 的例子 Xl X2 ，扛 0 0 0 0 1 1 1 0 1 1 1 0 的函数值，0 (我们把这样的一个表称为， z 的真值表(把右列函数值构 成的矢量称为 为使得， z 1的z取值的集合，即 Supp y z?F多I， z 1 ( 可知，wt y Isupp y I( 但是列表法表示的实函数不一定有解析表达式，而任何布尔函数都有解 析表达式( ( 2， 小项表示 对于Xi，q?F2，规定 Xj 毛，《0 瓦( 于是 凯产州 z孑: 1’ 当Xi?q时( 【0， 设 c Cl，C2，„，, ，X Xl，X2，„，, ( 布尔函数的密码学性质研究 则具有下述“正交性”: 茎 三::三::::::三:;蓁:兰:芝::::: 三;筹( 《1z字„z挈 三: 为了方便，记 zilz字„z挈 z。 于是 2n一1 m o， Q 铲， i 0 上式称为f x 的小项表示，其中的求和符号是指在咒上，每一个被加项称 为一个小项( 小项表示实际上是布尔代数表达方式，即逻辑表示(此种表示法常用于布尔 函数的设计 实现( 同时还有另外的一种写法:设 即，t wt f ，则 t f x-，X2，„，Xn ?莎 zl。Q1 z2。臼2 „ z。。Gn ， o o 这种小项表示很容易得到布尔函数f x 的汉明重量，其中 XlQ1 z2 o ci2 „ zn 确定(称矩阵 CllC12 Cln C21C22 C2n ??? Ctlct2 ctn 为佗元布尔函数f x 的特征矩阵( 如果将小项表示展开合并则变成多项式的形式(所以下面我们给出布尔 函数的代数 正规型表示( 3(多项式表示 任意f x ?玩都能表示成代数正规型的形式 ANF : o o„。012-((nzlX2„? f xl，,„，zn ao aijxixj o溉。o 0 lSt?他l i j n 其中ao，啦，aij，„，a12„n?F2( n元布尔函数f x 的代数次数，deg f ，是变量最多的非零单项式的变元个数(代数 记为厶，若其常数项为零，则称为次数最多为l的布尔函数称为仿射函数， 线性函数，记 为厶。 第二章基础知识 13 每一个线性函数都可表示成: Q222o„oQnzn， 妒Q z n??z alzl?D 其中口 Q1，口2，„，口n ?，?，z Xl，X2，„，zn ?，7( 有了前面的基础，下面我们给出n元布尔函数的Walsh谱表示( 4(Walsh谱表示 定义2(13 定义为: F ， z 。? ? 一1 他m出 ( 特别地，f x 是平衡的当且仅当F f 0( Walsh变换的逆变换为 o妒。 一1 抛( f z 2肛1―2州?F f 口?霹 有了Walsh谱的定义，可以给出非线性度的定义( 定义2(14 设f x ?鼠，则f x 的非线性度 ?， 定义为 F m 。? 1( ?， 2?一互1嬲l 从密码学角度来看，希望所选用的布尔函数f x 的非线性度越大越 好(由非线性度 F ， z 。? |尽可能的小??但是根据Parseval等式: 的定义可知，需要口m?a殿x ?F2 f x 。妒口 2轨( 口?露 所以， I F m o妒a I?2号 。m?a矸x F ， z 。? l取得最小值2号时，称这时对应的布尔函 数为Be秕函 此时当Qm?a毋x 数【102]，但是这时17,必须为偶数( 所以我们就知道 定理2(4 设f x ?风，则 ?，?2n,一2三一( 2(3(2布尔函数的安全指标 布尔函数有很多安全指标，如相关免疫性，严格雪崩准则，扩散准则，全局雪崩准则， 代数免疫性，代数厚度，正规性等(这节介绍这些指标( 14 布尔函数的密码学性质研究 1，相关免疫性 相关免疫性的概念是为了防止密码分析者或者攻击者对流密码进行相关攻击最早 由Siegenthaler【119]提出的(下面给出其定义和等价刻画( 定义2(15 设z f x1，z2，„，zn 是n个彼此独立，均匀分布的二元随机变量的 布尔函数，称， z 是m阶相关免疫的当且仅当z与z1，X2，„，zn中任意m个随机变量 ，z 。，„，X?统计独立，或者，当且仅当互信息 毛。 ， 名;虢1，Xi2，„，Xi。 0 对任一组i1，i2，„，?，1?i1?i2?„?im?佗成立( 或者等价于 定义2(16 设, x ?Bn，z1，z2，„，zn是易上的独立的，均匀分布的随机变量( 如果对任意的 al，a2，„，am ?霹 m?72 和a?足，都有 元都统计无关，则称, x 是m阶相关免疫的 CorrelationlTl2muTl息 ( 平衡的m阶相关免疫函数称为m阶弹性函数(平衡的但没有相关免疫性 的布尔函 数的可以看为是0阶弹性函数( 下面给出Xiao-Massey定理，它刻画了相关免疫函数的谱特征( 定理2(5 u?毋且1?wt w ?m有 F f0, 0( 同时Cadet在文献【21]中给出了仇阶弹性函数Walsh谱的特征: 定理2(6 设, x ?鼠且deg f d(若f x 是m阶弹性函数，则 mod2m+2+【下n--yr(--2J( F f?B? 兰0 rood2m( 可看出m阶相关免疫函数, x ?Bn其汉明重量满足wt f 兰0 最后我们给出代数次数，变元数和弹性阶的制约关系: 定理2(7 【119】设f x ?鼠且deg f k(若, x 是m阶相关免疫， 则 k+m?n( 若f z 还满足平衡性且f?m?n一2，则 k+m 佗一1( 第二章基础知识 2，严格雪崩准则与扩散准则( Webster[130]在研究S盒的设计时，将“完全性”和“雪崩效应”这两 个概念进行 Avalanche 了组合定义了一个新的概念:严格雪崩准则 Strict Criterion ，记作SAC( 概念进行了一般化，引入了高次扩散准则 PropagationCriteria 的概念，记作PC( 定义2(17 o f xQ 表示f z 在点 设f x ?Bn，a?曰(用Ds a 0 f x o a处的差分( 1 使Dl a 为常数的Q，称为f z 的线性结构( f z 满足严格雪崩准则，记为SAC( 次扩散准则，记为PC k ( 可知f z 的线性结构构成毋的一个线性子空间( 在f x 在点Q的差分基础上，可给出自相关和互相关的定义( 定义2(18 设(厂 z ，g z ?玩，OL?曰，则f z 的自相关函数为: ?水 ? 一1 D小 -? 一1 他M‘咖’， z?霹 z?―F? f z 和g z 的互相关函数为: ?幻 a ? 一1 D，??，‘口 ? 一1 m’。如钒 ( Avalanche Characteristics 来克服扩散准则在某些点的值，使密码函数在整体上达到最优( 进而给出全局雪崩准则 GAC : 定义2(19 8urn 设f z ?玩，则f x 的平方和指标定义 theofsquart 为 町 ??; Q ; 口?毋 absolute f z 的绝对值指标 thevalue 定义为 。 l?小 I??。、 ’’ ?， 口暴器o口?霹，口?O。 町和?，越小，f z 的GAC性质越好( Zhang和Zheng在文献【136】中已经证明了这两个指标的上下界: 22n?o'y?23n( ’0??，?2n， 16 布尔函数的密码学性质研究 3，代数厚度与正规性 Carlet在文献[231124][27]中提出代数厚度 AlgebraicThickness 概 念，用来衡量一 个密码函数在仿射变换下其代数正规型中单项式的个数问题(这个指标是从复杂度角度 给出的( 定义2(20 z??B o b，其中B?Q。，b?曰(f x 的代数厚度定义为， 7-0 的代数正规型中具有非 零系数单项式的最小个数，记为乃( 定义2(20中的7I z 也称为仿射变换(在代数厚度定义的基础上可知对任意的布尔 函数f x ?Bn，其代数厚度乃是， 7( z 的代数正规型中具有非零系数单项式的最小 个数，等价于机算布尔函数 ， 丁 z (厂 f?? z ，f2 z ，„，In z 的单项式的个数，其中如 z ，12扛 ，„，zn@ 是仿射函数且其线性部分是线性独立的( Dobbertin『561提出了正规性，这个指标反映了密码函数在某一个子空间上的特性( 定义2(21 设， z ?Bn，如果f x 在叼的一个【詈J维仿射子空间上是常数 仿 间上是常数 仿射函数 ，则称f x 是 弱 k-正规的( 文同时献【13，37]已经给出了:若， z ?玩是尼-正规的，则非线性度 ?， 满足: 2“,一2七一( ?，S 4， 代数免疫 Immunity 概念用来抵 抗 Meier[931等引入一个密码函数的代数免疫性 Algebraic 代数攻击( 定义2(22 个零化子(记 AN f 夕 z ?BnI， z 9 z o deg g 为， z 的代数免疫阶，其中 为，@ 的所有零化子的集合，称AI f 2加m ?sin o S AN f t3AN f1 ( Meier和Courtois在文献【93]中给出了代数免疫阶的上界是: 定理2(8 设f x ?Bn，则AI f ?『詈1( 17 第二章基础知识 同时Li[78】也得到了具有最大代数免疫的奇数元对称布尔函数， 】构造了代 Dalai【51 数免疫阶最大的的布尔函数:设， z ?B竹， 1 如果n是奇数，那么 ， zl，z2，„，zn :0，如果wt zl,z2，„，zn ?【昙J， 1，如果wt x1，X2，„，zn ?f芸1( 厶 2 如果佗是偶数，那么 f x1，z2，„，zn 0，如果wt xl，X2，„，z。 芸， 1， 如果wt x1，X2，„，zn -“5， bxl，材嘞?F2，如果wt xl,z2，„， zn in( 可知这样构造的布尔函数具有最大的代数免疫阶( ’ ’ 本章小节’ ’ ?2(4U 本章我们介绍了密码函数的数学基础:群，环，域和线性空间，最后给出了密码函数 的基本知识和安全性指标，这些是本文后续工作的基础( 19 第三章布尔函数的全局雪崩准则和非线性度 第三章 布尔函数的全局雪崩准则和非线性度 本章的研究是基于Walsh谱，自相关函数和互相关函数基础上的(全局雪崩准则 GAC 【136】是用来克服布尔函数在某些点上的自相关值，使整体上 达到最优(Son 在此基础上得到平衡布尔函数的GAC指标的下界[120]，但对于不同的布尔函数