布尔函数代数免疫性质研究

论文摘要

2003年法国密码学专家N.Courtois提出代数攻击以来,代数攻击被广泛用于分析各类密码算法,密码算法中布尔函数的代数免疫性能已成为判断布尔函数密码学性能好坏的一个重要准则。目前,代数攻击最成功的实例是针对序列密码Toyocrypt和LILI-128的攻击。文献利用这两个密码算法中非线性函数各自存在的低次零化子,建立了关于输入、输出和密钥的低次方程组,成功破译了这两个算法。通过分析我们发现,这两个算法所使用的非线性函数的补函数也存在低次零化子,且数量与原函数的低次零化子数量相同,利用这一点,我们可建立两倍于文献的代数方程,使得代数攻击破译这两个算法所需明密文对的数量减少了一半。对安全性基于非线性布尔函数的密码算法,找出其非线性布尔函数的低次零化子是利用代数攻击方法破译这类密码算法成效的关键。本文利用布尔函数支撑点逻辑相邻关系和函数代数次数的联系,给出了一种计算布尔函数低次零化子的新方法——卡诺图法,并分析了卡诺图法和目前几个有代表性的计算布尔函数零化子算法的区别和联系。布尔函数的代数免疫阶是体现布尔函数抗代数攻击能力强弱的重要指标。本文分析了两个布尔函数相加生成新函数的代数免疫阶的变化情况,还给出了布尔函数通过非线性级联组合生成新函数的代数免疫阶变化结果。同时,文章还对这两种函数组合方式在均衡布尔函数其它密码学性质上的作用进行了分析。另外,文章还分析了布尔函数代数免疫阶与布尔函数汉明重量、非线性度、相关免疫阶等密码学性质之间的相互关系。最大代数免疫阶布尔函数是一类抗代数攻击最有效的布尔函数。文章证明了最大代数免疫阶平衡布尔函数本身及其补函数都存在代数次数为代数免疫阶的零化子。文章还对一种最大代数免疫阶布尔函数——择多函数进行了分析,研究了这种函数的平衡性、对称性、Walsh循环谱、自相关性、非线性度以及相关免疫阶等密码学性质。文章还介绍了三种已有的构造最大代数免疫阶布尔函数的方法,重点分析了这三种构造函数的一些其它密码学性质。

论文目录

• 目录
• 摘要
• Abstract
• 第一章 引言
• 1.1 布尔函数代数免疫性质的研究背景
• 1.2 基础知识
• 1.2.1 布尔函数及其表示方法
• 1.2.2 布尔函数密码学性质的相关定义
• 1.2.3 布尔函数代数免疫性质的相关定义
• 1.3 本文内容安排
• 第二章 代数攻击介绍
• 2.1 代数攻击的原理
• 2.1.1 序列密码的代数攻击
• 2.1.2 分组密码的代数攻击
• 2.2 代数攻击实例
• 2.2.1 对 Toyocrypt算法的代数攻击
• 2.2.2 对 LILI-128算法的代数攻击
• 2.2.3 对 AES算法的代数攻击
• 2.3 小结
• 第三章 布尔函数的零化子
• 3.1 布尔函数零化子的性质
• 3.1.1 零化子的性质
• 3.1.2 min deg（An（f））的相关性质
• 3.1.3 平衡函数存在d次零化子的概率
• 3.2 布尔函数零化子的计算方法与分析
• 3.2.1 算法1
• 3.2.2 算法2
• 3.2.3 算法3
• 3.3 一种计算布尔函数零化子的新方法—卡诺图法
• 3.3.1 基本定义
• 3.3.2 利用卡诺图表示布尔函数
• 3.3.3 卡诺图和布尔函数的简化表达式
• 3.3.4 利用卡诺图计算布尔函数的零化子
• 3.4 小结
• 第四章 布尔函数的代数免疫阶
• 4.1 布尔函数的代数免疫性质
• 4.1.1 相关定义
• 4.1.2 布尔函数零化子的利用问题
• 4.1.3 #LDAn（f）的计数问题
• 4.2 组合布尔函数的代数免疫阶
• 4.2.1 布尔函数相加后代数免疫阶的变化情况
• 4.2.2 级联函数的代数免疫阶
• 4.3 代数免疫阶与其它密码学性质的关系
• 4.3.1 代数免疫阶与函数汉明重量的关系
• 4.3.2 代数免疫阶与非线性度的关系
• 4.3.3 代数免疫阶与相关免疫阶的关系
• 4.4 小结
• 第五章 最大代数免疫阶布尔函数
• 5.1 最大代数免疫阶布尔函数的性质
• 5.1.1 最大代数免疫阶布尔函数的基本性质
• 5.1.2 最大代数免疫阶布尔函数的计数问题
• 5.2 一种最大代数免疫阶布尔函数
• 5.2.1 择多函数
• 5.2.2 择多函数的代数免疫阶
• 5.2.3 择多函数的其它密码学性质
• 5.3 最大代数免疫阶布尔函数的构造与分析
• 5.3.1 构造方法一
• 5.3.2 构造方法二
• 5.3.3 构造方法三
• 5.4 小结
• 结束语
• 参考文献
• 附录
• 附录1: LILI-128所用非线性函数及其补函数的4次线性无关零化子
• 作者简历 攻读硕士期间的科研经历
• 致谢