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

论文摘要

任何没有信息扩张的密码体制都可以看作是置换的结果。而起源于雷达信号设计的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
• 第1章 引言
• 1.1 背景知识
• 1.2 COSTAS 阵列的定义
• 1.3 COSTAS 阵列的构造方法
• 1.4 COSTAS 阵列的搜索方法
• 1.5 COSTAS 阵列的理论难题
• 1.6 本文的主要工作及章节安排
• 第2章 COSTAS 阵列的存在性研究
• 2.1 广义GOLOMB 构造法应用的一个前提条件
• 2.2 COSTAS 阵列的存在性探测优化模型
• 2.3 基于模拟退火算法的COSTAS 阵列随机搜索算法——SAACAS
• 2.3.1 模拟退火算法概述
• 2.3.2 SAACAS 设计
• 2.3.3 SAACAS 分析
• 2.4 基于遗传算法的COSTAS 阵列随机搜索算法——GACAS
• 2.4.1 遗传算法概述
• 2.4.2 GACAS 设计
• 2.4.3 GACAS 分析
• 2.5 基于广义粒子群优化算法的COSTAS 阵列随机搜索算法——GPSOCAS
• 2.5.1 广义粒子群优化算法概述
• 2.5.2 GPSOCAS 设计
• 2.5.3 GPSOCAS 分析
• 2.6 SAACAS、GACAS 和GPSOCAS 的比较
• 2.7 小结
• 第3章 COSTAS 阵列的计数研究
• 3.1 对称COSTAS 阵列的计数
• 3.1.1 符号定义
• 3.1.2 Costas 阵列的旋转特性
• 3.1.3 对称Costas 阵列的计数
• 3.2 COSTAS 阵列的通用串行搜索算法
• 3.3 并行算法概述
• 3.4 COSTAS 阵列的通用并行搜索算法
• 3.4.1 在特例上对CAPS 的改进
• 3.4.2 CAPS 的性能分析
• 3.5 小结
• 第4章 COSTAS 阵列的密码学应用
• 4.1 COSTAS 阵列的分布
• 4.2 一种基于COSTAS 阵列的数字签名方案
• 4.3 COSTAS 阵列应用于SHAMIR 背包数字签名
• 4.4 COSTAS 阵列应用于NIEDERREITER 公钥体制
• 4.5 COSTAS 阵列应用于S 盒
• 4.5.1 S 盒的设计准则
• 4.5.2 S 盒的构造方法
• 4.5.3 Costas 阵列应用于S 盒
• 4.6 小结
• 第5章 结束语
• 参考文献
• 致谢
• 攻读硕士学位期间发表的论文
• 攻读硕士期间参与的项目
• 攻读硕士期间参加的学术会议和研讨班