流密码构造与分析中一些问题的研究

摘要

流密码是一类常用的密码体制，它具有小巧、快速、硬件实现简单等优点。流密码被广泛应用于军事、商业等方面，尤其是用于无线通信领域。因此，流密码的设计与分析是非常重要的工作。
　　布尔函数是流密码的重要组件，其密码学性质直接影响着密码体制的安全性。因此，构造具有好密码学性质的布尔函数对设计流密码很重要。在布尔函数的各密码学性质中，代数免疫是非常重要的一种。本文研究了如何构造具有高代数免疫度的对称布尔函数，这方面的主要贡献如下:
　　(1)构造全部具有最优代数免疫的偶数元对称布尔函数一直是悬而未决的密码学难题，有人曾证明此类函数的结构非常复杂。本文通过研究低度数对称布尔函数的权值分布，构造出了全部具有最优代数免疫的偶数元对称布尔函数，并对此类函数进行了计数。
　　(2)构造出了一大类代数免疫度不低于d的2k元对称布尔函数，其中d是k二进制表达的后缀。基于这个构造，得到了一个此类函数计数的下界，这是第一个此类界。
　　另外，伪随机序列生成器也是流密码的核心组件之一。FCSR是一类新型伪随机序列生成器，流密码F-FCSR系列及BEAN都是基于FCSR构造的。其中，F-FCSR-H v2和F-FCSR-16曾是欧盟eSTREAM计划的最终轮作品之一，但在2008年被Hell和Johansson攻破。后来，学者们设计出新型流密码F-FCSR-H v3和F-FCSR-16 v3。新版本的F-FCSR系列不仅具有旧版本的优点，更重要的是它能够抵御Hell-Johansson攻击。本文对以上这几种流密码进行了安全性分析，这方面的主要贡献如下:
　　(1) Tian和Qi曾发现了FCSR输出序列上的线性关系，但未曾有人成功地将这种线性关系应用于攻击中。本文首次设计出了一个扩展生日攻击算法来寻找FCSR输出序列上的线性关系。基于此算法，给出了一个针对流密码F-FCSR-H v3的区分攻击。攻击的在线时间复杂度为237.2，离线时间复杂度为256.2。这是第一个成功的对F-FCSR-H v3的攻击，第一个低于暴力攻击时间复杂度280的攻击。虽然本文只介绍了对F-FCSR-H v3的攻击，但实际上这种攻击的应用面非常广，所有基于线性过滤器的FCSR组合器都会受到此攻击的威胁。
　　(2)传统的快速相关攻击只能应用于LFSR，而不能应用于FCSR。需特别指出的是，F-FCSR系列密码的设计者声称，这个系列的流密码是对快速相关攻击免疫的。本文首次将快速相关攻击从LFSR扩展至FCSR，在扩展后的模型中，二进制对称信道中加入了一个新噪音。作为例子，本文展示了一个针对流密码F-FCSR-16 v3的密钥恢复攻击。攻击的总时间复杂度为21.9。这是第一个成功的对F-FCSR-16 v3的密钥恢复攻击，第一个低于暴力攻击时间复杂度2128的攻击。除了F-FCSR-16 v3以外，任何FCSR组合器都有可能成为此攻击的目标。
　　(3)(A)gren和Hell曾发现了流密码BEAN的一个弱点，并据此提出了一个密钥恢复攻击。但此密钥恢复攻击的时间复杂度为273，这比暴力攻击的时间复杂度280仅略低一点。本文发现了BEAN的一些新的弱点，并提出了一个新密钥恢复攻击。新攻击的时间和数据复杂度分别为257.53和259.94。此外，本文给出了两个新输出函数，这两个函数比原输出函数的硬件实施更简单且更有效，最重要的是这两个函数对新攻击免疫。同时，本文给了出一些针对FCSR的改进意见。

目录

摘要

第一章 绪论

§1．1 研究背景

1．1．1 密码学

1．1．2 流密码

1．1．3 布尔函数

1．1．4 带进位的移位反馈寄存器

§1．2 国内外研究情况

§1．3 本文的主要工作

§1．4 各章组织

第二章 预备知识

§2．1 布尔函数

§2．2 带进位的移位反馈寄存器

2．2．1 Fibonacci FCSR的基础知识

2．2．2 Galois FCSR基础知识

2．2．3 Ring FCSR基础知识

第三章 关于具有最优代数免疫κ的2κ元对称布尔函数

§3．1 研究背景

§3．2 预备知识

§3．3 具有最优AI偶数元对称布尔函数的必要条件

§3．4 类1中的函数具有最优代数免疫

§3．5 类2中的函数具有最优代数免疫

§3．6 成果小结

§3．7 构造具有代数免疫度不低于d的偶数元对称布尔函数

§3．8 本章小结

第四章 对流密码F-FCSR-H v3的区分攻击

§4．1 研究背景

§4．2 预备知识

4．2．1 FCSR序列基础知识

4．2．2 (l)-序列的线性关系

§4．3 扩展(l)-序列的线性关系

4．3．1 用于搜索(2+2)-关系的扩展生日算法

§4．4 利用分段模运算来改进算法

4．4．1 不同线性关系之间的依赖关系

§4．5 仿真实验

§4．6 应用于ring FCSR，F-FCSR，FCSR组合以及F-FCSR-H v3

§4．7 本章小结

第五章 对F-FCSR流密码的快速相关攻击

§5．1 研究背景

§5．2 针对LFSR的一次通过算法

§5．3 针对FCSR的快速相关攻击

§5．4 对F-FCSR密码的快速相关攻击

5．4．1 主要思路

5．4．2 两序列之间的相关关系

5．4．3 搜索序列上的线性关系

5．4．4 密钥恢复攻击

§5．5 本章小结

第六章 改进对流密码BEAN的密钥恢复攻击

§6．1 研究背景

§6．2 预备知识

6．2．1 布尔函数基础知识

6．2．2 BEAN的结构和性质

§6．3 ?gren和Hell的攻击

§6．4 对BEAN的新密钥恢复攻击

6．4．1 恢复S2i

6．4．2 猜测Si中的60比特

6．4．3 改进攻击

6．4．4 使用S2i恢复Bi

6．4．5 恢复初始密钥

§6．5 改进BEAN

§6．6 本章小结

第七章 总结与展望

致谢

参考文献

攻读博士期间主要工作

声明