基于维度细胞自动机的对称加密算法及其周期性分析.doc

基于维度细胞自动机的对称加密算法及其周期性分析重庆大学硕士学位论文（专业学位）学生姓名：杨小馨杨小馨指导教师：廖晓峰教授廖晓峰学位类别：工程硕士（计算机技术领域）重庆大学计算机学院二O一四年四月 Analysis of A Symmetric Encryption Algorithm Based on Dimension Cellular Automata and the Period Distribution of CA A Thesis Submitted to Chongqing Universityin Partial Fulfillment of the Requirement for theProfessional DegreeByYang XiaoxinSupervised by Prof. Liao XiaofengSpecialty: ME(Computer Technology Field)College of Computer Science of Chongqing University , Chongqing, China April 2014 中文摘要摘要传统的加密系统由于其效率性和安全性已无法满足现有网络环境的需要，为了寻求更为可靠的密码系统，人们开始对密码系统的设计引入新的理论和方法，随着人工智能等相关技术的发展，各种智能计算方法开始运用于密码学中。由于细胞自动机理论（Cellular Automata）已作为人工生命科学的一门重要的理论分支和研究工具，其在密码学的应用研究也成为了一个新的研究热点。本论文的目的是探讨并研究维度细胞自动机的周期性分部以及在对称加密算法中的应用。对此本论文主要讨论两个问题：第一，分析不同维度上的细胞自动机的周期性；第二，提出一种基于细胞自动机周期性的对称加密算法，并探讨不同维度的细胞自动机对于加密安全性的影响，该问题直接来源于第一个问题的深入研究。对于第一个问题，本文分别讨论了一维和二维细胞自动机在规则 R=170N下的周期性，利用矩阵的方法求解 170N规则下细胞自动机的 GOE(Gardens of Eden)，设 CAmn为一个规则的二维规则 170N细胞自动机（一维 CA可以看成 CA1n）,B为该 CA的任意一个位形，若存在一个可逆矩阵 P,Q通过求解 P (S)Q使其成为( )一个特定的对角矩阵 E，其中 E为单位矩阵，0为零矩阵，则 B为该细胞自动O机的 GOE当且仅当存在一个 d i 0, n + 1- gcd( m + 1,n + )1 i n。其中= P(Pm-1(S) Pm-2 (S)P S( )nmn B。由此来获取 GOE的个数，()Td1,d2, dn0并以此计算出细胞自动机的瞬时长度 和极大圈长，从而求得细胞自动机的周期，并且分析该周期的分布特点。对于第二个问题，在设计密码系统时我们知道二进制可以用来表示数字信息，而将细胞自动机运用于密码系统的设计也是因为 CA与二进制一样，在表示数字信息时都存在空间和状态上的离散型。通过附加简单的演化规则，细胞自动机可以模拟复杂的行为模式。通过对第一个问题的探讨得知 CA18在 170N下状态下具有周期性，且周期 P=14，由此将待加密的明文转换成二进制流后看成若干个一维 CA，进行加密，其密钥为所有 CA状态迁移数的集合。同时，CA18在 170N规则下其状态,迁移具有周期性，且周期 P=28，利用该特性提出了一种新的基于二维细胞自动机的对称加密算法，并将该算法推广到图像加密算法中并对图像进行位平面上的耦合触发加密。仿真结果表明采用 CA进行加密具有敏感性高，密钥空间大，硬件实现简单，算法执行效率高等优点。关键词：对称密码系统，维度性细胞自动机，触发规则，周期，170NI 重庆大学硕士学位论文II 英文摘要ABSTRACT It is well known that the traditional encryption method has become more difficult tosubstantially increase safety and efficiency of encryption. Therefore, researchers try tointroduce some new methods and theories to develop new encryption algorithm. Withthe development of artificial intelligence and other related technologies, manyintelligent computer methods have been applied in the fields of encryption. To searchthe intelligent computing on the encryption has become a new research direction.Cellular Automata (CA) is an important artificial life sciences research tools andtheoretical branch. CA theory in the field of encryption application has become a newhotspot.The purpose of this thesis is analysis of a symmetric encryption algorithm based onthe dimension cellular automata and the period distribution of CA. This thesis focuseson two problems: one is the analysis of the period distribution based on differentdimension of the Cellular Automata, and the other is that a symmetric encryptionalgorithm is designed based on periodic CA. Futthermore, we study on the influence ofthe encryption security between different dimensions of CA, which is directly motivatedby the in-depth research of the first problem.For the first problem, we respectively analyze the period of one-dimensional andtwo-dimensional CA under the rule of 170N. By using the method of matrix, CAsGOE(Gardens of Eden) under the rule of 170N is solved. Set CAmn be a 2D CA by rule170N(see 1D CA as CA1n), B be a configuration of the CA. If there exists an invertiblematrix P and Q such that the PP (S)Q is a diagonal matrix (E0), where E is identitymatrix, and 0 is zero matrix, the B is a GOE of CAmn only if there exsits aanddi 0,n+1- gcd m 1,n 1( + + ) i n ,and (d1,d2, dn) P0(S)nmn B.T= P(Pm-1(S) Pm-2(S)Then the number of GOE is derived, therefore we can compute the transient length and the great lap length to obtain the period of CAmn and period distribution.For the second problem, the use of CA in encryption algorithm is due to thepeculiarity that the number can be expressed by CA and also by binary system, and bothof those two systems have the discreteness on state and space. Through to the firstquestion discussion,we can get that CA18 is perodical under the rule 170N with theperiod of 14. By converting the plaintext into a binary stream, we regard the stream as anumber of one-dimensional CAs to be encrypted. The secret key is the collection of allIII 重庆大学硕士学位论文the CAs state transition. Meanwhile, CA38 that under the rule 170N is periodical withthe period of 28. Based on these properties, we construct a new secure image encryptionalgorithm which coupled toggle encrypts every bit plane of the image with periodictwenty-eight 2D CA. Let the set of each CAs iteration numbers be the key, then thedecryption is the inverse process of encryption. Simulation results show that theproposed algorithm has the advantages of high sensitivity, simple hardwareimplementation, large key space, and high efficiency.Keywords：Symmetric Encryption, Dimensional Cellular Automata, Trigger rules,periodicity ,Rule170NIV 目录目录中文摘要.I英文摘要. III1绪论. 11.1课题的背景与意义 . 11.2课题研究内容及本文组织 . 11.3本章小结 . 32密码学. 52.1密码与密码学 . 52.2密码学发展概况 . 62.2.1古代加密方法（手工阶段） . 62.2.2古典密码（机械阶段） . 72.2.3近代密码（计算机阶段） . 72.3密码的主要特性 . 72.4密码体制分类 . 72.5常见对信息系统和密码系统的攻击方法. 82.6密码分析 . 92.7加密算法安全及性能指标 . 112.7.1明文敏感性. 122.7.2密钥空间和密钥敏感性 . 132.7.3相关性分析. 132.7.4图像加密的直方图. 142.8本章小结 . 153细胞自动机. 173.1细胞自动机历发展 . 173.1.1细胞自动机的发展历史 . 173.1.2细胞自动机的应用领域 . 183.2细胞自动机的基本原理 . 183.3细胞自动机分类 . 193.3.1按空间维数分类. 193.3.1按动力学行为分类. 203.4细胞自动机边界 . 20V 重庆大学硕士学位论文3.5触发规则 . 213.5.1演化规则. 213.5.2触发规则定义. 223.6常见的几种细胞自动机 . 223.6.1初等细胞自动机（ECA）25 . 233.6.2加型细胞自动机. 233.6.3触发式细胞自动机. 243.6.4 T型细胞自动机 . 233.6.5混合型细胞自动机和一致性细胞自动机. 243.6.6周期性细胞自动机. 243.6.7耦合细胞自动机. 253.7周期性细胞自动机 . 253.7.1常用规则表达. 263.7.2细胞自动机的映射矩阵. 273.7.3 CA在规则 170N下的 GOE . 283.7.4规则 170N下 2D细胞自动机的 GOE. 313.7.5规则 170下的 和 . 313.7.6 和 的推导 . 323.6.7 和 的计算 . 333.8本章小结 . 344细胞自动机的加密. 354.1现有细胞自动机加密技术 . 354.1.1 T型细胞自动机分组加密 . 354.1.2基于 ECA的状态环加密. 374.2数字图像加密 . 384.3现今图像加密技术 . 384.4基于 CA的图像加密 . 394.5本章小结 . 395基于周期性细胞自动机的加密设计 . 415.1周期细胞自动机的分组加密 . 415.1.1 CA的分组加密 . 415.1.2周期细胞自动机的分组加密. 425.1.3分组加密的仿真实验. 435.2周期性细胞自动机的图像加密 . 45VI 目录5.3周期性 2D-CA的选取. 475.4图像加密的仿真实验 . 485.4.1加密前的预处理. 495.4.2周期性 CA的耦合加密. 515.4.3细胞自动机的图像解密 . 545.5周期性细胞自动机图像加密安全性分析. 565.5.1迭代次数 I对直方图的影响. 575.5.2细胞自动机大小对明文敏感性影响 . 585.5.3密钥敏感性和密钥空间 . 595.5.4加密速度分析. 605.6本章小结 . 616总结与展望. 62致谢. 64参考文献. 66VII 1绪论1 绪论1.1课题的背景与意义Internet的出现及发展为人们带了方便快捷的生活，然而频繁出现的病毒事件和黑客事件使信息安全问题成为了制约信息产业发展的一大重要因素。日益增长的商业活动使得经由互联网或者通过使用一个网络环境来交换私人信息的方式变得越来越普遍，而这恰恰需要在一个安全的，隐私的通讯环境中进行。密码学技术作为信息安全的核心是保障安全通信的重要组成部分。当今社会主要有两种密码体系被用于到实践中：对称密码体系（也称带密钥的密码体系，私钥密码），以及非对称密码体系（也称公钥密码体系）。对称密码技术实现了对数据的加密，包括流密码和分组密码两种加密模式。在预先密钥不共享的情况下，非对称加密算法很好的实现了通信双方的安全通信。也就是说，公钥密码解决了对称密码技术加密后如何进行密钥分配的复杂问题，这就使得基于对称密码技术加密的密文得以在网络信道中安全传输。B. Schneier的Applied Cryptography1是目前一篇完整概括已知的或者新兴的密码学技术。而随着密码技术的发展，传统的加密方法已很难更大幅度的提高加密效率和安全性，人们开始对加密技术引入新的理论和方法，探索新的加密算法。随着人工智能和其他相关技术的发展，在密码学理论中不断涌现出各种智能计算。同时涉及了前两种密码学技术的加密技术逐渐被运用到实际工程领域中，也成为了近来的研究热点。细胞自动机（CAs）就是这种新兴的技术中的一种。细胞自动机理论成为了人工生命科学的一门重要的理论分支以及研究工具。基于细胞自动机的加密技术可以很好的利用细胞的状态多样性、非线性、并行性等优势特点，可以很好的保证加密的安全和高效。同时由于 CA的多维度性和周期性，CA可以同时运用到明文的加密以及图像加密中。本课题的目的即是探讨并研究基于一维周期细胞自动机的分组加密以及二维周期细胞自动机的图像加密，并且对于明文的分组加密做出改进，将各个加密后的分组组合成一个二维平面，对该二维平面再次用二维周期 CA进行加密。1.2对称加密算法国内外研究现状对称加密算法属于私钥密码体制，相比于公钥加密算法，其技术成熟，算法应用较早。由于对称加密算法加密和解密所使用的密钥是唯一的，因此要想保证密文传输的安全则还需要保证密钥的传输安全。对称加密算法的优点在于加解密的高速度和使用长密钥时的难破解性。假设如果企业内用户有n个，则要实现整个企业内部用户的互相安全通信则需要n(n -1)个密钥，密钥的生成和分发将成为1 重庆大学硕士学位论文企业信息部门的恶梦。对称加密算法的唯一密钥很好解决了类似问题，但同时对称加密算法的安全性取决于加密密钥的保存情况，要求企业中每一个持有密钥的人都保守秘密也将是一个难题。对称加密算法按类型主要可以分为分组密码和流密码两类。1.2.1分组密码美国早在 1977年就制定了自己的数据加密标准DES。随着 DES的出现，人们对分组密码展开了深入的研究和讨论。现已有大量的分组密码，如 DES的各种变形、IDEA算法、SAFER系列算法、RC系列算法、Skipjack算法、Rijndael算法、FEAL系列算法、REDOC系列算法、LOKI系列算法，CAST系列算法、Khufu、Khafre、MMB、3-WAY、TEA、MacGuffin、SHARK、BEAR、LION、CA.1.1、CRAB、Blowfish、GOST、SQUARE、MISTY，等等。在分组密码设计技术发展的同时，分组密码分析技术也得到了空前的发展。已有很多分组密码分析技术，如强力攻击（包括穷尽密钥搜索攻击、字典攻击、查表攻击、时间-存储权衡攻击）、差分密码分析、差分密码分析的推广（包括截段差分密码分析、高阶差分密码分析、不可能差分密码分析）、线性密码分析、线性密码分析的推广（包括多重线性密码分析、非线性密码分析、划分密码分析）、差分-线性密码分析、插值攻击、密钥相关攻击、能量分析、错误攻击、定时攻击等等。同时分组密码也具有加密速度慢，易产生错误扩散和传播，因此无法在信道质量较差的情况下使用分组加密系统。1.2.2序列密码序列密码主要用于政府、军方等国家要害部门，而且用于这些部门的理论和技术都是保密的，但由于一些数学工具（比如代数、数论、概率等）可用于研究序列密码，其理论和技术相对而言比较成熟。从20世纪80年代中期到90年代初，序列密码的研究非常热，特别是在序列密码的设计方法、序列密码的安全性度量指标、序列密码的分析方法、用于设计序列密码的各种组件等方面取得了一大批有理论和应用价值的成果。近年来，序列密码的研究虽然不像原来那么热，但有很多有价值的公开问题需要进一步研究，比如自同步流密码的研究、有记忆前馈网络密码系统的研究、多输出密码函数的研究、混沌序列密码和新研究方法的探索等。另外，虽然没有制定序列密码标准，但在一些系统中广泛使用了序列密码比如RC4，用于存储加密。事实上，欧洲的NESSIE计划中已经包括了序列密码标准的制定，这一举措有可能导致序列密码研究热。2 1绪论1.2.3基于细胞自动机的对称加密算法细胞自动机（cellular automata），简称为 CA，也称为元胞自动机5，可以看成是在有限域上具有空间上，状态上和时间上都具有离散性的动力学系统。细胞可以有多种状态，而细胞可以看成一个存储介质，其状态即为其存储内容。最简单的细胞自动机具有两种状态。所有细胞都在一定规则的作用下随着其领域细胞的改变而同步更新。细胞（cell）是细胞自动机最基本的组成单位，又称为单元，元胞或者基元。它们一般是结构和性质都相同的元素或者看成一个点。每个 cell地位相同，同时开始演化并且同时转入下一状态；而每个细胞仅仅和该细胞邻域内的细胞存在联系，和其他细胞处于独立并且无关状态。并且因为 CA中的每个细胞都与领域细胞存在运算中的关联性，在状态迁移一定次数后，整个细胞自动机的细胞之间却形成了复杂的联系。所以细胞自动机有着简单的结构却能模拟复杂的演化的过程，这可以被很好的运用到密码学技术中。Wolfram很早就将CA用于流密码的设计。朱保平等人提出了一种基于耦合可控CA的伪随机数发生器17等等。且近年来 CA在图像处理领域中的广泛应用，人们开始利用细胞自动机来设计图像加密算法，如张晓岩等人提出了一种基于二维CA的图像加密算法20；夏学文等人则设计了基于耦合触发 CA的图像加密算法21。本文主要工作就是研究细胞自动机在特殊规则下的周期性分布，并利用其具有周期性的特点提出了一种新的对称加密算法。1.3课题研究内容及本文组织本课题的主要研究并探讨基于一维周期细胞自动机的分组加密以及二维周期细胞自动机的图像加密。通过引入人工智能计算来探新的加密算法，已解决传统的加密算法效率低，安全性差，加密质量不理想等弊端。本课题通过在某些规则下细胞自动机的演化呈现周期性的特点进行加密，细胞自动机演化 K步后，其配置作为密文，密钥为所有 CA演化的步数集合，解密为加密的逆运算，细胞自动机执行 T-K步后，回到初始配置，即完成解密过程。本文第二部分简要介绍了密码学的基本概念以及发展现状，引出了基于人工智能的新的加密方法，基于细胞自动机的加密；第三部分介绍了细胞自动机的基本概念及原理，以及触发规则如何控制着细胞的演化，同时系统的介绍了周期性细胞自动机的推导过程；第四部引入了细胞自动机的加密概念，并