基于流密码的代数攻击研究

摘要

随着人类社会科技的不断发展，各个领域尤其是移动通信领域的信息安全问题受到高度重视，现代密码学理论的发展为各种信息起到强大的安全保护作用。密码学理论研究中的流密码相比分组密码而言，其“一位一密”的特性更适合于移动通信领域，且其构造相对简单，易于软件硬件的实现，因而受到广泛的关注。“代数攻击”作为流密码领域研究的新热点，从新的角度来分析密码体制的安全性，将其转化到求解超定的多变元方程组的问题上，对传统的密码体系的设计产生了巨大的冲击。
　　代数攻击的过程可以分为两个阶段:第一是找出初始密钥与密钥流之间的关系，并依据此关系建立多元方程组;第二是求解建立的方程组，从而得到初始密钥值。为了使求解的方程易于求解，需要考虑将方程组降次，一个经典的降次方法就是构造出函数的零化子。对于如何求解降次后的方程，经典的算法包括Linearization、Relinearization、XL算法以及Gr(o)bner Bases等，基于这些算法又出现过多种变种算法，如F4、F5等。
　　本文主要对代数攻击的这两个方面进行研究，首先分析比较已有的构造零化子的算法，总结其优劣，并从新的视角提出一种简单的构造零化子的算法;之后分析比较已有的求解超定的多变元方程组的方法，并提出一种基于本原多项式求解方程组的方法，该方法适用于已知的密钥流比特数较少的情况。

目录

声明

摘要

第一章 引言

1．1 背景介绍

1．2 国内外研究现状

1．3 本文的主要工作

第二章 预备知识

2．1 基础数学

2．2 线性反馈移位寄存器LFSR

2．3 布尔函数

2．3．1 真值表表示

2．3．2 小项表示

2．3．3 多项式表示

2．3．4 迹表示

2．3．5 布尔函数与LFSR结合

2．4 代数攻击

第三章 布尔函数的零化子构造

3．1 基于代数式的构造

3．2 基于矩阵的构造

3．3 基于子空间的构造

3．4 基于Apriori算法的构造

3．5 实例应用

第四章 快速求解方程组

4．1 求解方程组的方法

4．1．1 Linearization算法

4．1．2 Relinearization算法

4．1．3 XL算法

4．1．4 Gr?bner Bases算法

4．2 LFSR的等价性研究

4．2．1 LFSR等价性

4．2．2 实例应用

4．3 基于LFSR求解方程组的新方法

4．4 实例应用

4．5 方法扩展

第五章 结论

参考文献

致谢

攻读学位期间论文发表情况