现代密码算法分析与研究

论文摘要

本文分析了AES和CAC分组密码算法的代数性质和安全性，并对ElGamal签名算法的安全性进行了分析，主要成果有： （1）证明了有限域上q-多项式、n阶矩阵和线性函数间的等价关系；然后通过证明有限域上同一线性函数在严格不同基下对应不同矩阵，扩展出一种通用的方法快速确定有限域上线性函数和n阶矩阵间的线性关系；最后，提出了有限域上q-多项式和n阶矩阵相互确定的一种新方案，从本质上解释了Rijndael S-box代数表达式的简洁性。 （2）提出了一种改进的AES S盒，在没有降低代数次数的前提下，将项数从原来的9项增加到255项，大大地提高了其代数表达式的复杂度；同时，改进S盒的布尔函数的严格雪崩、平衡性等密码学性质、抵抗差分密码分析的能力都没有改变，安全性高； （3）对AES S盒的阶次运算进行了研究，发现AES S盒的连续状态转移是一个马尔可夫链，其256个状态可以划分为5个常返态闭集，状态周期分别为59，87，81，27，2。 （4）从改变Rijndael的变换常量这一全新的角度降低了其实现的代价，包括软件和硬件的实现代价，尤其是硬件实现代价。改进后的AES加密和解密可以共享同样的硬件资源，尤其是其中的S盒，乘法列混合和其列混合的逆运算。除了密钥的安排顺序，Rijndael的加解密实现过程都是对称的。字节替换，字节逆变换，列混合与逆列混合都有同样的时间和空间复杂度。列混合和逆列混合的计算仅仅需要2次乘法和4次加法运算，此步运算与原先标准的AES的运算相比，时间复杂度降低了68％，从而可以大大的提高实现效率和减少实现资源。研究结果比目前其他的任何方法都要有效。 （5）分析了选择性明文攻击下，Subhayan Sen等人提出的基于细胞自动机的分组密码系统CAC（cellular automata based cryptosystem）是极不安全的，攻击数据复杂度仅为2个明密文对，时间复杂度为2次加密过程；尽管设计者隐瞒了其中某些模块的关键设计细节，本文给出了破解明文线性移位次数δ，Major CA的变换过程和其叠代次数Δ，使得这些隐瞒模块的细节更加明朗清楚，从而攻破了整个密码系统。 （6）分析了ElGamal签名方案在选择性密文攻击的情况下是不安全的，攻击者可以假冒签名者进行签名，而且可以攻击签名者的私钥，其攻击性不依赖于离散对数的求解问题。 （7）Bent函数是一类重要的密码函数，在密码学、纠错编码和组合设计中都有重要应用。通过对Bent函数的研究，发现偶数n≥4元平衡布尔函数的循环谱的所有谱值都可以被4整除，并给出了其最大绝对谱值。通过正规Hadamard矩阵研究给出了GF（2n）上Bent函数计数的上下界，降低了Bent函数搜索的空间。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 基本的密码学技术
• 1.1.1 对称密码技术—分组密码概述
• 1.1.2 非对称密码技术
• 1.2 本文主要工作及结构安排
• 第二章 Rijndael算法设计原则及分析现状
• 2.1 Rijndael密码设计的准则
• 2.1.1 分组密码设计的基本准则
• 2.1.2 Rijndael算法设计准则和参数选取
• 2.2 Rijndael算法原理
• 2.3 AES密码分析现状
• 2.4 本章小结
• 第三章 Rijndael的代数性质研究
• 3.1 Rijndael算法S盒仿射运算的研究
• 3.1.1 研究现状
• 3.1.2 线性函数、q-多项式和矩阵的等价关系
• 3.1.3 q-多项式和矩阵相互确定的方案
• 3.1.4 文献的推广方案
• 3.1.5 本文的新方案
• 3.2 增强复杂度的AES S盒及其密码学分析
• 3.2.1 研究背景
• 3.2.2 AES S盒简单性的代数本质
• 3.2.3 一种改进的AES S盒代数结构与代数性质
• 3.3 AES S盒的马尔可夫性质研究
• 3.4 本章小结
• 第四章 AES的实现
• 4.1 最小实现代价的AES
• 4.1.1 研究现状
• 4.1.2 仿射变换的修改
• 4.1.3 字节替换及其逆替换的结构
• 4.1.4 列混合的改变
• 4.2 加解密过程的资源共享分析
• 4.3 密码特性分析
• 4.3.1 布尔函数的特性分析
• 4.3.2 差分分析
• 4.4 本章小结
• 第五章 细胞自动机分组密码CAC的分析
• 5.1 CAC密码系统的简史
• 5.2 等效的CAC密码系统
• 5.2.1 细胞自动机
• 5.2.2 CAC密码系统
• 5.2.3 等效的CAC密码系统
• 5.3 对CAC密码系统的攻击
• 5.3.1 CAC密码系统的的初步分析
• 5.3.2 明文字节移位bit数d的恢复
• 5.3.3 仿射变换Major CA的恢复
• N的恢复'>5.3.4 密钥S_N的恢复
• 5.4 本章小结
• 第六章 ElGamal签名算法的分析
• 6.1 ElGamal签名方案的私钥攻击
• 6.1.1 研究现状
• 6.1.2 ElGamal签名方案
• 6.1.3 对ElGamal签名方案的伪造攻击
• 6.2 改进的ElGamal签名方案
• 6.3 本章小结
• 第七章 Bent函数的计数问题
• 7.1 Bent函数计数的一个上下界
• 7.2 本章小结
• 第八章 结束语
• 致谢
• 参考文献
• 攻读博士学位期间完成的论文和科研工作