可逆元胞自动机加密技术研究

doi:1000-436X(2008)05-0026-08

摘要/Abstract

摘要：

利用可逆元胞自动机无信息损失和高度并行处理的特点，提出了一种新的基于可逆二阶触发元胞自动机的分组加密算法。该算法没有取整个规则空间为密钥空间，而是通过引入规则表的λ参数，对原本庞大的规则空间进行了划分，证明了满足λ=0.5 的一类规则适合用于加密。经分析表明，与一般不可逆触发元胞自动机加密技术相比，这种可逆触发元胞自动机加密技术不仅提高了加密速度，而且增加了密钥空间，具有良好的抵抗蛮力攻击和差分分析的能力。

关键词: 密码学, 二阶元胞自动机, 触发规则

Abstract:

The reversible cellular automata is featured by its no information loss and parallel information processing.A new block cipher based on reversible second-order toggle cellular automata was proposed.Instead of using the whole rules space as the keys space,the new algorithm introduces a parameter λ to partition the rules space and proves that rules with λ=0.5 are becoming to encrypt.Compared with the general irreversible toggle cellular automata cryptosystem,the proposed method greatly improves the speed of encryption and has large keys space,it can resist bruce attack and differential cryptanalysis.

Key words: cryptography, second-order cellular automata, toggle rule

平萍,周曜,张宏,刘凤玉. 可逆元胞自动机加密技术研究[J]. 通信学报, 2008, 29(5): 26-33.

Ping PING,Yao ZHOU,Hong ZHANG,Feng-yu LIU. Encryption based on reversible cellular automata[J]. Journal on Communications, 2008, 29(5): 26-33.

图/表 13

表1

图1

图2

图3

表2

2-TCA规则真值表"

$s_{i - 1}^{t}, s_{i}^{t}, s_{i + 1}^{t}$	$s_{i}^{t + 1}$
$s_{i - 1}^{t}, s_{i}^{t}, s_{i + 1}^{t}$	$s_{i}^{t - 1} = 0$	$s_{i}^{t - 1} = 1$
000	1	0
001	1	0
010	0	1
011	1	0
100	0	1
101	1	0
110	0	1
111	0	1

表2

表3

表4

表5

表6

表7

表8

图4

图5

参考文献 9

[1]	WOLFRAM S . A New Kind of Science[M]. Champaign,IL: Wolfram MediaPress, 2002.
[2]	WOLFRAM S . Cryptography with cellular automata[A]. Advances in Cryptology-CRYPTO’85:Proceedings,LNCS,218[C]. Berlin: Springer-Verlag, 1986. 429-432.
[3]	SIPPER M , TOMASSINI M . Generating parallel random number generators by cellular programming[J]. International Journal of Modern Physics C, 1996,7(2): 181-190.
[4]	ZHAO X L , LI Q M , XU M W ,et al. A synmmetric cryptography based on extended cellular automata[A]. IEEE-SMC2005[C]. Hawaii,USA, 2005.
[5]	GUAN P . Cellular automata public-key cryptosystems[J]. Complex System, 1987,1: 51-57.
[6]	MIHALJEVIC M , ZHENG Y , IMAI H . A family of fast dedicated one-way hash functions based on linear cellular automata over GF(q)[J]. IEICE Transactions on Fundamentals, 1999,E82-A(1): 40-47.
[7]	张传武, 沈野樵, 彭启琮 . 细胞自动机反向迭代加密技术研究[J]. 计算机学报, 2004,27(1): 125-129. ZHANG C W , SHEN Y Q , PEN Q C . Encryption based on cellular automata inverse iteration[J]. Chinese Journal of Computers, 2004,27(1): 125-129.
[8]	GUTOWITZ H . Method and Apparatus for Encryption,Decryption and Authentication Using Dynamical Systems[P]. USA:5365589, 1994.
[9]	祝玉学, 赵学龙 . 物理系统的元胞自动机模拟[M]. 北京: 清华大学出版社, 2003. ZHU Y X , ZHAO X L . Cellular Automata Modeling of Physical Systems[M]. Beijing: Tsinghua University Press Press, 2003.

符号	ASCII码	二进制编码
a	97	01100001
c	99	01100011
e	101	01100101
l	108	01101100
r	114	01110010
u	117	01110101

规则45/210	加密过程

迭代次数1
2
3
4
5
6
7
8
9
左右交换

规则45/210	加密过程

迭代次数1
2
3
4
5
6
7
8
9
左右交换

密码系统	r=1	r=2	r=3	r=4
TCA的密钥空间	32	1.31×10⁵	3.69×10¹⁹	2.32×10⁷⁷
2-TCA的密钥空间	70	6.01×10⁸	2.4×10³⁷	4.73×10¹⁵²

[1]	田有亮, 蒋小霞. 通用可组合框架下的公平理性委托计算[J]. 通信学报, 2021, 42(9): 106-119.
[2]	田苗苗, 陈静, 仲红. 格上基于身份的增量签名方案[J]. 通信学报, 2021, 42(1): 108-117.
[3]	于斌, 黄海, 刘志伟, 赵石磊, 那宁. 面向多椭圆曲线的高速标量乘法器设计与实现[J]. 通信学报, 2020, 41(12): 100-109.
[4]	杜蛟,刘春红,庞善起. 4t-1元旋转对称2-弹性函数的构造[J]. 通信学报, 2020, 41(11): 169-175.
[5]	田苗苗,高闯,陈洁. 格上基于身份的云存储完整性检测方案[J]. 通信学报, 2019, 40(4): 128-139.
[6]	严新成,陈越,贾洪勇,陈彦如,张馨月. 支持高效密文密钥同步演化的安全数据共享方案[J]. 通信学报, 2018, 39(5): 123-133.
[7]	王真,马兆丰,罗守山. 基于身份的移动互联网高效认证密钥协商协议[J]. 通信学报, 2017, 38(8): 19-27.
[8]	杜蛟,尚玉婧,赵金玲,董乐,张恩. 8元多输出旋转对称弹性函数的构造与计数[J]. 通信学报, 2017, 38(7): 47-55.
[9]	汤永利,胡明星,刘琨,叶青,闫玺玺. 新的格上基于身份的全同态加密方案[J]. 通信学报, 2017, 38(5): 39-47.
[10]	袁峰,江继军,杨旸,许盛伟. 与3类向量值密码函数仿射等价的函数数量研究[J]. 通信学报, 2017, 38(11): 84-92.
[11]	杜红珍,温巧燕. 无证书强指定验证者多重签名[J]. 通信学报, 2016, 37(6): 20-28.
[12]	田叶,张玉清,胡予濮,伍高飞. 一类布尔函数的代数免疫度的下界[J]. 通信学报, 2016, 37(10): 92-98.
[13]	伍高飞，刘雪峰，田叶，张玉清. 对称布尔函数的扩展代数免疫度[J]. 通信学报, 2014, 35(Z2): 24-183.
[14]	伍高飞,刘雪峰,田叶,张玉清. 对称布尔函数的扩展代数免疫度[J]. 通信学报, 2014, 35(Z2): 179-183.
[15]	梁鹏，沈昌祥，宁振虎. 云计算下可信虚拟群体内访问控制研究[J]. 通信学报, 2013, 34(Z1): 27-215.