一种高阶可逆元胞自动机加密算法

一种高阶可逆元胞自动机加密算法

空间数据是促进经济和社会发展的重要战略资源。元胞自动机(cellularautomaton,CA)在空间、时间和状态上的离散性是其应用于图像加密的重要依据,其组成单元的简单性、单元之间作用的局部性、信息处理的高度并行性以及全局复杂性等特点,使其在密码学领域具有独特的优势目前,已有多位学者研究了元胞自动机图像加密方法,多体现为结合密码学基本方法和单规则元胞自动机设计加密算法。文献[6]引入密码学中的移位变换方法,提出了一种可逆多层元胞自动机分组加密算法,达到了一次一密的加密效果,具有较大的密钥空间,但此类算法无法抵抗关于演化规则的穷举攻击。文献[7]结合分组密码方法,利用可逆元胞自动机无信息损失和高度并行处理的特点,提出了一种基于可逆二阶触发元胞自动机的分组加密算法,具有较高的安全性,但应用于图像加密时,存在加密和解密效率低的问题。文献[8]将已知灰度图像变为二值图像,应用可逆元胞自动机规则实现图像加密,具有较好的扩散特性,但数据重排增加了计算时间,尤其对较大的图像加密,加密速度较低。文献[9]结合图像像素置换方法,将元胞与相邻元胞的链接状态加权后作为加密矩阵,通过置换对图像进行加密,混乱特性和扩散特性较好,但存在密钥空间较小的不足。本文针对单规则元胞自动机图像加密算法安全性不足的问题,结合可逆元胞自动机无信息损失和全局并行处理及四叉树图像分割速度快、分割过程全自动的优点,提出了一种多规则可逆元胞自动机图像加密算法,在不显著增加算法复杂性的情况下,提高计算速度与安全性。1高阶可逆元胞自动机的定义通常元胞自动机加密是基于单个规则对元胞进行多次演化,而本文提出的多规则可逆元胞自动机是在每次演化过程中构造多个演化规则,形成复杂的构形转移,实现栅格地图加密,达到混淆特殊用途地图中的重要符号和标识,保证重要栅格地图数据安全的目的。定义1的元胞自动机为二阶可逆元胞自动机。文献[10]给出了其可逆性证明。假设在一个K阶RCA中,新构形C式中,V式中,Φ定义2在元胞自动机中,称具有形式局部转换函数的元胞自动机为多规则高阶可逆元胞自动机。其中,Φ式中,B在进行逆向RCA演化时,逆序操作构形,即B根据式(5)可以得到:根据可逆元胞自动机定义,式(6)中的C因此,式(5)定义的RCA可以从构形C2许多规则的高可逆元生动机加密方法2.1子块的处理及演化首先,本文将四叉树分解的4个子图像状态作为构形,根据高阶元胞自动机定义,则构造出的为4阶元胞自动机,其每个演化过程需要3个规则,多个过程需要多个规则。其次,借鉴文献[11]中的密钥产生方法,将非均衡元胞自动机的演化结果作为4阶元胞自动机规则,并将其规则由固定改为随机选择,以增强算法安全性。由于分割粒度越小加密结果越安全,本文分割的最小粒度为4×4像素。但是,也存在分割粒度越小计算量越大的问题,本文并未对所有子块进行连续分割,而是选取左上角子块进行继续分割,即降低了分割粒度,保证图像内容的安全性,又降低了加密过程的计算量。根据四叉树分解定义,四叉树深度取决于图像大小,对于一个L×L的方图,图像分解后的数量m等于log需要说明的是,每幅地图加密前,都需要进行一次非均衡元胞自动机演化规则的随机选择,并记录所选择的演化规则及其顺序。这是因为在解密过程中,同样需要子密钥定义关于4阶RCA的演化规则。随机选择规则30、90、110和150作为非均衡元胞自动机的演化规则:1)使用伪随机序列发生器随机产生128位密钥,记为C2)使用非均衡元胞自动机,按照规则30、90、110和150的顺序对C3)将规则30、90、110和150循环左移一次,即150、30、90和110,作为非均衡元胞自动机新的规则对构形C4)继续将规则循环左移,作为新的规则对步骤3产生的结果进行演化,产生Φ作为密钥空间的组成部分,演化规则的随机选择和移位均扩大了传统单规则元胞自动机加密算法的密钥空间。2.2左方图像分解加密过程中,使用分层分解方法处理图像的内容,除明文图像分解结果全部作为构形外,其余过程只选取4个子图像中的一块继续进行四叉树分解,每次分解结果作为构形。为便于计算,本文选取左上角子图像进行分解。1)将明文图像按照四叉树分解策略分解成4个子图像,并将这4个子图像看作式(5)定义的4阶RCA的4个初始化构形C2)将2.1节中产生的密钥作为RCA的演化规则,按照4阶可逆元胞自动机演化规则,对初始化构形C3)左上角产生的C4)递归重复该过程,分离块C特别地,最后一层数据的大小等于16个字节(128)位,对应块C通过逆向执行加密过程,可从加密图像中恢复出明文图像。3加密网格地图的实验和分析3.1图像a、c#算法实验所用数据为3幅512×512像素、1幅1024×1024像素和1幅4096×4096像素的数字栅格地图(分别记为图像a、图像b、图像c、图像d和图像e)。算法通过C#语言和Matlab实现,实验配置为Intel(R)Core(TM)i5-CPU3GHz,8GB内存。根据统计分布和熵测量准则等指标评估算法安全性,在密钥空间和算法速度方面与文献[12]基于混沌的图像加密算法、文献[13]基于初等可逆元胞自动机的图像加密算法、文献[14]基于二阶可逆元胞自动机的图像加密算法进行了比较。3.2结果与分析3.2.1图像信息熵实验本小节通过验证加密图像的不确定性评估算法的安全性。图像信息熵越大,灰度分布越一致,算法扩散性越好,安全性越高,理想加密图像的信息熵理论最大值为8。图2为图像a、b、c明文图像及其密文图像。分别测试明文图像和密文图像的信息熵,并随机选择了16个子图像数据块(分别记为s从实验结果可知,每个密文图像的整体熵非常接近理论值8,每个局部熵在重要水平的差距为5%左右,在可接受范围内。这就证明了密文图像的局部熵和整体熵均满足要求。3.2.2不同加密次数的密钥空间差异为评估本文方法对明文图像细微变化的敏感性,选择测试图像a、b、c、d、e,随机改变明文图像的一个bit,通过多轮加密对加密结果进行NPCR和UACI评估。其中,NPCR表示两幅不同像素所占百分比,UACI表示两图像之间差异的平均强度,以33%为标准理论值。图3给出了不同加密次数的测试结果。由图3中的结果可以看出,针对不同的加密次数,图像a、b、c、d和e的NPCR值和UACI值结果均高于各自理论值99%和33%,说明基于四叉树分解的高阶元胞自动机加密方法对明文变化具有较高的敏感性,能够有效抵抗基于差分的明文攻击。表3列出了本文算法和其他3种算法在相同半径r下密钥空间的对比。相比于另外3种算法,多演化规则和规则移位的使用,以及元胞自动机阶数的增加使得密钥空间显著提升。阶数越高,与元胞自动机状态相关的邻胞数目越多,所占密钥空间就越多。3.2.3加密过程及算法对比根据NPCR和UACI分析,本文方法只需要进行一次加密就能达到与现有算法使用多次加密相同的敏感程度。因此,与现有相关算法相比,避免了大量循环计算过程,加密和解密速度有较大提升。其中,解密过程与加密过程的计算过程所涉及的计算方法相同,实验结果表明,解密时间与加密时间基本相同。表4列出了本文算法和其他3种算法分别对5幅栅格地图的加密时间和解密时间对比。由表4中不同算法的加密时间可知,相对于文献[12]的算法,本文算法速度是其约3倍;相对于文献[13]和文献[14]中的算法,本文算法速度分别提高了约2倍、1.5倍。本文算法避免了反复的循环迭代过程,在加密阶段,每个四叉树分解的子图像只加密一次,避免对所有像素进行多次循环迭代加密的过程,省去了基于混合长度块分解和像素转换操作所需的时间。