（基础数学专业论文）最优代数免疫度弹性布尔函数的构造.pdf

。中文摘要 摘要 对称密码包括流密码和分组密码，这些密码系统中的非线性部分常由布尔函 数和多输出的布尔函数组成特别地，在流密码中，反馈移位寄存器中的布尔函数 的密码学性质在一定程度上决定了系统的安全性为了保证密码系统能抵抗所 有已知的攻击，布尔函数应满足一定的准则，如应具有较高的代数次数。较高的非 线性度和弹性阶数等目前，密码系统中的代数攻击成为了密码学家研究的热点 它的主要思想是通过建立初始密钥和输出密钥之间的代数方程组，然后求解方程 组，达到破译密码的目的为了抵抗这种攻击，布尔函数应具有较高的代数免疫 度一个n 元布尔函数的代数免疫度最人可为等 当n 元布尔函数的代数免疫度 为罟 时，我们称这个布尔函数具有最优的代数免疫度目前人们已经对代数免疫 最优的布尔函数做了一些工作：如给出了奇变元的布尔函数代数免疫度最优且为 一阶弹性的一个充要条件，但是具体怎样构造这种布尔函数类还是个公丌问题： 还构造了几类代数免疫度最优且非线性度较高的平衡布尔函数，但是这些函数不 具有弹性且不能与任何一阶弹性布尔函数仿射等价 本文首先基于已知的构造奇变元代数免疫最优布尔函数的方法给 n 了一种 摹奉构造，满足这种构造的布尔函数均具有最优的代数免疫度根据这种构造， 我们定义了两类奇变元的平衡非对称布尔函数，并利用k r a w t c h o u k 多项式的一些 性质分析了它们的非线性度以及代数次数所构造的平衡布尔函数的非线性度 为2 n - l 一( 2 二 ) ，代数次数为他一1 或是凡一2 进一步，本文还构造了几类代数免疫 最优的平衡布尔函数，并且当礼一1 不能表示成2 的方幂时，所构造的函数是一阶 弹巾牛的，并确定了这些函数的非线性度 关键词：布尔函数；零化子；代数免疫度；弹性；非线性度；代数次数； k r a w t c h o u k 多项式 湖北大学硕士学位论文 a bs t r a c t s y m m e t r i cc r y p t o g r a p h yc o n s i s t so fs t r e a mc i p h e r sa n db l o c kc i p h e r s b o o l e a n f u n c t i o n sp l a ya ni m p o r t a n tr o l ei nt h e s ec r y p t o g r a p h i cs y s t e m s i np a r t i c u l a r , t h ec r y p - t o g r a p h i cp r o p e r t i e so ft h eb o o l e a nf u n c t i o n su s e di nl f s ri ns t r e a mc i p h e r sd e t e r m i n e t h es e c u r i t yo ft h es y s t e m t or e s i s tv a r i o u sk n o w na t t a c k s ，t h eb o o l e a nf u n c t i o n su s e d i nc r y p t o g r a p h i cs y s t e m ss h o u l ds a t i s f ys o m ec r y p t o g r a p h i c a lc r i t e r i as u c ha sb a l a n c e d - n e s s ，h i g hn o n l i n e a r i t y ，h i g ha l g e b r a i cd e g r e ea n dc o r r e l a t i o ni m m u n i t y r e c e n t l y , a l - g e b r a i ca t t a c ka t t r a c t sm u c ha t t e n t i o nf o rm a n yc r y p t a n a l y s t t h ei d e at h a tt h ei n i t i a l k e yb i t sc a nb ec h a r a c t e r i z e da st h es o l u t i o n so fas y s t e mo fm u l t i v a r i a t ee q u a t i o n s ，i t t r a n s l a t e st h es e c u r i t yo fc r y p t o g r a p h ya l g o r i t h m si n t os o l v i n gt h es y s t e mo fn o n l i n - e a rm u l t i v a r i a t ee q u a t i o n s an e c e s s a r yc o n d i t i o nt or e s i s ta l g e b r a i ca t t a c ki st h a tt h e b o o l e a nf u n c t i o ns h o u l dh a v eah i g ha l g e b r a i ci m m u n i t y t h eo p t i m u ma l g e b r a i ci m m u n i t yo f 扎- v a r i a b l eb o o l e a nf u n c t i o ni s 吲i nt h ep r e s e n tp a p e r , s e v e r a lc l a s s e so f b o o l e a nf u n c t i o n sw i t ho p t i m u ma l g e b r a i ci m m u n i t ya r ei n t r o d u c e d as u f f i c i e n ta n d n e c e s s a r yc o n d i t i o no f ( 2 t + 1 ) 一v a r i a b l eb o o l e a nf u n c t i o n sw i t ho p t i m u ma l g e b r a i ci m m u n i t ya n d1 - r e s i l i e n ti sp r e s e n t e d ，b u ti ti sa l s od i f f i c u l tt oc o n s t r u c tt h o s ef u n c t i o n s s e v e r a li n f i n i t ec l a s s e so fb a l a n c e db o o l e a nf u n c t i o n sw i t ho p t i m u ma l g e b r a i ci m m u n i t ya n dh i g hn o n l i n e a r i t ya r ec o n s t r u c t e d ，b u tt h e s ea r en o t1 - r e s i l i e n ta n de v e nn o t a f f i n e l ye q u i v a l e n tt o1 - r e s i l i e n tb o o l e a nf u n c t i o n s i nt h i sp a p e r , w ef i r s tg i v eab a s i cc o n s t r u c t i o nb a s e do nt h ek n o w nm e t h o d sf o r c o n s t r u c t i n gb o o l e a nf u n c t i o n sw i t ho p t i m u ma l g e b r a i ci m m u n i t y t h ef u n c t i o n si nt h i s c o n s t r u c t i o nh a v eo p t i m u ma l g e b r a i ci m m u n i t y a n dt w oc l a s s e so fb a l a n c e db o o l e a n f u n c t i o n sw i t ho p t i m u m a l g e b r a i ci m m u n i t yi no d dn u m b e ro fv a r i a b l e sa r ep r e s e n t e d b yu t i l i z i n gt h ep r o p e r t i e so fk r a w t c h o u kp o l y n o m i a l ，t h en o n l i n e a r i t i e sa n dt h ea l g e - b r a i cd e g r e e sa l ea l s oa n a l y z e d t h en o n l i n e a r i t i e sa r ee q u a lt o2 ”1 一( 皇) ，a n dt h e a l g e b r a i cd e g r e e sa r ee q u a lt o 礼一1o rn 一2 f u r t h e r , f o ra ni n t e g e r 钆1 0 ，s e v e r a l c l a s s e so fn - v a r i a b l eb a l a n c e db o o l e a nf u n c t i o n sw i t ho p t i m u ma l g e b r a i ci m m u n i t ya r e c o n s t r u c t e d t h ep r o p o s e df u n c t i o n sa r eo f1 - r e s i l i e n c yi f 佗一1i sn e v e re q u a lt oa n y p o w e ro f2 ，a n dt h e i rn o n l i n e a r i t i e sa r ea l s od e t e r m i n e d k e y w o r d s ：b o o l e a nf u n c t i o n ；a n n i h i l a t o r ；a l g e b r a i ci m m u n i t y ；r e s i l i e n c y ；n o n - l i n e a r i t y ；a l g e b r a i cd e g r e e ；k r a w t c h o u kp o l y n o m i a l 湖北大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研 究所取得的研究成果除了文中特别加以标注引用的内容外，本论文 不包含任何其他个人或集体已经发表或撰写的成果作品对本文的研 究做出重要贡献的个人和集体，均己在文中以明确方式标明本人完 全意识到本声明的法律后果由本人承担 论文作者签名：苏海 签名日期：o ? 年r 月午日 学位论文使用授权说明 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即： 按照学校要求提交学位沦文的e i j 刷本和电子版本；学校有权保存并向国家有 关部门或机构送交论文的复印件和电子版，并提供目录检索与阅览服务；学校可 以允许采用影印、缩印、数字化或其它复制手段保存学位论文：在不以赢利为目 的的前提下，学校可以公开学位论文的部分或全部内容( 保密论文在解密后遵守 此规定) 作者签名：长海 指导教师签名：嗜亏军夸 日期：哆o 2 钲 日期：6 p 2 毕 1 引言 1引言 密码学有着悠久的历史，它用于保护军事和外交通信可追溯剑儿千年前在 当今的信息时代，随着计算机科学技术和通信技术的发展，使得计算机和通信网 络的应用进入了人们的日常牛活和- t 作中，出现了电子商务、电子金融等必须确 保信息安全的网络信息系统，密码学也因此不在局限于军事、政治和外交，而逐 步走向商用，成为受到广泛关注的学科 本章主要介绍了密码学发展的历史和以及一些基本的概念，并简述了布尔函 数在密码体系中的重要作用及其设计准则，最后简要介绍了本论文的研究内容和 组织结构 1 1 密码学概论 1 1 1 密码学发展历史 密码学的发展历史大致可划分为两个时期，即古典密码时期和现代密码时 期【1 1 古典密码时期是从古代到1 9 4 9 年。这一时期可以看作是科学密码学的前夜， 这阶段的密码技术可以说是一一种艺术，是一种技巧和经验的综合体，但还不是一 种科学，密码专家常常是凭直觉和信念来进行密码设计和分析，而不是推理和证 明 现代密码时期是从1 9 4 9 年至今1 9 4 9 年s h a n n o n “保密系统的信息理论”【2 】在 贝尔系统技术杂志上发表，首次将信息论引入密码技术的研究，为现代密码 学研究与发展奠定了坚实的理论基础，把已有数千年历史的密码技术推向了科学 的轨道，使密码学成为一门真j 卜的学科 从1 9 4 9 年到1 9 6 7 年，密码学文献近乎空白1 9 6 7 年，k a h n 出版的破译 者【3 】一书不仅记述了之前密码学发展的历史，还使成千上万的人了解了密 码学 1 9 7 7 年，美国国家标准局( n b s ，即现在的国家标准与技术研究所n i s t ) 正式 公布实施了美国的数据加密标准( d e s ) 【4 】，d e s 被批准用于美国政府非机密单位 及商业上的保密通信，并被多个部门和标准化机构采纳为标准，甚至成为事实上 的国际标准更具有重要意义的是d e s 密码开创了公开全部密码算法的先例，从 而揭开了密码学的神秘面纱，大大推动了分组街码理论的发展和技术应用 1 9 7 6 年，美国斯著名密码学家d i f f i e 和h e l l m a n 发表了“密码学新方向”f 5 】一文， 首次提出了公钥密码体制的概念和设计思想，开辟了公开密钥密码学的新领 1 一 湖北大学硕士学位论文 域受他们的思想启迪，各种公钥密码体制被提出，特别是1 9 7 8 年，美国的r i v e s t ， s h a m i r 和a d l e m a n 提出了第一个比较完善的公钥密码算法，这就是著名的r s a 算 法 6 1 自从那时起，人们基于不同的计算问题，提出了大量的公钥密码算法 由于计算机技术及网络通信技术研究与应用的迅速发展，过去人们认为 具有足够安全性的d e s 算法，在新的分析方法及计算机技术面前已证明不安全 了于是，1 9 9 7 年美国国家标准技术研究所( n i s t ) i 句伞世界征集高级加密标准算 法2 0 0 0 年1 0 ) q ，n i s t 宣布r i j m e n 和d a e m e n 提出的“r i j n d a e l 数据加密算法”被确 定为a e s 算法1 7 1 ，作为新一代的数据加密标准 随着信息时代的到来，各种基于密码技术的应用系统不断出现，密码学的研 究和应用已大规模地扩展到民用方面 1 1 2 密码学基本概念 密码学研究的是如何保证信息系统的安全它以认识密码变换的本质、研究 密码保密与破译的基本规律为对象，主要以可靠地数学方法和理论为基础，对解 决信息安全中的机桁性、数据完整性、认证和身份识别，信息的可控性以及不可 抵赖性等提供系统的理论方法和技术 密码学主要包括密码编码学和和密码分析学两个分支密码编码学的主要任 务是寻求有效密码算法和协议，以保证信息的机密性或认证性的方法它主要研 究密码算法的构造与设计，也就是密码体制的构造它是密码理论的基础，也是保 密系统设计的基础密码分析学的主要任务是研究加密信息的破译或认证信息的 伪造它主要是对密码信息的解析方法进行研究 一个密码体制( 或系统) 是一个五元组( p ，c ，k ，e ，d ) ，其中p 为明文空间， c 为密文窄问，k 为密钥空间，e 和d 分别表示加密算法和解密算法集，它们满 足对每一个k k 必存在一个取e 和一个d d ，使得对任意的仇p ，恒 有d 七( 风( 仇) ) = m 在信息的传输和处理系统中，除了指定的接受者外，还有密码 分析者或破译者，他们通过各种手段来获取机密信息他们虽然不知道密码系统 所使用的密钥，但通过分析可能会从截获的密文推断出原来的明文，这一过程称 作密码分析或密码攻击密码分析者破译或攻击密码的方法有穷举破译法和分析 法两种根据密码分析者破译时对明文和密义等资源的掌握程度，通常人们将攻 击类型分为四种，即唯密文攻击、已知明文攻击、选择明文攻击和选择密文攻击 ( 1 ) 唯密文攻击：密码分析者知道密码算法，但仪能根据截获的密文进行分析， 以得出明文或密钥 ( 2 ) 已知明文攻击：密码分析者除了有截获的密义外，还有一些已知的“明 文一密文对”来破译密码 ( 3 ) 选择明文攻击：密码分析者不仅可得到一些“明文一密文对”，还可以选择 2 1引言 被加密的明文，并获得相应的密文 ( 4 ) 选择密文攻击：密码分析者可以选择一些样文，并得到相应的明文 一个密码体制的安全性涉及两方面的因素：一个是所使用密码算法本身的保 密强度，另一个方面是密码算法之外的不安全冈素实际使用中，一个密码系统的 安全性应该不依赖于对密码算法的保密( k e r c k h o f f s 假设) ，而仅依赖于对密钥的保 密 1 1 3 密码体制的分类 根据密钥的特点，可以将密码体制分为对称密码体制( 也称为私钥密码体制) 和非对称密码体s t j ( 也称为公钥密码体制) 1 8 , 9 ，i o 】如果一个密码系统，它的加密密 钥和解密密钥相同，或是虽然不相同，但由其中的任意一个可以很容易地导出另 外一个，那么该系统所采用的就是对称密码体制如果其加密算法和解密算法分 别用两个不同的密钥实现，并且由加密密钥不能推导出解密密钥，则该系统所采 用的就是非对称密码体制 根据密码算法对明文信息的处理方式，又可将对称密码体制再分为分组密码 和流密码( 也称为序列密码) 分组密码是将消息进行分组，一次处理一个分组元 素的输入，对每个输入块产生一个等长的输出块如d e s 【4 ，1 ，a e s1 7 ，i d e a 1 2 , 1 3 1 ， r c 50 4 1 5 等即为分组密码算法流密码则是连续地处理输入元素，并随着处理过 程的进行，一次产生一个元素的输出 1 6 - 1 9 】典型的流密码有r c 4 ，a 5 ，s e a l 等 1 2 布尔函数在密码系统中的作用 对称密码体制中的许多问题，如分组密码中的s 一盒及常见的基于线性移位寄 存器的流密码中的滤波函数和非线性组合函数，它们的研究都可以归结为布尔函 数的研究同时这些问题和编码理论、组合设计及序列设计中许多问题的研究是 等价的，并有着罩要的应用背景 1 2 1 布尔函数的应用 分组密码的设计就是找到一种算法，能在密钥摔制下简单而迅速地选出一个 置换，用来对当前输入的明文进行加密变换一个好的分组密码应该是既容易实 现又难破译的分组密码一般采用代换置换网络的结构，这种结构的一个典型代 表是f e i s t e l 密码结构，其密码算法的基本思路是采用“扩散与混淆”两种主要思想 由于f e i s t e l 密码结构具有较多优点，以至于后来许多重要的密码算法如d e s ，r c 5 ， g o s t , f e a l 。l o k i 等都采用这种结构或是类似的结构米进行密码设计因此，要 保证一般分组密码的安全性，除了必须遵循混淆与扩散这两个基本准则外，还需 重点考虑的有：s 盒的设计，p 盒的设计，轮函数f 的设计等而这些问题都可以用 1 湖北大学硕士学位沦文 布尔函数来设计或是表达成布尔函数的形式来分析因此，在设计安令强度较高 的分组密码体制的过程中，构造密码性质较好的密码函数至关重要 在流密码中，加密器中存储器的状态随时间而变化，这一变化过程可用一个 函数( 通常称为状态转移函数) 来描述，记为厶根据状态转移函数厶是否依赖于输 入的明文符号，可将流密码分为同步流密码和自同步流密码在同步流密码中，状 态转移函数，s 与输入的明文符号无关在自同步流密码中，状态转移函数厶与输入 的明文符号有关从公开发表的文献米看，目前的绝大多数有关流密码的研究成 果都是同步流密码方面的 在研究同步流密码生成器时，r u e p p e lh 6 1 将这类生成器分成两部分，即驱动部 分和非线性组合部分驱动部分的任务是控制存储器的状态转移，负责提供若干 组合部分使用的周期大、统计特性好的序列【2 0 - 3 8 ，而非线性组合部分的任务是将 驱动部分所提供的序列组合成满足某些要求的好的密钥流序列由于l f s r 序列 的理论已经成熟，特别是m 一序列具有良好的伪随机性，所以驱动部分的设计比较 容易于足非线性组合部分的设计已成为密码流生成器设计的重点和难点非线 性组合部分可由布尔函数来实现，冈此，非线性组合部分的研究也可归纳为布尔 函数的研究 1 - 2 2 布尔函数的设计准则 为了能使密钥流生成器抵抗各种攻击，在功能上人们已对同步流密码牛成器 的非线性组合部分提出了多项要求，因此，为了提高系统的安全强度，布尔函数必 须满足一定的准则，以保证其系统能符合安全性的基本要求，并能抵抗现有攻击， 如线性攻击，相关攻击等为此，人们对密码系统中的布尔函数提h 了多条准则， 主要包括以下几条 为了保证输出的密钥流序列有良好的统计特性，布尔函数应该是平衡的 为了遵循混淆准则，所有密码系统中所使用的布尔函数( 流密码中的非线 性组合部分，分组密码中的s 一盒等) 都应该具有较高的代数次数例如，在一 个非线性组合生成器中，假设几个l f s r 的长度分别为l 1 ，k ，密钥流由这 些l f s r 的输出的组合函数，生成若f ( x ) =0o j ( nz i ) ，其中p ( j v ) 表示集 i e p ( n ) i e l 合= l ，礼) 的幂集，则函数，可由长度l n ，( 兀厶) 的l f s r 生成 3 9 1 j p ( | ) i e l 在分组密码中，如果所使用的币j 尔函数的代数次数较低，则不能抵抗高阶差分攻 击m , 4 h 为了抵抗线性逼近攻击，布尔函数的非线性度应尽可能的大根据守恒定 律( w z ( a ) ) 2 = 2 加，有罂誉l w z ( a ) i 的最小值为2 号，所以n 元布尔函数的非线 a f ? tr2 性度的最大值为2 1 2 詈一而布尔函数_ 厂为b e n t f f l 数当且仅当对任意的a 都 4 有i w a a ) l = 2 号所以说b e n t 函数是抵抗线性逼近攻击的最佳选择但是各种指标 之间存在着制约关系，女f l b e n t 函数不是平衡的，它的代数次数f i 超过导，限制佗为 偶数【4 2 - 4 6 因此，不一定要求函数具有最高非线性度，而只要求较高 为了抵抗相关攻击，系统中的布尔函数应是相关免疫的为了抵抗其他相应 的攻击，在不同的背景下使用的布尔函数还应满足：非退化性，对称性，严格雪崩 准则，扩散性等【4 7 - 5 4 1 近几年，代数攻击作为一种新的攻击方法被提出，它的提出对流密码和分组 密码系统都造成了极大地威胁 5 5 - 6 2 】代数攻击的基本思想是通过建立初始密钥和 输出密钥流之间的代数方程组来恢复出密钥或是初始密钥但是在实际中，这个 方程组的求解很困难，因此，人们试图寻找的这个方程组等价的，代数次数较低的 方程组来进行快速有效地代数攻击为了抵抗代数攻击，布尔函数，必须不存在低 次数的函数g 和h 满足关系f g = h ，而这一条件可等价于函数f f t i f + l 不存在低次 数的零化子布尔函数门铂，+ 1 的所有零化子的最低代数次数称为函数厂的代数 免疫度，记为a i ( f ) 【5 5 1 所以一个布尔函数具有较高的代数免疫度是抵抗代数攻 击的必要条件 布尔函数的这些性质都是在一定背景下保证安全性的必要条件，并非充分条 件另外，一般一个指标是无法保证安全性的，如高代数次数并不能保证高非线性 度，从而不能保证对线性逼近攻击的安全性所以，在特定的某密码系统中，可 根据安全性要求，选择满足某些性质的布尔函数于是研究满足几条性质的布尔 函数类已成为布尔函数研究的一个热点问题 1 2 3 有关布尔函数代数免疫度的研究 由代数免疫度的定义可知，布尔函数的代数免疫度小于等于它的代数次数 文献【6 3 给出了布尔函数的代数免疫度和非线性度的关系： 2 鬯( i ) ) ( 铲1 ) i = 0 文献【6 4 给出了代数免疫度和汉明权重之间的关系： a i n ( i ) - 1n - a i 。( ，) ( ：) w t ( f ) ( ：) 1 = ul = u 根据上面的关系可知，当n 为奇数时，n 元布尔函数的代数免疫度达到字，则 函数，是平衡的而且若布尔函数具有较高的代数免疫度，则它的代数次数和非 线性度也比较高，不过函数具有较高的代数次数和非线性度并不意味着它的代数 免疫度也比较高文献【5 5 ，6 5 】证明了一个n 元布尔函数的代数免疫度的最大值 5 湖北大学硕士学位论文 为圈 目前已有一些关于构造具有最优代数免疫度的布尔函数的方法：文献【6 6 证 明t m a j o r i t y 函数具有最优的代数免疫度，并对其进行了推广，得到了一类偶变元 的代数免疫最优的非对称布尔函数文献【6 7 7 0 1 证明了奇变元的对称布尔函数 中，代数免疫最优的有且仅有m a j o r i t y 函数和它的补函数，并在此基础上给出了奇 变元的布尔函数代数免疫度最优的充要条件，分析了这些函数具有较高非线性度 的必要条件；文献【7 1 从一个代数免疫度为1 的函数厶一2 d 出发，通过迭代的方法， 经过d + 1 步得到了代数免疫度为d + 2 的布尔函数厶+ 2 ，其中d + 2 f 下n + 2 1 由此 可以构造代数免疫度最优的布尔函数文献【7 2 给出了构造任意代数免疫度的布 尔函数的一一般性方法，基于这篇文献中的构造方法，文献【7 3 构造了一类代数免 疫最优的旋转对称布尔函数文献【7 4 构造了几类代数免疫最优且非线性度较高 的布尔函数，但是这些函数4 i 具有弹性 1 3 论文的研究内容和组织结构 基于文献【7 2 中关于代数免疫度较高的布尔函数的构造方法，本文在保证代 数免疫度最优的前提下，给出了两类的奇变元平衡非对称布尔函数和几类一阶弹 性布尔函数，并讨论了它们的代数次数和非线性度 论文结构如下： 第1 章介绍了密码学发展的历史和以及一些基本的概念，并简述了布尔函数 在密码体系中的重要作用及其设计准则 第2 章介绍了有火布尔函数的一些基本概念和密码学指标，并讨论 了k r a w t c h o u k 多项式的一些性质和有关组合数学的一些结论 第3 章首先介绍了一种奇变元布尔函数的的基本构造，满足这种构造的函数 均具有最优代数免疫度且是甲衡的基于这种基本构造，本章给出两类具有最优 代数免疫度的奇变元布尔函数，并利用k r a w t c h o u k 多项式的一些性质，计算了所 得到的函数的非线性度以及代数次数 第4 章首先介绍了两类具有最优代数免疫度的偶变元布尔函数的构造方法， 并利用一些组合等式和k r a w t c h o u k 多项式计算了它们的非线性度这两类布尔 函数经过一个可逆的线性变换均可变为一阶弹性函数然后给出了一类具有最 优代数免疫度的奇变元的布尔函数的构造方法，计算了这类函数的非线性度 当礼一1 不能表示成2 的方幂时，所构造的函数与一阶弹性布尔函数仿射等价 第5 章是对本文工作的总结和展望 6 2 预备知识 2 预备知识 本章丰要介绍了有关布尔函数的基本概念，k r a w t c h o u k 妻；项式的一些结论以 及在下文中涉及到的一些有关组合等式的性质 2 1 布尔函数的基本概念 设足表示由两个元素组成的有限域，曰表示在f 2 上的n 维向量空间一 个佗元布尔函数，是从毋到r 的一个映射所有n 元布尔函数组成的集合记 作风任意一个n 元布尔函数f ( x 1 ，一，z n ) 都与一条长为2 “的二元序列 ( f ( o ，0 ，o ) ，f ( 1 ，0 ，o ) ，f ( o ，1 ，o ) ，f ( 1 ，1 ，o ) ，f ( 1 ，1 ，1 ) ) 相对应，该二元序列被称为，的真值表 布尔函数f b n 的支集定义为s u p p ( f ) = z 毋if ( x ) = 1 ) f 的汉明权 重简称为，的权重，记为w t ( f ) ，即f ( x ) = l 的x 的个数，亦且p w t ( f ) = i s u p p ( f ) 1 特别地，当w t ( ，) = 2 n ，即7 , 元布尔函数，的真值表中0 和1 的个数相等时，我们 称，是平衡的两个布尔函数，和g 之间的汉明距离d ( f ，9 ) 定义为，和g 的真值 表中不列元素的个数，即 d ( f ，g ) = w t ( f g ) = i z ，? iy ( x ) 9 ( z ) ) 1 在全文中，我们用0 表示足上的加法 类似地，定义一个向量q = ( a 1 ，a 2 ，a n ) 的支集为s u p p ( a ) = 1 i 几io = 1 ) ，q 的汉明权重为w t ( q ) = i s u p p ( a ) 1 设q ，卢毋，我们记q 墨卢当且仅 当s u p p ( a ) s u p p ( p ) 对任意的整数后，0 k 礼一1 ，定义向量z 的循环移位作用： 破( z ) = ( x k + l ，x nz 1 ，z 七) ， 其中z = ( z 1 ，z n ) 曰称集合 g n ( z ) = p ：( z 1 ，x 2 ，z 九) 10 k n 一1 ) 为包含元素z 的轨道，z 被称为该轨道的一个代表元 根据1 2 节中布尔函数的设计准则可知，在密码体系中使用的布尔函数应尽 一7 一 湖北大学硕士学位沦文 可能地具有平衡性，较高的代数次数，较高的非线性度，较高的弹性阶数和较高的 代数免疫度等密码学性质 布尔函数，还可以看成是马上的一个佗元多项式，能被唯一地表示为： m ，z n ) = o 五， u e 牙 n 其中厶f 2 ，乱= ( u l ，u 2 ，乱n ) 曰，= 兀z 这个n 元多项式被称为，的 _ = 1 代数正规型( a n f ) 函数，的代数次数定义为其代数正规型中系数不为零的乘积 项中向量u 的汉明权重的最大值，记作d e g f 如果函数，的代数次数不超过1 ， 则称布尔函数，为仿射函数所有仿射函数构成的集合记作a n 设a = ( a 1 ，k ) ，z = ( z 1 ，z n ) 露，入和z 点积定义为 入z = a l z l0 0 入n z n ， 扎元布尔函数，的w a l s h 谱函数( w a l s h 变换) 定义为： 晰( a ) = ( 一1 ) m z ，入霹， z 曰 这是一个从毋到整数环z 的函数如果函数，是平衡的当且仅当，在零点 的w a l s h 谱值w s ( o ) = 0 称函数f b 。是m 阶相关免疫的当且仅当对任意满 足l w t ( s ) m 的l 幻量s 毋，有w r ( s ) = 0 特别的，若布尔函数，是m 阶相关 免疫的平衡布尔函数( 即对任意满足0 w t ( s ) m 的向量8 曰，有w r ( s ) = o ) ， 则称函数厂具有m 阶弹性 扎元布尔函数f 的非线性度n 1 ( ，) 定义为m 啦d ( f ，9 ) ，记作n l ( f ) ，即，与所有仿 射函数的最短距离实际上，的非线性度还可以用，的w a l s h 谱来表示： n l ( ，) = 2 n - i _ _ 互1 蹴i ( w 设f 鼠，若存在g b n ，使得f g = 0 ，则称g 为，的零化子使得f g = 0 或 者( ，o1 ) g = o 成立的g 的代数次数的最小值，称为厂的代数免疫度，记作a i n ( ，) 对任意的一个n 元布尔函数，都存在代数次数不超过罟1 的非零布尔函 数g ，使得f g = o 或者( ，o1 ) g = 0 ，即a i 。( ，) 罟1 5 5 6 5 1 ，其中f x l 表示不小于z 的 最小的整数，i z i 表示不大于z 的最大的整数例如，f 3 4 = 4 ，1 3 4 i = 3 当n 为奇数时，在n 变元的对称布尔函数中，代数免疫度达到最优的有且仅 一r 2 预备知识 有如和，oo1 6 7 , 7 0 ，其中 为m a j o r i t y 函数，其定义为 r ( z ) = 【 0 ，w t ( x ) s 孚， 1 ，w t ( x ) 丁n + 1 如果存在。个可逆的r t 阶二元方阵a 和个向量6 毋，使得n 元布尔函 数，和g 满足：g ( x ) = f ( a zo6 ) ，则称函数，与g 仿射等价可证明，布尔函数的 代数次数，非线性度，代数免疫度均为仿射不变量 2 2k r a w t c h o u k 多项式 对任一固定的a 毋，、7 l r t ( a ) = k ，有 萎( 一1 ) * 。= ( 一1 ) c ) ( ：j ) = k ( 忌，n ) ， ( 2 1 ) r t ( ) = j = o 。 。 其中k ( z ，死) 是k r a w t c h o u k 多项式【4 3 】 命题2 11 4 3 , 6 6 k r a w t c h o u k 多项式有下列一些性质： ( 1 ) k o ( ，几) = 1 ，k 1 ( k ，礼) = n 一2 七； ( 2 ) ( i + 1 ) k i + l ( k ，n ) = ( n 一2 七) ( 南，n ) 一( n i + 1 ) k 一1 ( 后，几) ； ( 3 ) k ( 七，几) = ( - 1 ) 七k _ 一 ( 七，n ) ； ( 4 ) k ( 后，佗) = ( - 1 ) 。k ( 他一k ，n ) ； ( 5 ) ( ：) k ( 后，n ) = ( ? ) 玩( i ，n ) ； c 6 ，若几为偶数，有k c 警，佗，= 。一1 嚣( i ) ，喜：茎君萋： 命题2 2 【州( 1 ) 对任意的正整数n ，七1 以及0 r 礼，有 ( 七，死) = 厨( 七一l ，儿一1 ) ； i = 0 ( 2 ) 设n 和k 是两个整数，且2 k 死一2 ，则 k 号一l ( 七，礼一1 ) = 一k 量一1 ( 后一1 ，n 一1 ) = k 号( 后，几) 为了下文巾分析函数的w a l s h 谱值，我们还需要下面两个关于k r a w t c h o u k 多 项式的引理 9 湖北大学硕士学位论文 引理2 3 对任意的偶数t t ，有 f 0 ，若i 是奇数， o “瓦m21 ( - 1 诤骅，若删数； ( 孙。勰。峨( 七一1 ，n ) i = i k 詈( o ，n ) l = 峨( 扎，n ) l = ( ；) ， 3 m 胁a x 一。i k - 罟( k 一1 ，n ) i = i k 暑( 2 ，, 0 1 = i k 量( n 一2 ，n ) l = 击( ；) ； ( 3 ) k 号( 七一1 ，扎) = 【1 + ( 一1 ) 七一1 】k 暑( 庇一1 ，礼一1 ) ； 证明( 1 ) 由命题2 1 巾的等式5 ，有( ? ) k 詈( i ，n ) = ( ；) ( 詈，佗) 再由命题2 1 中的等 式6 ，既得 f 0 ， 若i 是奇数， 吩。m 卜1 ( - 1 诤骅，若删甄 ( 2 ) 由( 1 ) 可知，当南为偶数时，k ( k - l ，扎) = 0 ，因此只需要证明当七为奇数时 成立即可 当七( n 一1 ) 为奇数时， 因此，当1 k 号时， 矧= 黜喃卿2 莉2 盎 k 暑( 七+ 1 ，儿) l i k 詈( 后一1 ，扎) l ； 当鸶k n l 时， i 号( 七+ 1 ，几) l i k 号( 七一1 ，n ) 1 由于l k 詈( 扎，n ) l = i k 罟( o ，n ) l = ( ；) ，i k 量( n 一2 ，n ) l = i k 号( 2 ，n ) l = 由( ；) ，因 此得证 2 ( 3 ) 由等式( 2 1 ) ，不妨设a = ( a ，o ) ，z = ( z 7 ，) 曰一1 毋，并r w t ( a ) = k 一1 。则有： 镌( 后一1 ，n ) =( 一1 ) z 、 r t ( z ) = 暑 2 叭( 骁詈( 州嘻毗号一1 ( 叫口7 - w t ( z ) = 罟w t ( z ，) = 罟一 = k 罟( k 一1 ，n 1 ) + k 等一l ( k 一1 ，n 一1 ) = 1 + ( 1 ) 詹一1 】k 鲁( 七一1 ，n 一1 ) 一1 0 2预备知识 引理2 4 设r t 为偶数，且n 8 ，则 ( 1 ) 若为奇数，且3 七礼一3 ，有 惫嘞( 后一1 ，礼) l = l 南k 暑( n 一七一1 ，礼) l 南( ；) ； ( 2 ) 若七为偶数，且2 k n 一4 ，有 k 号一2 ( 七，n 一3 ) = 一k 罟一2 ( 克一l ，n 一3 ) = ( 一1 ) 鲁 ，、fn - 4 。k - 4 k - 。一2 ( 七，仡一3 ) ， 若血为偶数， ( 3 ) k z k 3 ) 2 13n-竹4k-sk2_趴_2(k,n一：)，；忌菇磊薮：2 、 ， 。 证明( 1 ) 由引理2 3 ( 1 ) 可知，当若k 为奇数，且3 k t , 一3 ，有 与 比较可得， 由于 忐坞( 七一1 ，n ) i = 煮 南k 号( n - k - l ，n ) i = n 七 芸- - k k - ( k 一1 ，佗) i = 因此，当3 k 詈一l 时， 当七= 詈一1 时， 因为，当后= 3 时， i 刮高k 号( n k - 1 ，n ) i 赢k 詈( k n - ( k + 2 +1 “亏 1 ，咒) l = 不i k 乏， | 惫k 号( 七一1 ，n ) ； 习 i 啪t 广i n ( 七+ 1 ，n ) l = | 惫k 量( 七一l ，犯) 1 南镌( 2 ，佗) l = 南 = 上( n - 1 ) ( n - 3 ) ( ；) ，2 l 号， 噼牿 湖北大学硕士学位论文 因此得证 ( 2 ) 由命题2 2 ( 2 ) ，有若k 为偶数，且2 k n 一4 ， 而 k 鸶一2 ( 七，n 一3 ) = 一k 号一2 ( 七一l ，几一3 ) = ；k 争一l ( 忌，佗一2 ) ， k - - x ( k , n - 2 ) = 昝- ( _ 蟒释 ( 3 ) 由命题2 1 ( 2 ) ，有 詈k 詈( 七，凡一3 ) = ( n 一3 2 k ) k 詈一l ( k ，佗一3 ) 一( 一1 ) k 争一2 ( k ，佗一3 ) 由命题2 1 ( 3 ) ，有 k 詈一l ( k ，佗一3 ) = ( 一1 ) k 三一2 ( k ，佗一3 ) 综合上面两个等式即得 2 3 相关组合关系式 在考虑布尔函数的代数次数和非线性度时，会涉及到一些组合关系式，这一 节中我们给出了两个在下文中将会用到的有关组合式子的引理以及一些记号 引理2 5 设扎为偶数，且佗6 ，则有 ( 1 ) ( 銎) 三0 ( m o d 2 ) ； ( 2 ) ( 銎) 三0 ( m o d4 ) 当且仅当礼不能表示成2 的方幂，即n 2 ，仃l 3 ； ( 3 ) 元n ( n - 一1 2 3 ) i 罟- - 一3 l ， 三1 ( m o d2 ) 当且仅当几形如2 - 1 或2 ”1 + 2 ，n l 2 证明不妨设n = 2 ”1 + 2 n 2 + + 2 ，其中1 n 。一1 2 m 一1 + ( 罟m - - 一2 1 ， ( 2 ) 若m 为奇数，( 翟：) 2 m - 1 + ( 军) 这个引理可由组合等式的性质及归纳法得到，具体证明过程就不在这罩详 细叙述了如当m = 7 时，( 弩) = 1 2 0 8 4 = 2 6 + ( ：) ；当m = 8 时，( 学) = 4 9 5 1 4 8 = 2 7 + ( ：) ；当m = 9 时，( 訾) = 2 0 0 2 3 2 6 = 2 8 + ( ：) 为了简便起见，下面