留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

一种多规则可逆元胞自动机的栅格地图加密算法

薛帅 王光霞 郭建忠 李冬辉 徐振

薛帅, 王光霞, 郭建忠, 李冬辉, 徐振. 一种多规则可逆元胞自动机的栅格地图加密算法[J]. 武汉大学学报 ● 信息科学版, 2018, 43(5): 773-778. doi: 10.13203/j.whugis20160345
引用本文: 薛帅, 王光霞, 郭建忠, 李冬辉, 徐振. 一种多规则可逆元胞自动机的栅格地图加密算法[J]. 武汉大学学报 ● 信息科学版, 2018, 43(5): 773-778. doi: 10.13203/j.whugis20160345
XUE Shuai, WANG Guangxia, GUO Jianzhong, LI Donghui, XU Zhen. An Encryption Algorithm of Multi-rule Reversible Cellular Automata for Raster Map[J]. Geomatics and Information Science of Wuhan University, 2018, 43(5): 773-778. doi: 10.13203/j.whugis20160345
Citation: XUE Shuai, WANG Guangxia, GUO Jianzhong, LI Donghui, XU Zhen. An Encryption Algorithm of Multi-rule Reversible Cellular Automata for Raster Map[J]. Geomatics and Information Science of Wuhan University, 2018, 43(5): 773-778. doi: 10.13203/j.whugis20160345

一种多规则可逆元胞自动机的栅格地图加密算法

doi: 10.13203/j.whugis20160345
基金项目: 

国家自然科学基金 41401462

详细信息
    作者简介:

    薛帅, 博士, 主要从事地理信息服务与地理信息安全方面的研究。xueshuai912@sohu.com

  • 中图分类号: P208

An Encryption Algorithm of Multi-rule Reversible Cellular Automata for Raster Map

Funds: 

The National Natural Science Foundation of China 41401462

More Information
    Author Bio:

    XUE Shuai, PhD, specializes in geographic information services and geographic information security. E-mail: xueshuai912@sohu.com

  • 摘要: 针对单规则元胞自动机图像加密易受明文攻击的问题,分析了其密钥空间的局限性,提出了一种高阶可逆元胞自动机加密算法。通过分析可逆元胞自动机的特点,结合栅格地图的四叉树分解结果,构造了多规则高阶可逆元胞自动机,取代传统方法中对所有像素进行多次循环迭代加密的方式,在不增加元胞自动机结构复杂性的前提下,实现栅格地图加密。实验结果表明,该方法密钥空间较大,加密效率较高,在保证地图数据完整性的基础上,能够有效抵抗差分攻击和明文攻击,适用于实时图像加密。
  • 图  1  加密过程示意图

    Figure  1.  Descriptive Diagram of the Proposed Enciphering Scheme

    图  2  明文图像abc及其密文图像

    Figure  2.  Plain Text Image a, b, c and Their Encrypted Image

    图  3  加密次数与NPCR及UACI关系

    Figure  3.  Relation Ship Between the Number of Times of Encryption and NPCR and UACI

    表  1  图像abcde香农熵

    Table  1.   Shannon Entropy of Image a, b, c, d, e

    图像 大小 明文图像 密文图像
    a 512×512 7.098 1 7.996 9
    b 512×512 6.954 9 7.996 8
    c 512×512 6.157 4 7.997 2
    d 1 024×1 024 7.692 1 7.991 2
    e 4 096×4 096 7.487 0 7.989 4
    下载: 导出CSV

    表  2  明文及密文图像局部信息熵

    Table  2.   Local Information Entropy of the Text and the Image

    数据块 图像a 图像b 图像c 图像d 图像e
    明文 密文 明文 密文 明文 密文 明文 密文 明文 密文
    s1 5.343 9 7.965 5 6.692 7 7.977 6 6.802 3 7.967 5 6.730 2 7.968 3 6.257 1 7.991 8
    s2 5.213 1 7.979 4 5.803 4 7.982 5 6.941 9 7.974 9 6.681 7 7.989 4 7.216 3 7.978 5
    s3 5.698 6 7.973 2 6.792 6 7.968 9 6.702 5 7.996 8 7.241 7 7.987 9 6.365 6 7.978 0
    s4 7.127 6 7.970 6 6.962 3 7.972 1 6.285 7 7.978 9 6.871 3 7.973 2 7.207 5 7.976 9
    s5 5.532 3 7.970 4 6.991 2 7.970 5 6.933 2 7.977 2 6.691 2 7.970 7 6.135 2 7.988 1
    s6 5.461 9 7.967 1 6.980 5 7.971 8 7.012 8 7.981 9 6.820 2 7.981 2 7.245 3 7.976 6
    s7 6.028 1 7.975 6 7.011 5 7.991 3 7.035 6 7.972 3 7.068 2 7.992 9 6.490 9 7.975 2
    s8 7.335 7 7.982 1 6.766 7 7.966 9 7.351 7 7.973 4 6.840 9 7.969 8 6.909 9 7.989 5
    s9 5.804 3 7.971 6 5.639 4 7.978 7 6.104 4 7.979 1 7.331 6 7.977 8 7.121 7 7.976 7
    s10 6.386 4 7.977 5 5.720 8 7.976 1 7.231 7 7.967 6 7.291 0 7.975 3 6.783 5 7.971 8
    s11 6.780 6 7.966 3 5.307 6 7.971 6 7.027 5 7.983 5 7.178 7 7.968 1 7.378 2 7.993 9
    s12 7.057 3 7.983 6 6.026 9 7.967 2 7.257 6 7.977 1 6.904 1 7.996 3 6.782 6 7.971 9
    s13 5.572 5 7.969 4 5.719 3 7.970 6 6.132 3 7.976 3 7.093 8 7.981 9 6.539 2 7.968 4
    s14 5.904 9 7.969 1 5.633 9 7.973 1 6.752 6 7.964 9 7.287 5 7.997 8 7.322 9 7.972 0
    s15 6.803 2 7.973 8 6.703 7 7.969 2 7.255 2 7.961 3 6.712 6 7.983 5 7.249 0 7.982 6
    s16 5.130 8 7.960 9 5.997 6 7.974 7 7.093 4 7.977 6 7.137 4 7.975 7 6.775 6 7.997 3
    下载: 导出CSV

    表  3  不同算法密钥空间对比

    Table  3.   Comparison of Key Spaces in Different Algorithms

    加密方法 r=1 r=2 r=3
    文献[12] 2 256 2 256 2 256
    文献[13] 28 232 2 128
    文献[14] 240 264 2 160
    本文算法 2 560 2 608 2 800
    下载: 导出CSV

    表  4  与不同算法加密和解密时间对比/ms

    Table  4.   Time Comparison of Encryption and Decryption with Different Algorithms/ms

    图像 加密和解密时间
    文献[12] 文献[13] 文献[14] 本文算法
    a 加密
    解密
    812.2
    809.4
    697.5
    694.2
    443.7
    447.6
    269.4
    243.2
    b 加密
    解密
    823.7
    822.9
    699.1
    698.7
    451.9
    449.0
    273.6
    271.8
    c 加密
    解密
    787.6
    786.1
    655.6
    656.3
    426.5
    423.3
    236.8
    236.4
    d 加密
    解密
    2 340.0
    2 215.2
    1 528.8
    1 528.8
    1 216.8
    1 263.6
    795.6
    748.8
    e 加密
    解密
    19 260.0
    19 244.4
    12 261.6
    11 902.8
    10 058.8
    10 018.4
    6 671.6
    6 422.0
    下载: 导出CSV
  • [1] 丁凯孟, 朱长青, 卢付强.基于自适应格网划分的遥感影像感知哈希认证算法[J].武汉大学学报·信息科学版, 2015, 40(6):716-720 http://ch.whu.edu.cn/CN/abstract/abstract3265.shtml

    Ding Kaimeng, Zhu Changqing, Lu Fuqiang. Remote Sensing Image Perception of Hashi Adaptive Grid Based Authentication Algorithm[J]. Geomatics and Information Science of Wuhan University, 2015, 40(6):716-720 http://ch.whu.edu.cn/CN/abstract/abstract3265.shtml
    [2] 时向勇, 李先华, 郑成建.基于椭圆曲线密码体制的遥感图像加密算法[J].武汉大学学报·信息科学版, 2010, 35(11):1309-1313 http://ch.whu.edu.cn/CN/abstract/abstract1108.shtml

    Shi Xiangyong, Li Xianhua, Zheng Chengjian. Remote Sensing Image Encryption Algorithm Based on Elliptic Curve Cryptosystem[J]. Geomatics and Information Science of Wuhan University, 2010, 35(11):1309-1313 http://ch.whu.edu.cn/CN/abstract/abstract1108.shtml
    [3] Yang Y G, Tian J, Lei H, et al. Novel QuantumImage Encryption Using One-Dimensional Quantum Cellular Automata[J]. Information Sciences, 2016, 345:257-270 doi:  10.1016/j.ins.2016.01.078
    [4] 田力, 张晓盼, 袁艳斌.交互式遥感影像分割算法研究[J].武汉大学学报·信息科学版, 2014, 39(4):406-410 http://ch.whu.edu.cn/CN/abstract/abstract2950.shtml

    Tian Li, Zhang Xiaopan, Yuan Yanbin. Research on Interactive Remote Sensing Image Segmentation Algorithm[J]. Geomatics and Information Science of Wuhan University, 2014, 39(4):406-410 http://ch.whu.edu.cn/CN/abstract/abstract2950.shtml
    [5] 文昌辞, 王沁, 苗晓宁, 等.数字图像加密综述[J].计算机科学, 2012, 39(12):6-9 doi:  10.3969/j.issn.1002-137X.2012.12.002

    Wen Changci, Wang Qin, Miao Xiaoning, et al. Summary of Digital Image Encryption[J]. Computer Science, 2012, 39(12):6-9 doi:  10.3969/j.issn.1002-137X.2012.12.002
    [6] 张星, 赵学龙, 张宏, 等.改进多层可逆元胞自动机加密算法研究[J].南京理工大学学报, 2014(3):313-317 doi:  10.3969/j.issn.1005-9830.2014.03.001

    Zhang Xing, Zhao Xuelong, Zhang Hong, et al. Research on the Encryption Algorithm of Multi Layer Reversible Cellular Automata[J]. Journal of Nanjing University of Science and Technology, 2014(3):313-317 doi:  10.3969/j.issn.1005-9830.2014.03.001
    [7] Faraoun K M. Design of Fast One-Pass Authenticated and Randomized Encryption Schema Using Reversible Cellular Automata[J]. Communications in Nonlinear Science & Numerical Simulation, 2014, 19(9):3136-3148 https://www.sciencedirect.com/science/article/pii/S1007570414000586
    [8] Abdo A A, Lian S, Ismail I A, et al. A Cryptosystem Based on Elementary Cellular Automata[J]. Communications in Nonlinear Science & Numerical Simulation, 2013, 1(1):136-147 https://www.sciencedirect.com/science/article/pii/S1007570412002523
    [9] 王晓东, 王丽丹, 段书凯.基于忆阻细胞自动机的图像像素值置换加密技术[J].计算机科学, 2013, 40(9):133-135 http://www.cnki.com.cn/Article/CJFDTOTAL-JSJA201309029.htm

    Wang Xiaodong, Wang Lidan, Duan Shukai. Image Pixel Value Permutation Encryption Based on Cellular Automata[J]. Computer Science, 2013, 40(9):133-135 http://www.cnki.com.cn/Article/CJFDTOTAL-JSJA201309029.htm
    [10] 平萍, 周曜, 张宏, 等.可逆元胞自动机加密技术研究[J].通信学报, 2008, 29(5):26-33 http://d.wanfangdata.com.cn/Periodical_txxb200805005.aspx

    Ping Ping, Zhou Yao, Zhang Hong, et al. Research on Encryption Technology of Reversible Cellular Automata[J]. Journal of Communication. 2008, 29(5):26-33 http://d.wanfangdata.com.cn/Periodical_txxb200805005.aspx
    [11] Wu Y, Zhou Y, Saveriades G, et al. Local Shannon Entropy Measure with Statistical Tests for image Randomness[J]. Information Sciences:An International Journal, 2013, 222:323-342 doi:  10.1016/j.ins.2012.07.049
    [12] Mohamed F K. A Parallel Block-Based Encryption Schema for Digital Images Using Reversible Cellular Automata[J]. Engineering Science & Technology:An International Journal, 2014, 17(2):85-94 http://www.sciencedirect.com/science/article/pii/S2215098614000147
    [13] Elshamy E M, El-Rabaie E S M, Faragallah O S, et al. Efficient Audio Cryptosystem Based on Chaotic Maps and Double Random Phase Encoding[J]. International Journal of Speech Technology, 2015, 18(4):619-631 doi:  10.1007/s10772-015-9279-3
    [14] Kumar J, Chenna K, Salivahanan S. Novel and Efficient Cellular Automata Based Symmetric Key Encryption Algorithm for Wireless Sensor Networks[J]. International Journal of Computer Applications, 2010, 13(4):1-8 http://www.researchgate.net/publication/49607392_Novel_and_Efficient_Cellular_Automata_Based_Symmetric_Key_Encryption_Algorithm_for_Wireless_Sensor_Networks
  • [1] 郭庆胜, 黄鹤声, 王琳, 刘远刚.  顾及制图规则的地图多要素协同移位方法 . 武汉大学学报 ● 信息科学版, 2018, 43(5): 726-731. doi: 10.13203/j.whugis20160362
    [2] 沈意浪, 艾廷华, 赵荣.  一种彩色栅格地图注记识别方法 . 武汉大学学报 ● 信息科学版, 2018, 43(1): 145-146. doi: 10.13203/j.whugis20150381
    [3] 张鑫龙, 陈秀万, 李怀瑜, 李飞.  一种改进元胞自动机的人员疏散模型 . 武汉大学学报 ● 信息科学版, 2017, 42(9): 1330-1336. doi: 10.13203/j.whugis20150763
    [4] 沈意浪, 艾廷华.  栅格地图注记一致性探测与度量 . 武汉大学学报 ● 信息科学版, 2017, 42(6): 737-743. doi: 10.13203/j.whugis20150549
    [5] 惠珊, 芮小平, 李尧.  一种耦合元胞自动机的改进林火蔓延仿真算法 . 武汉大学学报 ● 信息科学版, 2016, 41(10): 1326-1332. doi: 10.13203/j.whugis20140811
    [6] 王伟, 李欣, 陈能成, 刘静波.  利用元胞自动机计算河道槽蓄量 . 武汉大学学报 ● 信息科学版, 2013, 38(2): 235-239.
    [7] 罗广祥, 刘苗, 樊鸿宇, 杨芳.  全球等面积四叉树离散格网建模与编码体系研究 . 武汉大学学报 ● 信息科学版, 2012, 37(10): 1252-1255.
    [8] 王海军, 张文婷, 陈莹莹, 贺三维.  利用元胞自动机作用域构建林火蔓延模型 . 武汉大学学报 ● 信息科学版, 2011, 36(5): 575-578.
    [9] 赵彬彬, 邓敏, 徐震, 刘慧敏.  多尺度地图面目标匹配的统一规则研究 . 武汉大学学报 ● 信息科学版, 2011, 36(8): 991-994.
    [10] 王海军, 邓羽, 张文婷, 贺三维.  利用元胞自动机和遗传算法的Voronoi图生成 . 武汉大学学报 ● 信息科学版, 2010, 35(7): 778-781.
    [11] 王海军, 张文婷, 贺三维, 邓羽.  利用元胞自动机和模糊C均值进行图像分割 . 武汉大学学报 ● 信息科学版, 2010, 35(11): 1288-1291.
    [12] 赵学胜, 崔马军, 李昂, 张美娟.  球面退化四叉树格网单元的邻近搜索算法 . 武汉大学学报 ● 信息科学版, 2009, 34(4): 479-482.
    [13] 喻永平, 陈晓勇, 刘经南, 都洁.  状态扩展元胞自动机模型在时空数据挖掘中的应用 . 武汉大学学报 ● 信息科学版, 2008, 33(6): 592-595.
    [14] 吴芳, 芮国胜.  基于四叉树和纠错编码的数字图像水印算法 . 武汉大学学报 ● 信息科学版, 2007, 32(3): 208-211.
    [15] 白建军, 赵学胜, 陈军.  基于线性四叉树的全球离散格网索引 . 武汉大学学报 ● 信息科学版, 2005, 30(9): 805-808.
    [16] 罗平, 杜清运, 雷元新, 王涛.  地理特征元胞自动机及城市土地利用演化研究 . 武汉大学学报 ● 信息科学版, 2004, 29(6): 504-507,512.
    [17] 刘耀林, 刘艳芳, 明冬萍.  基于灰色局势决策规则的元胞自动机城市扩展模型 . 武汉大学学报 ● 信息科学版, 2004, 29(1): 7-13.
    [18] 盛业华, 唐宏, 杜培军.  线性四叉树快速动态编码及其实现 . 武汉大学学报 ● 信息科学版, 2000, 25(4): 324-328.
    [19] 樊红, 杜道生, 张祖勋.  地图注记自动配置规则及其实现策略 . 武汉大学学报 ● 信息科学版, 1999, 24(2): 154-157.
    [20] 邓朝晖, 贾华.  直接表达区域的四叉树链式编码 . 武汉大学学报 ● 信息科学版, 1995, 20(3): 224-227.
  • 加载中
图(3) / 表(4)
计量
  • 文章访问数:  1438
  • HTML全文浏览量:  82
  • PDF下载量:  209
  • 被引次数: 0
出版历程
  • 收稿日期:  2017-02-15
  • 刊出日期:  2018-05-05

一种多规则可逆元胞自动机的栅格地图加密算法

doi: 10.13203/j.whugis20160345
    基金项目:

    国家自然科学基金 41401462

    作者简介:

    薛帅, 博士, 主要从事地理信息服务与地理信息安全方面的研究。xueshuai912@sohu.com

  • 中图分类号: P208

摘要: 针对单规则元胞自动机图像加密易受明文攻击的问题,分析了其密钥空间的局限性,提出了一种高阶可逆元胞自动机加密算法。通过分析可逆元胞自动机的特点,结合栅格地图的四叉树分解结果,构造了多规则高阶可逆元胞自动机,取代传统方法中对所有像素进行多次循环迭代加密的方式,在不增加元胞自动机结构复杂性的前提下,实现栅格地图加密。实验结果表明,该方法密钥空间较大,加密效率较高,在保证地图数据完整性的基础上,能够有效抵抗差分攻击和明文攻击,适用于实时图像加密。

English Abstract

薛帅, 王光霞, 郭建忠, 李冬辉, 徐振. 一种多规则可逆元胞自动机的栅格地图加密算法[J]. 武汉大学学报 ● 信息科学版, 2018, 43(5): 773-778. doi: 10.13203/j.whugis20160345
引用本文: 薛帅, 王光霞, 郭建忠, 李冬辉, 徐振. 一种多规则可逆元胞自动机的栅格地图加密算法[J]. 武汉大学学报 ● 信息科学版, 2018, 43(5): 773-778. doi: 10.13203/j.whugis20160345
XUE Shuai, WANG Guangxia, GUO Jianzhong, LI Donghui, XU Zhen. An Encryption Algorithm of Multi-rule Reversible Cellular Automata for Raster Map[J]. Geomatics and Information Science of Wuhan University, 2018, 43(5): 773-778. doi: 10.13203/j.whugis20160345
Citation: XUE Shuai, WANG Guangxia, GUO Jianzhong, LI Donghui, XU Zhen. An Encryption Algorithm of Multi-rule Reversible Cellular Automata for Raster Map[J]. Geomatics and Information Science of Wuhan University, 2018, 43(5): 773-778. doi: 10.13203/j.whugis20160345
  • 空间数据是国民经济与社会发展的重要基础战略资源[1]。其中,包含国家重要设施、国防重要目标符号和标识的栅格地图,必须提供安全的网络传输方法以保证其完整性和可用性。栅格地图数据(简称为栅格地图)具有数字图像的特征和数据量大的特点,使用传统加密方法很难满足置乱和扩散要求,而且图像加密对加密方法有不同于文本和一般二进制数据的要求[2-3]

    元胞自动机(cellular automaton,CA)在空间、时间和状态上的离散性是其应用于图像加密的重要依据,其组成单元的简单性、单元之间作用的局部性、信息处理的高度并行性以及全局复杂性等特点,使其在密码学领域具有独特的优势[4-5]。目前,可逆元胞自动机(reversible cellular automata,RCA)的图像加密算法多基于单规则,针对多种演化规则和高阶可逆元胞自动机的研究相对较少,单规则数量的局限性使得算法极易受到穷举攻击,存在安全隐患,多规则演化能够提高加密算法抗攻击能力。

    目前,已有多位学者研究了元胞自动机图像加密方法,多体现为结合密码学基本方法和单规则元胞自动机设计加密算法。文献[6]引入密码学中的移位变换方法,提出了一种可逆多层元胞自动机分组加密算法,达到了一次一密的加密效果,具有较大的密钥空间,但此类算法无法抵抗关于演化规则的穷举攻击。文献[7]结合分组密码方法,利用可逆元胞自动机无信息损失和高度并行处理的特点,提出了一种基于可逆二阶触发元胞自动机的分组加密算法,具有较高的安全性,但应用于图像加密时,存在加密和解密效率低的问题。文献[8]将已知灰度图像变为二值图像,应用可逆元胞自动机规则实现图像加密,具有较好的扩散特性,但数据重排增加了计算时间,尤其对较大的图像加密,加密速度较低。文献[9]结合图像像素置换方法,将元胞与相邻元胞的链接状态加权后作为加密矩阵,通过置换对图像进行加密,混乱特性和扩散特性较好,但存在密钥空间较小的不足。

    本文针对单规则元胞自动机图像加密算法安全性不足的问题,结合可逆元胞自动机无信息损失和全局并行处理及四叉树图像分割速度快、分割过程全自动的优点,提出了一种多规则可逆元胞自动机图像加密算法,在不显著增加算法复杂性的情况下,提高计算速度与安全性。

    • 通常元胞自动机加密是基于单个规则对元胞进行多次演化,而本文提出的多规则可逆元胞自动机是在每次演化过程中构造多个演化规则,形成复杂的构形转移,实现栅格地图加密,达到混淆特殊用途地图中的重要符号和标识,保证重要栅格地图数据安全的目的。

      定义1[10]  在元胞自动机中,称演化规则为:

      $$ s_i^{t + 1} = \emptyset \left( {s_{i - r}^t \cdots s_i^t \cdots s_{i + r}^t \cdots s_{i - r}^{t - 1} \cdots s_{i + r}^{t - r}} \right) $$

      的元胞自动机为二阶可逆元胞自动机。文献[10]给出了其可逆性证明。

      假设在一个K阶RCA中,新构形Ct+1依赖于K个之前的构形CtCt-K。使用K个不同演化规则F1, F2FK,每个构形的状态定义为[11]

      $$ S_i^{t + 1} = {F_1}\left( {V_i^t} \right) \oplus {F_2}\left( {V_i^{t - 1}} \right) \oplus \cdots \oplus {F_K}\left( {V_i^{t - K + 1}} \right) $$ (2)

      式中,Vit表示元胞<i>在时刻t的邻胞。相应地,全局转移函数能够由构形的集合定义:

      $$ \begin{array}{*{20}{c}} {\mathit{\Psi }:C \times C \cdots \times C \to C}\\ {{C^{t + 1}} = \mathit{\Psi }\left( {{C^t},{C^{t - 1}}, \cdots ,{C^{t - K + 1}}} \right) = }\\ {{\mathit{\Phi }_1}\left( {{C^t}} \right) \oplus {\mathit{\Phi }_2}\left( {{C^{t - 1}}} \right) \oplus \cdots {\mathit{\Phi }_K}\left( {{C^{t - K + 1}}} \right)} \end{array} $$ (3)

      式中,Φ1, Φ2ΦK是演化规则F1, F2FK对应全局转移函数。根据定义1和式(2),令Ct代表t时刻元胞的邻域内所有元胞的状态,构造出多规则高阶可逆元胞自动机。

      定义2  在元胞自动机中,称具有

      $$ \begin{array}{*{20}{c}} {{C^{t + 1}} = {\mathit{\Phi }_1}\left( {{C^t}} \right) \oplus {\mathit{\Phi }_2}\left( {{C^{t - 1}}} \right) \oplus \cdots \oplus }\\ {{\mathit{\Phi }_{K - 1}}\left( {{C^{t - K + 2}}} \right) \oplus {C^{t - K + 1}}} \end{array} $$ (4)

      形式局部转换函数的元胞自动机为多规则高阶可逆元胞自动机。

      其中,Φ1, Φ2ΦK-1分别为可逆元胞自动机的规则。式(4)对任意转换函数是可逆的,逆向CA的定义为:

      $$ \begin{array}{*{20}{c}} {{B^{t + 1}} = {\mathit{\Phi }_{K - 1}}\left( {{B^t}} \right) \oplus {\mathit{\Phi }_{K - 2}}\left( {{B^{t - 1}}} \right) \oplus \cdots }\\ { \oplus {\mathit{\Phi }_1}\left( {{B^{t - K + 2}}} \right) \oplus {B^{t - K + 1}}} \end{array} $$ (5)

      式中,Bi表示逆向RCA的构形。

      在进行逆向RCA演化时,逆序操作构形,即Bt-k+2=CtBt=Ct-K+2,通过推导由Bt+1恢复Ct-K+1的过程,验证该多规则高阶元胞自动机的可逆性。

      根据式(5)可以得到:

      $$ \begin{array}{*{20}{c}} {{B^{t + 1}} = {\mathit{\Phi }_{K - 1}}\left( {{B^t}} \right) \oplus {\mathit{\Phi }_{K - 2}}\left( {{B^{t - 1}}} \right) \oplus \cdots \oplus {\mathit{\Phi }_1}\left( {{B^{t - K + 2}}} \right) \oplus {B^{t - K + 1}} =\\ {\mathit{\Phi }_{K - 1}}\left( {{C^{t - K + 2}}} \right) \oplus {\mathit{\Phi }_{K - 2}}\left( {{C^{t - K + 3}}} \right) \oplus }\\ { \cdots \oplus {\mathit{\Phi }_1}\left( {{C^t}} \right) \oplus {C^{t + 1}} = {\mathit{\Phi }_1}\left( {{C^t}} \right) \oplus {\mathit{\Phi }_2}\left( {{C^{t - 1}}} \right) \oplus \cdots \oplus {\mathit{\Phi }_{K - 1}}\left( {{C^{t - K + 2}}} \right) \oplus {C^{t + 1}}} \end{array} $$ (6)

      根据可逆元胞自动机定义,式(6)中的Ct+1可使用式(4)代替并转换为:

      $$ \begin{array}{*{20}{c}} {{B^{t + 1}} = {\mathit{\Phi }_1}\left( {{C^t}} \right) \oplus {\mathit{\Phi }_2}\left( {{C^{t - 1}}} \right) \oplus \cdots \oplus {\mathit{\Phi }_{K - 1}}\left( {{C^{t - K + 2}}} \right){\mathit{\Phi }_1}\left( {{C^t}} \right) \oplus {\mathit{\Phi }_2}\left( {{C^{t - 1}}} \right) \oplus \cdots \oplus }\\ {{\mathit{\Phi }_{K - 1}}\left( {{C^{t - K + 2}}} \right) \oplus {B^{t - K + 1}} = \left[ {{\mathit{\Phi }_1}\left( {{C^t}} \right) \oplus {\mathit{\Phi }_1}\left( {{C^t}} \right)} \right] \oplus \left[ {{\mathit{\Phi }_2}\left( {{C^{t - 1}}} \right) \oplus {\mathit{\Phi }_2}\left( {{C^{t - 1}}} \right)} \right] \oplus \cdots \oplus }\\ {\left[ {{\mathit{\Phi }_{K - 1}}\left( {{C^{t - K + 2}}} \right) \oplus {\mathit{\Phi }_{K - 1}}\left( {{C^{t - K + 2}}} \right)} \right] \oplus {C^{t - K + 1}} = {C^{t - K + 1}}} \end{array} $$

      因此,式(5)定义的RCA可以从构形Ct+1, CtCt-K+2中恢复构形Ct-K+1。同理可推导出Ct-K+2Ct+1,故上述多规则高阶元胞自动机可逆。

    • 首先,本文将四叉树分解的4个子图像状态作为构形,根据高阶元胞自动机定义,则构造出的为4阶元胞自动机,其每个演化过程需要3个规则,多个过程需要多个规则。

      其次,借鉴文献[11]中的密钥产生方法,将非均衡元胞自动机的演化结果作为4阶元胞自动机规则,并将其规则由固定改为随机选择,以增强算法安全性。

      由于分割粒度越小加密结果越安全,本文分割的最小粒度为4×4像素。但是,也存在分割粒度越小计算量越大的问题,本文并未对所有子块进行连续分割,而是选取左上角子块进行继续分割,即降低了分割粒度,保证图像内容的安全性,又降低了加密过程的计算量。根据四叉树分解定义,四叉树深度取决于图像大小,对于一个L×L的方图,图像分解后的数量m等于log2(L-1)。图像每次演化所需的子密钥数是3log2(L-2)+1。

      需要说明的是,每幅地图加密前,都需要进行一次非均衡元胞自动机演化规则的随机选择,并记录所选择的演化规则及其顺序。这是因为在解密过程中,同样需要子密钥定义关于4阶RCA的演化规则。

      随机选择规则30、90、110和150作为非均衡元胞自动机的演化规则:

      1) 使用伪随机序列发生器随机产生128位密钥,记为CK0,作为非均衡元胞自动机的初始构形。

      2) 使用非均衡元胞自动机,按照规则30、90、110和150的顺序对CK0进行演化,演化结果记为CK1。把CK1当作第一个密钥K1,即演化规则Φ1

      3) 将规则30、90、110和150循环左移一次,即150、30、90和110,作为非均衡元胞自动机新的规则对构形CK1进行演化,演化结果记为CK2,当作第二个密钥K2,即Φ2

      4) 继续将规则循环左移,作为新的规则对步骤3产生的结果进行演化,产生Φ3以及新的密钥。重复此步骤,直到产生所有的密钥。

      作为密钥空间的组成部分,演化规则的随机选择和移位均扩大了传统单规则元胞自动机加密算法的密钥空间。

    • 加密过程中,使用分层分解方法处理图像的内容,除明文图像分解结果全部作为构形外,其余过程只选取4个子图像中的一块继续进行四叉树分解,每次分解结果作为构形。为便于计算,本文选取左上角子图像进行分解。

      1) 将明文图像按照四叉树分解策略分解成4个子图像,并将这4个子图像看作式(5)定义的4阶RCA的4个初始化构形C00C01C02C03

      2) 将2.1节中产生的密钥作为RCA的演化规则,按照4阶可逆元胞自动机演化规则,对初始化构形C00C01C02C03进行演化。

      3) 左上角产生的C04被递归分解为4个等大的子块,使用一个由密钥产生的新演化规则集合,为4阶RCA定义新的构形C10C11C12C13。并用新的RCA迭代产生新的构形C14C15C16C17替换子块C04

      4) 递归重复该过程,分离块Ci4的每一层i,直到最深的一层m,将块Cm4等分为4×4块。

      特别地,最后一层数据的大小等于16个字节(128)位,对应块Cm4与最后产生的子密钥进行异或操作。根据操作过程,该层需要3个演化规则(子密钥),所需要的全部子密钥等于3m+1。图 1表示了加密方法的流程。

      图  1  加密过程示意图

      Figure 1.  Descriptive Diagram of the Proposed Enciphering Scheme

      通过逆向执行加密过程,可从加密图像中恢复出明文图像。

    • 实验所用数据为3幅512×512像素、1幅1 024×1 024像素和1幅4 096×4 096像素的数字栅格地图(分别记为图像a、图像b、图像c、图像d和图像e)。算法通过C#语言和Matlab实现,实验配置为Intel(R)Core (TM)i5-CPU 3 GHz,8 GB内存。根据统计分布和熵测量准则等指标评估算法安全性,在密钥空间和算法速度方面与文献[12]基于混沌的图像加密算法、文献[13]基于初等可逆元胞自动机的图像加密算法、文献[14]基于二阶可逆元胞自动机的图像加密算法进行了比较。

    • 本小节通过验证加密图像的不确定性评估算法的安全性。图像信息熵越大,灰度分布越一致,算法扩散性越好,安全性越高,理想加密图像的信息熵理论最大值为8。图 2为图像abc明文图像及其密文图像。

      图  2  明文图像abc及其密文图像

      Figure 2.  Plain Text Image a, b, c and Their Encrypted Image

      分别测试明文图像和密文图像的信息熵,并随机选择了16个子图像数据块(分别记为s1s2s16进行仿真,所用参数与文献[11]相同。表 1给出了灰度图像a、图像b、图像c、图像d及图像e的香农熵结果。表 2给出了实验得到的3幅图像局部熵。

      表 1  图像abcde香农熵

      Table 1.  Shannon Entropy of Image a, b, c, d, e

      图像 大小 明文图像 密文图像
      a 512×512 7.098 1 7.996 9
      b 512×512 6.954 9 7.996 8
      c 512×512 6.157 4 7.997 2
      d 1 024×1 024 7.692 1 7.991 2
      e 4 096×4 096 7.487 0 7.989 4

      表 2  明文及密文图像局部信息熵

      Table 2.  Local Information Entropy of the Text and the Image

      数据块 图像a 图像b 图像c 图像d 图像e
      明文 密文 明文 密文 明文 密文 明文 密文 明文 密文
      s1 5.343 9 7.965 5 6.692 7 7.977 6 6.802 3 7.967 5 6.730 2 7.968 3 6.257 1 7.991 8
      s2 5.213 1 7.979 4 5.803 4 7.982 5 6.941 9 7.974 9 6.681 7 7.989 4 7.216 3 7.978 5
      s3 5.698 6 7.973 2 6.792 6 7.968 9 6.702 5 7.996 8 7.241 7 7.987 9 6.365 6 7.978 0
      s4 7.127 6 7.970 6 6.962 3 7.972 1 6.285 7 7.978 9 6.871 3 7.973 2 7.207 5 7.976 9
      s5 5.532 3 7.970 4 6.991 2 7.970 5 6.933 2 7.977 2 6.691 2 7.970 7 6.135 2 7.988 1
      s6 5.461 9 7.967 1 6.980 5 7.971 8 7.012 8 7.981 9 6.820 2 7.981 2 7.245 3 7.976 6
      s7 6.028 1 7.975 6 7.011 5 7.991 3 7.035 6 7.972 3 7.068 2 7.992 9 6.490 9 7.975 2
      s8 7.335 7 7.982 1 6.766 7 7.966 9 7.351 7 7.973 4 6.840 9 7.969 8 6.909 9 7.989 5
      s9 5.804 3 7.971 6 5.639 4 7.978 7 6.104 4 7.979 1 7.331 6 7.977 8 7.121 7 7.976 7
      s10 6.386 4 7.977 5 5.720 8 7.976 1 7.231 7 7.967 6 7.291 0 7.975 3 6.783 5 7.971 8
      s11 6.780 6 7.966 3 5.307 6 7.971 6 7.027 5 7.983 5 7.178 7 7.968 1 7.378 2 7.993 9
      s12 7.057 3 7.983 6 6.026 9 7.967 2 7.257 6 7.977 1 6.904 1 7.996 3 6.782 6 7.971 9
      s13 5.572 5 7.969 4 5.719 3 7.970 6 6.132 3 7.976 3 7.093 8 7.981 9 6.539 2 7.968 4
      s14 5.904 9 7.969 1 5.633 9 7.973 1 6.752 6 7.964 9 7.287 5 7.997 8 7.322 9 7.972 0
      s15 6.803 2 7.973 8 6.703 7 7.969 2 7.255 2 7.961 3 6.712 6 7.983 5 7.249 0 7.982 6
      s16 5.130 8 7.960 9 5.997 6 7.974 7 7.093 4 7.977 6 7.137 4 7.975 7 6.775 6 7.997 3

      从实验结果可知,每个密文图像的整体熵非常接近理论值8,每个局部熵在重要水平的差距为5%左右,在可接受范围内。这就证明了密文图像的局部熵和整体熵均满足要求。

    • 为评估本文方法对明文图像细微变化的敏感性,选择测试图像abcde,随机改变明文图像的一个bit,通过多轮加密对加密结果进行NPCR和UACI评估。其中,NPCR表示两幅不同像素所占百分比,UACI表示两图像之间差异的平均强度,以33%为标准理论值。图 3给出了不同加密次数的测试结果。

      图  3  加密次数与NPCR及UACI关系

      Figure 3.  Relation Ship Between the Number of Times of Encryption and NPCR and UACI

      图 3中的结果可以看出,针对不同的加密次数,图像abcde的NPCR值和UACI值结果均高于各自理论值99%和33%,说明基于四叉树分解的高阶元胞自动机加密方法对明文变化具有较高的敏感性,能够有效抵抗基于差分的明文攻击。表 3列出了本文算法和其他3种算法在相同半径r下密钥空间的对比。

      表 3  不同算法密钥空间对比

      Table 3.  Comparison of Key Spaces in Different Algorithms

      加密方法 r=1 r=2 r=3
      文献[12] 2 256 2 256 2 256
      文献[13] 28 232 2 128
      文献[14] 240 264 2 160
      本文算法 2 560 2 608 2 800

      相比于另外3种算法,多演化规则和规则移位的使用,以及元胞自动机阶数的增加使得密钥空间显著提升。阶数越高,与元胞自动机状态相关的邻胞数目越多,所占密钥空间就越多。

    • 根据NPCR和UACI分析,本文方法只需要进行一次加密就能达到与现有算法使用多次加密相同的敏感程度。因此,与现有相关算法相比,避免了大量循环计算过程,加密和解密速度有较大提升。其中,解密过程与加密过程的计算过程所涉及的计算方法相同,实验结果表明,解密时间与加密时间基本相同。表 4列出了本文算法和其他3种算法分别对5幅栅格地图的加密时间和解密时间对比。

      表 4  与不同算法加密和解密时间对比/ms

      Table 4.  Time Comparison of Encryption and Decryption with Different Algorithms/ms

      图像 加密和解密时间
      文献[12] 文献[13] 文献[14] 本文算法
      a 加密
      解密
      812.2
      809.4
      697.5
      694.2
      443.7
      447.6
      269.4
      243.2
      b 加密
      解密
      823.7
      822.9
      699.1
      698.7
      451.9
      449.0
      273.6
      271.8
      c 加密
      解密
      787.6
      786.1
      655.6
      656.3
      426.5
      423.3
      236.8
      236.4
      d 加密
      解密
      2 340.0
      2 215.2
      1 528.8
      1 528.8
      1 216.8
      1 263.6
      795.6
      748.8
      e 加密
      解密
      19 260.0
      19 244.4
      12 261.6
      11 902.8
      10 058.8
      10 018.4
      6 671.6
      6 422.0

      表 4中不同算法的加密时间可知,相对于文献[12]的算法,本文算法速度是其约3倍;相对于文献[13]和文献[14]中的算法,本文算法速度分别提高了约2倍、1.5倍。本文算法避免了反复的循环迭代过程,在加密阶段,每个四叉树分解的子图像只加密一次,避免对所有像素进行多次循环迭代加密的过程,省去了基于混合长度块分解和像素转换操作所需的时间。

    • 本文基于可逆元胞自动机和分层四叉树分解,提出了一种多演化规则的高阶可逆元胞自动机图像加密方法,通过演化规则和构形的构造,实现了栅格地图的加密。与普通元胞自动机图像加密方法相比,该方法通过提高元胞自动机阶数取代对所有像素进行多次循环迭代加密。实验结果表明了该算法具有较高的安全性,并在算法效率和计算复杂度之间取得了较好的平衡。

参考文献 (14)

目录

    /

    返回文章
    返回