弹性布尔函数的构造

《弹性布尔函数的构造》由会员分享，可在线阅读，更多相关《弹性布尔函数的构造（65页珍藏版）》请在金锄头文库上搜索。

1、 分类号 TP391 学号 09021039 密级 公 开 理学硕士学位论文 弹性布尔函数的构造弹性布尔函数的构造 硕士生姓名 高凌 学 科 领 域 数学 研 究 方 向 编码密码理论及其应用 指 导 教 师 李超 教授 国防科学技术大学研究生院 二一一年十一月 国防科学技术大学研究生院 二一一年十一月 弹性布尔函数的构造 国防科学技术大学研究生院 Constructions of Resilient Boolean Functions Candidate：Gao Ling Advisor：Li Chao A dissertation Submitted in partial fulfillm

2、ent of the requirements for the professional degree of Master of Natural Science in Mathematics Graduate School of National University of Defense Technology Changsha，Hunan，P.R.China November，2011 国防科学技术大学研究生院硕士学位论文 第 I 页 目目 录录 摘 要 . i ABSTRACT.ii 第一章 绪论 1 1.1 选题背景. 1 1.2 国内外研究现状. 2 1.2.1 代数免疫度 2 1.2

3、.2 平衡性与相关免疫度 3 1.3 论文的组织和安排. 4 第二章 基本概念和预备知识. 5 2.1 布尔函数的基本概念. 5 2.2 代数攻击和代数免疫度. 7 2.2.1 基于LFSR的流密码的代数攻击. 7 2.2.2 代数免疫度的概念及与其它密码学指标的关系 8 2.3 弹性函数的定义和性质. 10 第三章 非线性度几乎最优的弹性布尔函数的构造. 13 3.1 弹性布尔函数的构造方法. 13 3.1.1 直接构造法 13 3.1.2 递归构造法 15 3.1.3 其他构造法 19 3.2 偶数元非线性度几乎最优弹性布尔函数的构造. 20 3.3 奇数元弹性布尔函数的构造. 24 3.

4、4 本章小结. 30 第四章 代数免疫度最优的一阶弹性布尔函数的构造. 31 4.1 基于平面理论构造MAI布尔函数的方法 . 31 4.2 Krawtchouk多项式的定义及其性质 . 33 4.3 偶数元 1 阶弹性MAI布尔函数的构造 . 35 4.3.1 构造方法 35 4.3.2 所构造函数的非线性度 39 4.4 本章小结. 44 第五章 结论与展望. 45 国防科学技术大学研究生院硕士学位论文 第 II 页 致 谢 47 参考文献. 49 作者在学期间取得的学术成果. 55 国防科学技术大学研究生院硕士学位论文 表 目 录 表 1 与文61中( ,1,) f n m nmN弹性函

5、数的非线性度的比较. 24 表 2 与文62中奇数元弹性布尔函数的非线性度的比较 28 表 3 对于偶数元n，F x与文54中给出的布尔函数非线性度的比较 44 ( ) 第 III 页 国防科学技术大学研究生院硕士学位论文 第 IV 页 图 目 录 图 1 非线性滤波生成器. 7 国防科学技术大学研究生院硕士学位论文 第 i 页 摘 要 布尔函数作为分组密码、序列密码和Hash函数中的重要组件，其密码学性质 的好坏直接关系到密码算法的安全性。布尔函数的相关免疫度是针对抵抗密码系 统的相关攻击而提出，这一概念一经提出就引起了广泛的重视，尤其是肖国镇和 Massey提出相关免疫函数的频谱特征化定理

6、(即Xiao-Massey定理)后，人们对相关 免疫函数与弹性布尔函数的认识更加深刻。代数攻击的提出为密码体制中使用的 布尔函数提出了一个新的密码学指标：代数免疫度。为了抵挡代数攻击，密码算 法中所使用的布尔函数必须具有较大的代数免疫度。因此，研究密码学指标最优 的布尔函数对于密码算法的设计与分析具有十分重要的意义。 本文首先讨论了弹性布尔函数的构造问题，在系统总结现有弹性布尔函数构 造方法的基础上， 发展了唐小虎等构造的高非线性度的1阶偶数元弹性布尔函数的 思想，分别给出了偶数元和奇数元非线性度几乎最优弹性布尔函数的构造方法， 并分析了所构造函数的非线性度。然后对基于平面理论构造的具有最大代

7、数免疫 度的布尔函数（即MAI布尔函数）的方法进行了研究，给出了一类偶数元1阶弹性 MAI布尔函数的构造方法，并计算了其非线性度，结果表明该类函数的非线性度 优于之前已有的构造结果。 主题词：布尔函数；相关免疫度；弹性函数；非线性度；代数免疫度 国防科学技术大学研究生院硕士学位论文 第 ii 页 ABSTRACT Boolean functions are important components of block ciphers, stream ciphers and Hash functions. The cryptographic criteria of Boolean function

8、s are crucial to the security of cryptographic algorithms. Correlation immune of Boolean functions is to prevent correlation attacks on the cryptographic systems and suggested that the concept was put forth, it caused widespread attention, especially Xiao Guozhen and Massey proposed the spectral cha

9、racteristics related to correlation immunity function theorem (Xiao-Massey theorem), correlation immunity function and resilient functions are more profound understanding by people. To prevent algebraic attacks, the research on Boolean functions to be used in the cryptographic systems provides a new

10、 cryptographic criteria: algebraic immunity. Possessing optimum algebraic immunity is a necessary criteria for Boolean functions used in the cryptographic systems against algebraic attacks. The study of the cryptographic criteria of Boolean functions is important in the design and analysis of crypto

11、graphic algorithms. In this thesis, the recent constructions of resilient Boolean functions are reviewed at first. Based on the system summary of the existing constructions of resilient Boolean functions, by developing the idea of the 1-resilient functions given by Tang X.H. et al., we present two c

12、lasses of even and odd variables resilient Boolean Function with almost optimal nonlinearity respectively, and analysis the nonlinearity of constructed functions. Then the construction based on plane theoretical of Boolean functions with maximum algebraic immunity (MAI) have been studied, given a cl

13、ass of n-variables 1-resilient Boolean functions with MAI, and their nonlinearities are also determined, which is higher than the Boolean functions of the existing structure. Key Words：Boolean functions；correlation immunity；resilient functions； nonlinearity；algebraic immunity 国防科学技术大学研究生院硕士学位论文 第 1

14、页 第一章 绪论 1.1 选题背景选题背景 随着计算机和网络的普及，社会信息化建设已初具规模，越来越多的商业行 为和交易及政府的服务都在公开的计算机和通讯网络进行，这也就产生了信息安 全问题。信息安全不仅关系到国家的政治、军事和外交等，而且与社会团体和个 人密切相关。因此，信息系统的安全和保密至关重要，而信息安全的核心是密码 理论与技术，即密码学。 目前，序列密码、分组密码和Hash函数的设计与分析是目前信息安全领域中 的热点问题。当前密码体制的研究基本上沿着非对称密码体制和对称密码体制这 两个方向进行。非对称密码体制对于通信环境的安全性要求相对比较弱，因此它 的应用领域越来越广。但是它的最大

15、缺点是速度比较慢，而且结构复杂。对称密 码体制正好相反，它的结构及实现都比较简单，并且速度非常快，其速度是非对 称密码体制的上百倍甚至上千倍，但它的私钥必须是保密的，这就要求必须解决 私钥交换问题。现实中使用的密码方案一般都是同时使用这两种密码体制。使用 非对称密码体制来生成和交换密钥，使用对称密码体制来加密处理大部分的数据。 按加密方式的不同，对称密码体制可分为分组密码和序列密码。分组密码的安全 强度主要取决于S盒的安全性能，而S盒可用一组布尔函数来实现，因此分组密码 的安全强度研究可归结为布尔函数的研究。而在研究序列密码时，人们常把它分 为两个部分驱动部分和非线性组合部分，驱动部分控制存储

16、器的状态转移， 负责提供若干供组合部分使用的周期大，统计特性好的序列，而线性组合部分则 将驱动部分提供的序列组合成满足要求的，密码性能更好的密钥流序列。由于线 性移位寄存器的技术己经很成熟，所以驱动部分的设计比较容易，而非线性组合 部分的设计则成为了密钥流生成器的重点和难点。非线性组合部分也可以由布尔 函数来实现，因此对序列密码的安全强度研究等价于对布尔函数的研究。因此， 布尔函数密码学性质的好坏直接关系到算法本身的安全性。 序列密码和分组密码的设计都是建立在Shannon51 引入的两个基本原则混 淆和扩散之上的。混淆旨在消除密码算法任何可能的内在代数结构，它和算法所 使用布尔函数的复杂度密切相关。扩散旨在把输入数据或是密钥的最微小变化影 响到所有输出比特上。从这两条准则提出开始，对于各种已知密码算法提出的许 多攻击一再验证这两条准则的正确性，并使得密码算法中所使用的布尔函数必须 满足各种密码学指标41, 43, 47, 52。