演化计算在密码分析中的应用研究

密码是信息安全的基础，没有密码的安全就没有互联网的信息安全。研究密码的安全性具有重要的现实意义和理论价值。本课题将用演化计算的思想来研究分组密码和公钥密码的攻击。对于分组密码，研究如何用演化计算寻找分组密码的最/次优差分路径以攻击分组密码。对于公钥密码，主要研究大数分解和离散对数的计算，包括：研究群上随机映射的枝圈结构规律，首先将问题归约到指数所在的整数环上，利用演化计算研究该整数环上简单函数的枝圈结构规律，以寻找短的枝圈结构，这在利用pollard的rho方法计算离散对数时有直接重要的应用；用演化计算研究数域筛法里多项式选择的方法，以找到接近最/次优的多项式，提高数域筛法的效率。另外还将研究那些能快速降低问题规模的数学工具（如中国剩余定理，欧几里德算法）在大数分解和离散对数计算上的适用性。通过上述研究，攻击一个分组密码，获得大数分解和离散对数计算的一种新解法或/并改进已有的攻击方法。

本课题研究演化计算在大数分解，离散对数和分组密码分析中的应用。由于离散对数问题研究可归约于大数分解研究，且数域筛法是目前最快的分解算法，所以我们重点研究数域筛法和分组密码。. 数域筛法中多项式选择至关重要，好多项式在筛法里产生更多关系，且可以减少矩阵步骤矩阵的大小。筛法和矩阵这两个步骤的效率决定了大数分解整体效率。在演化设计多项式过程中存在多项式空间过大的问题。首先我们利用统计和代数方法研究了多项式好坏和其系数的关系，得出重要结论：当多项式尾系数含有更多小素因子时通常多项式更好，对于一个d次多项式，当其d-2次系数为负数且足够小时通常多项式更好。这些研究结论可用于减少多项式的有效空间。其次，我们进一步提出用几何学观点来选择多项式并得出如下结论：一个好多项式对应的图形应该靠近x轴且变化比较平缓。为了尽量靠近x轴，d-2次的系数应该为负数且足够小，对于5次以上多项式，其d-1次和d-3次系数符号应该相反；为了使多项式图形比较平缓，次数较高的系数应该尽量小，首系数更应该尽量小。大量实验结果表明上述结论的有效性：我们方法获得的结果比实际分解采用的多项式效果都好，MurphyE指标要好10%-30%。如RSA190于2010年被俄罗斯人I.Popovyan以及荷兰人A.Timofeev分解，我们的多项式要比他们所用多项式在指标上好26%。如果进行分解比赛，其它条件相同时我们会比他们提前约26%的时间。. 上述结论的科学意义：研究结论回答了好多项式在哪里分布，如何快速找到它们这些重要问题。具有重要应用价值，该研究结果发布在国际密码学研究会网站上：http://eprint.iacr.org/2013/583。法国INRIA著名科学家Paul Zimmermann，CARAMEL项目（CADO-NFS是CARAMEL的子项目）科研负责人密切关注并将我们关于首系数的结论用于其后继版本的大数分解国际开源项目CADO-NFS（版本a9cbbb5之后，包括最新的2.0发行版）。. 另外，在分组密码分析方面，我们基于启发式搜索算法，给出并完善了面向字/字节的差分路径搜索优化算法，研究了密码算法和部件在HAIFA、Sponge、树型结构下的安全性。并对AES进行了攻击：我们找出了一条新的差分路径，进一步降低了Biclique攻击算法的复杂度。