Rijndael算法的新型破译方法及应用研究

本项目旨在研究Rijndael算法的新型攻击方法，并将攻击方法应用到我国的SMS4算法等其他分组密码标准中。具体内容包括：在GF(2)的多个扩域上进行插值攻击；提出具有普适性的XSL算法来恢复密钥；降低不可能差分分析方法在各种密钥长度下攻击的复杂度；提炼不可能差分攻击过程中所需的明文对数与加密轮数的权衡关系；结合具体的密码函数找到与其匹配的生物启发性计算模型；设计出合理、有效的适应度函数及制定好的搜索策略；围绕具体密码体制的差分和线性特点，找到高概率的差分和线性路径。希望能在分组密码体制的设计理论及分析技术上有一定的突破，研究成果将为分组密码体制的设计和分析提供系统的理论支撑和有力的分析工具。该研究既有理论和技术上的前瞻性，也注重实际应用的有效性。

项目完成如下重要成果：.1、结合密钥扩展算法和划分子集的方法, 提出7 轮高级加密标准AES-192的不可能差分分析方法. 首先估算猜测初始轮的错误密钥的最小概率，然后计算所需的明密文对的数量并选择明密文对，计算密文对的差分，猜测特殊的密钥字节对其进行不可能差分攻击。该攻击需要2^78选择明文, 记忆存储空间为2^129分组, 以及约2^155的7轮AES-192 加密. 与目前现有的结果相比，该攻击需要更少的选择明文数和较低的时间复杂度。.2、Joanne Fuller曾指出Rijndael S盒输出分量函数等价，但是该方法复杂度随着搜索的函数空间大小急剧升高。利用有限域中元素分量与迹函数间的关系，从迹函数的角度研究Rijndael S盒输出分量函数，证明了Rijndael S盒输出比特的分量函数间存在着线性等价关系，与Joanne Fuller方法相比，该方法简单复杂度低，不受搜索的函数空间限制；同时根据有限域中元素分量函数之间的等价, 发现其元素分量函数代数表达式的系数全不相等且不为0和1。.3、使用差分方法分析了18轮的SMS4差分特征，并在此基础上攻击了22-轮的SMS4，攻击过程需要2^117个选择明文，2^112字节的存储空间，而时间复杂度为2^123次22-轮加密。此结果是目前对SMS4差分分析的最好结果。.4、不可能差分攻击是通过从足够多的明文对中，寻找出满足某种不可能差分链的明文对，进而排除满足不可能差分链的密钥，最终恢复出正确密钥的攻击方法。本文研究了七轮AES的不可能差分攻击的一般情况，利用第七轮和第六轮输入的全0列数(a,b)作为参数，得到不可能差分攻击过程中所需的明文对数与加密轮数的权衡关系，给出了( a, b)在不同密钥长度下对应的明文对数与加密轮数,其对应关系直接说明了攻击的可行性,及攻击复杂度。.5、提出一种改进的lt码译码方法；基于LDGM码，针对有损信源压缩，提出了一种改进的置信传播算法。