基于均匀化混沌系统生成S盒的算法研究

臧鸿雁 黄慧芳



基于均匀化混沌系统生成S盒的算法研究

臧鸿雁①黄慧芳*②

①(北京科技大学数理学院 北京 100083)②(厦门大学嘉庚学院信息科学与技术学院 漳州 363105)

该文给出了一个新的二次多项式混沌系统，并利用系统与Tent映射拓扑共轭的性质，给出了系统的概率密度函数，基于概率密度的形式，进一步设计了一个变换函数，实现了系统的均匀化。针对均匀化前后的混沌系统构造了S盒生成算法，对该算法产生的300个S盒进行差分概率(DP)和线性概率(LP)的统计分析，结果表明均匀化后混沌系统产生的S盒的DP和LP略优于均匀化前的值。

混沌系统；均匀化；拓扑共轭；S盒

1 引言

1975年，Li等人[1]发表了著名的“周期三蕴含混沌”一文，首次用数学定义描述了“混沌”一词。通过研究混沌系统的复杂非线性动力学现象能够发现其具有伪随机性、遍历性和初值敏感性等特性。自1989年，Matthews[2]提出“混沌密码”后，人们对混沌系统及其应用的了解越来越深入。密码学家分析得出一个好的密码系统本质上也是一个混沌系统的结论[3]。这一发现挖掘了混沌在密码学领域内的应用潜力，自20世纪80年代以来该领域成为了日益热门的研究方向[4]。

混沌系统具有各态历经的特性，利用混沌映射的概率密度可以描述系统长期的统计特征。文献[5]通过证明Logistic映射与Tent映射的拓扑共轭关系以及Chebyshev映射与Tent映射的拓扑共轭关系，推出了Logistic映射和Chebyshev映射的概率密度。通过混沌映射的概率密度函数可以发现大部分混沌序列不服从均匀分布。2011年，文献[6]中给出了一个将Logistic混沌序列转化为服从均匀分布的随机序列生成方法。

S盒是多数分组密码中的唯一非线性部件，设计具有良好性能的S盒是分组密码算法设计的关键要素之一。一个S盒本质上可以看作映射，或者可以写作：，它是将位输入映射到位输出的非线性映射。构造动态S盒的方法有很多[7]，利用混沌系统良好的伪随机性质来构造动态S盒已经成为构造S盒的一个重要方法[8]。

本文利用文献[9]提出的一般二次多项式映射存在3-周期点的充分必要条件构造了一个新的二次多项式混沌系统，并依据该系统与Tent映射拓扑共轭的性质，给出了系统的概率密度函数，在此概率密度的基础上对该系统进行了均匀化处理；分别利用均匀化前后的混沌系统设计了动态S盒生成算法，对算法生成的300个S盒的性能指标进行统计分析，发现利用均匀化后系统能够产生性能更好的S盒。

本文其余部分安排如下：在第2节中提出了一个新的混沌系统，并基于概率密度函数对系统进行了均匀化处理。在第3节中，对均匀化前后的混沌系统进行了统计直方图和熵的对比分析。第4节中设计了一个动态S盒的生成方法，利用均匀化前后的混沌系统分别产生了300个S盒，并进行了S盒性能的对比。第5节总结全文。

2 二次多项式混沌系统的均匀化处理

文献[9]提出了一般非线性二次多项式的3-周期点的等价命题。

引理1[9]二次多项式有实的3-周期点的充分必要条件是。

定义1[10]设和为两个映射，如果存在一个可逆映射，使得成立，则称和是拓扑共轭的。此处表示两个映射的复合。

拓扑共轭是动力系统中的重要理论。如果两个系统满足拓扑共轭关系，则它们具有相同的动力行为。

基于引理1，本文构造了新的1维混沌系统为

将系统表示为

(2)

定理1 混沌系统

与Tent映射是拓扑共轭的。

令Tent映射

和连续可逆函数

(5)

定理2 混沌系统

的概率密度函数为

(7)

(8)

由系统式(1)的概率密度函数可知，该二次多项式混沌系统产生的序列不是均匀分布的，意味着其产生的混沌序列容易具有明显的统计特性，不利于推广应用。为了使其服从均匀分布，以下对式(1)进行均匀化处理。

则随机变量为

(10)

(12)

以上是利用原混沌系统的概率密度函数对其进行均匀化处理的方法。由证明过程可知，在文中给定区间内，均匀分布的随机变量与原随机变量满足一一对应关系，因为是式(1)混沌系统的变量，从而系统

必是混沌系统，并且与式(1)系统有着相同的Lyapunov指数。

3 二次多项式混沌系统的熵分析

以下针对均匀化前混沌系统式(1)和均匀化后系统式(13)产生的序列从直方图统计、信息熵和离散熵等方面进行了分析，验证均匀化方法的有效性。

3.1 统计分析

图1(a)是均匀化前混沌系统生成的序列的统计直方图，图1(b)是均匀化后反三角函数生成的序列的统计直方图。由对比图可见，处理后的混沌序列均匀性明显增强。

3.2 信息熵分析

信息熵是信息论中用以度量信源不确定性程度的概念，最早由香农提出。以下是本文中均匀化前后系统产生的混沌序列的信息熵检测。令离散混沌序列长度为，将式(13)迭代得到的离散混沌序列，将序列值域等分成个区间，统计落在每个区间内的值的个数，记为。计算每个区间的统计概率，有。根据最大信息熵原理，信息熵最大值为，其中表示统计区间个数，对应通信系统中的信源符号数。下面选定序列长度，分别测试时均匀化前后序列的信息熵与最大熵，比较结果如表1。

表1 均匀化前后混沌序列的信息熵对比

3.3 离散熵分析

2007年Amigo等人[11]基于排列熵(PE)定义，提出了有限集合上的离散熵(DE)的概念，可替代拓扑熵衡量系统的混沌程度。该定义为

从图2(a)、图2(c)、图2(e)中式(1)系统的熵和离散熵图像可以看出，系统离散熵近似于熵偏移固定长度后的图像，这也从某种程度说明，离散熵能够有效衡量系统的混沌程度；图2(b)、图2(d)、图2(f)显示均匀化前后系统的离散熵完全相同，图2表明，经过本文中的均匀化方法处理之后，混沌系统的混沌特性不会被破坏，同时均匀性得到了有效的改善。

4 基于均匀化混沌系统构造S盒

本文分别利用均匀化前后的两个混沌系统式(1)和式(13)设计动态S盒生成算法，并对两组S盒进行统计分析和性能检测。具体的算法和分析结果如下。

图1 统计直方图

图2 均匀化前后系统K熵与离散熵分析对比图

4.1 S盒算法构造

(4)从前往后依次取位置序列中不相等的256个变量作为最终的S盒序列。

在保持算法中参数一致的情况下，将步骤(2)中产生置乱效果的混沌系统分别用均匀化前的式(1)系统和均匀化后的式(13)系统替换，基于不同的初始值动态生成S盒序列。

检测生成的300个混沌S盒的差分概率(DP)和线性概率(LP)，并统计各个指标值对应的S盒的个数，作直方图如下，其中图3为利用均匀化前混沌系统生成的S盒的统计。图4为利用均匀化后混沌系统生成的S盒的统计。

差分概率(DP)用以度量S盒抵抗差分密码攻击的能力，DP越小，S盒越能够抵抗差分攻击。而线性概率(LP)用来度量S盒对于线性密码攻击的抵抗能力，LP越小，抵抗能力越强。从两个图的对比中可以看出，基于均匀化后混沌系统生成的DP, LP指标值较好的S盒数量相对更多，进一步说明本文提出的均匀化方法可以有效地改善混沌系统的均匀性，并保持良好的混沌特性。

4.2 S盒性能分析

下面从均匀化后的混沌系统构造生成的S盒中选取出一个DP, LP指标值良好的进行其他密码学性能分析，并且与近两年内发表的文献中构造的混沌S盒进行对比，检验本文构造生成的S盒是否适用于分组密码算法设计中。

表2为选取的均匀化后混沌系统生成的S盒序列。对该S盒的双射特性，非线性度，严格雪崩准则，输出比特间独立性，差分概率，线性概率和Lyapunov指数等指标依次进行分析。

图3 均匀化前系统生成S盒数

图4 均匀化后系统生成S盒数

表2 均匀化混沌系统式(13)生成的S盒序列

对双射特性进行检测，S盒8个分量布尔函数的线性运算之和都为128，充分满足双射特性。

检测S盒的严格雪崩准则和输出比特独立性时，直接看相关矩阵对比可能不能直观看出差距。为了比较满足严格雪崩效应的程度，利用公式估计了相关矩阵与理论值0.5的偏移量，将第1个相关矩阵的偏移量记为，第2个相关矩阵与0.5理论值的偏移量记为。本文构造的S盒与现有S盒的两个偏移量的比较如表3所示。我们希望S盒的相关矩阵元素与理论值越接近越好，也就是偏移量越小越好。从表3的对比结果可见，本文S盒较好地满足严格雪崩准则和输出比特间独立性。

表3 S盒的对比

表3 S盒的对比

S盒 均匀化后系统生成的S盒0.033453130.01692857 文献[12]中的S盒0.060421870.01771428 文献[13]中的S盒0.039156250.01664286 文献[14]中的S盒0.034718750.01546429

利用文献[15]中提出的S盒的Lyapunov指数定义，映射的离散Lyapunov指数揭示的是双射映射中自变量改变1 bit时，状态值变化位数的情况[15]。因而 Lyapunov指数越大，说明自变量改变引起的函数值变化越大，混乱程度越高。本文构造S盒的DP, LP及其Lyapunov指数结果与文献中结果的对比见表4。

表4 S盒的指数对比

表4 S盒的指数对比

S盒DPLP 均匀化后系统生成的S盒0.039062500.054931641.79624435 文献[12]中的S盒0.062500000.129150391.60528688 文献[13]中的S盒0.039062500.054931641.76551996 文献[14]中的S盒0.039062500.062500001.82665493

5 结论

本文提出了一个新的二次多项式混沌系统，利用拓扑共轭理论给出了系统的概率密度函数，进一步提出一个变换函数对系统进行了均匀化处理。为了验证均匀化方法的效果，对均匀化前后系统生成的混沌序列进行了直方图统计、信息熵分析和离散熵分析。分析结果表明了均匀化方法的有效性。本文基于混沌系统设计了一个新的构造S盒的算法，利用均匀化前后的混沌系统分别生成两组各300个S盒并对其DP, LP指标进行统计分析。通过差分及线性攻击的分析对比可见，本文均匀化方法处理的混沌系统能够产生密码性更好的S盒。这些S盒可以为进一步设计分组密码算法提供良好的非线性资源。

[1] LI Tienyien and YORKE J A. Period three implies chaos[J]., 1975(82): 985-992.

[2] MATTHEWS R. On the serivation of a “chaotic” encryption algorithm[J]., 1989, 13(1): 29-42.

[3] GOTZ M, KELBER K, and SCHWARZ W. Discrete-time chaotic coders for information encryption--Part 1: Systematic structural design[C]. Workshop on Nonlinear Dynamics of Electronic Systems, Moscow, Russia, 1997: 21-26.

[4] KOCAREV L, JAKIMOSKI G, STOJANOVSKI T,. From chaotic maps to encryption schemes[C]. IEEE International Symposium on Circuits, & Systems. Monterey, USA, 1998: 514-517.

[5] 何振亚, 李克, 杨绿溪. 具有良好安全性能的混沌映射二进制序列[J]. 电子与科学学刊, 1999, 21(5): 646-651.

HE Zhenya, LI Ke, and YANG Luxi. Chaotic Map Binary Sequences with Good Security[J]., 1999, 21(5): 646-651.

[6] 曹光辉, 胡凯, 佟维. 基于Logistic均匀分布图像置乱方法[J]. 物理学报, 2011, 60(11): 125-132.

CAO Guanghui, HU Kai, and TONG Wei. Image scrambling based on logistic uniform distribution[J]., 2011, 60(11): 125-132.

[7] TERRY R. Substitution cipher with pseudo-random shuffling: The dynamic substitution combiner[J]., 1990, 14(4): 289-303.

[8] WONG K W, HO S W, and YUNG C K. A chaotic cryptography scheme for generating short cipher text[J]., 2003, 310(1): 67-73.

[9] 周海玲, 宋恩彬. 二次多项式映射的3-周期点判定[J]. 四川大学学报(自然科学版), 2009, 46(3): 561-564. doi: 103969/j. issn. 0490-6756.2009.03-009.

ZHOU H L and SONG E B. Discrimination of the 3-periodic points of a quadratic polynomial[J].(), 2009, 46(3): 561-564. doi: 103969/j.issn.0490-6756.2009.03-009.

[10] 郝柏林. 从抛物线谈起--混沌动力学引论[M]. 第2版, 北京: 北京大学出版社, 2013, 114-118.

HAO B L. Starting with Parabola: An Introduction to Chaotic Dynamics[M]. 2nd Edition, Beijing: Peking University Press, 2013, 114-118.

[11] AMIGO J M, KOCAREV L, and TOMOVSKI I. Discrete entropy[J]., 2007, 228(1): 77-85.

[12] KHAN M, SHAH T, and BATOOL S I. Construction of S-box based on chaotic Boolean functions and its application in image encryption[J].&, 2016, 27(3): 677-685.

[13] 韩丹丹, 闵乐泉, 赵耿, 等. 一维鲁棒混沌映射及S盒的设计[J]. 电子学报, 2015, 43(9): 1770-1775. doi: 10.3969/j.issn. 0372-2112.2015.09.014.

HAN D, MIN L, ZHAO G,. One-dimensional robust chaotic map and the construction of S-box[J]., 2015, 43(9): 1770-1775. doi: 10.3969/j. issn.0372-2112.2015.09.014.

[14] LIU G, YANG W, LIU W,. Designing S-boxes based on 3-D four-wing autonomous chaotic system[J]., 2015, 82(4): 1867-1877. doi: 10.1007/s11071-015- 2283-y.

[15] 臧鸿雁, 范修斌, 闵乐泉, 等. S-盒的 Lyapunov 指数研究[J]. 物理学报, 2012, 61(20): 200508.

ZANG H, FAN X, MIN L,. Research of Lyapunov exponent of S-boxes[J]., 2012, 61(20): 200508.

Research on Algorithm of Generating S-box Based on Uniform Chaotic System

ZANG Hongyan①HUANG Huifang②

①(,,100083,)②(,,363105,)

A new quadratic polynomial chaotic system is given and homogenized based on its probability density function. Then, based on the chaotic systems before and after homogenization, an S-box generation algorithm is constructed. By numerical simulation, the algorithm dynamically generates 300 S-boxes and then analyses their Differential Probability (DP) and Linear Probability (LP). The statistical results show that the uniform chaotic system can produce better performance of S-boxes.

Chaotic system; Homogenization; Topological conjugation; S-box

TN918. 1

A

1009-5896(2017)03-0575-07

10.11999/JEIT160535

2016-05-26；改回日期：2016-10-27；

2016-12-20

黄慧芳 13661363592@163.com

国家自然科学基金(61170037)

The National Natural Science Foundation of China (61170037)

臧鸿雁： 女，1973年生，副教授，研究方向为非线性系统同步理论与混沌密码学.

黄慧芳： 女，1991年生，助教，研究方向为混沌密码学.