论文部分内容阅读
任何没有信息扩张的密码体制都可以看作是置换的结果。而起源于雷达信号设计的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盒,从而为将来设计各种分组密码算法提供非线性资源。