密码函数的复杂性分析与构造

Boolean functions play an important role in stream and block ciphers. The security of those systems depends largely on the complexity of Boolean functions. There are many complexity criteria for Boolean functions, but some of which restrict each other. So there exist two important research aspects in cryptography. That is wether a given Boolean function can satisfy all the criteria, and the other is how to construct Boolean functions which can achieve the trade-offs between criteria. We mainly focus on the following problems: Firstly, we characterize the normality and algebriac immunity of Boolean functions based on the theory of matrix, Walsh spectrum, and the decomposition of spaces. Then we use the conclusion that we have achieved to improve the algorithm for checking normality of Boolean functions. Moreover, we will build software to check the algorithm and pick up those good Boolean functions. Finally, Boolean functions with high nonliearity, nonnormality, with high level of algebraic immunity and some reasonable level of resiliency will be constucted in view of the theory of mean value, spectrum, and indeterminate equation. Meanwhile, we will get some good cryptographic functions by changing some functions which is not very good in cryptography but with simple structure.

布尔函数（又称密码函数）在流密码及分组密码中发挥着重要的作用.这些体制的安全性在很大程度上取决于密码函数的复杂性,而复杂性度量指标有很多,且其中某些指标是相互制约的.一个给定的布尔函数是否能满足各个密码学指标以及如何构造出能达到多个复杂性指标折中的布尔函数一直都是密码函数研究中的重要问题.本项目主要研究以下几个方面的问题:用矩阵论、频谱理论及空间分解理论来刻画和分析非线性度较高的密码函数的正规性及代数免疫阶; 基于所得结论给出判定正规性的改进算法,同时编制软件进行统计测试,筛选出密码学性质优良的布尔函数; 用数论中的均值理论, 频谱理论及不定方程理论来构造同时满足高非线性、非正规、具有较高代数免疫阶及适当弹性阶的密码函数; 最后通过对一些密码学性质不是很好,但是结构较简单的函数进行适当的改造来得到能达到多个密码学指标的函数.

布尔函数（又称密码函数）在流密码及分组密码中发挥着重要的作用. 这些体制的安全性在很大程度上取决于密码函数的复杂性, 而复杂性度量指标有很多, 且其中某些指标是相互制约的. 一个给定的布尔函数是否能满足各个密码学指标以及如何构造出能达到多个复杂性指标折中的布尔函数一直都是密码函数研究中的重要问题. 本项目主要对布尔函数的复杂度进行了进一步深入分析. 讨论了具有高复杂度的布尔函数的存在空间的大小；用频谱理论和空间分解理论刻画和分析了非线性度较高的密码函数的正规性及代数免疫阶，基于所得结论给出了判定正规性的改进算法；对数论中的均值理论、指数和理论进行了深入研究，并利用所得结论在有限域上构造出了具有高阶非线性性的布尔函数；基于Walsh谱理论和不定方程理论构造出了一些具有较高复杂度的布尔函数；通过对一些密码学性质不是很好，但是结构较简单的函数如正规Bent函数进行适当的改造得到了能达到多个密码学指标的函数；分析了平衡函数的全局雪崩特性. 随着计算能力的不断增强，对密码体制的复杂性要求日益趋高，我们的研究结果将会对密码体制的安全性提供更好的保障。