基于Logistic混沌序列的灰度图像加密算法

发表于 | 分类于 | 阅读数

写本篇文章的目的在于初步了解混沌密码体系的思想

参考

什么是混沌理论？
42思维模型：混沌理论一20世纪最伟大的三项理论之一
图像加密技术综述(李昌刚 韩正之 张浩然)
Theory and practice of chaotic cryptography
混沌密码学-百度百科
混沌系统在密码学中的应用现状及展望(刘金梅-丘水生)
混沌理论及其在密码学的应用(邓绍江-李传东)
混沌理论在密码学中的应用
Logistic map
基于Logistic混沌序列的灰度图像加密算法(燕善俊-余昭平)

混沌理论

简单了解一下混沌理论
“万物皆混沌”，混沌尤其是指非线性系统表现出的一种非常复杂的、无法根据给定的初始条件确定系统将来状态的类似行为
混沌理论是对不规则而又无法预测的现象及其过程的分析，一个混沌过程是确定的，虽然看上去无序、随机，所以混沌与完全随机不同

因此混沌是指发生在确定性系统中的貌似随机的不规则运动,其行为却表现为不确定性、不可重复、不可预测、非周期、非收敛

有几个关键点：

  1. 混沌系统演化对初始条件的变化极为敏感，最初状态的轻微变化会导致不成比例的巨大后果，例如“蝴蝶效应”，这使得由确定性系统产生的混沌轨道具有长期不可预测性，即虽然描述混沌的方程是确定的，但系统对初值有极强的敏感性，即初值有极微小的变化 ，将引起系统后来不可预测的改变；
  2. 确定与随机：系统运动大的范围，描述混沌的方程，是确定的，可预测的；但是运动的细节是随机的，不可预测的。举个例子：上海的外环有一辆公共汽车，汽车的路径就是完全围绕外环重复转圈，假如没有固定的公交车站，司机会随机性停车，请问你到哪里去等？
  3. 分形性：局部与整体具有相似性，例如中国的海岸线在中国地图上看是弯弯曲曲的，其局部例如浙江的海岸线，放大后从浙江地图上看也是弯弯曲曲的，两者间具有相似性，这样我们就说海岸线是分形的
  4. 遍历性：遍历性也称为混杂性，混沌运动在有限时间内能够到达混沌区域内任何一点

系统走向混沌的演化过程

参考自混沌理论及其在密码学的应用(邓绍江-李传东)
作者所说非线性系统从非混沌状态到混沌状态的演化过程有多种形式，典型的有下面三类：

  1. 倍周期分叉过程。设某一非线性系统最初处在定常态，随着控制参数的增加，在达到某一数值时，系统状态发生突变，出现稳定的周期振荡状态，随着控制参数的不断增加，系统的状态将发生一系列的突变，振荡频谱中出现分频或周期倍增现象。当系统出现非周期的混乱的振荡状态，即混沌运动状态。分频现象只有在非线性系统中控制参数的某个阈值上才能出现，它是混沌运动产生的序曲；
  2. 阵发混沌过程。对于具有倍周期分叉演化过程的非线性系统，当进入混沌状态以后，在控制参数的某个范围以内构成一个混沌区。在混沌区内，并不是每一个控制参数对应的都是混沌态。在控制参数的多个小区间内，对应着周期振荡状态，这些小区间称为混沌区内的周期窗口。在周期窗口附近，状态变量的时间行为表现出时而周期、忽而混乱，随机地在二者之间跳跃；
  3. 准周期运动到混沌。如果系统随控制参数增加，在振荡频谱中出现两个不可公约（没有公因数）的频率，此运动被称为准周期运动。准周期和锁频（频率稳定）交替出现，最终进入混沌状态。

混沌密码学

介绍

2
混沌系统用于数据加密最早由英国数学家Mattllcws提出，从此人们开始了混沌密码的研
究。人们之所以对这种方法感兴趣，是因为某些确定而简单的动力学系统产生的混沌信号能表现出非常复杂的伪随机性(这符合shannon所提出的密码设计应遵循的混乱原则)，它们难以预测任何微小的初始偏差都会随时问被指数式放大(这符合shannon所提出的密码设计应遵循的扩散原则)，因此，关于初始状态的少量参数就可以产生满足密码学基本特性的混沌密码序列，具有自然的伪随机特性，因而特别适用于进行保密通信。即使解密者已掌握产生混沌序列的方程，也难以猜测决定混沌序列的系数参数以及混沌序列的初始值。因为这些关键值，来源于有理数域（尽管这些关键值是定义在实数域上，但是由于计算机的舍入误差，实际上处理混沌加密序列是在有理数域），在任一个区域上,有理数都是稠密的。单纯的猜测几乎得不到系数参数。
以上内容选自：图像加密技术综述(李昌刚 韩正之 张浩然)
文章作者指出混沌加密方法属于对称加密体制的范畴，作者给出了利用混沌加密进行保密通信的原理图：
1
作者指出：混沌加密的原理就是在发送端把待传输的有用信号叠加（或某种调制机制）上一个（或多个）混沌信号，使得在传输信道上的信号具有类似随机噪声的性态，进而达到加密保密通信的目的。在接收端通过对叠加的混池信号的去掩盖(或相应的解调机制)，去除混沌信号，恢复出真实传输的信号。从混沌加密的原理框图可以看出，要想可靠地
恢复出传输的有用信号，其关键是如何实现混沌的同步。
上述是混沌密码学其中的一个研究方向：以混沌同步技术为核心的混沌保密通信系统，主要基于模拟混沌电路系统

下面介绍混沌理论在密码学的另一个应用：利用混沌系统构造新的流密码和分组密码，主要基于计算机有限精度下实现的数字化混沌系统
Theory and practice of chaotic cryptography这篇文章的作者认为混沌理论用于密码学可以粗略地归为两种形式：

  1. 使用混沌系统产生伪随机数序列，然后作为密钥流来掩盖明文，这一点对应于我们所学的流密码体系；流密码的关键在于有良好的随机密钥序列，而混沌系统因为对初值非常敏感，相同的混沌系统在具有微小差别的初始条件下，将会发生完全不同的长期行为，混沌系统长期行为不可预测。然而，只要系统参数和初始条件给定，混沌现象本身是可以重复再生的。利用混沌系统，可以产生数量众多、相关性弱、非相关、类似噪声、又可以再生的混沌序列。所以混沌理论应用于流密码中是可行的。参考自混沌密码学-百度百科
    主要有两种形式：
  • 以混沌系统为基础设计PRNG（伪随机数发生器）
  • 利用混沌逆系统
  1. 使用明文作为初始的一个参数，参与迭代/反向迭代的过程得到密文，对应于分组密码，很多混沌系统本身就与密码学中常用的Feistel网络结构是非常相似的，比如标准映射、Henon映射等等，因为往往都需要经过多轮迭代。所以，只要算法设计正确合理，就完全可能实现将混沌理论用于分组密码中。如Baptista型算法、Alvarez型算法
  • 基于逆向迭代混沌的分组密码
  • 基于正向迭代混沌的分组密码，基本工作流程为，通过正向迭代一个混沌映射来伪随机地置乱明文，然后利用某些替代算法改变明文的值，多次重复以上过程得到密文。

另外混沌理论也可以用于公钥密码体系
更多参考应用可以参见这篇文章混沌系统在密码学中的应用现状及展望(刘金梅-丘水生)

不足

选自混沌理论在密码学中的应用
尽管混沌加密具有上述特点和优势，但目前混沌理论在密码学上的实际应用中还存在着许多问题。比如说，混沌系统在计算机或其它数字系统实现时，由于对混沌映射的参数和状态模拟精度的限制，使混沌序列表现出短周期、强相关及局部线性的缺点，因此在较小精度实现下的混沌系统不适合加密。当前混沌加密方法仍存在以下不足：

  1. 短周期响应
    现有的混沌序列的研究对于所生成序列的周期性、伪随机性、复杂性、互相关性等的估计是建立在统计分析上，或是通过实验测试给出的，这难以保证其每个实现序列的周期足够大，复杂性足够高，因而不能使人放心地采用它来加密。例如，在自治状态下，输入信 号为零时，加密器表现为有限周期响应。不同的初始状态对应于不同的周期，其周期长度可能很短。这一缺点在某种程度上降低了混沌加密系统的保密性。
  2. 有限精度效应
    混沌序列的生成总是要用有限精度器件来实现的，从而混沌序列生成器可归结为有限自动机来描述，这样，混沌生成器否能超越已有的用有限自动机和布尔逻辑理论所给出的大量研究成果，是一个很值得研究的课题。大多数在有限精度下实现的混沌系统，其性质会与其理论结果大相径庭,从而使许多基于混沌系统的应用无法实现。甚至有学者认为，有限精度效应是目前混沌理论走向应用中出现的一大难题。
  3. 实现精度与保密性的矛盾
    对于分段线性的混沌映射加密系统，相邻的两个状态可能落在同一条直线段上，这样，在数字实现精度很高的情况下，解密者就可利用此特点，在知道少量的明文-密文对照的情况下轻易地恢复出具有足够精度的密钥。也就是说，它对于选择明文攻击的抵抗力很差，从而在这一意义上不具有保密性。任何特定混沌序列的实现都是由其非线性方程和相应的初始条件完全确定了的，有人在研究跟踪混沌序列进行破译的工作。

Logistic映射

logistic映射是一个经典的混沌模型，可以用来模拟生物种群的生长行为，所以也被称为“虫口模型”
其方程形式如下：X(k+1)=u * X(k) * [1-X(k)]
初始条件为X(0)，对于任意的k，X(k)∈[0,1]，u是一个可调的控制参数，为了保证”对于任意的k，X(k)∈(0,1)”，u∈[0,4]
所以在该模型中X(0)与u是未知量，是我们可以设定的
该模型属于前面所说的倍周期分叉的一种(设某一非线性系统最初处在定常态，随着控制参数的增加，在达到某一数值时，系统状态发生突变，出现稳定的周期振荡状态，随着控制参数的不断增加，系统的状态将发生一系列的突变，振荡频谱中出现分频或周期倍增现象。当系统出现非周期的混乱的振荡状态，即混沌运动状态。分频现象只有在非线性系统中控制参数的某个阈值上才能出现，它是混沌运动产生的序曲)
而这个系统状态的变化是与u这个控制参数有关的
维基百科上的动图很好：
3
它那里的控制参数使用r表示的
我们分阶段来看一下：

0<u<1

u取此区间的值的时候，系统最终经过多次迭代都会渐进趋近于0

1<u<2

u取此区间的值的时候，系统最终经过多次迭代会趋近于(u-1)/u

2<u<3

u取此区间的值的时候，系统最终经过多次迭代后会收敛于(u-1)/u，注意此时用的是收敛，因为一开始会在这个值的左右振动

3<u<约3.5699

u取此区间的值的时候，系统呈现周期状态，且随u值增大，周期长度增大

约3.5699<u<4

u取此区间的值的时候，系统呈现混乱与周期相交替的状态，因为对于某些特定的u的取值(如3.82)，系统会呈现周期状态

u=4

当u=4时，系统完全混乱

随迭代次数增加的不同u值下所对应的X的取值如下图汇总所示：
4
所以当u取(3.5699,4]之间的值，特别是靠近4的时候，迭代生成的值是一种伪随机分布的状态
当初始条件微微改变时，迭代的结果之间有着很大的差异，如下图所示：
5
上图显式的是X0=0.663489000和X0=0.663489001，μ=3.99时两个Logistic序列的图像
可以看出随着迭代次数的增加，两者之间的差异开始明显，所以很好地说明了具有初值敏感性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 绘图代码
import matplotlib.pyplot as plt
plt.rcParams['font.family'] = 'sans-serif'
plt.rcParams['font.sans-serif'] = 'SimHei'
X=0.663489000
X1=0.663489001
u=3.99
Y_data=[]
Y_data1=[]
Y_data.append(X)
Y_data1.append(X1)
X_data=[0]
for i  in range(1,301):
    X=X*u*(1-X)
    X1=X1*u*(1-X1)
    if i%4==0:
        Y_data1.append(X1)
        Y_data.append(X)
        X_data.append(i)
plt.plot(X_data,Y_data,label="1",color="green",linewidth=1)
plt.plot(X_data,Y_data1,label="2",color="red",linewidth=1)
plt.xlabel('迭代次数')
plt.ylabel('X取值')
plt.show()

基于Logistic混沌序列的灰度图像加密算法

首先可以想到的一种是流密码方式，利用logistic映射产生伪随机数与明文异或，但这种方法经不起已知明文攻击，除非每一次加密都调整u或X0值
下面介绍一种改进过的算法（考虑到了香农曾提过的diffusion和confusion）：
这部分参考的是燕善俊，余昭平于2008年发表在《计算机工程与应用》上的《基于Logistic混沌序列的灰度图像加密算法》这篇论文中所提及到的一种灰度图像加密算法
参考链接：基于Logistic混沌序列的灰度图像加密算法(燕善俊-余昭平)
算法步骤如下：

选取密钥

上文中曾经说过“混沌加密方法属于对称加密体制的范畴”，所以选取一个加密方和解密方共同知道的密钥K
K=(X0,u,k1,k2,m1,n1,m2,n2)
X0为logistic映射的初始值，u为控制参数，根据上文分析当u∈(3.5699,4]之间时，系统处于混乱状态，k1、k2、m1、n1、m2、n2均为正整数，且m1与m2不能互相整除，n1与n2不能互相整除

根据m1、m2、n1、n2扩充图像

令M=mul(m1,m2)，N=mul(N1,N2)
对于我们所选择的实验图像g，扩充其行数和列数，使其分别为M和N的倍数，用255像素扩充生成新的图像G

利用密钥和logistic产生的伪随机序列产生异或矩阵和置换矩阵

我们知道logistic映射每一次产生的随机数的值都是位于0和1之间的，而像素值都是0-255之间的，所以需要先进行映射，从产生的随机序列得到整数序列x1、x2、x3等

生成异或矩阵

假设我们要生成的异或矩阵大小为m X n，给定一个整数k(密钥中的k1和k2)，在所得到的整数列x1、x2、x3……中依次选取xk+1、xk+2、……、xk+m*n，按行进行排列组成异或矩阵PkmXn

异或操作

待加密图像矩阵与异或矩阵对应像素值逐比特异或加密

生成置换矩阵

假设我们要生成的置换矩阵大小为m X n，给定一个正整数k(密钥中的k1和k2),在所得到的整数列x1、x2、x3……中依次选取xk+1、xk+2、……、xk+m*n，然后将其从小到达排序后，按行进行排列组成置换矩阵ZkmXn

置换操作

在置换矩阵ZkmXn中，若Zi,j=r，并且r=p*n+q
则将待加密图像中的(p,q)的像素值赋给新生成图像中的(i,j)位置的像素

异或与置换

将像素矩阵G按m1Xn1大小进行分块，指定异或矩阵大小为m1Xn1，指定k=k1，生成异或矩阵Pk1m1Xn1
进行逐块异或，后组成新图像G1
将像素矩阵G1按m2Xn2大小进行分块，指定置换矩阵大小为m2Xn2，指定k=k1，生成置换矩阵Zk1m2Xn2
进行逐块置换，后组成新图像G2
后令k=k2，重复异或与置换

解密

解密算法为逆过程，先k=k2，先置换后异或

简单代码

用logistic生成随机序列，与明文异或

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
package graphic;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import javax.imageio.ImageIO;
public class logistic_map {
	public static void encrypt(File imageFile,double x,double u) throws IOException {
		BufferedImage image=ImageIO.read(imageFile);
		int width=image.getWidth();
		int height=image.getHeight();
		int sum=width*height;
		int logisticArray[]=new int[sum];
		for(int i=0;i<sum;i++) {
			x=x*u*(1-x);
			logisticArray[i]=(int)Math.floor(256*x);
		}
		int count=0;
		BufferedImage outImage=new BufferedImage(width,height,image.getType());
		for(int i=0;i<width;i++) {
			for(int j=0;j<height;j++) {
				int pixel=image.getRGB(i, j);
				int R=(pixel&0xff0000)>>16;
				int G=(pixel&0xff00)>>8;
				int B=pixel&0xff;
				pixel=(R+G+B)/3;
				int setPixel=pixel^logisticArray[count];
				setPixel=255 << 24|setPixel << 16|setPixel << 8|setPixel;
				outImage.setRGB(i, j,setPixel);
				count++;
			}
		}
		String path="E:\\大学课程\\大三下学期\\创新设计\\第五、六周学习\\T1.png";
		File outFile=new File(path);
		ImageIO.write(outImage, "png",outFile );
		System.out.println("加密完成！");
	}
	public static void decrypt(File imageFile,double x,double u) throws IOException{
		BufferedImage image=ImageIO.read(imageFile);
		int width=image.getWidth();
		int height=image.getHeight();
		int sum=width*height;
		int logisticArray[]=new int[sum];
		for(int i=0;i<sum;i++) {
			x=x*u*(1-x);
			logisticArray[i]=(int)Math.floor(256*x);
		}
		int count=0;
		BufferedImage outImage=new BufferedImage(width,height,image.getType());
		for(int i=0;i<width;i++) {
			for(int j=0;j<height;j++) {
				int pixel=image.getRGB(i, j);
				int R=(pixel&0xff0000)>>16;
				int G=(pixel&0xff00)>>8;
				int B=pixel&0xff;
				pixel=(R+G+B)/3;
				int setPixel=pixel^logisticArray[count];
				setPixel=255 << 24|setPixel << 16|setPixel << 8|setPixel;
				outImage.setRGB(i, j,setPixel);
				count++;
			}
		}
		String path="E:\\大学课程\\大三下学期\\创新设计\\第五、六周学习\\T2.png";
		File outFile=new File(path);
		ImageIO.write(outImage, "png",outFile );
		System.out.println("解密完成！");
	}
	public static void main(String[] args) throws IOException {
		File f=new File("E:\\大学课程\\大三下学期\\创新设计\\第五、六周学习\\测试.png");
		double x=0.78355;
		double u=3.99;
		encrypt(f,x,u);
		File f1=new File("E:\\大学课程\\大三下学期\\创新设计\\第五、六周学习\\T1.png");
		decrypt(f1,x,u);
	}
}

结果

测试原图与加密（参数x0=0.78355，u=3.99）后：
6
7
解密成功
改变x0=0.78356后加密一张图片后，用（参数x0=0.78355，u=3.99）解密，发现：
8
发现解密不成功，可见微小的参数改变就会使解密不成功，体现了对初值的极大的敏感性

算法分析

  1. X0∈(0,1)位于实数域中，理论上密钥空间无穷大，这个就和我们之前所讲过的Arnold变换不同了，因为离散数字图像是有限点集，在有限步内能恢复状态，但是因为计算机精度等问题也是往往无法到达理论要求；
  2. 异或矩阵经不起已知明文、选择明文等攻击，通过增加置换矩阵，而置换矩阵又是根据k1、k2变化而改变的，加强抵抗攻击的能力；