（应用数学专业论文）生成具有优良密码性质布尔函数的方法.pdf

摘要 具有优良密码性质的布尔函数在密码研究和应用中具有重要的意义，在流 密码的安全设计中尤为重要；采用优良密码性质的布尔函数的密码体制可以抵 抗多种已知的密码攻击 本文首先介绍了布尔函数密码性质的一些基本概念和定理，并简要的介绍 布尔函数的基本构造方法 然后介绍一类具有较高非线性度和最大可能的代数次数的n 元m 阶弹性 函数的构造 sm a i t r a 对两个m a i o r a n a m c f a r l a a d 方法构造的合适的b e n t 函数 级联得到的布尔函数进行修改，这样可以构造得到具有最优代数次数和非线性 度为2 n 一2 孚的n 元乎衡函数和1 阶弹性函数本文对这一修改方法做了进 一步扩展，把构造中的常数值函数修改为海明重量为奇数的任意布尔函数，保 持了原有函数的平衡性，代数次数和非线性度，这样就可以构造出更多的平衡 函数和1 阶弹性函数；而sm a i t r a 所构造的函数仅仅是它的一个特殊实例把 上述新构造得到的函数作为初始函数，通过递归运算来获得具有尽可能最优的 代数次数和非线性度的更高阶弹性函数与sm a i t r a 所能构造的函数相比，本 文构造出的函数不但在代数次数，相关免疫度，平衡性，非线性度方面保持了 原有的优良密码性质，而且在数量方面有进一步的增加 本文还研究了sm a i t r a 提出的1 阶弹性函数进行次数最优化的一种方法 在次数最优化的过程中，由于改变了函数真值表中的4 个比特，使得函数的非 线性度可能会增加4 ，减少4 ，或者保持不变本文对次数优化过程中非线性度 的影响进行分析，并给出了决定非线性度变化相应的判定定理；利用这些判定 定理，给出1 阶弹性函数次数最优化的一系列算法，在对函数进行次数最优化 的同时，使得非线性度增加4 或者保持不变这样就得到具有更高非线性度和 最优代数次数的1 阶弹性函数本文将这些算法应用于6 元和8 元代数次数非 最优化的1 阶弹性函数 本文还将介绍布尔函数的基本运算以及本文所提到的n 元m 阶弹性函数 的构造和1 阶弹性函数次数最优化的一系列算法的实现在算法实现的过程 中，将广泛使用一些表单和关于h a d a m a r d 矩阵的快速算法表单主要有三个： 长度为8 的比特串中“1 ”个数，“1 ”个数的奇偶性以及比特的逆序排列；这 三个表单的使用可以节省程序的运行时间；计算w a l s h 谱，自相关性以及r e e d m u l l e r 谱中都采用了h a d a m a r d 矩阵的快速算法，将原有算法的计算复杂度从 o ( 2 n 2 n ) 降到o ( n 2 n ) ，极大的提高了运算速度 最后，总结本文的主要工作和它的意义，并指出工作的不足之处 关键词：平衡性；非线性度；相关免疫度；弹性；代数次数 a b s t r a c t i ti sw e l l k n o w nt h a tb o o l e a nf u n c t i o n sw i t hg o o dc r y p t o g r a p h i c p r o p e r 。 t i c sp l a ya mi m p o r t a n tr o i ci ne r y p t o g r a p h i cr e s e a r c ha a da p p l i c a t i o n se s p e c i a l l y i nd e s i g n i n gs e c u r es t r e a mc i p h e r s c r y p t o s y s t e mp o s s e s s e sg o o dc r y p t o g r a p h i c p r o p e r t i e st ow i t h s t a n dt h ek n o w nc r y p t a n a l y t i ca t t a c k s f i r s to fa l l lt h i sp a p e rp r e s e n t st h eb a s i cd e f i n i t i o n sa n ds o m ei m p o r t a n t t h e o r e m sa b o u tc r y p t o g r a p h i cp r o p e r t i e so fb o o l e a nf u n c t i o n s ，i tg i v e ss o m e b a s i cm e t h o d sf o rc o n s t r u c t i n gg o o db o o l e a nf u n c t i o n s t h e nt h ep a p e ri n t r o d u c e sm e t h o d so fc o n s t r u c t i n gn v a r i a b l e ，m r e s i l i e n t f u n c t i o n sw i t hm a x i m u mp o s s i b l ed e g r e ea n dv e r yh i g hn o n l i n e a r i t ysm a i t r a s h o w st h a tb ya l g e b r a i c a l l ym o d i l y i n gt h ec o n c a t e n a t i o no ft w op r o p e r l yc h o s e n m a i o r a n a m c f a r l a n db e n tf u n c t i o n s ，n v a r i a b l eb a l a n c e df t l n c t i o n sa n d1 一 r e s i l i e n tf u n c t i o n sw i t hm a x i m u m p o s s i b l ed e g r e ea n dh i g hn o n l i n e a r i t y2 ”一2 孚 c a l lb ec o n s t r u c t e d t h i sm o d i f i c a t i o ni sf u r t h e re x t e n d e di nt h i sp a p e r ：c o n s t a n t f u n c t i o n sm e n t i o n e di nm a i o r a n a m c f a r l a n dc o n s t r u c t i o na r ea l t e r e dt oa n y b o o l e a nf u n c t i o n sw i t ho d dh a m m i n g w e i g h tw h i l eb a l a n c e d n e s s ，a l g e b r a i cd e g r e e a n dn o n l i n e a r i t yr e q u i r ek e e p i n g ；s om o r eb a l a n c e df u n c t i o n sa n d1 一r e s i l i e n t f u n c t i o n sc a nb ec o n s t r u c g e d ；b o o l e a nf u n c t i o n sc o n s t r u c t e db ysm a i t r aa r et h e o n l ys p e c i a lc a s e so ft h e m a l lt h ec o n s t r u c t e df u n c t i o n sa b o v ec a nb eu s e da s i n i t i a lf u n c t i o n sw i t hc e r t a i nr e c u r s i v eo p e r a t o r st op r o v i d eh i g h e ro r d e rr e s i l i e n t f u n c t i o n sw i t hm a x i m u mp o s s i b l ed e g r e ea n dh i g hn o n l i n e a r i t y t h ef u n c t i o n s c o n s t r u c t e dk e e pt h es a r n eg o o dc r y p t o g r a p h i cp r o p e r t i e sa st h o s eb ys m a i t r ai n b a l a n c e d n e s s ，n o n l i n e a r i t y ，c o r r e l a t i o ni m m u n i t y ，r e s i l i e n c ya n dd e g r e e ，m o r e o v e r ， t i l ea m o u n to fc o n s t r u c t e df u n c t i o n si sr e m a r k a b l yi n c r e a s e d a l s oa na l g o r i t h mb ysm a i t r ao fd e g r e eo p t i m i z a t i o no fl r e s i l i e n tf u n c t i o n si ss t u d i e d w h i l ed e g r e eo ft h ef u n c t i o n si so p t i m i z e d ，n o n l i n e a r i t yo ft h e m m a yv a r y ：e i t h e ri n c r e a s e4 1 o rr e d u c e4o rr e m a i nu n c h a n g e ds i n c e4b i t si nt h e t r u et a b l e su n d e rc o n s t r u c t i o na r ec h a n g e d h n p a c to nn o n l i n e a r i t yf r o mn o n o p t i m i z e dd e g r e er e s i l i e n tf u n c t i o n st oo p t i m i z e dd e g r e er e s i l i e n to n e si sa n a 1 y z e d ，a n d d e t e r m i n a n tt h e o r e m st od e t e r m i n et h ev a r i e t yo fn o n l i n e a r i t ya r eg i v e n ；b a s e do n t h et i l e o r e m sas e r i e so fa l g o r i t h m so fd e g r e eo p t i m i z a t i o no fl r e s i l i e n tf u n c t i o n s a r 8p r e s e n t e d 。w h i c hm a k en o n l i n e a r i t yi n c r e a s e4o rr e m a i nu n c h a n g e da tt h e s a m et i m ed e g r e eo ff u n c t i o n si so p t i l n i z e ds ow eo b t a i n1 一r e s i l i e n tf u n c t i o n s w i t hm a x i m u m d e g r e ea n dh i g h e rn o n l i n e a r i t y f u r t h e r m o r e ，t h ea l g o r i t h m sa r e a p p l i e dt on o n o p t i m i z e dd e g r e e1 一r e s i l i e n tf u n c t i o n so n6a n d8v a r i a b l e s i ti si n t r o d u c e dh o wt oi m p l e m e n ta l g o r i t h m so ft h eb a s i co p e r a t i o n s ，c o i l s t r u c t i o no fn v a r i a b l e m r e s i l i e n tf u n c t i o n sa n dd e g r e eo p t i m i z a t i o no f1 一 r e s i l i e n to n e ss o m et a b l e sa n df a s ta l g o r i t h m so fc o m p u t i n gh a d a m a r dm a t r i x a r eu s e de x t e n s i v e l yi ni m p l e m e n t a t i o n so ft h ea l g o r i t h m s ：t h r e em a i nt a b l e s i n c l u d et h en u m b e ro fl ，i t sp a r i t ya n dt h er e v e r s eo r d e ro fe v e r yb i ts t r i n go f l e n g t h8 ，w h i c hc a nr e d u c et h ep r o g r a m m i n gr u n t i m e ；f a s ta l g o r i t h m so fc o r n p u t i n gh a d a m a r dm a t r i xa r ea p p l i e dt oc o m p u t a t i o no f ，a l s hs p e c t r a a u t o c o r r e l a t i o na n dr e e d m u l l e rs p e c t r a ，r e d u c i n gt h ef o r m e ra l g o r i t h mc o m p l e x i t y 2 “2 “t on 2 “a n di n c r e a s i n gt h er u n t i m er a t eg r e a t l y i nt h ee n dt h ep a p e rs u m m a r i z e sa l lt h ew o r ka n di t sm e a n i n ga n di n d i c a t e s i t s f l a w s k e yw o r d s ：b a l a n c e d n e s s ；n o n l i n e a r i t y ；c o r r e l a t i o ni m m u n i w ；r e - s i l i e n c y ；a l g e b r a i cd e g r e e 广州大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指 导下，独立进行研究工作所取得的成果。除文中已经注明引 用的内容外，本论文不含任何其他个人或集体已经发表或撰 写过的作品成果。对本文的研究做出重要贡献的个人和集体， 均已在文中以明确方式标明。本人完全意识到本声明的法律 后果由本人承担。、 学位论文作者签名谚岳、珊c 日期：肿牛年，月彭日 广州大学学位论文版权使用授权书 本人授权广州大学有权保留并向国家有关部门或机构送 交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权 广州大学可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇 编学位论文。( 保密的学位论文在解密后适用本授权书) 、l 学位论文作者签名岳1 烈日期& 哗年，月时日 导师签名：彩蟛乏一日期：加哆牢易眇日 第一章绪论 1 t 1 布尔函数与密码学 密码学是一门古老而又年轻的科学，它用于保护军事和外交通信可追溯到 几千年前密码学的发展历史大致可以划分为三个阶段： 第一个阶段足从古代到1 9 4 9 年密码学专家凭借直觉和信念来进行密码 的设计和分析，因而这段时期的密码技术与其说是科学，而不如说是一门艺术 第二个阶段是从1 9 4 9 年到1 9 7 5 年1 9 4 9 年s h a n n o n 发表保密通信的 信息理论i i ，成为私钥密码学的理论基础，从此密码学成为具有艺术性的 门科学 第三个阶段是1 9 7 6 年至今1 9 7 6 年d i 5 和h e l l m a n 发表的“密码学的 新方向f 2 1 ，提出公钥密码体制，使得通信双方无须事先交换密钥就可以进行 安全保密通信1 9 7 7 年美国国家标准局( n b s ) 正式发布实旃美国数据加密标 准( d e s ) 【3 1 ，广泛应用于商业数据加密，揭开了密码学的神秘面纱 7 0 年代 密码学界的这两件大事标志着现代密码学的诞生 在当今信息社会，特别是互联网迅猛发展的今天，信息安全越来越受到重 视，极大地推动了信息安全的核心一现代密码学的研究，如今密码理论与技 术的应用已经覆盖了国防、军事、政府、商业、金融、文教等领域随着信息 化的到来，现代密码学理论与技术与个人的信息保密密切相关，这些都给密码 学的研究以极大的推动，也为密码理论和技术的应用提供了广阔的前景 密码学是研究密码系统或安全通信的一门科学，包括密码编码学和密码分 析学两个分支密码编码学主要是寻求安全有效的密码算法，满足消息保密或 者认证的方法；而密码分析学主要是研究加密消息的破译或者消息的伪造这 两个分支相互促进，极大的推动了密码学的发展 密码体制根据密钥特点分为公钥密码密码体制和私钥密码体制我们通常 也把公钥密码体制称为非对称密码体制，把私钥密码体制称为对称密码体制 我们来关注密码体制的安全性：公钥密码体制的安全性建立在一定数学难题的 基础之上，如r s a 公钥密码算法的安全性就建立在大整数素因子难分解这一 数学难题基础上私钥密码体制按照加密方式又分为分组密码和流密码( 流密 码也被称为序列密码) 对于序列密码，目前最常用的组合序列密码系统和滤波 序列密码系统，其安全强度与所选用的组合和滤波函数的性能密切相关，这些 性能包括：函数的相关免疫度、扩散性、非线性度、雪崩特性、稳定性、差分 特性等等分组密码的典型代表是d e s 体制，d e s 的强度取决于s 盒的安全 性能，如s 盒的非线性度、雪崩性、平衡性、差分性，扩散性等等美国公布 的a e s 的1 5 个候选方案和欧洲n e s s i e 的候选方案的安全性几乎都有赖于 布尔函数的这些密码性能另外广泛用于数字签名的哈希( h a s h ) 散列函数如 s h a 一1 、m d 5 等算法的安全性也与一定的布尔函数的密码性能息息相关 对于任何私钥密码算法以及c a g - f f i 数来的设计说，采用一系列具有若干良好密 码性质的布尔函数可以使其能够抵御各种已知的密码分析攻击，这些密码分析 攻击包括：线性攻击、差分攻击 4 ，5 1 等等布尔函数的某种密码特性越强，相 应地，私钥密码算法和哈希散列算法抵抗某种攻击的能力越强一般要求任何 密码算法必须抵御多于一种的密码分析攻击，所以布尔函数应该具有多种优良 的密码性质而由于密码性质之间在不同程度上是相互制约的，各种密码性质 总是不能同时达到最优，也并非满足的密码性质越多越好，根据具体的应用情 况，选取适当的折中处理，满足不同密码算法的需求， 因此，布尔函数是密码体制实现中一个有效的工具，在私钥密码系统和哈 希散列算法的设计中占有举足轻重的地位找到大量具有一定良好密码性质的 布尔函数，在私钥密码体制以及哈希散列函数的设计和构造中具有重要意义 2 1 2流密码中布尔函数研究的一些进展 在私钥密码设计应用中，考虑到抵御的密码分析攻击方式不同，要求所采 用的布尔函数具有的密码性质也备不相同布尔函数一般研究的密码准则有： 非线性次数、非线性度、线性结构、退化性、相关免疫性、严格雪崩准则和扩 散准则等等 在全世界范围内，流密码系统广泛被用于的国防通信，提供一种可靠、高 效的安全通信方式在一个典型的流密码模型中，使用一个非线性布尔函数来 合成多个相互独立的线性反馈移位寄存器( l f s r ) 的输出来生成密钥流密钥 流和消息比特流之间相互进行异或运算得到密文解密机和加密机所生成的 密钥流足完全一样的这时采用了非线陛布尔函数的流密码如果被认为是安全 的，就必须能够抵御各种已知的密码分析攻击，这就要求布尔函数应该具有以 下几个重要的密码性质：平衡性、相关免疫度、代数次数以及非线性度等等 平衡性足一个基本的密码准则，一个不平衡的布尔函数其无条件熵是最不理想 的，也就是说它和一个常函数相关，因而布尔函数必须是平衡的相关免疫度 一向被认为足密钥流生成器6 1 的构造中合成线性移位寄存器的非线性函数最 关键的密码性质之一对于抵抗针对流密码的相关攻击【7 】高的相关免疫度是 非常理想的密码特性如果流密码中采用非线性度比较低的布尔函数，一种被 称为“最佳逼近攻击”的密码分析攻击【8 】能够成功地攻击这样的流密码因 而布尔函数的非线性度是加密算法的设计和分析中最重要的指标，布尔函数还 ：凶须具有较高的代数次数，这样流密码中的密钥流生成器才能抵御b e r l e k a m p m a s s e y 攻击阱总之，平衡性、相关免疫度、代数次数以及非线性度四个密 码性质在这个流密码模型的设计中足必不可少的 近年来，国内外学者对具有良好密码性质的布尔函数进行了大量的研究工 作，主要围绕几个方面进行；构造具有受好密码性质的布尔函数；满足某种密 码性质的布尔函数的计数问题；布尔函数的密码性质及其相互的关系 我们主要介绍关于在n 元d 次( 代数次数为d ) m 阶相关免疫的平衡布尔 函数研究方面所取得的一些研究成果平衡性、相关免疫度、代数次数以及 非线性度满足一定的制约关系，不可能同时达到最优，必须找到一个合理的折 中s i e g e n t h a l e r 在文献【6 】提出，n 元d 次( 代数次数为d ) m 阶相关免疫的 平衡布尔函数满足以下的关系：m + d n 一1 ( s i e g e n t h a l e r 不等式) 近年来围 绕s i c g e n t h a l e r 不等式的研究有：相关免疫度、非线性度、代数次数之问的关 系f 1 0 一1 5 】；通过固定变元n 和相关免疫度? r t 来设计具有尽可能高的非线性度 的平衡布尔函数f 1 6 1 北能够达到非线性度上界和取得高阶免疫度的平衡布尔 函数的构造方面f l o 1 4 ，2 0 ，2 讣 目前国内外的学者研究具有某种特性的布尔函数，如具有三个w a l s h 谱 值的布尔函数，此时可以构造出非线性度，相关免疫度和代数次数相互制约 关系达到最优的平衡布尔函数【2 2 】本文将会对一类具有五个v 池l s h 谱值的函 数f 2 3 1 构造方法进行修改，得到新的具有优良密码性质的函数，尽管这些函数 在非线性度方面并没有达到最优，但是已经可以达到抵御攻击的要求，可以广 泛地应用于密码体制的构造中 1 3论文的安排以及主要研究结果 本文主要研究如何构造大量的n 元d 次m 阶相关免疫的平衡布尔函数 本文的安排以及主要研究结果如下： 第二章系统地给出了本文即将用到的关于布尔函数密码性质的一些基本 概念和相关定理，并简要的介绍布尔函数的基本构造方法 第三章首先对文献f 2 3 1 中达到b e n t 函数级联得到的非线性度2 ”1 2 掣 的平衡函数和1 阶弹性函数的构造方法作了一般性的扩展构造，得到大量的具 有同等密码性质的布尔函数；然后将这些函数作为初始函数，利用一定的递归 运算来构造更多具有较高非线性度的高阶弹性函数 第四章先给出1 阶弹性函数次数最优化的一种方法 5 9 1 ，对次数优化过程 中非线性度的影响进行分析，并给出决定非线性度变化相应的判定定理；然后 利用这些判定定理，给出1 阶弹性函数次数最优化的算法，对函数进行次数最 优化的同时，得到具有尽可能高非线性度的1 阶弹性函数 第五章给出布尔函数的基本运算以及前两章所提到的n 元m 阶弹性函数 的构造和1 阶弹性函数次数最优化的一系列算法的实现在算法实现的过程 中，将广泛使用一些表单和关于h a d a m a r d 矩阵的快速算法 第六章对本文进行概括，指出文章的不足和进一步研究的方向 第二章布尔函数的基本理论 为了以后叙述和理解的方便，在这一章中，我们将介绍布尔函数的一些理 论知识，系统地给出布尔函数密码性质的一些基本概念和相关的重要定理，并 简要的介绍布尔函数的基本构造方法这章节理论详见文献【3 2 】 2 1布尔函数中的定义以及若干密码性质 为了使密码系统能够抵御已知的若干密码分析攻击，在其设计中所采用布 尔函数应具有一些密码性质，如平衡性、相关免疫度、扩散性、非线性度、自 相关性等等下面将给出布尔函数的定义以及若干密码性质这些基本概念 一个n 元的布尔函数f ( 3 7 ) 是从坷到f 2 的一个函数或映射，一般记为； f ( x ) ：露一f 2 f 2 表示二元域，曰表示r 上的n 维线性空间 定义2 1 设n 元的布尔函数f ( x ) ：日+ f 2 ，自变量z = ( z 1 ，2 ：2 ，- - ，z 。) ，把 每一组自变量( 3 2 1 ，x 2 ，茹。) 与它所对应的函数值( 值为0 或者1 ) 全部列 成表格，这种表格被称为这个布尔函数的真值表 习惯上我们可以把一个n 元的布尔函数看成长为2 ”的二进制序列，设 ( y - o nh ，a 2 n 一1 是坷上的所有元素，是整数i 的二进制表示，若f ( e x i ) 表 示真值表中第i 个位置所对应的值，则f ( x ) = ( ，( o o ) ，( o t ) ，( n 。n t ) ) 若，( z ) = 1 2 ( x ) = ( 一1 ) m ) ，则有，( z ) 1 ，一1 ) ，我们把，( z ) = ( ( 一1 ) 弛”，( 一1 ) 7 ( 8 “，一，( 一j ) 伽。”一，) 称为布尔函数f ( x ) 的极性真值表( p o l a r i t y t r u t , ht a b l e ) 定义2 2 ( 平衡性) 一个 元的布尔函数，( z ) 是平衡的，如果f ( x ) 的真值表 中0 和1 的个数相等，即，( z ) 的海明重量( h a m m i n gw e i g h t ) ：w t ( f ) = i z 露c ，( z j l 【= 2 ”1 个n 元的布尔函数f ( z ，x 2 ，z 。) 能够被唯一表示为一个f 2 上的一 个多元多项式 定义2 3 ( 代数正则形式) f ( 2 ：1 ，x 2 ，z 。) 是一个n 元的布尔函数，可以写 成如下形式： ，( 钆，z 。) = a o + 嘴+ 础j 4 - + 1 2 n x l x 2z 。( 2 1 ) t = l l i j “ a o ，a i ，a 玎，a 1 2 。毋，f 的这个表达形式被称为f 的代数正则形式( a n f ) 定义2 4 ( 代数次数) 在n 元的布尔函数的代数正则形式( 形如式( 2 1 ) ) 中， 具有非零系数的乘积项中的最大次数称为，扛) 的代数次数，记为d e g ( f ) d e g ( f ) = 1 时布尔函数被称为仿射函数；仿射函数常数项系数为0 时，函 数被称为线性函数a ( n ) = a o + n l z l + 。2 2 2 + - + a n x 。ia i f 2 ，1 i n ) 表 示所有n 元仿射函数的集合；a o = 0 时，l ( n ) = a l x l a 2 x 2 + + 。z n a i 玛，l s i n ) 表示所有元线性函数的集合 定义2 5 ( 非线性度) 布尔函数，( 2 ) 的非线性度? ：。，2 ，黜1 “( ，2 ) _ m ) 的相关度c r ：q 3 1 戮日i m ) = ) l 其中，d ( f ，2 ) 表示，和f 之间的海明距离( h a m m i n gd i s t a n c e ) ，且d ( f ，c ) = w t ( f + f 1 w m s h 变换f 8 】是布尔函数的分析中一个非常重要的工具 定义2 6 ( w a l s h 变换) ，( z ) 是n 元的布尔函数，令z = ( 。l ，z 2 ，x n ) ， u = ( u l ，“2 ，u 。) ，u z = 川1 2 1 + k 0 2 2 2 + + u 。z 。，则，( z ) 的w a l s h 变换是 叼上的实值函数，有如下定义： ( “) = ( 一1 ) m m 。 u 腔( 2 2 ) w a l s h 变换有时候被称为谱分布或者简单地称为布尔函数的谱 令f 。( z ) = u z ，定义w d ( f ，2 。) = i z f ? l f ( x ) = f 。( ) ) j 1 z 1 i ，( z ) f 。( z ) ) i = 2 ”一2 l z f l ，( z ) c 。( z ) l = 2 “一2 d ( 厂，乙) ，贝0 ( 叫) = w d ( f ，1 w ) 1 9 8 8 年文献【2 4 提出相关免疫度的特征化定理( x i a o - m a s s e yt h e o r e m ) ，使 得w a l s h 变换广泛应用于密码学中；之后很多文献都把此定理直接作为相关免 疫度的定义 定义2 7 ( 相关免疫度) 佗元的布尔函数f ( x ) 是m 阶相关免疫的，如果，( 。) 的w a l s h 变换满足：哪) = 0 ， 1s w t ( w ) m 由 d ( ，l 。) 的定义以及u ，知) = d ( ，l 。) 很容易得到，( x ) 是平衡的布 尔函数当且仅当i 吩( 0 ) = 0 我们一般把m 阶相关免疫的平衡函数称为m 阶 弹性函数下面我们用w a l s h 变换给出弹性函数的定义 定义2 8 ( 弹性函数) i i , 元的布尔函数，( z ) 是m 阶弹性函数，如果( x ) 的 w a l s h 变换满足：晰) = 0 ，0 w t ( w ) m 定义2 9 ( 扩散准则) 2 5 ，( z ) 是n 元的布尔函数，n 叼，如果( x ) 十 ，扛+ o t ) 是平衡函数，则( x ) 关于n 满足扩散准则如果对所有的o t 毋： 1 w t ( a ) s ，f ( x ) 关于a 满足扩散准则，则，扛) 满足次扩散准则如 果任意固定f ( z ) 的m 个输入比特为常数得到的所有n m 元布尔函数都满 足次扩散准则，则称f ( x ) 满足m 阶次扩散准则 1 次扩散准则被称为严格雪崩准则1 2 6 , m 阶1 次扩散准则被称为i n 阶严 格雪崩准则 2 7 j 1 定义2 1 0 ( 自相关函数) ，( z ) 是n 元的布尔函数，称，( n ) = ( 一1 ) 7 ( 。) + 扣“) “碍为，( j ：) 的自相关函数，可简单记为：( n ) 全局雪崩特性【2 8 】用平方和指标( s u m o f - s q u a r ei n d i c a t o r ) 和绝对值指标 ( a b s o l u t ei n d i c a t o r ) 来衡量 定义2 1 1 ( 全局雪崩准则) 设，( z ) 是7 , 元的布尔函数，( z ) 雪崩特性的平 方和指标为： 口，2 ；2 似) 绝对值掘标为：，2 。m 吁& 。x 。i ) i 8 2 2 布尔函数中的一些重要定理 本节我们将介绍w a l s h 变换在布尔函数研究中的重要应用，并简明扼要 地说明平衡性、代数次数、相关免疫度、非线性度之间的关系 在研究布尔函数密码性质的时候，w a l s h 变换是一个非常实用快捷的工 具，可以简化一些密码性质的计算，而且很清晰地认识密码性质之间的关系 定理2 1 ( w a i s h 逆变换) f ( x ) 是n 元的布尔函数，) 是f ( x ) 的w a l s h 变换，则有： ( 一1 ) 他= 丽1 w a - ) ( 一1 ) u 露 ( 2 3 ) 定理2 2 ( p a r s e v a l 等式) 2 9 ，3 0 ，( ) 是n 元的布尔函数，扣) 的所有 w a l s h 变换的平方之和是2 2 “，即： 叼( u ) = 2 饥 ( 24 ) 定理2 3 ，( z ) 是7 l 元的布尔函数，则有 孵( u ) 小) ( 一l r u 霹 ( 2 5 ) 制用定理2 1 和定理2 3 ，很容易推导出下面的定理： 定理2 4 ，( z ) 是n 元的布尔函数，别有： 小) ：而1 叼( u ) ( 一1 ) s 霹 ( 2 6 ) - u 定理2 5 f ( x ) 是“元的布尔函数，别有： g s ：2 一一；m 圳w a u ) 9 ( 2 7 ) c s = 2 ”1 + ；m a x i 盼( 5 0 ) l( 28 ) ，+ q = 2 “( 2 9 ) 由定理25 式( 2 7 ) 知，r 警i 眄) i 越小，n 越大，但是m 。a r x l ) l 不可能为0 ，由定理2 2 ，m a x i 吩) i 2 9 ，因而j 兰2 “一2 i 当n 为偶 数，达到最优上界，即v ，= 2 ”1 2 9 ，此时，称为b e n t 函数【3 1 ，其 w a l s h 谱的绝对值均为2 ； 定理2 6 f ( x ) 是n 元的布尔函数，则有： ( 1 ) f ( x ) 关于。坷 o ) 满足扩散准则，则 孵( u ) ( 一1 ) “。= 0 ( 2 1 0 ) ( 2 ) ，扛) 满足k 次扩散准则，当且仅当对于任意的o l 露，1 w t ( a ) k ，都 有式( 2 1 0 ) 成立 ( 3 ) ，扛) 满足m 阶k 次扩散准则，当且仅当对任意的1 i l i 2 ；一1 ，月1 j 坼 2 n - l 一2 ( 2 ) 盯l 为偶数且k 1 甚一1 ，丑qj v r ；一1 ，则 ( 2 ) ，n 为偶数且己l ；一1 ，贝咔 z m “) ，f 的变元。j 取0 ，u j = 1 ：否 f 2 “一1 2 l r n i m a x ( n ) 的倍数 则m 3 ) 元布尔函数，弘是 元非退化线性函数，s s 定义同引理3 4 ，取r l ，r 2 ，r 。毋，方法如下： ( 1 ) 当h = 弘，n 兰3 m o d4 或者h = ，i 。，n ；1r o o d4 时，定义 1 。8 7 十。+ 8 每 n ：e 筹1 。2 t n + f l n ：簖+ e ，n ，n f + l + 1 e n 1 嚣惹 ( 2 ) 当h = 肛，扎三1 r o o d4 或者h = ，n 三3 r o o d4 时，定义 r l = e ? + e ；+ e ：一l + e 。n n ：e 髯1 。2 is 半 ( 3 5 ) ( 3 , 6 ) n ：e ：+ e ：+ l _ ；，翌 2 + 1 i n 这里e ? 表示n 维向量第i 个位置是1 ，其余位置是0 则r l ，r 2 ，一，t n 研，且 这咒个向量线性无关，令b ，= ( 7 l ，r 2 ，r 。) r ( t 表示矩阵的转置) ，则b ，是 非奇异的令c i = b i l ，f 7 扛) = ，( o z ) ，则，是( n ，1 ，n 一2 ，2 “一2 警) ，7 具 有与f 相同的谱值 证明要证n ，7 2 ，s ，需证h 0 ) = 0 ( 1 i n ) 令l 。= z ，我们知 道，w ，( n ) = 2 n 一2 d ( f ，l r , ) ，故只需证明d ( f ，= 2 瓠( 1 is n ) 可分两种 情形证明： 情形一：对于取法( 1 ) ( 如( 35 ) 式所示) ：先征d ( ，：l r , ) = 2 2 ( 1 i 兰! 孚) ，证明 同定理33 中情形一( 3 ) 的证明我们注意到当n 3 r o o d4 时，定理3 3 中 h ：“时，h 为奇数变元的非退化函数，则u l 为1 ， ；为o ；而当ne 17 r z o d4 时，定理3 3 中h = 肛c 时，h 为偶数变元的非退化函数，则口为l ，口i 为 0 ，从而在，的构造中，f 乜的真值表中最后一个位置值为0 我们可以证明 d ( f ，f 。) 一2 2 ( 丁n + l + 1 z n ) ，证明同定理3 3 中情形二( 6 ) 的证明 情形二：对于取法( 2 ) ( 如( 3 6 ) 式所示) ：先证d ( f ，z 。) = 2 2 ( 2 。s 萼! ) ，证明 同定理3 3 中情形一( 3 ) 的证明我们注意到当n1 1r a o d4 时，定理3 3 中 = “时，h 为偶数变元的非退化函数，则v i 为0 ，。；为1 ；而当ni 3m c d4 时，定理3 3 中h = 旷时， 为奇数变元的非退化函数，则v l 为0 , v ；为 1 ，从而在，的构造中，h 。的真值表中最后一个位置值为1 我们可以证明 d ( z ，f 。) = 2 2 0 = 1 ，下n + l + 1si n ) ，证明同定理3 3 中情形二( 6 ) 的证明 文献 2 3 】给出了有关r z ，t 2 ，r 。线性无关，b ，为n 阶非奇异矩阵的证 明，这里不再赘述 又由引理3 4 可得：，7 和，具有相同的海明重量、代数次数以及非线性 度，从而可知，是( n ，l ，n 一2 ，2 “一一21 孚) 由线性变换并不改变谱值的分布数目，从而，7 具有与，相同的谱值i 土2 半，0 ，2 半一8 ，一8 定理得证 注释： ( 1 ) 定理3 6 中符合条件的b ，并不是只有式( 35 ) ，( 3 6 ) 这样的构造形式，而 且这样的b ，个数有很多我们将给出了一个实例( 详见附录a ) ( 2 ) 对于由定理3 4 构造的，若能在s ，中找到线性无关的n 个向量r 1 ，r 2 ，如 令b f = ( 1 1 ，7 2 、，7 。) 7 ，b y 是非奇异的，7 ( z ) = f ( b ，1 z ) ，则有f 是 ( m1 ? t 一2 、2 “_ 。2 孚) 我们举例说明注释( 2 ) 的构造方法( 详见附录u ) 这样的构造方法能够得到( y t 1 ，n 一2 ，2 1 21 争) f 7 和，保持相同的谱值 但由于d 取值的复杂性和多样性，目前还不能证明对于所有的，这 样的br 是必定存在的，也还没有找到一个如定理3 6 这样比较好的结论 ( 3 ) 定理3 t ，3 2 中，h i 的构造中，9 1 ，a “1 i 2 一1 ) 的排列顺序是可以任 意改变的，同样也的构造中也是如此，且和，。中的排列顺序可以不同 这祥构造的函数仍然会保持原有的密码性质和谱分布定理3 3 ，3 4 的构 造中，构造，的前半部分时，g ，：( 1 i 2 一2 ) ，h 。的排列顺序可以任意 改变，同样构造，的后半部分时，9 。，九( 1si 2 一2 ) ， ：排列顺序也可 以任意改变，而且可以和前面的构造顺序不同，这样构造的函数能够保持 原有的密码性质和谱分布。因而，这样扩展得到的函数经过运用定理3 5 、 3 6 以及注释( 2 ) ，可以得到更多的同等性质的优良函数 定理3 5 中用到了定理3 1 ，3 2 构造的，而文献【2