多层元胞自动机加密算法的研究与实现

摘要

随着信息和通讯技术的迅猛发展和广泛应用，信息安全已经成为信息时代一个不可或缺的重要问题。在对信息安全的核心技术之一—密码学的自主性研究与开发中，元胞自动机因其特有的组成结构的简单性、组成单元之间相互作用的局部性、信息处理的高度并行性和复杂的动力学特性，使其在密码学领域有着独特的优势，具有重要的理论意义和广泛的应用前景。
　　本论文在研究元胞自动机理论和分析现有的元胞自动机加密算法的基础上，针对元胞自动机在密码学不同领域的应用，对多层元胞自动机和可逆元胞自动机构造分组密码、公钥密码的方法进行了相关的研究和探讨，取得的主要研究成果和创新点如下:
　　1.针对已有的基于多层可逆元胞自动机的分组加密算法密钥结构简单，且扩散性效果不理想的缺陷，利用多层元胞自动机的结构特点，引入层内和层间半移位变换，以及具有随机性的全局移位变换，设计了一种新的多层可逆元胞自动机分组加密算法。该算法增强了层与层之间的联系，表现出更复杂的动力学行为，仿真实验结果表明，该算法提高了密文对明文和密钥的敏感性，具有良好的扩散性和混淆性效果。
　　2.针对可逆元胞自动机数量稀少的问题，设计了一种可逆元胞自动机的构造方法，在此基础上，构建了一种基于可逆元胞自动机的反向迭代分组加密算法。该算法充分利用了多层元胞自动机的层状结构优点，在层与层之间进行交叉异或运算，并引入伪随机序列，反向演化实施加密，前向迭代实施解密。仿真结果表明，该算法具有良好的扩散性和混淆性，而且密文和随机序列是不可区分的;这些性质确保了提出的加密算法能够抵抗统计分析、线性分析和差分分析攻击。
　　3.在分析图像数据的结构与八层元胞自动机关系的基础上，提出了一种新的基于多层元胞自动机的图像加密方案。该方案是反向迭代的分组加密算法的扩展和应用，同样的引入了伪随机序列和伪随机数，但是本算法中对伪随机序列又进行了随机演化，而且利用伪随机数控制加密过程中不同层之间的交叉运算，使得密图中的像素分布更具随机性。详细的实验表明该算法具有足够大的密钥空间，加密后的图像像素分布均匀、相邻像素的相关性低，并且对密钥和明文非常敏感，即该算法是安全的，且具有良好的性能。
　　4.在研究了一种已有的基于可逆元胞自动机理论的公钥加密算法的基础上，借助于多层元胞自动机定义了一种新型的邻域结构，进而设计出基于多层元胞自动机的公钥加密算法。利用可证明安全理论，可以证明该算法是安全抵抗选择明文攻击的，弥补了其他元胞自动机公钥加密方案的不足;并且，利用随机预言模型，还可以将其改进成可以安全抵抗选择密文攻击的公钥加密算法。对密钥空间的分析以及仿真实验结果表明，本算法相较于RSA-1024加密算法具有高效性。
　　5.尝试利用元胞自动机理论构建数字签名算法，在上述公钥加密算法的基础上，设计了一种基于多层元胞自动机的数字签名算法，弥补了元胞自动机在数字签名上的空白。该算法选取可逆的一维元胞自动机作为私钥进行签名，构建出的二维规则作为公钥进行签名的验证。此算法是一个随机算法，元胞自动机的状态数和一维元胞自动机的个数以及二维元胞自动机的邻域半径均是不固定的，可以依据实际应用随机设定。基于二维元胞自动机可逆性的困难性假设，本签名算法在随机预言模型下被证明能够在适应性选择消息攻击下抵抗存在性伪造。

目录

声明

摘要

图目录

表目录

1 绪论

1．1 研究背景

1．1．1 信息安全的重要性

1．1．2 信息安全的核心

1．2 元胞自动机的创立和研究历史

1．2．1 元胞自动机的诞生与发展

1．2．2 元胞自动机的应用研究

1．2．3 元胞自动机的研究现状分析

1．3 主要研究内容

1．4 本文的结构与内容

2 元胞自动机理论与密码体制的安全性

2．1 元胞自动机的定义

2．1．1 元胞

2．1．2 元胞空间

2．1．3 元胞邻居

2．1．4 规则

2．2 元胞自动机的分类

2．2．1 维数分类

2．2．2 动力学分类

2．2．3 其他分类

2．3 可逆元胞自动机

2．4 元胞自动机的基本特征和主要优点

2．4．1 基本特征

2．4．2 主要优点

2．5 密码体制的安全性

2．5．1 评估密码体制安全性的主要方法

2．5．2 攻击方法

2．5．3 密码体制的攻击模型

2．6 加密算法的安全性分析

2．6．1 分组密码的安全性分析

2．6．2 公钥密码体制的安全性分析

2．7 本章小结

3．基于多层元胞自动机的分组加密算法

3．1 分组密码

3．2 多层元胞自动机

3．3 多层可逆元胞自动机加密算法

3．3．1 ILRCA算法加密思想

3．3．2 ILRCA加密算法

3．3．3 实验

3．3．4 安全性分析

3．4 反向迭代分组加密算法

3．4．1 二阶可逆规则的构造

3．4．2 基于多层元胞自动机的反向迭代分组加密算法

3．4．3 方案的安全性分析

3．5 反向迭代图像加密算法

3．5．1 引言

3．5．2 算法描述

3．5．3 算法安全性和性能分析

3．6 本章小结

4 基于多层元胞自动机的公钥加密算法

4．1 公钥密码体制

4．2 公钥密码体制的安全模型

4．2．1 IND-CPA安全

4．2．2 安全假设

4．3 基于多层元胞自动机的公钥加密方案

4．3．1 具有T型邻域结构的多层元胞自动机

4．3．2 元胞自动机公钥加密的思想

4．3．3 多层元胞自动机公钥加密方案的设计

4．4 LCAPKE加密方案的安全性分析

4．5 实例

4．6 效率分析

4．7 方案的改进

4．8 本章小结

5 基于多层元胞自动机的数字签名方案

5．1 数字签名

5．2 数字签名的安全性

5．2．1 攻击模型和安全目标

5．2．2 安全假设

5．3 基于多层元胞自动机的数字签名方案

5．3．1 密钥生成算法

5．3．2 签名算法

5．3．3 签名验证算法

5．4 签名方案的安全性证明

5．5 数字实例

5．6 签名方案的效率分析

5．6．1 一维元胞自动机的个数对效率的影响

5．6．2 密钥空间分析

5．7 应用实例

5．8 本章小结

6 总结与展望

6．1 全文总结

6．2 展望与设想

致谢

参考文献

攻读博士学位期间发表和完成的论文情况

攻读博士学位期间参加的科学研究情况