布尔函数在现代密码学中的应用

布尔函数在现代密码学中的应用布尔函数在现代密码学中的应用 THE APPLICATION OF THE BOOLEAN FUNCTION IN MODERN CRYPTOGRAPHY 指指 导导 教教 师：师： 申请学位级别：学士申请学位级别：学士 论文提交日期：论文提交日期：2014 年年 6 月月 9 日日 摘 要 在密码学中扮演着重要角色的布尔函数被广泛用于流密码和分组密码的分 析和设计中。最主要的原因是布尔函数的密码学性质在某种程度上直接决定系 统的安全性。本文是一篇关于布尔函数的密码学性质及其应用的文章。 文中首先介绍了布尔函数的研究背景、重要性及国内外研究现状，并概述 了密码学相关的基础知识，给出了布尔函数的定义，对其各种表示方法和研究 方法进行介绍，主要介绍了真值表，小项表示等。 其次讨论了布尔函数的几个密码学性质和定理，重点介绍了作为布尔函数 研究的一个重要工具Walsh 谱，并介绍了布尔函数的密码学性质，主要包 括非线性、平衡性、相关免疫和严格雪崩等。 最后重点研究了布尔函数在流密码和分组密码中的应用。序列密码体制的 安全性取决于密钥流，而密钥流序列由密钥流生成器产生，在密钥流生成器中， 布尔函数起着极其关键的作用。分组密码体制的算法中最具有代表性之一的是 DES 算法，其设计的关键是盒，而多输出布尔函数可以很好地用来描述盒。SS 关键词：序列密码； 分组密码； 密钥流生成器； DES 算法； 盒； 布尔S 函数； Walsh 谱 ABSTRACT The Boolean function playing an important role in cryptology is widely used in the analyses and designs of stream cipher or block cipher.The main reason is that at some degree the cryptographic properties of Boolean function directly decide the security of system.This dissertation is devoted to the cryptographic properties and applications of the Boolean functions in modern cryptography. Firstly the research background and significance of Boolean function, and the status-quo of this research both at home and abroad are introduced.And the basic knowledge of cryptography are summarized,and the Boolean function is definited , furthermore the denotation methods and the research methods of the properties of Boolean function,mainly including the truth table and polynomial denotation, etc are summarized . Secondly several cryptographic properties and theorem about the Boolean function are discussed , Walsh spectrum which is thought as an important tool of studying the Boolean function are introduced, and the cryptographic properties of the Boolean function, mainly including nonlinear, balance, related immune and strict avalanche,etc are introduced. Finally we focuse on the applications of the Boolean function in stream cipher and block cipher. The security of stream cipher depends on the key stream furthermore the key stream sequences are generated by the key stream generators where the Boolean function plays an important role.One of the most representative block cipher algorithm is DES algorithms, which the key on designing is S-box,which can be described by multiple output Boolean function. Key word：Stream cipher ; block cipher； key stream generators； S-box； Boolean function; Walsh spectrum 目 录 1 前言1 1.1 背景和意义1 1.2 国内外研究现状综述1 1.3 本文研究的主要内容2 2 基本理论知识3 2.1 密码学基本概念3 2.2 布尔函数的基本知识5 2.3 布尔函数的研究方法8 3 布尔函数的密码学性质10 3.1 布尔函数的 Walsh 变换及其性质10 3.2 布尔函数的线性性11 3.3 布尔函数的非线性性12 3.4 相关免疫性13 3.5 布尔函数的平衡性13 3.6 布尔函数的对称性14 3.7 严格雪崩准则14 3.8 扩散准则14 4 序列密码与布尔函数15 4.1 序列密码概述15 4.2 密钥流生成器16 4.3 位移寄存器16 4.4 序列密码中布尔函数的设计准则19 5 分组密码与布尔函数21 5.1 分组密码概述21 5.2 DES 算法23 5.3 分组密码中布尔函数的设计准则30 6 结论31 参考文献36 致 谢37 天津科技大学 2014 届本科生毕业论文 0 1 前言 1.1 背景和意义 在信息技术飞速发展的今天，网络数据的传输和共享越来越复杂，信息传 递过程中的安全性越来越被人们所重视，这在某种程度上推动了人们对现代密 码学的研究。从第二次世界大战以来，密码学理论和技术的应用已经不在局限 于某个领域，不仅涵盖了军事、国防和金融，而且包含了政府、文教和商业的 各个领域1。而现在，现代密码理论及其技术已与个人信息保密与否密切相关， 这也就为密码学理论及其技术的应用和研究提供了极为广阔的前景。 当消息通过开放的网络发布时，可能没有任何保密的必要，但用户可能需 要确保收到的消息在传输过程中尚未改变。此外，他们还需要确保他们知道发 送者的身份。所以，如何保证通过互联网传来的信息来源的可靠性、完整性和 安全性就显得极为重要，密码学正是能在这一问题上提供保障的重要手段之一， 由于布尔函数在流密码和分组密码的加密系统中起着重要作用，而这些系统的 安全性主要由布尔函数的密码学性质决定2。 自1977年开始，美利坚合众国发行了第一数据加密标准，各国对密码技术 的研究都是非常重视的，特别是从单钥密码到双钥密码这一突破性的进展和 DES到AES的过程，更使密码算法的研究风潮一直不退。 无论是单输出布尔函数还是多输出布尔函数，都在密码算法的设计与分析 中起有很大的作用，如序列密码中常用的密钥流生成器，既有非线性组合生成 器也有非线性滤波生成器，显然对这些生成器的分析也可归结到对布尔函数的 分析。而对现代分组密码体制中的起决定作用的S盒的研究亦可归为多输出布尔 函数的研究，而且现在已经将S盒的应用推广到了序列密码体制中，由此可见对 密码体制某种程度归结为布尔函数的研究3。 所以，为保障信息来源的完整性可靠性，必须有效地构造具有良好的加密 特性的布尔函数。人们已经对布尔函数的研究比较多的有高非线性，平衡性， 对称性，扩散性，相关免疫性和严格雪崩等特性，并且硕果累累，但要达到人 们对信息保密程度的要求仍还有很多工作要做。 总之，布尔函数在密码学中的研究不仅具有理论价值，而且具有使用价值。 1.2 国内外研究现状综述 人们从几千年前就开始运用密码技术了，而当 Shannon 在1949年发表“保 密通讯信息理论”一文之后，密码学才算成为一门科学。但是1949年到1975年 这段时间密码学的研究发展比较缓慢。但自1976年，赫尔曼和狄菲在其发表的 “密码学的新方向”一文中提出了双钥体制，这一密码体制的提出打破了沿用 天津科技大学 2014 届本科生毕业论文 1 已久的单钥体制，使得收发双方在建立保密通信前不再需要事先交换密钥1。 在1976年，Rothaus 证明了元布尔函数的非线性度是，这里n 1n/2 1 22 n 是偶数2。这就是 bent 函数，具有高非线性，这对于抵抗线性攻击和最佳放n 射攻击具有很好的作用。 相关免疫性作为布尔函数的一种统计性质，在布尔函数的研究中有着重要 意义，它首先由 Tsiegenthaler 于 1984 年在研究流密码系统安全性时提出。我国 密码学研究的代表人物肖教授发现了 bent 函数具有一个非常重要的性质：函数 的相关免疫阶与非线性次数之间此消彼长，相互矛盾。通过降低对相关免疫性 的要求，可以在非线性次数跟相关免疫阶之间找到某个平衡点，由此提出了广 义相关免疫函数。 严格雪崩准则首先是由 Webster 和 Tavares 在 1986 年提出的，这一准则对 S 盒的研究有重要意义。 在 2003 年，Courtois4和 Armknecht5提出的强大代数攻击使用了一个新的 设计准则，即代数免疫。代数攻击的主要思想是通过求解多元代数方程组来恢 复密钥。如 XL 算法等有效算法的出现，解决了被过度定义的多元代数方程的 系统，代数攻击成功地破译出如 Toyocrypt 和 LILI-128 等比较有名的序列密码6。 在此背景下，Meier, Pasalic 和 Carlet 对代数免疫提出了一种新概念7：具 有代数免疫性的布尔函数对抵制代数攻击具有较高的免疫性。 1.3 本文研究的主要内容 本文着重讨论布尔函数的密码学性质及其在密码学中应用，主要内容安排 如下： 主要介绍布尔函数的研究背景和意义，以及国内外的研究现状。 主要介绍与密码学相关的概念以及密码体制和布尔函数的表示方法和研 究方法。 主要介绍布尔函数的密码学性质，主要有非线性、相关免疫性和严格雪 崩等 主要介绍布尔函数在序列密码中的应用，如密钥流生成器中的位移寄存 器序列。 主要介绍布尔函数在分组密码中的应用，如 DES 算法和 S 盒。 天津科技大学 2014 届本科生毕业论文 2 2 基本理论知识 2.1 密码学基本概念 2.1.1 密码学基本原理 密码学是一门研究通信安全或密码系统的学科，现代密码学（Cryptology） 由密码分析学（crypto-analytics）和密码编码学（cryptography）组成2。密码技 术通过对信息进行编码来保护或隐蔽某些需保密的信息，从而防止信息在存储 或传输时被未授权者删除、增添、识别、伪造或修改，从而达到实现消息保密 性、可认证性的和完整性目的2。 密码系统的思想是以某种方式伪装机密信息，而该方式的含义对于那些未 经授权的人来说是难以理解的8。待隐藏的信息被称为明文（或只是消息） ，此 隐藏过程被称为编码或加密的操作。经过加密的消息称为密文，加密该消息的 编码工具被称为编码器，而他们发送密码电文的对象被称为接收器。使用该编 码器来加密明文的一组规则称为加密算法。通常，该算法的操作将依赖于一个 加密密钥，其中该编码器将加密密钥连同消息一起输入到算法中。)(Ek 为了使收件人可以从密文得到消息，必须有一个算法，该算法中，解密密 钥将密文再现为明文，如图 2-1： )(Dk 图 1 图 2-1 算法原理 即使未授权者知道解密算法，未授权者也不知道解密密钥，正是缺乏解密 密钥防止他们知道明文的信息，所以密码编码学是设计密码系统和密码分析的 科学，而密码分析学是从不知道密钥的密文推断明文的过程的一个名称，密码 学是密码编码学和密码分析学的总称。 在实践中，大多数密码攻击都与试图确定解密密钥的行为有关，因为，如 果成功，攻击者就会有相同的信息成为预期收件人，并且攻击者就能够解密所 有其他通信，直到密钥改变。但是，有时候攻击者唯一目的是读取某一个特定 的消息。 加密算法 解密算法 加密密钥解密密钥 信息 信息 密码电文 天津科技大学 2014 届本科生毕业论文 3 通过以上介绍可以得出：从密文获得消息时，加密密钥是不重要的。这个 简单的事实已经对现代密码学产生了巨大影响，并导致其被自然划分成两种类 型的密码系统公钥系统和私钥系统，这也是我们下一节将要介绍的内容。 2.1.2 密码体制的分类 根据不同的标准，密码体制有不同的分类。 私钥密码体制和公钥密码体制1 根据密码系统密钥的特点，密码体制可以分为私钥密码体制和公钥密码体 制，而私钥密码体制又称对称密码体制或单钥密码体制，公钥密码体制则又称 为非对称密码体制或双钥密码体制。 .1 私钥密码体制 对于私钥密码体制主要研究的问题是怎么生成满足要求的密钥流。目前主 要有以下两种方法：一是把具有良好随机性统计特征的伪随机序列作为密钥序 列，二是分组加密算法。 在私钥密码体制中，由于加密密钥和解密密钥相互对应，因而私钥密码体 制的安全性取决于密钥的安全性。而且在进行通信前，通信的双方必须通过安 全信道传送所使用的密钥，因而增加了用户的使用成本。 .2 公钥密码体制 1976 年，赫尔曼（Hellman）和狄菲（Diffie）在其发表的“密码学的新方 向”中提出了公钥密码体制的概念。因为它有两个不同的密钥（公开的密钥和 秘密的密钥） ，彼此之间很难推出对方，而且加密变换和解密变换之间可以相互 交换，所以我们也称公钥密码体制为双钥密码体制。 因为双钥密码体制的特点是将加解密的密钥分开，同时也就将加解密能力 分开了，因此它既可用于在公共网络中实现保密通信，也可以用于认证系统中 进行发送者的身份确认。 公钥密码体制相对于私钥体制对通讯环境的安全性要求较弱，因而其应用 领域较广，但是其运行速度较慢8。而私钥密码体制正好相反，机构简单，速 度快，其运行速度是公钥密码体制的成百上千倍。其缺点就是保密程度相对较 差，而现实中我们就要在他们之间找到一个平衡点，既保证一定的速度，又保 证信息尽可能不泄露，所以，现实中通常是两种体制交叉并相互运用，即使用 公钥密码体制来生成和交换密钥，而使用私钥密码体制来传输大量数据。 使用公钥密码体制的系统成为公钥系统，它趋向于使用非常大的数字运算 处理，公钥系统的两个主要用途是提供数字签名和作为加密密钥为对称密钥系 统分发密钥。在每一种情况下，攻击者有两种不同的方法攻击系统。一个是在 取得相关的密钥。这个可能是由通过从公钥计算密钥或通过取得其存储和/或使 用该密钥的设备来实现的（该计算攻击可以通过使用合适的密钥，或者指望攻 天津科技大学 2014 届本科生毕业论文 4 击者完成必要的计算后觉得不可行而主动放弃。涉及设备滥用的攻击必须通过 良好的管理或使用适当的防篡改设备进行防御。 ） 。另一个是对方攻击打算替换 公钥。如果公钥系统被用于对称密钥加密，那么，由于攻击者的密钥已经被用 于加密，公钥系统将成为攻击者，而不是获得的对称密钥的预期收件人。如果 公钥系统被用来提供数字签名，那么，很明显攻击者可以伪造签名者真正的签 名。要解决这一系列问题，就必须了解密码体制实现的具体方式。 序列密码和分组密码 根据明文消息加密方式和实现形式的不同，我们将密码体制分为流密码和 分组密码。 .1 分组密码 分组密码则是将明文消息序列 12 ,.,. k m mm 分成等长的消息组 （） ， 12 ,., n m mm 12 (,.,),. nn mm 在密钥控制下按固定的算法一组组进行加密。加密后输出的等长密文组 k E 112 (,.,),(,.,),. mmn yyyy .2 序列密码 序列密码也称为流密码（Stream Cipher）9，具有实现简单、加解密速度快、 几乎没用错误传播的特点，所以其在专用或机密机构中有很大的优势，其应用 领域主要包括无线通信、外交通信。只有一次一密的密码体制是不可能被破译 的，这一结论于 1949 年已被香农（Shannon）证明，这极大的支持了流密码的 研究，序列密码方案的研究过程便是对一次一密系统的尝试，或者说“一次一密” 的密码只是序列密码的入门。如果序列密码所使用的密钥并非伪随机方式产生 的、并与消息流长度相同，那么此时的序列密码即一次一密的密码体制。若我 们能产生某种随机序列（密钥流） ，其由密钥来确定，那么用这样的序列则可进 行加密，也就是将密钥、明文表示成二进制，对应地进行加密,加解密时一次性 处理明文中的若干个比特。 分组密码和序列密码是实现密码体制的两种基本方式，要实现密码体制， 不可缺少的一个重要工具就是布尔函数（亦即该课题要研究的重点） 。布尔函数 在序列密码中的地位显得极为特殊而且重要。所以密码学研究的始终，一直伴 随着对布尔函数的研究。 2.2 布尔函数的基本知识 2.2.1 布尔函数的定义 定义 2.2.110 设，是布尔代数中的任意数，则有 1 x 2 x 天津科技大学 2014 届本科生毕业论文 5 1 x 2 x 12 1 ,1 0 , x x 当同时为时 其他 1 x 2 x 12 0 ,0 1 , x x 当同时为时 其他 若用“” 、 “”表示上的加、乘运算；1,0 看做上的元素，则有 2 F 2 F 1 x 2 x 1 x 2 x 1 x 2 x 1 x 2 x 1 x 2 x 1 x 1 x1 因此布尔代数中的运算可用上的函数来表示。 2 F 在本文中，我们用表示在有限域=上的所有元组中的集合的元 n F2 2 F1 , 0n 素。然后，一个元布尔函数被定义为一个从到的映射。所有元布尔函n n F2 2 Fn 数的集合表示为。自然地，我们将上的函数称作布尔函数。一般地我们定 n B 2 F 义如下映射： ：)(xf n F2 2 F 为元布尔函数，其中为二元域，为的元向量空间，记为n 2 F n F2 2 Fnx n F2 。为了方便，我们用普通加、乘记号分别表示上的“” 、 “” 。如f 2 F 1 x 记为，记为；但有时仍用记。 2 x 21 xx 1 x 2 x 21x x 1 x 1 x1 2.2.2 布尔函数的表示 为方便布尔函数的研究和应用，不同情况下将采用不同的表达方式。本节 将简要介绍几种布尔函数的表示方法。 真值表 定义2.2.2 任何元布尔函数可以被表示为一个长度的二进制向量，这就n n 2 是所谓的真值表： , （2-2-1）)11 , 1 ()0, 0 , 1 ()0, 0 , 0(，ffff 也称为的函数值向量，记为 4。1在真值表中的个数称被为 的汉明重量，)(xf ff 记为或，如果它的真值表有相等数目的1和0，我们说是平衡的，这( )w f f wf 意味着若，=，此时则称为平衡布尔函数。( )w f 1 2 n )(xf 小项表示 定义2.2.3 对任意给定的，约定 i x i c 2 F ， 1 i x i x ii xx 0 于是 时，当 时，当 i i i ic i cx cx x i 0 1 设 ，),.,( 1n ccc ),.( 1n xxx 则有 天津科技大学 2014 届本科生毕业论文 6 （2-2-2） n c n cc xxx. 21 21 nn nn ccxx ccxx .).(, 0 .).(, 1 11 11 当 当 为简便，今后亦记 n c n cc xxx. 21 21 c x 于是 （2-2-3）)(xf 12 0 )( n i c xxf 称为的小项表示10。小项表示其实就是布尔代数表达式，亦即逻辑表达式)(xf 10。 多项式表示 我们知道线性空间是同构的有限域，那么在中，任意 n F2 n F2 21 0 ( ) n i i i f xa x 元布尔函数都可以唯一表示为二元域上的一个单变量多项式11：n n Bf 2 F .)( 2112110 xxxxxf nn ,. 21,.2, 111nnnn xxxxxa （2-2-4） n njjk jjjj k kk xxaaa .1 , 1 0 1 11 . 其中，。 0 a i 212 Fa n 2 2 )( ii aa n F2221 n i 这就是所谓的代数范式（ANF） 。的代数次数记为，它是具有)(xf)( fdef 非零系数的最高阶项的变量的个数。若，则定义；若0)(xf0)(fdef ，则称为仿射函数；当时，仿射函数被称为线性函数；若1)(fdef)(xf0 0 a ，则称为非线性函数11。2)(fdef)(xf Walsh 谱表示 设，与的点积定义为 1 ( ,.,) n xxx 1 (,.,) n www 2 n Fxw x wA 11 . nn x wx w 2 F 则元布尔函数的 Walsh 变换定义为n( )f x （2-2-5） 21 0 ( )2( 1)( ) n nw x f x Swf x A 其逆变换为 （2-2-6） 21 0 ( )( )( 1) n w x f x f xSw A （）称为的 Walsh 谱。此式亦即的 Walsh 谱表示。)(wSfw n F2)(xf)(xf 天津科技大学 2014 届本科生毕业论文 7 因为 Walsh 变换可逆，因而布尔函数的 Walsh 谱唯一。 迹函数 在有限域上的布尔函数的迹函数表示为 22 :FFtr n （2-2-7） 1 2 0 ( ) t n t tr xx 迹函数在上是线性的。 2 F 矩阵表示 定义 2.1.4 设是一个元布尔函数，。若，则称为)(xfn n Fx 2 1)(xfx 的一个特征向量，记的全体特征向量的集合为，)(xf)(xfD . 1 )(| 2 n FaafaD wD 将中的个向量按字典顺序从大到小排列，记第 个向量，则称Dwi i wwi 1 0,1 矩阵 wnww n n ccc ccc ccc . . . . 21 22221 11211 为的特征矩阵，记为，或简记为 11。 )(xf f CC 由于布尔函数的特征矩阵具有唯一性，因而可以将布尔函数的某些问题转 化为矩阵问题加以研究。布尔函数也可以通过投影空间的特征函数和状态图等 表示。 2.3 布尔函数的研究方法 布尔函数有不同的表示方法10，而不同的表示方法在不同的研究中有其各 自的优势，所以我们要根据不同的表示方法采用不同的研究方法，以便更好地 展开研究，目前主流的研究方法有以下几种。 2.3.1 代数分析方法 任何可以表示为多项式形式的函数都可以使用代数方法进行分析，显然， 布尔函数也不例外。从代数的角度，分析布尔函数主要采用多项式表示和小项 表示。 2.3.2 频谱方法 频谱分析作为研究布尔函数的一个重要工具，通过其可以分析布尔函数的 谱特性。 天津科技大学 2014 届本科生毕业论文 8 2.3.3 矩阵方法 布尔函数最直观的表示方法就是矩阵表示，在定序意义下，重量为的w 元布尔函数之集和上矩阵之间是一一对应的。n 2 Fnw)21 ( n w 2.3.4 重量分析方法 对任意两个布尔函数和，定义和),.,()( 1n xxfxf),.,()( 1n xxgxg)(xf 的距离为)(xg )(gfw 记为，即),(gfd ),(gfd)(gfw 对和函数的重量有如下关系式： （2-3-1）)(gfw)( fw)(gw)(2fgw 重量分析方法是通过分析布尔函数的重量特征来研究布尔函数的方法，这 种方法简单易懂，很适合工程应用。 以上研究方法因为其特点不同，适用于不同的研究场景和领域。 天津科技大学 2014 届本科生毕业论文 9 3 布尔函数的密码学性质 布尔函数在不同领域有着不同的应用，因而衍生出了不同的函数类。人们 对不同种类的布尔函数的研究归结为对布尔函数某种性质的研究。本章着重介 绍布尔函数的一些重要性质。 3.1 布尔函数的 Walsh 变换及其性质 3.1.1 两种 Walsh 变换 在 2.1.2 节中已经介绍过布尔函数的 Walsh 谱表示和 Walsh 变换对研究布 尔函数的重要性。本节首先讨论 Walsh 变换及其性质。如无特别声明，均)(xf 指元布尔函数。n 已知 21 0 ( )( )( 1) n w x f x f xSw A 若记 （3-1-1）( )( 1)w x w Qx A 则当取遍（或）时，就得到一个函数系11：w n F2 1 20 n w ， （3-1-2）)(xQww n F2 此函数系是一个正交函数系，即满足 )(xQu)(xQv vu vu n , 0 ,2 该函数系（3-1-1）称为 Walsh 函数系。显然，对给定的，有xw)(xQw 。)(wQx 可以看作在 Walsh 函数系下的展开式。是展 21 0 ( )( )( 1) n w x f x f xSw A )(xf)(wSf 开式的系数，即 Walsh 谱。 还有另外一种展开式：)(xf （3-1-3）)(xf)()( 2 1 2 1 12 0 )( xQwS w w f n 其中 （3-1-4）)() 1( 2 1 )( 12 0 )( )( xQwS w w xf n f n 天津科技大学 2014 届本科生毕业论文 10 为了区别，将称为的第一种 Walsh 谱或线性谱，而将称为)(wSf)(xf)( )( wS f 的第二种 Walsh 谱或循环谱。)(xf 定理 3.1.1 与的关系如下：)(wSf)( )( wS f （3-1-5）)( )( wS f 0),(21 0),(2 wxS wwS f f 3.1.2 Walsh 变换的性质 Walsh 变换有如下性质： 性质 1（平稳性） 若在的谱值为，则在的谱值为)(xfw)(wSf)(axfw （3-1-6）)(),(wSawQ f 性质 2（线性姓） 若在的谱值为， 若在的谱值为，)(xfw)(wSf)(xgw)(wSg 则在的谱值为)()(xbgxafw （3-1-7）)()(wbSwaS gf 性质 3（Plancheral 公式） （3-1-8）)(2)0()( 12 0 2 fwSxS n f w f n 此性质又称为初值定理。 性质 4（Parseval 公式） （3-1-9）1)( 12 0 )( 2 xS n w f 此即能量守恒定理。 3.2 布尔函数的线性性 定义 3.2.1 如果 ),.,( 1n xxf),.,(,.,( 11nbnbn xxlxxg 则称元布尔函数是部分线性的，其中n ；。 n bni iinbn xcxxl 1 1 ),.,(1, 2 bFc n i 定义 3.2.2 设是元布尔函数，称为的一个线性结构，)(xfn n Fa 2 a)(xf 则对任意，为常数。若，称为的 n Fx 2 )()(xfaxf0)()(xfaxfa( )f x 不变线性结构。若，称为的恒变线性结构。记全1)()(xfaxfa( )f xE 天津科技大学 2014 届本科生毕业论文 11 体线性结构，则是的一个线性子空间，若该子空间的维数为正，即E n F2 ，则称是一个线性结构函数10。0Dim)(xf 记 0)()(| 0 xfaxfEaE 1)()(| 1 xfaxfEaE 则有如下性质： ,； 10 EE 10 EEE 是的子空间； 00, 0EEE 若，则； 1 E 101 ,EaEaE 设，若，则，。 r E2 0 1 E r E2 1 1 2 r E 若，则称为的线性结构维数，此时有如下两种情况：12 q Eq)(xf ； 1 10 2| q EE ，即为空集。,2 0 q E 0 1 E 1 E 设是线性结构函数，若，则称为I型线性结构函数；若)(xf0 0 E)(xf ，这时必有，则称是一个II型线性结构函数。0 0 E1 1 E)(xf 定义 3.2.3 设，若的取值不影响的取值，则称)(xf),.,( 1n xxf i x)(xf 与无关。该性质称为与变元无关性，最初称与变元无关性为退化，定义)(xf i x 如下： 定义 3.2.4 设，若存在上的矩阵,使得)(xf),.,( 1n xxf n F2kn)(nk D ),.,()(),.,( 11kn yygxDgxxf 则称是退化的。)(xf 容易看出，若与变元无关，则必然退化，退化性是与变元无关性的推)(xf 广12。由此可以得出如下定理： 定理 3.2.5 是退化的。)(xf0 0 E 推论：II型线性结构函数是不可退化的。 定理 3.2.6 是部分线性的，则是退化的。)(xf)(xf 3.3 布尔函数的非线性性 顾名思义，非线性性和线性性是相对的。代数次数大于一的函数是非线性 函数，虽同为非线性函数，差异却很大12。例如和 43211 )(xxxxxf 都是 2 次非线性函数，但是部分线性的，而是非退 43212 )(xxxxxf)( 1 xf)( 2 xf 化的，比更接近线性函数，或者说更容易用线性函数来逼近，)( 1 xf)( 2 xf)( 1 xf 于是人们便引入了“非线性度”这一概念来描述一个函数非线性的程度10。 定义 3.3.1 设是元一个布尔函数，记为所有元线性函数之集。)(xfnxLnn 则称 （3-3-1） min xLl n ),(lfd min xLl n )(lfw 为的非线性度，记为，即的非线性度为其与所有线性函数的最短)(xf f N)(xf 天津科技大学 2014 届本科生毕业论文 12 距离，很明显线性函数非线性度为 10。同理称 0 （3-3-2） max xLl n ),(lfd 为的线性度，记为。 ，即的线性度为其与所有线性函数的最长距离。)(xf f C)(xf 由定义 3.3.1 可知，对任意元布尔函数有n)(xf （3-3-3） f N f C n 2 定义 3.3.2 设是元一个布尔函数，若比值函数满足)(xfn 1 2/)( n f Nnq ，则称布尔函数具有高非线性度。 lim (x)1 x q ( )f x 对任意元布尔函数，当其非线性度时，n( )f x 1/2 1 22 nn f N ，显然布尔函数满足高非线性度，此时，我们称 n/2 (n)1 2q lim (x)1 x q 为 Bent 函数。( )f x Bent 函数乃非线性度最高的函数，对布尔函数的研究有着极其重要的作用。 定义 3.3.3 对任意元布尔函数，若的取值不影响的),.,()( 1n xxfxf i x 取值，则称与无关。( )f x( )f x i x 定义 3.3.4 设布尔函数：，对于任意给定的，(x)f 22 n FF 2 , n aF且 0a 对任意的，如果恒为常数，那么称为的一个线性结 2 n xF(x)(x)ffaa(x)f 构。记其中的常数为，则线性结构表示为b ,。 2 |( )() n b ExFf xf axb 2 bF 3.4 相关免疫性 相关免疫性作为布尔函数的一种统计性质，在布尔函数的研究中有着重要 意义。 定义 3.4.1 设是个彼此独立且对称的元随机变量的布),.,()( 1n xxfxfn2 尔函数，当且仅当与中的个随机变量统计独立，即当且仅当互信( )f x 1,.,n xxn 息13 （3-4-1） 1 ( ( );,.,)0 m ii I f x xx 时，称为阶相关免疫函数。其中对任意一组，有( )f xm 1,.,m ii xx 成立。 1 1. m iin 当时，称为 阶相关免疫函数10，亦叫相关免疫函数；当，1m ( )f x12m 称为高阶相关免疫函数。显然，如果是阶相关免疫的，则对任意( )f x( )f xm ，是 阶相关免疫的，相关免疫记为，阶相关免疫记为1rm( )f xrCImCI ，相应的函数称为函数和函数。( )mCICI( )m 3.5 布尔函数的平衡性 我们在 2.2.2 节定义了平衡布尔函数：=，即的真值表中 0( )w f 1 2 n ( )f x 和 1 的个数相等。布尔函数的很多性质，例如扩散准则、雪崩准则和相关免疫 天津科技大学 2014 届本科生毕业论文 13 准则等都可以用平衡性来定义，平衡性也是密码函数的设计准则之一。 定义 3.5.1 对任意布尔函数，如果),.,()( 1n xxfxf （3-5-1） 1111 ( )( ,.,.,) iiin f xxf xxxx 则称对变量是线性的，其中是与无关的元函数。 i x 1( ) f x i x1n 定理 3.5.2 布尔函数对自变量是线性的，当且仅当对任 1 ( )( ,.,) n f xf xx i x 意有 1,.,n xx （3-5-2） 1 ( ,.,.,) in f xxx 1 ( ,.,.,) in f xxx 其中的取值为 0 或 1，。 i x1in i x 1 i x ( )1ff A 3.6 布尔函数的对称性 定义 3.6.1 设是元布尔函数，如果对任意阶置换矩阵有( )f xnnP （3-6-1）( )()f xf xP 则称是对称函数。( )f x 显然，如果是对称函数，那么任意交换其分量的位置，不变，也( )f x( )f x 就是，不妨设，。所以，ij ij 1 ( ,.,.,.,) ijn f xxxx 1 ( ,.,.,.,) jin f xxxx 对任意，只要，则，也就是说当布尔函数输出 2 , n x yF( )(y)w xw( )(y)f xf 向量的汉明重量相同时，产生的输出值也不变，这就是布尔函数的线性不变性， 亦称仿射不变性。 3.7 严格雪崩准则 严格雪崩准则由 Webster 和 Tavares 在 1986 年首次提出，它对研究 S 盒有 重要意义。 定义 3.7.1 若对任意，总有是平衡函数， 2 n aF( )1w a ( )()f xf xa 则称满足严格雪崩准则。如果固定任意个变元后得到的全部元函数( )f xknk 都满足严格雪崩准则，则称满足阶严格雪崩准则12。( )f xk 定义 3.7.2 若对任意，总有是平衡函数，则称 2 n aF0a ( )()f xf xa 为差分均匀函数。( )f x 差分均匀函数有个输入 个输出，任意若干个输入位发生改变，导致输出n1 发生变化的概率为，满足这种差分均匀性的函数为 Bent 函数。函数满足最1/ 2 大非线性性等价于函数满足差分分布均匀12。 3.8 扩散准则 定义 3.8 若对任意且，总有是平衡函数，即 2 n aF0a ( )()f xf xa ，则称关于满足扩散准则。若对任意满足 n 1 ( ( )()2w f xf xa ( )f xa 的，关于满足扩散准则，则称满足次扩散准则。如1( )w