Design of Dynamic S-Box Based on Perturbed Spatiotemporal Chaotic System

ZHAO Geng; MA Ying-jie; CHEN Lei; DONG You-heng; HOU Yan-li

doi:10.12263/DZXB.20210200

PDF(7020 KB)

ACTA ELECTRONICA SINICA ›› 2022, Vol. 50 ›› Issue (8) : 2037-2042. DOI: 10.12263/DZXB.20210200

CORRESPONDENCE

Design of Dynamic S-Box Based on Perturbed Spatiotemporal Chaotic System

Author information +

History +

HeighLight

The distribution of traditional spatiotemporal chaotic system is relatively concentrated, and the uniformity of its generating sequence is poor. In this paper, a new spatiotemporal chaotic system with perturbed one-way coupled map lattice is constructed based on elementary cellular automata. The numerical simulation results of the distribution diagram and phase diagram of the system show that the perturbed system can improve the uniformity of the original system and increase the dynamic complexity of the system. A dynamic S-box generation algorithm is designed based on the homogenized disturbed spatiotemporal chaotic system, and the dynamic S-box is generated according to the dynamic update strategy. The statistical analysis of nonlinearity, strict avalanche criterion and differential uniformity of the S-box generated by the algorithm is carried out. The results show that the dynamic S-box generated by the homogenized disturbed spatiotemporal chaotic system is more secure.

Key words

spatiotemporal chaos / elementary cellular automata / disturbance / dynamic S-box / safety analysis

Cite this article

EndNote

Ris (Procite)

Bibtex

Download Citations

ZHAO Geng , MA Ying-jie , CHEN Lei , DONG You-heng , HOU Yan-li. Design of Dynamic S-Box Based on Perturbed Spatiotemporal Chaotic System[J]. ACTA ELECTONICA SINICA, 2022, 50(8): 2037-2042. https://doi.org/10.12263/DZXB.20210200

1 引言

现代分组密码中，置换和替换网络是不可或缺的，如AES（Advanced Encryption Standard）算法.其中S盒作为分组密码中唯一的非线性部件，主要作用就是实现替换运算^［1］，构造动态S盒的方法有很多，利用混沌系统良好的伪随机性质来构造动态S盒已经成为构造S盒的一个重要方法^［2］.唐国坪等提出一种基于Logistic映射的两步构造S盒的方法，尽管这种设计方法很有效、实用，但还是存在着随机性和不可以测性不够强的缺点^［3，4］.陈果等用三维的Baker映射设计了一种S盒克服了这些缺点^［5］.王永^［6］等和Ozkaynak^［7］等分别提出了利用帐篷映射和连续时间的Lorenz混沌系统来构造S盒.佟晓筠提出了一种新的超混沌系统，并将其用于生成置换和替代图像像素的密钥流，使用动态S盒设计加密算法^［8］.闵乐泉设计了基于分段非线性鲁棒混沌映射的伪随机数发生器，提出了批量生成S盒的算法^［9］.Akram Belazi提出了一种基于正弦映射的S盒构造的有效方法^［10］.Majid Khan提出基于混沌布尔函数构造S盒，并将其用于图像加密^［11］.这些构造方法为得到抵抗差分密码分析和线性密码分析能力好的S盒提供了思路.朱虹宏等基于多混沌系统及复合思想，引入Arnold映射置乱算法构造了一种混沌S盒^［12］.Islam等构造了四维四翼超混沌系统，并以此设计了一种混沌S盒^［13］.然而上述方法所涉及到的混沌映射均在相空间或者回归映射中存在固定结构的吸引子，极易受到相空间重构^［14］或者回归映射分析^［15］的攻击，而且当混沌系统在有限精度的计算机中运行时会出现退化显现^［16］，出现周期现象，严重威胁到混沌密码系统的安全性.基于上述原因，Peizhao Zhou等人提出了一种基于PWLCM（Piece Wise Linear Chaotic Map）-sin映射的耦合映射格子的时空混沌系统^［17］，并用其生成了S盒，分析表明该系统生成的S盒具有良好的非线性，然而，每个格子生成的序列在回归映射中依然具有明显的固定帐篷形状，依然易受到回归映射分析攻击.王永^［18］等人为了解决时空混沌系统中存在的概率分布不均以及回归映射中形态结构固定的弱点，向基于分段Logistic映射的二维耦合映像格子模型添加了偏移量，使得结果更加均匀，然而该文仅仅对该系统的性能进行了分析并未涉及到模型的应用.

为了改进上述缺点，本文提出基于初等元胞自动机（Elementary Cellular Automata，ECA）的新型扰动单向耦合映像网络时空混沌系统，并进行了分布图、分岔图和相图的数值仿真，结果表明扰动系统能够改善原系统的均匀性，提高系统的动力学复杂性.采用均匀化的扰动时空混沌系统设计了动态S盒生成算法，并进行了非线性度、严格雪崩准则和差分均匀性的统计分析，结果表明均匀化扰动时空混沌系统产生的动态S盒具有更高的安全性.

2 基于初等元胞自动机扰动的时空混沌系统构造

2.1 单向耦合映像网络时空混沌系统及其数值仿真

单向耦合映像网络是一类时空混沌系统，具有易于产生、支持并行计算等优点，其定义为

x_{n + 1} (i) = (1 - ε) f (x_{n} (i)) + ε f (x_{n} (i + 1))

（1）

式中n=0，1，2，…和i=1，2，3，…，L分别代表时间维度（迭代次数）和空间维度（格点索引），x_n （i）表示在时刻n时，第i个格点的状态值，L表示格点的总数，ε（ε ∈ （0，1））代表耦合强度.该系统的边界条件可以表示为x_n （i－1）=x_n （L），底层映射ƒ为Logistic映射，即

f (x_{n} (i)) = u x_{n} (i) (1 - x_{n} (i))

（2）

当参数ε=0.625，u=4，L=100时，式（1）所示单向耦合映像网络的分布图如图1（a）所示，当参数ε=0.875，u=4，L=100时，单向耦合映像网络的分布图如图1（b）所示.从图1可以看出，参数ε的取值能够影响单向耦合映像网络时空混沌系统的分布情况，该系统存在均匀性较差的缺点.

图1 单向耦合映像网络的分布图

Full size|PPT slide

当参数u=4，改变参数ε的取值，式（1）所示系统的相图如图2所示.从图2可以看出，参数ε的取值能够影响单向耦合映像网络时空混沌系统的相图，该系统存在动力学特性不够复杂的缺点.

图2 相图u=4（ε=0.125, ε=0.625, ε=875）

Full size|PPT slide

2.2 初等元胞自动机

元胞自动机是由数学家Stanislaw M Ulam和John von Neumann于1948年提出的^{［19，20］}.初等元胞自动机是一种特殊的一维元胞自动机.初等元胞自动机的构成如图3所示.

图3 初等元胞自动机

Full size|PPT slide

图3中元胞C_n-₁和C_n+₁是元胞C_n 的邻居，其中C₁和C_L 互为邻居.在ECA中，每次迭代的当前元胞状态值由当前元胞和其邻居的前次状态值决定，如式（3）所示

S_{i}^{t + 1} = f (S_{i - 1}^{t}, S_{i}^{t}, S_{i + 1}^{t})

（3）

其中

S_{i}^{t}

代表了元胞C_i 在t时刻的状态值，t代表时间维度，即迭代次数，i代表空间维度，即元胞编号.此处f为布尔函数并由局部转换规则决定，其本质上是一个由集合｛000，001，010，011，…，111｝到集合｛0，1｝的映射.显然对于初等元胞自动机，共有256个转换规则.其中以第105号转换规则为例，其转换表如表1所示.

表1 第105号ECA转换规则

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

根据W Li等人的研究^［21］，具有不同转换规则的ECA，其在迭代过程中所表现出的动态特性也互不相同.任意一个具有全局混沌规则的ECA均能够用来构建本文所提出的时空混沌系统.这些全局混沌规则已在表2中给出.其中具有110号转换规则的ECA，我们简称为110号ECA，以此类推.

表2 全局混沌规则

Class	Rule number
Global chaotic	18（183）， 22（151）， 30（86， 135， 149）， 45（75， 89， 101）， 60（102， 153， 195）， 90（165）， 105， 106（120， 169， 225）， 129（126）， 137（110， 124， 193）， 146（182）， 150， 161（122）

为了进一步说明具有这些混沌规则的ECA在迭代过程中所表现的伪随机性.我们在图4中展示了60号，105号以及150号的迭代结果.

图4 全局混沌的ECA迭代结果

Full size|PPT slide

图4中黑色（白色）的方格代表本方格上的元胞其状态值为“1”（“0”），纵坐标代表迭代次数，由上至下递增，横坐标代表元胞索引.显然，三种ECA均显示出伪随机性.本文选择105号ECA用来构造时空混沌系统.

2.3 基于初等元胞自动机扰动的时空混沌系统构造及其数值仿真

针对式（1）所示传统单向耦合映像网络时空混沌系统存在均匀性较差以及动力学特性不够复杂的问题，本文基于初等元胞自动机构造了新型扰动单向耦合映像网络时空混沌系统，即

\begin{array}{l} x_{n + 1} (i) = [(1 - ε) f (x_{n} (i)) + ε f (x_{n} (i + 1)) \\ + 0.5 \times p (S^{n}) \times δ (s_{i}^{n})] m o d 1 \end{array}

（4）

式中，Sⁿ 为初等元胞自动机的迭代结果，S_iⁿ 为初等元胞自动机第i个元胞的迭代结果，其中

p (S^{n}) = \frac{b i n 2 d e c [S^{n} (b_{35} b_{36} \dots b_{66})]}{2^{32} - 1},

δ (s_{i}^{n}) = \{\begin{array}{l} 1, s_{i}^{n} = 1 \\ - 1, s_{i}^{n} = 0 \end{array}

当参数ε=0.625，u=4，L=100时，式（4）所示扰动时空混沌系统的分布图如图5（a）所示，当参数ε=0.875，u=4，L=100时，扰动时空混沌系统的分布图如图5（b）所示.

图5 扰动时空混沌系统的分布图

Full size|PPT slide

从图1、图5的对比可以看出，提出的基于初等元胞自动机构造的新型扰动单向耦合映像网络时空混沌系统均匀性明显优于传统时空混沌系统.

当参数u=4，改变参数ε的取值，式（4）所示系统的相图如图6所示.

图6 相图u=4（ε=0.125, ε=0.625, ε=0.875）

Full size|PPT slide

从图2、图6的对比可以看出，提出的基于初等元胞自动机构造的新型扰动单向耦合映像网络时空混沌系统的动力学复杂性明显优于传统时空混沌系统.

3 基于扰动时空混沌系统的动态S盒设计

3.1 扰动时空混沌系统产生序列

处理函数： M_seq =chaosGenFun（ K，n₀，n）

输入：密钥 K，输出长度n₀，n.

描述：①密钥 K 由8个长度相等的子密钥构成，可表示为（K（0），K（1），K（2），…，K（7））.②n₀为要舍去的混沌系统初始迭代次数，n是后续的迭代次数.

输出：扰动时空混沌序列 M_seq .

描述： M_seq 是一个矩阵，大小为n×8，生成的混沌序列中的元素以64位双精度浮点数型进行储存.

3.2 生成密钥流

处理函数：［ K_S ］=ksGenFun（ M_seq，n_ks）

输入： M_seq，输出长度n_ks.

描述：n_ks为后续步骤中所需密钥流的总长度.

输出：密钥流 K_S .

描述： K_S 是一个长度为n_ks的向量.

3.3 生成动态S盒

处理函数：［ S₁，S₂ ］=SboxGenFun（ K_S ）

输入： K_S .

描述： K_S 由上一个处理函数产生，要求其长度8n≥512+ n_ks.

输出：S盒 S₁， S₂ .

描述：双S盒 S₁， S₂ 均是大小为16×16的替换表，且满足双射条件.S盒和密钥流是由所生成 K_S 的不同部分构成.

（1）初始化S盒 S₁ 和 S₂ .按顺序赋值为0~255：

S_{1} = [\begin{array}{l} 0 1 \dots 15 \\ 16 17 \dots 31 \\ ⋮ ⋮ ⋮ ⋮ \\ 240 241 \dots 255 \end{array}]; S_{2} = S_{1}

（5）

（2）构造两个16×16的随机矩阵 R₁， R₂ .分别取 K_S 的256个元素，RV1= K_S （n_ks，n_ks+255），RV2= K_S （n_ks+256， n_ks+511），然后逐行将RV1和RV2分别转换为两个随机矩阵 R₁， R₂，大小为16×16.

（3）利用 R₁， R₂，对S盒 S₁ 和 S₂ 进行随机化处理.对 S₁， S₂ 的元素进行如下操作：

s w a p_{S_{1}} (R_{1} (i, j)) = \{\begin{array}{l} k = (R_{1} {(i, j))}_{M S B} \\ l = (R_{1} {(i, j))}_{L S B} \\ t m p = S_{1} (i, j) \\ S_{1} (i, j) = S_{1} (k, l) \\ S_{1} (k, l) = t m p \end{array}

（6）

其中，i，j=0，2，3，…，15代表 S₁ 中元素的索引，分别表示行和列.函数

{(x)}_{M S B}

和

{(x)}_{L S B}

分别代表取x的最高四位和最低四位.

s w a p_{S_{1}} (R_{1} (i, j))

的作用就是根据 R₁ （i，j）的值，得到与 S₁ 中位置（i，j）上的元素进行交换的元素索引（k，l），并将两元素进行交换.按顺序将 S₁ 中的所有元素即位置（1，1）至（16，16）按照式（6）进行交换乱序后得到随机化后的 S₁ 盒.具体过程如图7所示.同理，利用随机矩阵 R₂ 对 S₂ 盒进行上述乱序操作.

图7 构造S盒 S₁ 的示意图

Full size|PPT slide

4 动态S盒的安全性分析

4.1 非线性度

本文S盒的非线性度如表3所示，其平均值为105.75，略优于文献［4，11，12］的非线性度，说明该S盒抵抗线性分析的能力更强.

表3 S盒非线性度对比

S-box	Zhu^［11］		Liu^［12］		Chen^［4］		Our approach
NF	104	106	106	104	100	102	106	106
	108	106	100	106	103	104	104	106
	106	106	102	100	106	106	106	106
	100	108	106	108	106	108	104	108
Average	105.5		104		104.375		105.75

4.2 严格雪崩准则

严格雪崩准则是指若某个输入比特发生改变，那么对应的输出比特发生改变的概率为1/2.通过计算，该S盒的数据如表4所示.

表4 S盒严格雪崩准则对比

S-box	Ave-SAC	Difference with 0.500 0
Our approach	0.502 5	0.002 5
Zhu^［11］	0.497 2	0.002 8
Liu^［12］	0.507 8	0.007 8
Chen^［4］	0.498 9	0.001 1

表4中列出了平均值与理论值0.5的差距.根据表4可以得出，由本文算法得出的S盒仅与理论值0.5相差0.002 5，优于文献［11］和文献［12］，仅次于文献［4］提出的算法，可见该S盒能较好满足严格雪崩准则.

4.3 差分均匀性

通过计算可以得出本文S盒的差分均匀度与其他文献的S盒的差分均匀度的对比如表5所示，根据表5可以看出本文S盒的差分均匀度为10与文献［12］的相同，同样优于另外两个文献的数据.由此说明本文S盒针对差分线性分析的抵抗能力较强.

表5 S盒差分均匀性对比

S-box	Zhu^［11］	Liu^［12］	Chen^［4］	Our approach
Max-DP	11	10	12	10

4 总结

本文基于初等元胞自动机构造了新型扰动单向耦合映像网络时空混沌系统，并进行了分布图、分岔图和相图的数值仿真，结果表明扰动系统能够改善原系统的均匀性，提高系统的动力学复杂性.采用均匀化的扰动时空混沌系统设计了动态S盒生成算法，并进行了非线性度、严格雪崩准则和差分均匀性的统计分析，结果表明均匀化扰动时空混沌系统产生的动态S盒具有更高的安全性.故本文方案可产生大量性能优秀的S盒，在分组密码设计等方面拥有良好的应用前景.

References

Publishing order | Descend order by publishing year | Descend order by cited within

1	LIC, ZHANGY, XIEE Y. When an attacker meets a cipher-image in 2018: A year in review[J]. Journal of Information Security and Applications, 2019, 48: 102361. Cited in this article [1]

2	臧鸿雁, 黄慧芳. 基于均匀化混沌系统生成S盒的算法研究[J]. 电子与信息学报, 2017, 39(3): 575‐581. ZANGHong-yan, HUANGHui-fang. Research on the algorithm of generating S-box based on homogenization chaotic system[J]. Journal of Electronics & Information Technology, 2017, 39(3): 575‐581. (in Chinese) Cited in this article [1]

3	TANGG P, LIAOX F, CHENY. A novel method for designing S-boxes based on chaotic maps[J]. Chaos, Solitons and Fractals, 2005(23): 413‐419. Cited in this article [1]

4	唐国坪. 混沌分组密码及其应用研究[D]. 重庆: 重庆大学, 2005. TANGGuo-ping. Chaotic Block Cipher and Its Application Research[D]. Chongqing: Chongqing University, 2005. (in Chinese) Cited in this article [6]

5	CHENG, CHENY, LIAOX F. An extended method for obtaining S-boxes based on three-dimensional chaotic Baker maps[J]. Chaos, Solitons and Fractals, 2017, (31): 571‐579. Cited in this article [1]

6	WANGY, WONGK W, LIAOX, et al. A block cipher with dynamic S-boxes based on tent map[J]. Communications in Nonlinear Science and Numerical Simulation, 2009, 14(7): 3089‐3099. Cited in this article [1]

7	FatihÖzkaynaka, Ahmet Bedri Özerb. A method for designing strong S-Boxes based on chaotic Lorenz system[J]. Physics Letters A, 2010 (374): 3733‐3738. Cited in this article [1]

8	LIUYang, TONGXiaojun, MAJing. Image encryption algorithm based on hyper-chaotic system and dynamic S-box[J]. Multimedia Tools and Applications, 2016, 75(13): 7739‐7759. Cited in this article [1]

9	韩丹丹, 闵乐泉, 赵耿, 张丽姣, 闫世杰. 一维鲁棒混沌映射及S盒的设计[J]. 电子学报, 2015, 43(9): 1770‐1775. HANDan-dan, MINLe-quan, ZHAOGeng, ZHANGLi-jiao, YANShi-jie. One-dimensional robust chaotic mapping and the design of S-box[J]. Acta Electronica Sinica, 2015, 43(9): 1770‐1775. (in Chinese) Cited in this article [1]

10	AkramBelazi, A Abd El-LatifAhmed. A simple yet efficient S-box method based on chaotic sine map[J]. Optik, 2017, 130: 1438‐1444. Cited in this article [1]

11	MajidKhan, TariqShah, Syeda Iram Batool. Construction of S-box based on chaotic boolean functions and its application in image encryption[J]. Neural Computing and Applications, 2016, 27(3): 677‐685. Cited in this article [6]

12	朱虹宏, 佟晓筠, 张淼, 等. 基于动态复合混沌系统的S盒设计[J]. 南京大学学报(自然科学), 2018, 54 (240): 61‐65. ZHUHong-hong, TONGXiao-jun, ZHANGMiao, et al. S-box design based on dynamic compound chaotic system[J]. Journal of Nanjing University(Natural Sciences), 2018, 54 (240): 61‐65. (in Chinese) Cited in this article [7]

13	ISLAMF U, LIUG J. Designing S-Box based on 4D-4wing hyperchaotic system[J]. 3D Research, 2017, 8(1): 1‐9. Cited in this article [1]

14	ZHANGA, XUZ. Chaotic time series prediction using phase space reconstruction based conceptor network[J]. Cognitive Neurodynamics, 2020, 14(6): 849‐857. Cited in this article [1]

15	PENGY, SUNK, HES. An improved return maps method for parameter estimation of chaotic systems[J]. International Journal of Bifurcation and Chaos, 2020, 30(4):2050058 Cited in this article [1]

16	LIS J, CHENG R, MOUX Q. On the dynamical degradation of digital piecewise linear chaotic maps[J]. International Journal of Bifurcation and Chaos, 2005, 15(10): 3119‐3151. Cited in this article [1]

17	ZHOUP, DUJ, ZHOUK, et al. 2D mixed pseudo-random coupling PS map lattice and its application in S-box generation[J]. Nonlinear Dynamics, 2021, 103(1): 1151‐1166. Cited in this article [1]

王永, 赵毅, Gao

Jerry

, 等. 基于分段Logistic映射的二维耦合映像格子模型的密码学相关特性分析[J]. 电子学报, 2019, 47(3): 657‐663.

WANG

Yong

, ZHAO

, GAO

Jerry

, et al. Analysis of cryptographic characteristics of two-dimensional coupled map lattice model based on piecewise Logistic mapping[J]. Acta Electronica Sinica, 2019, 47(3): 657‐663. (in Chinese)

Cited in this article [1]

19	NEUMANNJ, BurksA W, Theory of self-reproducing automata[J]. Mathematics of Computation, 1967, 21(100): 745. Cited in this article [1]

20	WolframStephen. Cellular automata as models of complexity[J]. Nature, 1984, 311(5985): 419‐424. Cited in this article [1]

21	LIW, PACKARDN. The Structure of the elementary cellular automata rule space[J]. Complex Systems, 1990, 4(3): 281‐297. Cited in this article [1]

Funding

National Natural Science Foundation of China(61772047)

Advanced Discipline Construction Project of Universities in Beijing Municipality(3201017)

PDF(7020 KB)

1529

Accesses

Citation

Detail

Sections

Recommended

HeighLight
Key words
Cite this article
1 引言
2 基于初等元胞自动机扰动的时空混沌系统构造
2.1 单向耦合映像网络时空混沌系统及其数值仿真
图1 单向耦合映像网络的分布图
图2 相图u=4（ε=0.125, ε=0.625, ε=875）
2.2 初等元胞自动机
图3 初等元胞自动机
表1 第105号ECA转换规则
表2 全局混沌规则
图4 全局混沌的ECA迭代结果
2.3 基于初等元胞自动机扰动的时空混沌系统构造及其数值仿真
图5 扰动时空混沌系统的分布图
图6 相图u=4（ε=0.125, ε=0.625, ε=0.875）
3 基于扰动时空混沌系统的动态S盒设计
3.1 扰动时空混沌系统产生序列
3.2 生成密钥流
3.3 生成动态S盒
图7 构造S盒 S1 的示意图
4 动态S盒的安全性分析
4.1 非线性度
表3 S盒非线性度对比
4.2 严格雪崩准则
表4 S盒严格雪崩准则对比
4.3 差分均匀性
表5 S盒差分均匀性对比
4 总结
References
Funding

Received	Revised	Published
2021-02-02	2021-06-17	2022-08-25
Online First Date	Issue Date
2022-03-08	2022-09-08

Please choose a citation manager

Content to export