Costas阵列的存在性、计数问题及其在密码学中的应用

【作者】 刘涛；

【导师】 殷新春；

【作者基本信息】 扬州大学 ， 计算机应用技术， 2007， 硕士

【摘要】 任何没有信息扩张的密码体制都可以看作是置换的结果。而起源于雷达信号设计的Costas阵列,作为一种特殊的置换矩阵,与置换一一对应,经降维所得Costas序列是一种特殊的置换。现代密码学中的公钥体制基于特定的数学难题。而Costas阵列的存在性、计数等问题悬疑至今,成为困难的数学问题。围绕着Costas阵列的存在性、计数问题及其在密码学上的应用,本论文取得了以下三方面的研究成果。1.给出了广义Golomb构造法所缺少的一个必要条件;将随机优化算法应用于Costas阵列的存在性探测。本文首先对广义Golomb构造法进行了研究,发现该推广法缺少一个必要条件,并给出了该条件。代数构造法能构造无穷多阶的Costas阵列,但部分阶数的阵列不能由其构造,这些阵列的存在性尚不确定。计算机枚举法可以探测Costas阵列的存在性,但计算复杂度呈指数阶。针对高复杂度的弊端,本文将Costas阵列的存在性探索视为优化问题,建立了优化模型。在模型的求解上,文中基于模拟退火算法、遗传算法和广义粒子群算法等三大随机优化算法,分别提出了SAACAS、GACAS、GPSOCAS三种算法,实验结果初步表明:三种算法对于18阶以下Costas阵列的探测有效。2.给出了对称Costas阵列个数与一般Costas阵列个数的关系式;改进了现有的Costas阵列串行搜索算法并将其并行化。本文研究了对称Costas阵列的计数问题,得到了对称Costas阵列个数和该阶Costas阵列总个数的关系式。现有的Costas阵列枚举算法基于回溯法,通过置换的差分计算决定算法继续搜索或回溯。从计算、存储必要的差分及检查重复差分的角度,本文改进了现有算法,并以定理的形式给出了证明。最后将改进后的枚举算法并行化,该算法具有线性加速比和可扩放性。3.构造了一种基于Costas阵列的数字签名方案;将Costas阵列分别应用于Shamir背包数字签名、Niederreiter公钥体制和S盒。构造Costas阵列的复杂度属指数阶,而判定一个置换矩阵是否为Costas阵列可在多项式时间内完成,因而Costas阵列具有构造困难而判定容易的性质。由此,本文基于Costas阵列构造了一种数字签名方案。利用Costas阵列分布的稀疏性,将Costas阵列用于Shamir背包数字签名和Niederreiter公钥体制,提高其安全性。S盒是许多分组密码算法中的唯一非线性部件,因此,它的密码强度决定了整个分组密码算法的安全强度。任意n阶的双射S盒都可以看作是0到2n-1的所有整数的一个置换。本文提出将Costas阵列作为初始S盒进行演化以获得密码学性能良好的S盒,从而为将来设计各种分组密码算法提供非线性资源。更多还原

【Abstract】 A cryptography system without information expansion may be viewed as the product of permutations. Costas arrays, special permutation matrices, derive from radar signal design. There is one-to-one mapping between Costas arrays and permutations. After dimension being descended, Costas arrays produce Costas sequences which are special permutations. In modern cryptography, a public-key system is based on a certain hard mathematical problem. Existence problem and counting problem of Costas arrays remain unsolved yet, and become hard mathematical problems. Concentrating on existence problem and counting problem of Costas arrays and its cryptographic application, three achievements have been obtained in this thesis.1. A lacked necessary condition of extended Golomb construction was given, and stochastic algorithms were applied to existence detection of Costas arrays. Firstly, extended Golomb construction was studied. The extension was lack of a necessary condition and the condition was given. Algebraic methods could construct infinitely many orders of Costas arrays, but did not work on part of orders. Thus the existence of Costas arrays for some orders was not known. Computer enumeration could detect the existence of Costas arrays, which took exponential time. To avoid high complexity, existence detection was thought as an optimization problem, and an optimization model was developed. On model solution, SAACAS, GACAS and GPSOCAS were presented respectively based on simulated annealing algorithm, genetic algorithm and general particle swarm optimization which were stochastic algorithms. The experiment result preliminarily showed that three algorithms were effective for detection of Costas arrays whose orders were lower than 18.2. The relation between number of Costas arrays and number of symmetric ones was disclosed, and the existented sequential search algorithm of Costas arrays was improved and parallelized. Counting problem of symmetric Costas arrays was studied and relation formula was obtained. The formula disclosed the relation between number of symmetric Costas arrays for a certain order and number of Costas arrays for the same order. Existented enumeration algorithms were based on backtracking, and determined further search or backtracking by computing difference of the permutation. Focusing on computing, storing necessary difference and checkouting repetition, the thesis improved the algorithm and proved correlative theorems. The improved algorithm was parallelized, and the parallel algorithm had linear speedup and scalability.3. A digital signature scheme based on Costas arrays was constructed, and Costas arrays were applied to Shamir knapsack signature scheme, Niederreiter public-key system and S-boxes. Constructing Costas arrays took exponential time, but checkouting whether a permutation matrix was a Costas array or not took polynomial time. So Costas arrays were difficult to construct but easy to checkout. Based on this property, a digital signature scheme was designed. Based on low density, Costas arrays were applied to Shamir knapsack signature scheme and Niederreiter public-key system, and their security was enhanced. S-boxes were the only nonlinear components in many block ciphers. So, their cryptographic properties had determined the security of the whole cipher algorithms. An n-order bijection S-box could be regard as a permutation of all integers between 0 and 2n-1. The thesis presented that Costas arrays could be initial S-boxes for evolution to get S-boxes with better cryptographic properties, and provided abundant nonlinear resources for the further design of symmetric cryptographic algorithms.更多还原