代数动力系统及其序列密码相关问题研究

In cryptology, it is important to describe evolution of the initial state, i.e. the trajectory of a single particle in dynamical system terms. Recently, Many good works on non-linear pseudorandom sequences have appeared. Algebraic dynamics, especially the p-adic method has been turned out to be effective in the study of non-linearpseudorandom sequences and T-functions, as all the basic computer instructions such as integer addition, multiplication and logical operations can be regarded as continuous (1-Lipschitz) functions with respect to 2-adic metric. In this project, by combining algebraic dynamics and p-adic method, we will study the algebraic structure of dynamic systems of continuous maps, such as the linear and nonlinear relations in the systems based on T-functions; the ergodic problems on different discrete valuation rings(zero character and positive character); the graphic method on algebraic dynamic system and their applications in the design and analysis of stream ciphers.

在密码学中，描述密码系统初始状态的演变行为（即单点的进化轨道）是非常重要的。近年来，人们基于不同的思想和多种数学方法，对非线性序列进行了深入细致的研究。代数动力系统，特别是 p-adic方法被证明是研究这种信息过程问题的有力工具。不仅一些算术运算，而且各种计算机中的逻辑指令都可以被看作是2-adic整数空间中的连续映射。本项目将从代数动力系统的观点出发，结合p-adic数学方法，围绕p-adic连续函数动力系统内部代数结构，零特征与正特征离散赋值环上函数的保测及遍历性质，研究单圈T函数生成序列的内部代数结构、有限域上的形式幂级数环上连续函数的动力系统、代数动力系统中的图形化方法及其在流密码设计中的应用等问题，以期为研究非线性迭代关系提供一种新的思路，利用p-adic分析等数学工具，挖掘T函数更深层次的密码学性质，给出一套有关流密码的分析与设计理论。

本项目主要从代数动力系统的角度出发，利用相关的数学理论与方法，深入研究伪随机序列的生成理论，以期为伪随机序列的研究开辟新的途径，进而为序列密码算法设计和分析提供新的理论支持。项目执行过程中，课题成员分工协作、循序渐进地开展研究，完成了项目制定的研究计划，达到了项目提出的预期目标。项目所取得的主要成果包括：（1）给出了局部环上线性系统导出序列压缩保熵映射的新刻画，并给出压缩序列新的分布性质；（2）建立了非线性反馈动力系统研究的布尔网络和半张量积方法，得到了关于类Grain结构非线性反馈模型的新性质；（3）给出了De Bruijn序列邻接图的深刻性质；（4）建立了非线性反馈密码系统的代数次数理论估计模型，在Trivium序列密码算法分析方面取得国际最优成果。项目执行期间在国内外权威学术期刊、会议累计发表学术论文29篇，培养了博士/硕士研究生14名、博士后6名，同时开展了多种形式的国内外学术合作与交流活动。