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

项目名称： 密码函数的复杂性分析与构造

项目编号： No.61202437

项目类型： 青年科学基金项目

立项/批准年度： 2013

项目学科： 计算机科学学科

项目作者： 王维琼

作者单位： 长安大学

项目金额： 23万元

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

中文关键词： 布尔函数；复杂性；频谱；指数和；非线性

英文摘要： 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.

英文关键词： Boolean functions；complexity；Walsh spectrum；exponential sum；nonlinearity