【作者】 李志慧；

【导师】 李学良；

【作者基本信息】 西北工业大学 ， 计算机软件与理论， 2002， 博士

【摘要】 分组密码是现代密码学中的一个重要研究分支，而置换理论在分组密码的研究与设计中有着重要的地位。本文首先综述了分组密码的发展历程、设计原理，以及置换理论在这个体制设计中的重要作用。接着讨论了置换的密码指标问题，并证明了正形置换是一种密码性能比较良好的置换。最后着重研究了正形置换的表示、构造、计数以及如何将线性正形置换非线性化等问题。上述工作为分组密码中置换理论的研究提供了新的方法、新的思路，并得到了一批好的置换源。本论文的主要工作和取得的研究成果如下： （1） 研究了有限域上的正形置换的密码学性质；并讨论了正形置换与典型分组密码DES之间的关系，计算和分析了DES中所使用的部分置换的密码指标值，指出这些指标与同阶的正形置换在密码性能上接近。 （2） 从数学研究的角度，给出了正形置换的若干性质以及判别方法，为后几章的正形置换的构造与计数做了充分的准备。 （3） 对正形置换的表示问题进行了研究。证明了F₂ⁿ上正形置换与F_2ⁿ上的一个次数不超过n-1的正形置换多项式形成一一对应关系。从而给出了正形置换的多项式表示，并证明了F₂ⁿ上的全体正形置换数目一定可以被2ⁿ整除。 （4） 利用矩阵理论对线性正形置换给予了研究。讨论了线性正形置换与正形矩阵之间的关系，给出了正形矩阵的若干性质，求出了正形矩阵的有理标准形；利用对角正形矩阵的特点结合布尔函数构造了一批正形置换，其中包括一类非线性正形置换，得到了2ⁿ阶正形置换在计数方面的一个下界表达式。 （5） 讨论了最大线性正形置换的性质、计数以及如何利用最大线性正形置换来构造非线性正形置换的问题。介绍了利用最大线性正形置换构造非线性正形置换的一个方法，并给出了一个具体的构造实例。利用有限域上的多项式理论解决了最大线性正形置换的计数问题。摘要（6）研究了一类特殊的线性正形置换的圈结构及其腐化过程。并利用 构造一类特殊的线性置换的方法，给出了利用多项式理论构造相 应的线性正形置换的方法，并给出了一个实例。论述了腐化后的 非线性正形置换与原线性置换的密码指标之间的关系。（7）利用有限域上的多项式理论来研究具体的有限域凡上的正形置 换多项式，给出了具体计算有限域上正形置换多项式的过程，得 到了有限域Fs上的正形置换多项式的具体形式及计数。 （8）利用有限域上的多项式理论进一步研究了具体的有限域月。上的 正形置换多项式。介绍了Zeeh算法（也叫Jacobi算法）以及有 限域多项式根的判定方法。证明了在有限域月。不存在次数为2， 3，5，6，7，14次的正形置换多项式，同时还证明了存在次数为 1和4正形置换多项式。从而把有限域月。上的非线性正形置换多 项式次数锁定在{s，9，10，11，12，13}上。更多还原

【Abstract】 Block cipher is an important branch of mordant cryptography, and permutation theory has an important role in studying and designing of block cipher. First a review of developing history and designing principle of block cipher is given and the important function of permutation theory in block cipher is presented in this thesis. Then some cryptographic indices of permutations are discussed. Then we put more efforts on some expressions, enumerations and constructions of orthomorphic permutations, and on the problem of how to make linear orthomorphic permutations non-linear. The results obtained in this thesisoffers some new ideas and methods for studying of permutation theory in block cipher system. The main contributions of this dissertation are as follows:(1) The cryptographic properties of orthomorphic permutations in finite fields are studied; The relationship between orthomorphic permutations and DBS.is studied, at same time , some cryptographic indices of some permutations used in DBS are analyzed and calculated, and furthermore it is presented that these indices are access to that of some orthomorphic permutations with same degree .(2) From the point of mathematical view, some properties of and criteria’s for orthomorphic permutations are given. These results can be used as a sufficient preparation for the study of orthomorphic permutations in the later chapters.(3) The problem of the expressions of orthomorphic permutations is studied. It is showed that orthomorphic permutations in F2n are corresponding to orthomorphic permutation polynomials with degree n in finite fields F2n one by one. A conclusion is given based on this expression:The number of all orthomorphic permutations in F2n can be divided by 2n .(4) Linear orthomorphic permutations are studied by using matrix theory.The properties of orthomorphic matrices are given and rational standard forms of orthomorphic matrices are obtained. Using the characteristic of diagonal orthomorphic matricies and combining with Boolean functions, a kind of orthomorphic permutations is constructed, including a kind ofnon-linear orthomorphic permutations. And a lower bound of the enumeration of orthomorphic permutations with order 2" is obtained.(5) The properties and enumerations of maximal linear orthomorphic permutations are discussed, and the problem how to construct non-linear orthomorphic permutations is studied. A method how to construct non-linear orthomorphic permutations is introduced based on maximal linear orthomorphic permutations, and the enumeration of maximal linear orthomorphic permutations is solved out based on polynomial theory in finite fields.(6) The circle construction and corruption of a kind of linear orthomorph permutations are studied. The method for constructing linear orthomorphic permutations is given . And the cryptographic indices of non-linear orthomorphic permutations obtained are calculated.(7) The orthomorphic permutation polynomials in finite fields F8 are studied. We give all orthomorphic permutation polynomials in finite fields F8 , and the enumeration of orthomorphic permutation polynomials are obtained.(8) The orthomorphic permutation polynomials in finite fields F16 are studied. Zech algorithm( also called jacobia algorithm) and the criteria of polynomial roots in the finite fields are introduced. The following results are obtained: it is showed that there do not exist orthomorphic permutation polynomials with degree 2,3,5,6,7 and 14 , and there exists linear orthomorphic permutation polynomials with degree 1 and 4 in the finite fields F16 , so these results show that the degree of non-linear orthomorphic permutation polynomials will distributed in 8,9,10,11,12 and 13.更多还原