布尔多项式组的特征列方法及其在流密码分析中的应用

论文摘要

本文主要研究求解R2中布尔多项式方程组的吴特征列方法及其在流密码分析中的应用。具体工作包括下面三部分。我们首次给出布尔多项式的吴特征列方法,包括整序原理与零点分解定理。由于布尔多项式的特殊性,我们的给出的特征列方法与一股的特征列方法相比。具有以下优点。（1）我们给出分离首一零点分解定理,由此可以得到方程组解的个数的明确的表示公式。（2）我们证明了改进的整序原理可以在n步内终止,其中n是变量个数。（3）我们给出了只需要多项式加法的零点分解算法,有效地控制了算法对于空间的需求。我们系统地实现了所提的特征列方法,并通过使用分支-空间平衡原则、SZDD、并行化等技巧,得到求解布尔多项式组的高效软件。我们引进了求解方程组的分支-空间平衡原则,即在充分利用现在计算机内存的前提下,将方程组化简为一些更容易求解的子问题,并以此为基础给出了特征列算法的多种形式。我们给出了特征列方法的并行实现与基于SZDD的实现,大大提高了程序的效率、压缩了需要占用的内存空间。我们用特征列方法分析了一类基于非线性寄存器的流密码。通过对变量个数从40到128的问题进行的大量的实验,说明我们的方法是有效的。我们分析了这类布尔多项式方程组的解的个数与方程个数的关系,得到方程组有唯一解的一些实验结果。

论文目录

• 摘要
• Abstract
• 目录
• 第一章 引言
• 1.1 布尔函数求解
• 1.2 方程组求解的符号计算方法
• 1.3 密码的代数攻击
• 1.4 我们的工作
• 第二章 一般域上的特征列方法
• 2.1 多项式集、升列和偏序
• 2.1.1 变量的自然序
• 2.1.2 多项式的一些指标
• 2.1.3 非常量多项式的正则形式
• 2.1.4 多项式的偏序关系
• 2.1.5 升列和三角列
• 2.1.6 升列和偏序关系
• 2.1.7 多项式集的偏序
• 2.1.8 余式和余式公式
• 2.2 多项式集的特征列和整序原理
• 2.2.1 问题,原理和方法
• 2.2.2 特征列和它的构造图表
• 2.2.3 特征列
• 2.2.4 整序原理
• 2.2.5 特征列算法的变形
• 2.3 零点分解定理
• 2中的特征列方法'>第三章 R₂中的特征列方法
• 3.1 预备知识
• 3.2 三角列与升列
• 3.3 整序原理
• 2中的零点分解定理'>3.4 R₂中的零点分解定理
• 3.5 改进的整序原理的复杂性分析
• 3.6 吴升列与弱升列的应用
• 第四章 零点分解定理的直接算法
• 4.1 自上而下的零点分解算法
• 4.2 不需要乘法的零点分解算法
• 第五章 算法的实现
• 5.1 平衡原则
• 5.2 用SZDD减少内存的占用
• 5.3 并行实现
• 第六章 用特征列方法对一类流密码进行的密码分析
• 6.1 流密码
• 6.2 线性反馈移位寄存器与非线性组合器
• 6.3 用特征列方法对非线性组合函数进行的代数攻击
• 第七章 结论与展望
• 参考文献
• 发表文章目录
• 致谢