（应用数学专业论文）一类密码函数的构造及其研究.pdf

摘要 随着通信和计算机技术的不断发展，信息在社会中的地位和作用越来越重 要与此同时信息的安全问题也已成为人们关注的社会问题而信息安全的核心 是密码理论与技术在密码体制的构造中，布尔函数被广泛地应用，对分组密码 中s 一盒和流密码中组合生成器等的研究，实质上可归结为对布尔函数的分析另 外，布尔函数在编码、组合设计和序列设计等也扮演着重要的角色本文主要研 究了布尔函数中的p l a t e a u e d 函数，取得以下主要结果： ( 1 )对一类三次p l a t e a u e d 函数进行了研究，证明了该函数具有高非线性度且没有 非零线性结构借助对称矩阵给出了该函数和三次齐次p l a t e a u e d 函数等价的 条件，并给出了构造该三次齐次p l a t e a u e d 函数的具体方法 ( 2 ) 利用m a i o r a n a m c f a r l a n d 构造法构造出一类p l a t e a u e d 函数；在此基础上， 结合m 序列的状态转移矩阵，构造出了刀元( 刀+ 1 ) 2 维的玎一1 阶p l a t e a u e d 函数所构造的多维p l a e t a u e d 函数可以满足多个密码指标：高非线性度、没 有非零线性结构、平衡、代数次数达到最高等 关键词：布尔函数b e n t 函数p l a t e a u e d 函数s 盒 a b s t r a c t w i t ht h ed e v e l o p m e n to ft h ec o m m u n i c a t i o na n dt h ec o m p u t e rt e c h n o l o g y , t h e s t a t u sa n df u n c t i o no fi n f o r m a t i o nb e c o m e s 南o r ea n dm o r ei m p o r t a n ti ns o c i e t y a tt h e s a m et i m e t h ei n f o r m a t i o ns e c u r i t yi s s u e sh a v eb e c o m eas o c i a lp r o b l e mw h i c hi s p e o p l e su p p e r m o s tc o n c e r n c r y p t o g r a p h y i st h ec o r eo fi n f o r m a t i o ns e c u r i t y t e c h n o l o g y b o o l e a nf u n c t i o n sc a nb eu s e dt oc o n s t r u c ts o m ec r y p t o s y s t e m s w i d e l y i h e s t u d i e so fm a n yp r o b l e m so fs y m m e t r i cc i p h e rs y s t e m ，s u c ha st h es - b o x e si nb l o c k c i p h e ra n dt h ec o m b i n i n gf u n c t i o n si n s t r e a mc i p h e r a r ee q u i v a l e n tt ot h es t u d i e s0 1 b 0 0 1 e a nf u n c t i o n s b o o l e a nf u n c t i o n sa l s op l a yi m p o r t a n tr o l e si nc o d i n gt h e o r y c o m b i n a t o r i a ld e s i g na n ds e q u e n c ed e s i g n t h ef o c u so ft h i st h e s i si so np r o p e r t i e sa n d c o n s t r u c t i o n so fp l a t e a u e df u n c t i o n s t h em a i nr e s u l t sa r ea sf o l l o w s ： ( 1 ) ac l a s so fc u b i cp l a t e a u e df u n c t i o n sh a sb e e ni n v e s t i g a t e d i ti s s h o w nt h a tt h e f u n c t i o n sh a v eh i g hn o n l i n e a r i t ya n dn on o n z e r ol i n e a rs t r u c t u r e s ac o n d i t i o nl s g i v e nt h a tt h ef u n c t i o n sa r ee q u i v a l e n tt oc u b i ch o m o g e n o u sp l a t e a u e df u n c t i o n s b vm e a n so ft h es y m m e t r i cm a t r i x e s b e s i d e s ，am e t h o df o rc o n s t r u c t i n gac l a s so t c u b i ch o m o g e n o u sp l a t e a u e df u n c t i o n si sp r e s e n t e d t o o ( 2 1ac l a s so fp l a t e a u e d f u n c t i o n sh a sb e e ng o t t e nb yw a y o fu s i n gt h e m 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 n b yt h ec h a r a c t e ro ft h es t a t et r a n s f o r r f lm a t r i x o fm - s e q u e n c e ，ac l a s so f ( n + 1 ) 2 d i m e n s i o np l a t e a u e df u n c t i o n sw i t hn v a r i a b l e s i sc o n s t r u c t e d av a r i e t yo fc r y p t o g r a p h i c a l l yd e s i r a b l ec r i t e r i af o rm u l t i d i m e n s i o t q f u n c t i o n sc o u l db es a t i s f i e d ：h i g hn o n l i n e a r i t y , n o n e x i s t e n c eo fn o n z e r ol i n e m s t r u c t u r e s ，b a l a n c ea n dt h eh i g h e s ta l g e b r a i cd e g r e ee t c k e y w o r d s ：b o o l e a nf u n c t i o n s b e n tf u n c t i o n sp l a t e a u e df u n c t i o n s s - b o x e s 西安电子科技大学 学位论文创新性声明 秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在 导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特另t l d n 以标 注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成 果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说 明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切的法律责任。 本人签名：毯! 堑嚷 日期j 西安电子科技大学 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保 留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内 容，可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后 结合学位论文研究课题再攥写的文章一律署名单位为西安电子科技大学。 ( 保密的论文在解密后遵守此规定) 本学位论文属于保密，在一年解密后适用本授权书。 本人签名：亟丝2 巫豸乙 聊躲每 日期趔。必z 驴 日期兰掣筘 第一章绪论 第一章绪论 密码学是- f i 古老而又年轻的学科，它用于保护军事和外交通信可追溯到几 千年前在当今社会，随着信息时代的到来和计算机网络的迅速发展和普及，大 量的敏感数据如病历、法庭记录、资金转移、私人财产和商业机密等通过公共通 信设施或计算机网络来进行传输，而这些信息的秘密性和真实性是人们迫切需要 的因此，当代密码学的应用不再限于政治、军事和外交领域，其越来越多的商 业价值和社会价值也被认可 1 1 密码学简介 密码学包含密码编码学和密码分析学两个分支密码编码学的主要任务是寻 找保证信息的机密性和可认证性的方法，密码分析学的主要任务是研究加密信息 的破译和信息的伪造这两个分支相互独立，又统一；正是这种对立促进了密码 学的飞速发展 1 9 4 9 年s h a n n o n 发表了保密系统的通信理论【l 】一文，为密码学奠定了坚实 的理论基础，使密码学从此成为一门真正的科学1 9 7 6 年，d i f f i e 矛i h e l l m a n 发表的 密码学的新方向1 2 】导致了密码学上的一场革命首次证明了在发送端和接受端 无密码传输的保密问题是可能的，从而丌创了公钥密码学的新纪元公钥密码学 是密码分配问题和消息认证问题的产物，许多公钥体系既可用于认证，又可用于 消息保密近几年来，人们已经认识到了认证和保密是两个独立的密码属 性s i m m o n s 对认证问题进行了系统的研究，他建立了一套与s h a n n o n 保密理论平 行的认证理论 现代密码学形成于2 0 世纪7 0 年代，其中重要的标志有两个：一个是美国国家 标准局正式公布实施数据加密标准( d e s ) d 】，另一个是公钥密码体制的诞生【2 】【4 1 ， 这两个事件在密码学的发展史上具有罩程碑意义，成为现代密码学的开端 随后，密码学得到了迅速的发展，进入了一个全新的时期，各种更加安全的 加密算法、签名方案、攻击方法等被提出并广泛应用例如：1 9 7 8 年提出的r s a 方案1 5 1 、1 9 8 2 年a c y a o 提出的计算复杂度方法、1 9 8 5 年提出的e lg a m a l l 方案【6 】、 零知识证明思想、椭圆曲线密码系统、h a s h 函数、1 9 9 0 年b i h a m 和s h a m i r 提出的差 分密码分析方法【7 1 、1 9 9 3 年m i t s u r um a t s u i 的线性密码分析方法等1 9 9 7 - 2 0 0 0 年美 国高级加密标准a e s 的征集活动以及2 0 0 0 2 0 0 3 年欧洲n e s s i e 计划的实施，再一次 掀起了密码研究的高潮2 0 0 4 年2 月，欧洲启动了为期四年的e c r y p t i 程，目标 一类密码函数的构造及其研究 是促进欧洲信息安全研究人员在密码学和数字水印研究上的交流，促进学术界和 工业界的持久合作同年1 1 月，e c r y p t 发布了征集流密码算法的活动，这是对2 0 0 0 年欧洲委员会启动的n e s s i e - 1 - 程没有征集到流密码算法标准的一个补充 根据密钥的特点，密码体制分为对称和非对称密码体制对称密码体制又称 单钥或私钥或传统密码体制，非对称密码体制又称双钥或公钥密码体制在对称 密码体制中，加密密钥和解密密钥是一样的或彼此之问容易相互确定而非对称 密码体制中，用作加密的密钥和用作解密的密钥不同，且解密密钥不能根据加密 密钥计算出来对称和非对称密码体制在运行效率上也有很大的不同，非对称密 码体制相对对称密码体制来讲运算速度比较慢，但它在通信中有自己的优点在 实际的应用当中，一般采用二者结合的方法，特别是在协议中，充分发挥了二者 结合的功效 1 2 密码函数的研究背景和研究现状 随着信息化技术的快速发展，信息的安全性已成为信息化社会的焦点目前， 密码技术已经成为保障电子商务、通信安全以及保护公民隐私的关键技术因此， 密码技术的研究受到各军事大国的高度重视，使密码技术得到了迅速发展一些 早期的密码算法已经不能满足现代社会的需要为此，美国国家标准局于1 9 9 7 年 公丌征集a e s ( a d v a n c ee n c r y p t i o ns t a n d a r d ) 1 8 ，欧洲委员会在2 0 0 0 年投资2 4 6 j j 欧 元开始一项新的欧洲数字签名、数据的完整性和加密计戈i j n e s s i e ( n e we u r o p e a n s c h e m e sf o rs i g n a t u r e si n t e g r i t ya n de n c r y p t i o n ) p 】在欧美推出各自计划的同时，同 本也相应的推出了c r y p t r e c 计划，以提高在密码领域的影响力，保证信息传输 的安全继n e s s i e 结束后，欧洲于2 0 0 4 年又启动了一个更大的为期四年的信息安 全项目e c r y p t ( e u r o p e a nn e t w o r ko fe x c e l l e n c ef o rc r y p t o l o g y ) 0 1 0 j ，以上的项目都 是为了促进信息安全研究人员的交流 本文研究的密码函数主要用于对称密码的设计，即分组密码和流密码的设计 流密码，又称序列密码序列密码的加密和解密思想非常简单：用一个密钥 流序列与明文序列进行叠加来产生密文，用同一个密钥流序列与密文叠加来恢复 明文密钥流序列由密钥流生成器产生，密码函数在密钥流生成器的设计中扮演 着重要的角色密码函数通常是布尔函数，有些情况下，一般有限域上的函数， 或者其它代数结构上的函数也成为研究的对象 基于线性移位寄存器( l f s r ) 的密钥流生成器有非线性滤波生成器、非线性组 合生成器都要用到密码函数厂( x ) ( 如图1 1 所示) 第一章绪论 图1 1非线性滤波生成器和非线性组合生成器 由于有代数工具对l f s r 进行分析，其理论技术已非常成熟，这使驱动部分的 设计相当容易非线性组合部分的设计是密钥流生成器的重点和难点，它归结为 对密码函数的研究在二元情形下，非线性组合部分可用一个布尔函数表示在 实际应用中，为了提高密钥流的复杂性，所用的布尔函数是高代数次数的且没有 低次数的零化子另外，为了抵抗相关攻击【1 1 】【1 2 1 【1 3 】1 14 1 ，函数应该具有适当的弹性 阶和高非线性度值得一提的是，随着研究的深入，为了避免针对基于l f s r 的各 种攻击，人们意识到寻找新的驱动部分设计方法同样重要在欧洲e c r y p t 工程中 征集到的流密码算法中就有基于t 函数、n l f s r 、随机数组等驱动部件的例子 一些基于数论、几何等数学工具构造的密码函数，往往也具有优良的密码学 性质有限域上的幂函数是种实现简单、安全性好的密码函数，被广泛地应用于 序列和s 盒的设计 密码函数也被用于分组密码的设计中d e s 是分组密码的一个最经典的例子， 它的安全性取决于s 盒密码学性质的好坏，而s 盒可以用多输出布尔函数来描 述分组密码中用到的各种置换也可以看作多输出密码函数可以看出，构造密 码学性质优良的多输出密码函数是设计较高安全性的分组密码体制的关键 h a s h 函数可用于认证系统，它的设计与分组密码中s 盒的设计有许多相似之 处非线性函数在h a s h 函数的设计中有重要的应用 s h a n n o n 扩散和混淆的思想是对称密码系统设计中的两个基本原则，对密码 函数的设计和分析有着重要的指导意义 在密码函数所有的指标中，非线性度是很重要的一个指标，它与s h a n n o n 提 出的混淆原则密切相关非线性度不高的密码函数，其复杂性必然不好，用于流密 码和分组密码是不安全的非线性度是布尔函数的一个组合性质，它与一阶 r e e d m u l l e r 码t ”j 密切相关r o t h a u s l l 6 】在1 9 7 6 年首次证明了刀元布尔函数的非线性 度最大可达到2 ”一2 州2 ，这里刀为偶数，称达到最高非线性度的密码函数为b e n l 函数这类密码函数能有效的抵抗线性攻击【1 7 】和最佳仿射逼近( b a a ) 攻击1 1 引一 个密码函数还应满足平衡性，b e n t 函数却不是平衡的，这限制了它在密码学中的 4 一类密码函数的构造及其研究 直接应用于是构造以为偶数时，具有很高非线性度的平衡布尔函数成为人们考虑 的一个问题而确定平衡布尔函数的最大非线性度至今仍是一个公开问题当胛为 奇数且门7 时，布尔函数的最大非线性度是2 ”1 2 ”) 坨；当丹为奇数且刀9 时， 布尔函数的最大非线性度还不知道 人类在研究密码函数时，总是考虑多个密码学指标一类3 w a l s h 谱值的密码 函数逐渐引起了人们的重视，我们通常称之为p l a t e a u e d 函数【l9 1 这类函数能实现 多个密码学指标的折衷 相关免疫函数是s i e g e n t h a l e r 2 0 】为防止攻击者对密码系统进行d c ( 分别征服) 攻击而提出的这个概念一经提出就引起广泛重视尤其是肖囤镇年i m a s s e y 提出 相关免疫函数的频谱特征化定理( 国际上称为x i a o m a s s e y 定理【2 1 】) 后，人们对相 关免疫函数的认识更加深刻s i e g e n t h e l o r 不等式表明，布尔函数的相关免疫阶t 与 它的代数次数有很强的相互制约性：任何露元t 阶相关免疫函数的代数次数至多为 力一f ；任何t 阶弹性函数( 0 m 刀一1 ) 的代数次数都不超过玎一m 一1 ；任何以一1 阶 弹性函数的代数次数为1 人们逐渐认识到过分的强调相关免疫弊大于利相关免 疫性对密码函数的非线性度也有很强的制约密码函数的相关免疫性表现出来的 是一种规律性，因而和s h a n n o n 扩散和混淆的思想是背道而驰的 弹性函数的概念最初是f l d c h o r 等人【2 2 1 和b e n n e t t 等人1 2 3 1 分别独立提出随着密 码分析学的发展，人们更加认识到高非线性度弹性函数的重要性 密码函数的代数次数以及其代数正规型中单项式中的个数也影响着密码函数 的复杂性程度密码函数必须具有较高的代数次数，代数次数低的密码函数也不 能抵抗f l ：l k n u d s e n 矛l l a i 提出的高阶差分攻击【2 4 】【2 5 1 ；而代数次数低、单项式个数少 的密码函数用作非线性组合函数时，生成序列的线性复杂度不高，因而不能抵抗 b e r l e k a m p m a s s e y 算法攻击【2 6 1 【2 7 】c a d e t 注意到一个事实，给了一个定义：一个单 项式个数较多的密码函数在仿射变换下得到的最小的单项式个数定义为密码函数 的“代数厚度 这个指标对衡量密码函数的复杂性有重要的参考价值，对构造 复杂性好的密码函数也有指导意义 近几年来，兴起了一种有效又有趣的攻击方法一“代数攻击”这种攻击已 经成功的应用于一些基于l f s r 的流密码系统中为了抗击代数攻击，m e i e r 等1 2 引 引入了新的密码学指标：代数免疫( a l g e b r a i ci m m u n i t y ) 目前，具有最大代数免 疫阶的布尔函数成为人们感兴趣的研究课题 值得一提的是，利用有限域上的迹函数和幂函数可以得到具有优良密码学性 质的密码函数【2 9 1 目前，人们对于非线性理论知之甚少，加上密码体制本身的缺陷，使得构造 性能优良的密码函数不是一件容易的事，但人们关于密码函数的研究从来没有停 i e 过 第一章绪论 1 3 本文的研究意义 随着计算机和网络在社会政治、经济、文化、生产等领域的普及，社会信息 化已成为当今世界发展的潮流和核心与此同时信息的安全问题也已成为世人关 注的社会问题而信息安全的核心是密码理论与技术密码体制的研究基本上就 沿着这两个方向一非对称密码体制和对称密码体制进行 非对称密码体制对于通信环境的安全性要求相对比较弱，因此它的应用领域 越来越广但是它的最大缺点是速度比较慢，而且结构复杂对称密码体制正好 相反，它结构及实现都比较简单，并且速度非常快，其速度是非对称密码体制的 上百倍甚至上千倍但它的私钥必须是保密的这就要求必须解决私钥交换问 题现实中使用的密码方案一般都是同时使用这两种密码体制使用非对称密码 体制来生成和交换密钥，而使用对称密码体制来传输大部分的数据 对称密码体制的安全性主要是取决于密码体制中核心部件性能的好坏对分 组密码而言，安全强度主要取决于s 盒的安全性能而s 盒可用一组布尔函数来实 现，因此分组密码的安全强度的研究归结为布尔函数的研究在研究流密码时， 人们常把它分为两个部分一驱动部分和非线性组合部分由于线性移位寄存器的 技术己经很成熟，所以驱动部分的设计比较容易，而非线性组合部分的设计则成 为了密钥流生成器的重点和难点而非线性组合部分也可以由布尔函数来实现， 因此对非线性组合部分的研究等价于对布尔函数的研究为了抵抗各种攻击，使 用的布尔函数必须满足若干密码学准则，因此对具有良好的密码学性质的布尔函 数的研究是很有意义的 1 4 本文章节安排 本文的主要工作和内容安排如下： 第一章介绍了密码学的发展，密码函数的研究背景、研究现状和本论文的内容 安排 第二章介绍有限域的基本知识、布尔函数及其w a l s h 变换并给出了布尔函数的 安全性度量指标 第三章简述了b e n t 函数和p l a t e a u e d 函数的基本概念以及它们之间的关系，并 给出了三次齐次p l a t e a u e d 函数的构造方法 第四章介绍了m a i o r a n a m c f a r l a n d 类函数，在此基础上，构造了一类多维 p l a t e a u e d 函数 第二章基础知识 7 第二章基础知识 帚一早墨田面刘以 为了严谨而有条理地阐述本文，我们有必要先对一些重要的背景知识作简单 介绍，同时引入一些符号在以后的各章节里，如果不作特殊说明，符号代表的 意义都和本章定义的一样 2 1 有限域和线性空间 定义2 1 设g 是一个非空集合， 的变换g 到g 的满射称为满变换， 置换 矽是集合g 到g 自身的映射，则称是g 中 单射称为单变换，一一映射称为一一变换或 定义2 2 设g 是一个非空集合，在g 内定义了一种代数运算”；并满足以下 性质： ( 1 ) 封闭性对任意口，b g ，恒有a b g ； ( 2 ) 结合律对任意口，b ，c g ，恒有( a 6 ) c = a ( 6 c ) ； ( 3 ) g 中有一单位元e 存在，对任意a g ，恒有a e = e a = a ； ( 4 ) 对任意a g ，存在a 的逆元a 一g ，使a a = 口a 一= e ； 则称g 构成一个群 若群g 中，对任何a ，b g ，有a b = b 口，则称g 为交换群，也g q a b e l 群元 素个数有限的群称为有限群，元素的个数称为该有限群的阶若一个群g 的每一 个元素都是g 的某一个固定元a 的乘方，就称g 为循环群，称a 是g 的生成元由 置换组成的集合，在复合的运算下组成一个置换群 定义2 3 s 是一个非空集合，若在s 中定义了加法”+ ”和乘法”两种运算， 且满足下述性质： ( 1 ) s 关于加法运算构成a b e l 群，其加法单位元记为0 ： ( 2 ) s 中所有非零元素关于乘法运算构成a b e l 群，其乘法单位元记为1 ； ( 3 ) 对任意口，b ，c s ，加法和乘法间存在如下分配律： 口( 6 + f ) = a b + a c ，( 6 + c ) a = b 口+ c a 则称s 是一个域 由有限个元素的集合所构成的域称为有限域，也叫伽罗瓦( g a l o i s ) 域；域中 元素的个数称为该有限域的阶，记为q ，用g f ( q ) 或e 表示g 阶有限域 定义2 4s 是一个非空集合，若在s 中定义了加法”+ ”和乘法”两种运算， 且满足下述性质： 8 类密码函数的构造及其研究 ( 1 ) s 关于加法运算构成a b e l 群； ( 2 ) s 关于乘法运算有封闭性，且乘法适合结合律； ( 3 ) 对任意口，b ，c s ，加法和乘法间存在如下分配律： a ( b + c ) = a b + 口c ，( 6 + c ) 口= b a + c a 则称s 是一个环 域就是一种特殊的环 下面说明环中的一些性质 定理2 1 任何a b s ，有 ( i ) a 0 = 0 a = 0 ； ( i i ) a ( 一6 ) = ( 一口) b = 一口b ； ( i i i ) ( q ) ( 匆) = a j 屯 i = li = l i = 1 i = l 密码函数是定义在有限域或环上的逻辑函数，我们通常称满足某些密码学性 质的函数为密码函数，而布尔函数就是密码学中广泛使用的一类密码函数 定义2 5 设玩是分量取自域c 上的 元有序数组的集合，在k 中任意两个 元素之间都定义了加法”+ ”，并且对c 中任意元素和圪中任何元素之间都定义了乘 法”若玩关于这两种运算满足下述条件： ( 1 ) 阼关于加法构成a b e l 群； ( 2 ) 对任意x 酩，“c ，恒有甜x ，且当u = 1 时，1 x = x ； ( 3 ) 分配律成立对任意x ，y 玩，1 ，c ，恒有 u ( x + y ) = u x + 材y ，( “+ ，) x = “x + ，x ( 4 ) 结合律成立对任意x 玩，材v c ，恒有( ”v ) x = “( v x ) ； 则称圪是域c 上的一个甩维线性空间或向量空间 定义2 6 若子集k 圪，且满足线性空间的条件，则称k 是k 的一个子空 间 由定义可知，要确定一个集合是否是子空间，只要检测两点即可：( 1 ) 这个元 素集合是否关于加法构成a b e l 群；( 2 ) 数乘是否封闭 第二章基础知识 9 定理2 2 线性空间k 中矢量，。，v ：，v 。的所有线性组合所构成的集合s 是圪 的子空间 2 2 布尔函数及其w a l s h 变换 在本文中g f ( 2 ) ”与圪是等价的，它们均表示一个具有疗个g f ( 2 ) 元素的向量 空间x 是向量空间圪的一个向量，它是从0 至2 以一1 的一个整数的二进制表示， 例如x = ( x o ，而，一。) ，其中x o ，x j ，一。取值为0 或1 ( x ) 是一个取值为0 或1 的函数可以看到n 元布尔函数是刀个输入1 个输出的函数 定义2 7一般地，我们定义n 元布尔函数为以下映射： ( x ) ：g f ( 2 ) ”一g f ( 2 ) 其中x g f ( 2 ) ”，f ( x ) g f ( 2 ) 布尔函数的表示方法有：多项式法、小项表示法、真值表法、w a l s h 谱表示、 矩阵表示法以及状态图表示法【3 0 】 下面给出几种表示方法： 1 多项式表示 将x o , = x j0 1 上式中化简，将得到函数的多项式表示，实践证明，任意门布尔 函数f ( x ) 均可化为如下的多项式： f ( x ) = 0q 葺o o 毛 。口1 2 x l x 2o o 一l 。h 矗一1 o o 口l ，2 ， x l x 2 x n = a oq l 钳曼汹，n i i j k x j l i “x j i 其中“o 表示g f ( 2 ) 上的加，称上式为函数f ( x ) 的代数标准型或者代数正规型定 义函数( x ) 的次数为m a x ki , 矗0 ) ，记为d e g f 定义2 8 定义g f ( 2 ) ”上的仿射函数： ( 五，毛) = g 1 x io 饪) a n x no c 其中a i ，c g f ( 2 ) ，待l ，2 ，刀此外，如果c = 0 那么f ( x ) 被称为线性函数 1 0 一类密码函数的构造及其研究 2 小项表示 对于x ，c ，g f ( 2 ) ，规定 于是 x _ = x ix o , = i 砰= 忙豢i 嚣 设e = ( q ，巳) ，x = ( 葺，毛) ，则有 为了方便，今后记 牲钟= 锰豢_ 臻乳暑 十是 厂( x ) = f ( c ) x 。 c e g i ( 2 厂 其中厂( c ) 是真值表中c 对应的函数值小项表示布尔函数代数表达方式这种表示 法常用于布尔函数的设计实现 3 真值表 定义在圪上的函数厂( x ) 的真值表是( o ，1 ) 序列，定义为： ( ( ) ，f ( a 1 ) ，f ( o t 2 q ) ) 如果真值表中的o 和1 的个数相等，那么( x ) 就是平衡的函数厂的( 1 ，一1 ) 序列定义为： ( ( 一1 ) ，( ) ，( 一1 ) 。r ( q ) ，( 一1 ) ，口，一) 其中= ( o ，0o ) ，q = ( o ，01 ) ，一l = ( 1 ，1 ，1 ) 真值表是一种列表法，通过真值表可以给出f ( x ) 的解析表达式 4w a l s h 谱表示 w a l s h 变换是研究布尔函数的重要工具，布尔函数的许多特征都可以用w a l s h 谱表示 定义2 9 设x = ( j c l ，x 2 ，毛) ，国= ( q ，c 0 2 ，q ) g f ( 2 ) ”，x 与缈的点积定义为 第二章基础知识 x 国= qo 而哆o o 而q r t 元布尔函数f ( x ) 的第一种w a l s h 变换( 线性w a l s h 变换) 为 2 ”一l ( 缈) = ( 一1 ) ”。厂( x ) x = o 逆变换为 2 ”一l ( x ) = 2 一( 缈) ( 一1 ) ”。 m = 0 墨( 缈) 称为函数厂( x ) 的第一种w 矾s h 谱( 线性谱) 若将( x ) 的w a l s h 谱曲( 缈) 按缈的字典从小到大排列，就得到一个实向量： ( 墨( o ) ，量( 1 ) ，砖( 2 ”一1 ) ) w a l s h 变换是可逆的，所以布尔函数的w a l s h 谱是唯一的于是，我们就可以 建立布尔函数与2 ”维实向量的一一对应关系，从而将布尔函数的某些问题转化为 实向量来研究 5 矩阵表示 定义2 1 0 设f ( x ) 是g f ( 2 ) ”上的刀元布尔函数，若f ( x ) = 1 ，则称x 为f ( x ) 自勺 一个特征向量，记f ( x ) 的全体特征向量的集合为s s = 口if ( c t ) = l ，口g f ( 2 ) ”) 记l s l = w ，其中w y 赫- 0 且t l + 1 2 = t , 如下：矩阵e ：z ( 门 的行和列的下标分别用倪：和吼：中的元素表示，对于u 倪：，v 孵z ，矩阵 一类密码函数的构造及其研究 碰! z ( 厂) 中行标为u 列标为y 的元素为口f ，u 矿；对，c 1 ，2 ，刀) ，i ，i ，取口，2 0 对r ( t ，n ) r ( t 一1 ，刀) ，f 1 ，记( 厂) = 朋础( 倒i f 卜, n 。) ( ) ) 如果f r ( t ，门) ，则定义 ( 厂) = ( 厂or ( t l ，刀) ) 设e = ( f ，七) if ，七为整数) 是一个无序三元组的集合，如果巨一( u 川髟) g ， 则称无序三元组集合e 叫做规则无序三元组集，其中e = ( ，k ) l ( f ，j ，k ) e ) 设2 n - 1 元布尔函数g ( x ) 是式( 3 一1 ) 中的一个三次p l a t e a u e d 函数，则 r 3 ( g ) = 甩。记 n - i g ( x ) - ( ，息e x , x ：k 。x i x i + 其中e 是一个无序三元组的集合 接下来给出该函数的矩阵表示g ( x ) 的三次项部分记为 厂( 五，x 2 ，) 2 ( f 品；x j x j x k g ( x ) 的二次项部分记为 n - ! g ( x i ，x 2 川) = 9x i x i ，善i 记x = ( x ，x 2 川) = x ( i ) 圆x ( 2 ) ，其中 1 ) = ( _ ，邑) ，x ( 2 ) = ( 矗+ l ，x 2 川) 则 g 似) 的二次项部分可以表示为 g ( x ，x ：川) = n 鲁- i x ，x m = x 簖， 其中q = ( ；趵，7 是一个。一1 ) 仰一1 ) 阶单位阵- 我们知道r 3 ( 厂) = r 3 ( g ) 为获得g ( x ) 的三次项部分的矩阵表示，构造一个”行 丛专尘列的矩阵档( ) ：该矩阵的行标用婀? 中的元素表示，矩阵的列标用稍6 2 中 的元素表示；如果( f ，七) e ，那么矩阵的第f 行和第( j f ，七) 列的元素取为1 ；否则， 矩阵中元素就取为0 。于是g ( z ) 的三次项部分可以表示为 f ( x l ，x 2 ，_ 。) = x j ) q ：) 第三章高非线性度三次齐次p l a t e a u e d 函数 2 5 其中z ( 1 ) = ( x l x 2 ，x l x 3 ，x 。一l x 。) ，c = c ( 厂) = b 8 ”( 厂) 7 从而我们获得了式( 3 1 ) 中函数g ( x ) 的矩阵表示 g ( x ) = x 而q 五ox o x , ) ( 3 2 ) 设f ( x ) 和g ( x ) 是两个”元布尔函数，如果存在一个非奇异的矩阵d g l ( n ，2 ) ， b g f ( 2 ) ”，使得f ( x d ) e = g ( x ) ，那么我们称厂和g 等价，记为f 兰g 引理3 2 4 4 1 设a = ( ) 是一个? ix ”阶方阵，g f ( 2 ) ，1 f ，j 刀， x = ( 而，x n ) g f ( 2 ) ”，则x a x7 1 是一个线性布尔函数当且仅当a = a r 证明如果x a x 7 是一个线性布尔函数，那么存在一个向量b g f ( 2 ) ”使得 x a x7 = 工b 7 我们知道x b7 = b x r ，故 x 4 x 7 = 剃7 x 7 1 所以a = 彳7 假设a = a7 ，把x 4 x7 展丌可得 x a x r ，a t x j x j 2 i o = l a l ，# o 鲁l f f i ，蒙。( 0 9 ，) 嘞i ，车，+ i ” = o q ， i - - i x j 所以x a x 是线性函数 下面来讨论上面的三次p l a t e a u e d 函数与三次齐次p l a t e a u e d 函数等价的充分必 要条件文献 4 9 出了变元个数为偶数b e n t 函数的情形，这罩运用类似的方法给 出变元个数为奇数情形时的讨论，从而进一步获得三次齐次p l a t e a u e d 函数的构 造设n xp 阶矩阵d = ( 办) ，l f 门，l p 记矩阵的第列为d ，则 d = ( 吐，d ，) 记 d = ( d l 木d 2 ，d l 幸d ，d 2 * d 3 9 o,o 9 d ，一i 宰d ，) 定理2 设g ( x ) 2 悬。f x r ，x ，。是n x 。x ，是式( 3 1 ) 中的一个三次p l a t e a u e d 函数， 其中i j 9 七，f 尼，甜1 ，q 是无序2 元组，g ( x ) 和一个三次齐次p l a t e a u e d 函数 2 6一类密码函数的构造及其研究 等价当且仅当存在一个非奇异的( 2 n - 1 ) x ( 2 n - 1 ) 阶矩阵d = b ”固q ：) ，满足以下 条件 ( 珥) cod q ) = d ( 。) ( 硪) cod q ) r 其中d ( ”是个( 2 刀- 1 ) x ，- 阶矩阵，= 吩( g ) 证明 g ( x ) 的三次项部分记为 厂( x ) - 是。圩x ，坼( ，j ” ( 3 3 ) 固定( f ，七) e ，y = x d ，d = ( d ，见) ，；e o o d ，是矩阵的第f 列，d 。表示矩阵d 的第 ，列第行的元素， 其中 是三次齐次多项式，而 y , y | y k 。x d , x d i x d k = 固x u d h l x v d 以x w d w k ，v ，w = i = 与os 2 s t2 。固x u d h - x v d v r x w d 。k = 5 ：j k v r w 1 4 ” j 2 = ( 叟o 。叟。o 叟oo ) 吒以，x ，叱x 。d w k h = r = “r 2 u = = - ， = l ( 。叟。o ，叟。) o ( o o 叟) o ( ooo ) x 。z ，x ，民x 。d 。 、 h = r h = = h l = 1 4 r“= v = wh r = w；v 之w t， 一 = ( 里z ，z 。) ( 里以。x 。) o ( 里以，吃。吒) ( 粤d , ：x ，) o ( 旦吐骨d , ：l x 。) ( 生吃，x u ) = i”= i = iv = lr = l“= l = x ( d i 毒d ? | 、) x d k 固x l d | 毒d k ) x d jx ( d i 毒d k 、) x d 是次数小于三的多项式那么， f ( x d _ ( t ，) = i 思。，x d ，：x d ，蛾 2 仉恩。，岛to 仉息。f ( x ( p 宰d ，) 以o x ( d ，木协) x d ，o x ( 9 ，宰q ) x d ) 2 仉息。，k 。鲁m x ( d ，木q ) j 以 | = 凡e 固x 战f ( x 丫 其中，定! ； ( x ) 2 暑“毛tt ， j e ，： 第三章高非线性度三次齐次p l a t e a u e d 函数 则有 g ( x d ) = 厂( x o , i ) ) ox d q ( x d ( 1 ) ) 7 = 日( x ) ox ( 臻) co d 9 ) 球) x r 从而g ( x ) 兰h ( x ) 的充分必要条件是存在一个非奇异的矩阵，使得 x ( 珥) c o d q ) d 二) x7 是x 的一个线性函数由引理3 2 知，只需( 珥) c o d q ) d 石) 是一 个对称矩阵，于是定理得证 定理3 3 设2 n 一1 元布尔函数g ( x ) 是式( 3 - 1 ) 中的一个三次p l a t e a u e d 函数， 如果能够找一个( 2 刀一1 ) x ( 2 n - 1 ) 阶非奇异矩阵。= ( 三0 ，其中，是一个刀甩单 位矩阵，0 是一个i ( 疗一1 ) 阶零矩阵，m 是一个一1 ) x ( 珂一1 ) 阶非奇异矩阵， a = ( ) ，g f ( 2 ) ， i = l ，n - 1 ，= l ，刀那么g ( x d ) 是一个三次齐次 p l a t e a u e d 函数当且仅当 a * c = ( m0 ) ( 3 4 ) 其中，c 由式( 3 2 ) 定义，0 是零向量，a c 表示4 + 和c 的乘积 证明 g o ) 都能表示成型如式( 3 2 ) 的矩阵表示，此时9 和d 分别为 q = 阶 其中q 为( 2 n - 1 ) x 门阶矩阵，q 中的，是一个( n - 1 ) x ( n - 0 阶单位阵，d 为 ( 2 n - 1 ) xn 阶矩阵，b ，) 中的，是一个刀 阶单位矩阵有 耻赃 由定理3 2 知，g ( x ) 兰日( z ) 当且仅当( 3 - 3 ) 成立，其中h ( x ) 是一个三次齐次 布尔函数此时 ( 珥) c od q ) d 5 ) =? 。jn 幻