布尔函数在现代密码学中的应用本科学位论文.doc

布尔函数在现代密码学中的应用THE APPLICATION OF THE BOOLEAN FUNCTION IN MODERN CRYPTOGRAPHY 指 导 教 师：申请学位级别：学士论文提交日期：2014年6月9日摘 要在密码学中扮演着重要角色的布尔函数被广泛用于流密码和分组密码的分析和设计中。最主要的原因是布尔函数的密码学性质在某种程度上直接决定系统的安全性。本文是一篇关于布尔函数的密码学性质及其应用的文章。文中首先介绍了布尔函数的研究背景、重要性及国内外研究现状，并概述了密码学相关的基础知识，给出了布尔函数的定义，对其各种表示方法和研究方法进行介绍，主要介绍了真值表，小项表示等。其次讨论了布尔函数的几个密码学性质和定理，重点介绍了作为布尔函数研究的一个重要工具Walsh谱，并介绍了布尔函数的密码学性质，主要包括非线性、平衡性、相关免疫和严格雪崩等。最后重点研究了布尔函数在流密码和分组密码中的应用。序列密码体制的安全性取决于密钥流，而密钥流序列由密钥流生成器产生，在密钥流生成器中，布尔函数起着极其关键的作用。分组密码体制的算法中最具有代表性之一的是DES算法，其设计的关键是盒，而多输出布尔函数可以很好地用来描述盒。关键词：序列密码； 分组密码； 密钥流生成器； DES算法； 盒； 布尔函数； Walsh谱ABSTRACTThe 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 前言11.1 背景和意义11.2 国内外研究现状综述11.3 本文研究的主要内容22 基本理论知识32.1 密码学基本概念32.2 布尔函数的基本知识52.3 布尔函数的研究方法83 布尔函数的密码学性质103.1 布尔函数的Walsh变换及其性质103.2 布尔函数的线性性113.3 布尔函数的非线性性123.4 相关免疫性133.5 布尔函数的平衡性133.6 布尔函数的对称性143.7 严格雪崩准则143.8 扩散准则144 序列密码与布尔函数154.1 序列密码概述154.2 密钥流生成器164.3 位移寄存器164.4 序列密码中布尔函数的设计准则195 分组密码与布尔函数215.1 分组密码概述215.2 DES算法235.3 分组密码中布尔函数的设计准则306 结论31参考文献36致 谢37天津科技大学2014届本科生毕业论文1 前言1.1 背景和意义在信息技术飞速发展的今天，网络数据的传输和共享越来越复杂，信息传递过程中的安全性越来越被人们所重视，这在某种程度上推动了人们对现代密码学的研究。从第二次世界大战以来，密码学理论和技术的应用已经不在局限于某个领域，不仅涵盖了军事、国防和金融，而且包含了政府、文教和商业的各个领域1。而现在，现代密码理论及其技术已与个人信息保密与否密切相关，这也就为密码学理论及其技术的应用和研究提供了极为广阔的前景。当消息通过开放的网络发布时，可能没有任何保密的必要，但用户可能需要确保收到的消息在传输过程中尚未改变。此外，他们还需要确保他们知道发送者的身份。所以，如何保证通过互联网传来的信息来源的可靠性、完整性和安全性就显得极为重要，密码学正是能在这一问题上提供保障的重要手段之一，由于布尔函数在流密码和分组密码的加密系统中起着重要作用，而这些系统的安全性主要由布尔函数的密码学性质决定2。自1977年开始，美利坚合众国发行了第一数据加密标准，各国对密码技术的研究都是非常重视的，特别是从单钥密码到双钥密码这一突破性的进展和DES到AES的过程，更使密码算法的研究风潮一直不退。无论是单输出布尔函数还是多输出布尔函数，都在密码算法的设计与分析中起有很大的作用，如序列密码中常用的密钥流生成器，既有非线性组合生成器也有非线性滤波生成器，显然对这些生成器的分析也可归结到对布尔函数的分析。而对现代分组密码体制中的起决定作用的S盒的研究亦可归为多输出布尔函数的研究，而且现在已经将S盒的应用推广到了序列密码体制中，由此可见对密码体制某种程度归结为布尔函数的研究3。所以，为保障信息来源的完整性可靠性，必须有效地构造具有良好的加密特性的布尔函数。人们已经对布尔函数的研究比较多的有高非线性，平衡性，对称性，扩散性，相关免疫性和严格雪崩等特性，并且硕果累累，但要达到人们对信息保密程度的要求仍还有很多工作要做。总之，布尔函数在密码学中的研究不仅具有理论价值，而且具有使用价值。1.2 国内外研究现状综述人们从几千年前就开始运用密码技术了，而当Shannon在1949年发表“保密通讯信息理论”一文之后，密码学才算成为一门科学。但是1949年到1975年这段时间密码学的研究发展比较缓慢。但自1976年，赫尔曼和狄菲在其发表的“密码学的新方向”一文中提出了双钥体制，这一密码体制的提出打破了沿用已久的单钥体制，使得收发双方在建立保密通信前不再需要事先交换密钥1。在1976年，Rothaus证明了元布尔函数的非线性度是，这里是偶数2。这就是bent函数，具有高非线性，这对于抵抗线性攻击和最佳放射攻击具有很好的作用。相关免疫性作为布尔函数的一种统计性质，在布尔函数的研究中有着重要意义，它首先由Tsiegenthaler于1984年在研究流密码系统安全性时提出。我国密码学研究的代表人物肖教授发现了bent函数具有一个非常重要的性质：函数的相关免疫阶与非线性次数之间此消彼长，相互矛盾。通过降低对相关免疫性的要求，可以在非线性次数跟相关免疫阶之间找到某个平衡点，由此提出了广义相关免疫函数。严格雪崩准则首先是由Webster和Tavares在1986年提出的，这一准则对S盒的研究有重要意义。在2003年，Courtois4和Armknecht5提出的强大代数攻击使用了一个新的设计准则，即代数免疫。代数攻击的主要思想是通过求解多元代数方程组来恢复密钥。如XL算法等有效算法的出现，解决了被过度定义的多元代数方程的系统，代数攻击成功地破译出如Toyocrypt和LILI-128等比较有名的序列密码6。在此背景下，Meier, Pasalic 和Carlet 对代数免疫提出了一种新概念7：具有代数免疫性的布尔函数对抵制代数攻击具有较高的免疫性。1.3 本文研究的主要内容本文着重讨论布尔函数的密码学性质及其在密码学中应用，主要内容安排如下： 主要介绍布尔函数的研究背景和意义，以及国内外的研究现状。 主要介绍与密码学相关的概念以及密码体制和布尔函数的表示方法和研究方法。 主要介绍布尔函数的密码学性质，主要有非线性、相关免疫性和严格雪崩等 主要介绍布尔函数在序列密码中的应用，如密钥流生成器中的位移寄存器序列。 主要介绍布尔函数在分组密码中的应用，如DES算法和S盒。12 基本理论知识2.1 密码学基本概念2.1.1 密码学基本原理密码学是一门研究通信安全或密码系统的学科，现代密码学（Cryptology）由密码分析学（crypto-analytics）和密码编码学（cryptography）组成2。密码技术通过对信息进行编码来保护或隐蔽某些需保密的信息，从而防止信息在存储或传输时被未授权者删除、增添、识别、伪造或修改，从而达到实现消息保密性、可认证性的和完整性目的2。密码系统的思想是以某种方式伪装机密信息，而该方式的含义对于那些未经授权的人来说是难以理解的8。待隐藏的信息被称为明文（或只是消息），此隐藏过程被称为编码或加密的操作。经过加密的消息称为密文，加密该消息的编码工具被称为编码器，而他们发送密码电文的对象被称为接收器。使用该编码器来加密明文的一组规则称为加密算法。通常，该算法的操作将依赖于一个加密密钥，其中该编码器将加密密钥连同消息一起输入到算法中。为了使收件人可以从密文得到消息，必须有一个算法，该算法中，解密密钥将密文再现为明文，如图2-1： 加密密钥解密密钥图1密码电文信息信息 加密算法 解密算法 图2-1 算法原理即使未授权者知道解密算法，未授权者也不知道解密密钥，正是缺乏解密密钥防止他们知道明文的信息，所以密码编码学是设计密码系统和密码分析的科学，而密码分析学是从不知道密钥的密文推断明文的过程的一个名称，密码学是密码编码学和密码分析学的总称。在实践中，大多数密码攻击都与试图确定解密密钥的行为有关，因为，如果成功，攻击者就会有相同的信息成为预期收件人，并且攻击者就能够解密所有其他通信，直到密钥改变。但是，有时候攻击者唯一目的是读取某一个特定的消息。通过以上介绍可以得出：从密文获得消息时，加密密钥是不重要的。这个简单的事实已经对现代密码学产生了巨大影响，并导致其被自然划分成两种类型的密码系统公钥系统和私钥系统，这也是我们下一节将要介绍的内容。2.1.2 密码体制的分类根据不同的标准，密码体制有不同的分类。2.1.2.1 私钥密码体制和公钥密码体制1根据密码系统密钥的特点，密码体制可以分为私钥密码体制和公钥密码体制，而私钥密码体制又称对称密码体制或单钥密码体制，公钥密码体制则又称为非对称密码体制或双钥密码体制。2.1.2.1.1 私钥密码体制对于私钥密码体制主要研究的问题是怎么生成满足要求的密钥流。目前主要有以下两种方法：一是把具有良好随机性统计特征的伪随机序列作为密钥序列，二是分组加密算法。在私钥密码体制中，由于加密密钥和解密密钥相互对应，因而私钥密码体制的安全性取决于密钥的安全性。而且在进行通信前，通信的双方必须通过安全信道传送所使用的密钥，因而增加了用户的使用成本。2.1.2.1.2 公钥密码体制1976年，赫尔曼（Hellman）和狄菲（Diffie）在其发表的“密码学的新方向”中提出了公钥密码体制的概念。因为它有两个不同的密钥（公开的密钥和秘密的密钥），彼此之间很难推出对方，而且加密变换和解密变换之间可以相互交换，所以我们也称公钥密码体制为双钥密码体制。因为双钥密码体制的特点是将加解密的密钥分开，同时也就将加解密能力分开了，因此它既可用于在公共网络中实现保密通信，也可以用于认证系统中进行发送者的身份确认。公钥密码体制相对于私钥体制对通讯环境的安全性要求较弱，因而其应用领域较广，但是其运行速度较慢8。而私钥密码体制正好相反，机构简单，速度快，其运行速度是公钥密码体制的成百上千倍。其缺点就是保密程度相对较差，而现实中我们就要在他们之间找到一个平衡点，既保证一定的速度，又保证信息尽可能不泄露，所以，现实中通常是两种体制交叉并相互运用，即使用公钥密码体制来生成和交换密钥，而使用私钥密码体制来传输大量数据。使用公钥密码体制的系统成为公钥系统，它趋向于使用非常大的数字运算处理，公钥系统的两个主要用途是提供数字签名和作为加密密钥为对称密钥系统分发密钥。在每一种情况下，攻击者有两种不同的方法攻击系统。一个是在取得相关的密钥。这个可能是由通过从公钥计算密钥或通过取得其存储和/或使用该密钥的设备来实现的（该计算攻击可以通过使用合适的密钥，或者指望攻击者完成必要的计算后觉得不可行而主动放弃。涉及设备滥用的攻击必须通过良好的管理或使用适当的防篡改设备进行防御。）。另一个是对方攻击打算替换公钥。如果公钥系统被用于对称密钥加密，那么，由于攻击者的密钥已经被用于加密，公钥系统将成为攻击者，而不是获得的对称密钥的预期收件人。如果公钥系统被用来提供数字签名，那么，很明显攻击者可以伪造签名者真正的签名。要解决这一系列问题，就必须了解密码体制实现的具体方式。2.1.2.2 序列密码和分组密码根据明文消息加密方式和实现形式的不同，我们将密码体制分为流密码和分组密码。2.1.2.2.1 分组密码分组密码则是将明文消息序列分成等长的消息组（），在密钥控制下按固定的算法一组组进行加密。加密后输出的等长密文组2.1.2.2.2 序列密码序列密码也称为流密码（Stream Cipher）9，具有实现简单、加解密速度快、几乎没用错误传播的特点，所以其在专用或机密机构中有很大的优势，其应用领域主要包括无线通信、外交通信。只有一次一密的密码体制是不可能被破译的，这一结论于1949年已被香农（Shannon）证明，这极大的支持了流密码的研究，序列密码方案的研究过程便是对一次一密系统的尝试，或者说“一次一密”的密码只是序列密码的入门。如果序列密码所使用的密钥并非伪随机方式产生的、并与消息流长度相同，那么此时的序列密码即一次一密的密码体制。若我们能产生某种随机序列（密钥流），其由密钥来确定，那么用这样的序列则可进行加密，也就是将密钥、明文表示成二进制，对应地进行加密,加解密时一次性处理明文中的若干个比特。分组密码和序列密码是实现密码体制的两种基本方式，要实现密码体制，不可缺少的一个重要工具就是布尔函数（亦即该课题要研究的重点）。布尔函数在序列密码中的地位显得极为特殊而且重要。所以密码学研究的始终，一直伴随着对布尔函数的研究。2.2 布尔函数的基本知识2.2.1 布尔函数的定义定义2.2.110 设，是布尔代数中的任意数，则有若用“”、“”表示上的加、乘运算；1,0看做上的元素，则有因此布尔代数中的运算可用上的函数来表示。在本文中，我们用表示在有限域=上的所有元组中的集合的元素。然后，一个元布尔函数被定义为一个从到的映射。所有元布尔函数的集合表示为。自然地，我们将上的函数称作布尔函数。一般地我们定义如下映射：为元布尔函数，其中为二元域，为的元向量空间，记为。为了方便，我们用普通加、乘记号分别表示上的“”、“”。如记为，记为；但有时仍用记。2.2.2 布尔函数的表示为方便布尔函数的研究和应用，不同情况下将采用不同的表达方式。本节将简要介绍几种布尔函数的表示方法。2.2.2.1 真值表定义2.2.2 任何元布尔函数可以被表示为一个长度的二进制向量，这就是所谓的真值表：, （2-2-1）也称为的函数值向量，记为4。1在真值表中的个数称被为的汉明重量，记为或，如果它的真值表有相等数目的1和0，我们说是平衡的，这意味着若，=，此时则称为平衡布尔函数。2.2.2.2 小项表示定义2.2.3 对任意给定的，约定，于是设，则有 （2-2-2）为简便，今后亦记于是 （2-2-3）称为的小项表示10。小项表示其实就是布尔代数表达式，亦即逻辑表达式10。2.2.2.3 多项式表示我们知道线性空间是同构的有限域，那么在中，任意元布尔函数都可以唯一表示为二元域上的一个单变量多项式11： （2-2-4）其中，。这就是所谓的代数范式（ANF）。的代数次数记为，它是具有非零系数的最高阶项的变量的个数。若，则定义；若，则称为仿射函数；当时，仿射函数被称为线性函数；若，则称为非线性函数11。2.2.2.4 Walsh谱表示设，与的点积定义为则元布尔函数的Walsh变换定义为 （2-2-5）其逆变换为 （2-2-6） （）称为的Walsh谱。此式亦即的Walsh谱表示。因为Walsh变换可逆，因而布尔函数的Walsh谱唯一。2.2.2.5 迹函数在有限域上的布尔函数的迹函数表示为 （2-2-7）迹函数在上是线性的。2.2.2.6 矩阵表示定义2.1.4 设是一个元布尔函数，。若，则称为的一个特征向量，记的全体特征向量的集合为，将中的个向量按字典顺序从大到小排列，记第个向量，则称0,1矩阵为的特征矩阵，记为，或简记为11。由于布尔函数的特征矩阵具有唯一性，因而可以将布尔函数的某些问题转化为矩阵问题加以研究。布尔函数也可以通过投影空间的特征函数和状态图等表示。2.3 布尔函数的研究方法布尔函数有不同的表示方法10，而不同的表示方法在不同的研究中有其各自的优势，所以我们要根据不同的表示方法采用不同的研究方法，以便更好地展开研究，目前主流的研究方法有以下几种。2.3.1 代数分析方法任何可以表示为多项式形式的函数都可以使用代数方法进行分析，显然，布尔函数也不例外。从代数的角度，分析布尔函数主要采用多项式表示和小项表示。2.3.2 频谱方法频谱分析作为研究布尔函数的一个重要工具，通过其可以分析布尔函数的谱特性。2.3.3 矩阵方法布尔函数最直观的表示方法就是矩阵表示，在定序意义下，重量为的元布尔函数之集和上矩阵之间是一一对应的。2.3.4 重量分析方法对任意两个布尔函数和，定义和的距离为记为，即对和函数的重量有如下关系式： （2-3-1）重量分析方法是通过分析布尔函数的重量特征来研究布尔函数的方法，这种方法简单易懂，很适合工程应用。以上研究方法因为其特点不同，适用于不同的研究场景和领域。83 布尔函数的密码学性质布尔函数在不同领域有着不同的应用，因而衍生出了不同的函数类。人们对不同种类的布尔函数的研究归结为对布尔函数某种性质的研究。本章着重介绍布尔函数的一些重要性质。3.1 布尔函数的Walsh变换及其性质3.1.1 两种Walsh变换在2.1.2节中已经介绍过布尔函数的Walsh谱表示和Walsh变换对研究布尔函数的重要性。本节首先讨论Walsh变换及其性质。如无特别声明，均指元布尔函数。已知若记 （3-1-1）则当取遍（或）时，就得到一个函数系11：， （3-1-2）此函数系是一个正交函数系，即满足该函数系（3-1-1）称为Walsh函数系。显然，对给定的，有。可以看作在Walsh函数系下的展开式。是展开式的系数，即Walsh谱。还有另外一种展开式： （3-1-3）其中 （3-1-4）为了区别，将称为的第一种Walsh谱或线性谱，而将称为的第二种Walsh谱或循环谱。定理 3.1.1 与的关系如下： （3-1-5）3.1.2 Walsh变换的性质Walsh变换有如下性质：性质1（平稳性） 若在的谱值为，则在的谱值为 （3-1-6）性质2（线性姓） 若在的谱值为， 若在的谱值为，则在的谱值为 （3-1-7）性质3（Plancheral公式） （3-1-8）此性质又称为初值定理。性质4（Parseval公式） （3-1-9）此即能量守恒定理。3.2 布尔函数的线性性定义3.2.1 如果则称元布尔函数是部分线性的，其中；。定义3.2.2 设是元布尔函数，称为的一个线性结构，则对任意，为常数。若，称为的不变线性结构。若，称为的恒变线性结构。记全体线性结构，则是的一个线性子空间，若该子空间的维数为正，即，则称是一个线性结构函数10。记则有如下性质： ,； 是的子空间； 若，则； 设，若，则，。若，则称为的线性结构维数，此时有如下两种情况： ； ，即为空集。设是线性结构函数，若，则称为I型线性结构函数；若，这时必有，则称是一个II型线性结构函数。定义3.2.3 设，若的取值不影响的取值，则称与无关。该性质称为与变元无关性，最初称与变元无关性为退化，定义如下：定义3.2.4 设，若存在上的矩阵,使得则称是退化的。容易看出，若与变元无关，则必然退化，退化性是与变元无关性的推广12。由此可以得出如下定理：定理3.2.5 是退化的。推论：II型线性结构函数是不可退化的。定理3.2.6 是部分线性的，则是退化的。3.3 布尔函数的非线性性顾名思义，非线性性和线性性是相对的。代数次数大于一的函数是非线性函数，虽同为非线性函数，差异却很大12。例如和都是2次非线性函数，但是部分线性的，而是非退化的，比更接近线性函数，或者说更容易用线性函数来逼近，于是人们便引入了“非线性度”这一概念来描述一个函数非线性的程度10。定义3.3.1 设是元一个布尔函数，记为所有元线性函数之集。则称 （3-3-1）为的非线性度，记为，即的非线性度为其与所有线性函数的最短距离，很明显线性函数非线性度为10。同理称 （3-3-2）为的线性度，记为。，即的线性度为其与所有线性函数的最长距离。由定义3.3.1可知，对任意元布尔函数有 （3-3-3）定义3.3.2 设是元一个布尔函数，若比值函数满足，则称布尔函数具有高非线性度。对任意元布尔函数，当其非线性度时，显然布尔函数满足高非线性度，此时，我们称为Bent函数。Bent函数乃非线性度最高的函数，对布尔函数的研究有着极其重要的作用。定义3.3.3 对任意元布尔函数，若的取值不影响的取值，则称与无关。定义3.3.4 设布尔函数：，对于任意给定的，对任意的，如果恒为常数，那么称为的一个线性结构。记其中的常数为，则线性结构表示为,。3.4 相关免疫性相关免疫性作为布尔函数的一种统计性质，在布尔函数的研究中有着重要意义。定义3.4.1 设是个彼此独立且对称的元随机变量的布尔函数，当且仅当与中的个随机变量统计独立，即当且仅当互信息13 （3-4-1）时，称为阶相关免疫函数。其中对任意一组，有成立。当时，称为阶相关免疫函数10，亦叫相关免疫函数；当，称为高阶相关免疫函数。显然，如果是阶相关免疫的，则对任意，是阶相关免疫的，相关免疫记为，阶相关免疫记为，相应的函数称为函数和函数。3.5 布尔函数的平衡性我们在2.2.2节定义了平衡布尔函数：=，即的真值表中0和1的个数相等。布尔函数的很多性质，例如扩散准则、雪崩准则和相关免疫准则等都可以用平衡性来定义，平衡性也是密码函数的设计准则之一。定义3.5.1 对任意布尔函数，如果 （3-5-1）则称对变量是线性的，其中是与无关的元函数。定理3.5.2 布尔函数对自变量是线性的，当且仅当对任意有 （3-5-2）其中的取值为0或1，。3.6 布尔函数的对称性定义3.6.1 设是元布尔函数，如果对任意阶置换矩阵有 （3-6-1）则称是对称函数。显然，如果是对称函数，那么任意交换其分量的位置，不变，也就是，不妨设，。所以，对任意，只要，则，也就是说当布尔函数输出向量的汉明重量相同时，产生的输出值也不变，这就是布尔函数的线性不变性，亦称仿射不变性。3.7 严格雪崩准则严格雪崩准则由Webster和Tavares在1986年首次提出，它对研究S盒有重要意义。定义3.7.1 若对任意，总有是平衡函数，则称满足严格雪崩准则。如果固定任意个变元后得到的全部元函数都满足严格雪崩准则，则称满足阶严格雪崩准则12。定义3.7.2 若对任意，总有是平衡函数，则称为差分均匀函数。差分均匀函数有个输入个输出，任意若干个输入位发生改变，导致输出发生变化的概率为，满足这种差分均匀性的函数为Bent函数。函数满足最大非线性性等价于函数满足差分分布均匀12。3.8 扩散准则定义3.8 若对任意且，总有是平衡函数，即，则称关于满足扩散准则。若对任意满足的，关于满足扩散准则，则称满足次扩散准则。如果固定的任意个分量后得到的全部元函数都满足次扩散准则，则称满足阶次扩散准则12。阶次扩散准则就是次扩散准则。扩散准则记为，次扩散准则记为,满足相应准则的函数称为函数和函数12。在本章中，我们简要介绍了布尔函数的一些密码学特性及一些简单结论。布尔函数的密码学性质除了以上讨论的非线性、平衡性、相关免疫性、严格雪崩和扩散准则等外，还有退化性、线性结构等12。4 序列密码与布尔函数在第2章我们已经简单提到过序列密码。序列密码体制的安全性取决于密钥流，而密钥流序列由密钥流生成器产生，常见的密钥流生成器有前馈序列生成器、非线性反馈位移寄存器、非线性组合序列生成器和钟控序列生成器等1。在密钥流生成器中，布尔函数起着极其关键的作用，所以本章着重讨论布尔函数在流密码中的应用，对这些生成器我们并不一一介绍。4.1 序列密码概述4.1.1 序列密码原理现实中的各种信息或信源一般是图像、报文、语言和数据等，一般都是经编码器转化为0,1序列，即二进制序列，加密是针对0,1序列进行的。所以我们假设序列密码中的密文空间，密钥空间和明文空间均为二进制序列组成的集合14。通信系统的模型如图4-1所示。信道 明文0,1序列 恢复的明文0,1序列 密文0,1序列信源 加密器 解密器 信宿图4-1 保密通信模型在序列密码中，序列密码将明文消息序列用密钥流序列逐位加密，通过加密变换（通常采用二元加法运算）得到密文序列，因此密码系统的安全性主要取决于密钥流序列的性能。在序列密码系统中，因为明文序列与密钥流逐位加密，所以密钥流的长度必须与明文序列的长度相等，但这样的序列却难于管理和分配，所以实际中的密钥序列均由密钥空间中较短的密钥经过某些算法生成的1。当密钥流序列是完全随机序列时（一次一密钥），该系统是不可破的，称之为完全保密系统。称但通常通过确定的算法产生的密钥流序列是伪随机序列，并非完全随机，此时的密码系统就不再完全保密了，因此为了保证密码系统的安全性，密钥流序列必须满足一定的要求12。4.1.2 序列密码对密钥流的要求设计序列密码的目的是为了设计一个能产生具有完全随机性的密钥流序列生成器，而我们知道，完全随机是不可能的，所以通常主要从周期性、随机统计性和不可预测性等不同角度去衡量密钥流序列的安全性10。实际上，密钥序列通常是按一定算法生成的周期序列。为了使密钥流满足密码体制要求的安全性，避免遭受某些攻击，密钥流应当具备一定的伪随机性，所以我们对密钥流的伪随机性提出了如下要求： 尽可能大的周期。虽然随机序列是非周期的，但无论何种算法生成的序列都具有周期性，因而要求其有尽可能大的周期12； 密钥流应当具有良好的随机统计特性12； 要有很高的线性复杂度，亦即当某一部分暴露时，无法推出它的整体结构； 密钥系列易于高速生成。上述要求的前两条是为了扰乱或有效的掩盖明文序列的统计随机性，第三条是序列密码理论的核心，决定密码的强度。其包含了相关免疫性，线性复杂度和不可预测性等很多序列密码研究过程中的主要问题。第四条则主要是根据密钥流生成器的实用性考虑而提出的。这几条准则对保证系统安全性必要但非充分，也就是说对保证系统安全性是必须的，但要保证系统安全性，还需要其他条件，因此，随着对安全问题研究的深入，某种新的攻击方法的出现时，为确保系统的安全，还会提出更强的要求。4.2 密钥流生成器上一节我们讨论了序列密码对密钥流的要求，一般安全性要求越高，实现和设计也就越复杂，因此在密钥流生成器的设计中，除了考虑上面讨论的四种要求，还应考虑如下因素9: 密钥易于分配、保管和更换； 易于实现、快速10。因为位移寄存器结构简单，易于实现且运行速度快，能满足以上要求，所以目前密钥流生成器大都基于位移寄存器，这种基于位移寄存器的密钥流序列称为位移寄存器序列10。密钥流生成器通常由一个线性位移寄存器（LFSR）和非线性组合函数（布尔函数）组成。通常将这类生成器分解成线性位移寄存器，称为驱动部分，和非线性组合部分组成。因为驱动部分的设计相对更容易，因此非线性组合部分的设计便成为研究密钥流生成器的重点和难点。在二元域下，非线性组合部分可以用一个布尔函数来表示，所以对密钥流生成器的研究也就归结为对布尔函数的研究12。4.3 位移寄存器位移寄存器是密钥流生成器中不可缺少的一部分，反馈位移寄存器图4-2所示。 输出 图4-2 反馈移位寄存器图中序列由地推关系， （4-3-1）确定。称为反馈函数（二元时是布尔函数），有时也直接称为级位移寄存器，称为初始状态。由（4-3-1）式产生的序列称为由产生的递归序列，记，称为该位移寄存器在时刻的状态，则（4-3-1）式的递归关系可用状态变换描述为， （4-3-2）是由确定的状态转移变换。将每个状态看成状态空间中的一个点，按状态转移关系，若从状态转移到状态，就在状态和之间连一边：，则得位移寄存器的状态转换图，简称状态图。定义4.3.1 若一个反馈位移寄存器所产生的状态图仅由一些无公共点的圈组成，则称该反馈位移寄存器为非奇异的。定理4.3.2 上的一个级位移寄存器是非奇异的，当且仅当反馈函数可表示为 （4-3-3）其中是与无关的元布尔函数。定义4.3.3 序列是周期序列，若存在正整数使得， （4-3-4）满足（4.3.4）式的最小正整数称为序列的周期。若存在使，是周期序列，则称序列是终归周期。当位移寄存器产生的状态图仅由一个圈构成时，将产生的序列的周期首尾相连构成一个圈，则所有的长状态都出现在序列的一个周期圈上。定义4.3.4 上级位移寄存器产生的周期为的序列称为级序列。定理4.3.5 在级序列的一个周期内，0与1的个数各是，在序列的一个周期圈中，总游程为；对，长为的游程数为，其中0,1游程各占，长的游程0个。长为的0游程和1游程各1个。定理4.3.6 上的级序列的数目为。定理4.3.7 设序列的极小多项式为，则序列的周期是整除的最小正整数，即的阶。当上的级LFSR产生的序列的周期为时，称序列为级序列。为了描述序列，下面引进有限域上的迹函数。定义4.3.8 到上的