基于Spark和整数混沌的彩图拉格朗日加密分存方案

陈 飞，刘建东，胡辉辉，刘 博，张世博

(1.北京石油化工学院 信息工程学院，北京 102617；2.北京化工大学 信息科学与技术学院，北京 100029)

0 引 言

传统图像加密算法是把密文和密钥交给一位管理者管理，这样带来了如下不便：若管理者不幸遇难或者丢失密钥(密文)，那么这个秘密信息再也无法恢复;由于管理者是一个人，大大增加了密钥(密文)泄露或被窃的风险。现有的图像分存体制解决了上述传统加密算法的缺点，降低了密钥(密文)管理中的风险。图像分存这一思想主要来源于密码学中秘密共享方案。

现有的图像分存方案大多数都是基于拉格朗日差值公式的。但是，图像分存体制本身存在着相邻像素点相关性大，密码学特性较差的问题[1-3]。文献[4]提出了利用猫映射对分存图像进行置乱处理，解决了相邻像素点相关性大的问题，但是没有从根本上改变各个像素点值的大小，无法使各个像素点均匀遍历整个空间。

混沌系统是一种极其复杂的动力学系统，具有高度的初值敏感性。高维混沌系统具有复杂度高，相邻序列之间相关性较低的特性，实用于图像加密。文献[5]提出了利用混沌映射和门限方案对图像进行加密分存，但由于计算效率问题，很难实现大规模分存。图像分存算法具有高度并行化计算体制，随着计算机集群技术的发展，集群化计算为提高图像加密分存算法的效率提供了可实施的条件[6-9]。

目前，运用Spark框架进行分布式计算已经成为一种主流。2009年，Spark平台是由AMPLab实验室提出的概念。Spark平台在集群上计算效率高，易于实现[10,11]。

针对上述问题，提出了一种基于Spark平台的图像加密分存算法。将基于拉格朗日差值公式图像分存算法中的分存ID作为产生加密序列初始值的密钥，对分存图像分别进行加密，最后在Spark平台上实现，提高了图像加密分存的效率。

1 二维整数耦合帐篷映射

帐篷映射是一种极其简单的混沌映射，帐篷映射具有高遍历性、类随机性。实数域帐篷帐篷映射通过拉伸、折叠操作将计算域控制在[0,1]内，实数域帐篷映射表达式如下

(1)

式中：参数α为外部控制参数。α大小决定了映射中心点的位置，只有当其大小为0.5时，该映射才被称为标准帐篷映射。

由于在实数域帐篷映射要进行浮点运算，这样大大增加了计算时间。为了提高计算效率，将实数域帐篷映射转化为整数域帐篷映射[12]，如式(2)所示

(2)

式(2)解决了式(1)由于浮点运算过多而带来的计算量过大的缺点，但是由于计算机截断误差的存在，式(2)的整数模型不免出现了短周期现象。为了解决这一问题，在模型中提出了动态这一概念，且一维模型维数低，密码学特性较差、复杂度低，将一维整数模型拓展为二维整数动态帐篷映射，如式(3)所示

(3)

其定义域为

其中

gi=(xi+mi)mod2n
hi=(yi+ni)mod2n

在式(3)中，mod为取模运算，mi和ni分别为横轴动态参量和纵轴动态参量。通过控制mi和ni的大小来控制横轴和纵轴移动的偏移量。式(3)中，随着迭代的进行，xi+1的值不仅由xi的值决定，yi的值也会对其取值产生影响。同样，yi+1的值也不仅由yi的取值决定，同样xi也会对其产生影响。通过这种机制，大大提高了模型的复杂度，同时也减小了相同轴之间相邻点的相关性。

以式(3)作为耦合函数，在式(3)加入全耦合映像格子模型，耦合映像格子模型如下

xn+1(1)=f(xn(L))+f(xn(1))+f(xn(2))

(4)

当i>1

xn+1(i)=f(xn(i-1))+f(xn(i))+f(xn(i+1))

(5)

边界条件为

f(xn(L+1))=f(xn(1))

2 拉格朗日插值

目前大多数图像(K,N)分存方案都是基于1979年shamir提出的基于拉格朗日插值公式的有限域秘密共享算法。有限域内的拉格朗日插值公式为

f(x)=(S+r1x+r2x2+r3x3+…+rK-1xK-1)modq

(6)

式中：S为需要分存的秘密信息，x为图像分存ID，r1,r2,r3,…,rK-1为随机整数参数，N为分存份数，K为门限次数，且K需要小于等于N，q为素数。

将秘密信息S分存时，根据式(6)，构造如下方程组

(7)

方程组(7)中，x1,x2,x3,…,xN为分发给密钥管理者的公开分存ID，且这N份公开ID的值不能重复。在分存过程中，只需将根据方程组所求的 (x1,f(x1))， (x2,f(x2))， (x3,f(x3))， …， (xN-1，f(xN-1)) 发给相应的密钥管理者。利用拉格朗日插值公式可以将式(6)转化为下式

(8)

(9)

由式(9)可知，只要大于等于K个密钥提供出它们所管理的 (xi,f(xi)), 就能通过式(9)恢复出秘密S。当少于K个人时，则无法恢复秘密S。

3 Spark平台

Spark是基于HadoopMapReduce的基础上提出的一种高效的分布式集群计算平台，不仅拥有Hadoop的所有优点，而且由于Spark是基于内存运算的，各线程任务可直接在内存中读取数据，省去了从磁盘读取和存储数据I/O的时间,因此提高了Spark处理数据的效率。Spark的核心是弹性分布式数据集(resilient distributed datasets，RDD)。RDD主要支持两种类型操作，即Transformation和Action。Transformation操作包含Map，filter，flatMap等，将现有的数据集转换成新的数据集。Action操作包含reduce，collect等，将Transformation中的数据集进行运算。Transformation操作是不会马上提交给Spark集群执行的，只会记录需要这样的操作，只有当Action操作进行时，才会真正启动计算过程进行计算，大大提高了Spark运行效率。且Spark提供Java，scala，Python等语言接口，开发者可以根据自己的需要决定使用哪一种语言[13-15]。

4 基于Spark平台图像加密分存方案

基于拉格朗日差值公式的高度并行性，提出了一种基于Spark平台的彩色图像加密分存方案。具有密钥空间大、安全性高、密码学特性好、加密效率高等特性。

4.1 加密分存方案

采取二维整数耦合帐篷映射模型，通过耦合的方式生成多条二维混沌序列。分存方案采取基于伽罗域拉格朗日插值公式的(K,N)图像分存方案，对每个分存生成的图像运用不同的混沌序列进行加密。若分存份数N的值过大，需要迭代产生混沌序列是非常多的。且上述二维整数帐篷映射每迭代一次，需要判断4次，也就是说，随着分存份数N的增大，加密分存时间也会大大增加。将N份ID值分块，对于不同的ID值，对图像进行分存加密。这样可以有效解决由于分存份数过多而带来的加密分存时间过长的问题，具体加密分存算法如下：

(1)读取图像RGB矩阵，并将RGB矩阵，并将其广播。

(2)将所有N份ID值放到一个集合中，并分块。

(3)对于每个分块中ID值，通过方程组(10)产生L(L为耦合映像格子格点度，本次实验格点长度取条二维序列初始值(x1,y1),(x2,y2),(x3,y3),…，(xL,yL)， 式(10)如下所示

(10)

式中：kj为第j个ID， (x(0,i),y(0,i)) 为第i个格点序列的初始值，通过上述操作，使得每个ID值对产生的加密序列的初始值产生影响，混沌模型有着极强的初值敏感性，即每个ID值产生的L条混沌序列是不一样的，增加了加密安全性。

(4)将步骤(3)中产生的序列初始值 (x1,y1),(x2,y2),(x3,y3),…，(xL,yL) 作为二维整数耦合帐篷映射的初始值。二维整数耦合帐篷映射在时间上进行迭代、在空间上进行耦合，产生L条二维整数混沌序列，序列值在(0,255)之间分布。为了提高加密分存的效率，减少无用的序列出现，迭代次数为 (M*N)/4+1次，M为图像宽度，N为图像高度。

(5)对原始图像进行分存，分存操作是基于上述式(7)(拉格朗日插值公式的)，对于ID值分块中，将原始图像每个像素点的RGB这3个像素值分别作为秘密信息S方程组进行分存，可以得到Rxi，Gxi，Bxi这3个分存矩阵，xi为分存ID。

(6)准备好加密序列和原始图像RGB三矩阵分存完之后，需要对分存得来的Rxi，Gxi，Bxi三矩阵进行加密。从步骤(4)产生的4条长度为 (M*N)/4+1 的二维整数序列选取M*N格点，并把其重构为一条长度M*N的二维序列。由于在彩色图像中，人眼对R分量直觉感官最为直接，所以采取在加密时，人眼对R分量直觉感官最为直接，所以用生成的二维整数序列中的x值直接与分存矩阵中的R分量像素值相加取模251，用y值分别与G，B分量相加取模251，最终得到加密分存图像

4.2 Spark并行加密分存方案

Spark是一个分布式计算框架，其主要工作原理为当我们提交完一个作业后，会启动driver，driver向集群管理器申请作业所需要的资源，即Executor进程。然后在Exe-cutor进程运行task。在本文方案中，运用到的Transformations算子为map算子，map可以将原RDD中的每个数据通过自定义映射转化为一个新的元素，形成一个新的RDD。Action算子为collect，collect将Spark中的RDD返回为一个数组。

本文所设计的基于Spark平台的图像加密分存算法流程如图1所示。

图1 图像加密分存方案流程

4.2.1Broadcast函数与分块算法

读取图像RGB矩阵，并利用Broadcast函数将其广播到各个节点中，将所有的分存ID值放入一个集合中，在分片时，为了让所有Executor进程都能均匀的分配到任务，设集群包含有M个Executor，通过Sparkcontext中Parallelize函数将ID集合分片并生成RDD。通过Parallelize可以设置slices的数目(分块的数目)，本次实验slice的数目为M。Spark会在每个slice中起一个task，自行分给Wor-ker中的Executor处理。

操作1：分片算法

Parallelize()函数

输入：ID集合S

输出：分块RDD

4.2.2Map算子操作

在经过分片和广播操作后，每个Worker对部分ID进行图像加密分存。在每次图像加密分存时，首先根据RDD中ID值对图像矩阵imi进行基于拉格朗日插值公式分存生成imi1。然后，由ID值生成整数混沌系统的初始值，进而生成L条二维混沌加密序列x，进而对分存图像进行步骤f加密。输出为K/V对，K为分存IDi，V为每个ID生成的加密分存图像imi2。

操作2：加密分存算法

map()

输入：ID值

输出：key，imi2

imi2=(x+imi1)mod251

具体map操作流程如图2所示。

图2 map并行加密分存

等待map中所有计算完成之后，运用collect将所有的(Key，value)返回为一个数组。

5 实验结果分析

以512*512的标准测试图像，进行本文设计的算法(7,10)图像加密分存算法，如图3所示。

图3 原始图像与分存图像

由图3可知，分存加密图像为无序乱码图，可以隐藏原始图像所包含的大部分信息。

5.1 算法安全性分析

5.1.1 密钥空间分析

图像并行加密分存方案的加密安全性主要依赖于二维整数耦合帐篷映射混沌系统的安全性。密钥空间大小是衡量一个加密模型安全性的重要指标之一，本文采取全耦合作为耦合方式，每个格点的初始值在[0,255]分布，格点数为L，密钥空间大小即为28*L， 理论上耦合映像格子格点数L可以为拓展为无限大，几密钥空间为无限大，能够抵抗暴力破解密钥攻击。

5.1.2 抗统计攻击分析

(1)直方图分析

图4给出了512*512Lena彩色图像的原始图像和经过本文算法对Lena图进行(7,10)加密分存后的灰度直方图。

图4 原图与加密分存图像直方图

由图4可知，原始图像RGB这3个分量的直方图出现了明显的毛刺，分布极不均匀。各分存图像的直方图都呈现均匀分布，能够很好隐藏原始图像的信息。

(2)信息熵分析

图像的信息可以用来表征图像像素分布的混乱度。若图像的像素值呈均匀分布，则图像包含的信息量较少，其信息熵越大，反若分布不均匀，其信息熵越小。图像像素值在[0.255]分布，共有28种可能，所以图像像素的信息熵最大值为8。信息熵计算公式如下

(11)

式中：P(Si) 像素点在[0,255]区间的概率，表1给出了512*512标准测试Lena图像明文和加密分存的图像的信息熵。

表1 信息熵

如表1所示，原始图像RBG三分量矩阵信息熵均在7左右分布，包含了大量的图像信息，而加密分存图像的RGB三分量的信息熵均在7.97左右分布，基本接近于理想值8。就信息熵而言，本文所设计的加密分存算法得到的加密分存图基本接近于理想加密图像。

5.2 Spark平台实验结果

Spark平台主要包括Master节点和Worker节点。Master节点主要负责对整个集群的任务监控和调用，Worker节点负责任务的计算。

本次实验中，Master节点包含Master、ResourceMa-nager和Secondary-NameNode节点，CPU配置为Inter(R)Xeon(R) CPU E7-4807 @ 1.87 GHZ；drivermemory为2 GB。

Worker节点包含Worker和Node-Manager节点，CPU配置为Inter(R)Core(TM)2QuadCPUQ8200 @ 2.33 GHZ。Executormemory为2 GB，软件平台为Spark 2.2.0。

对标准测试图像Lena图进行加密分存，在分存份数不同的情况下，分别记录使用不同节点数时，加密分存的时间和不同核数加密分存时间与核数为1的时间比，如表2分存份数N=11和表3分存份数N=22所示。

表2 分存份数N=11

表3 分存份数N=22

由表2，表3可知，随着CPU核数的提升，加密分存时间有着明显的降低，且比较表2和表3，表3的N值为表2的两倍，而表3的加密分存时间均小于表2的两倍，也就说，随着N值变大，加密分存效率会提升。

6 结束语

提出了一种基于二维整数耦合帐篷映射的彩色图像并行加密分存方案，并给出在Spark框架下的并行算法，取得了较为理想的实验效果。利用分存ID产生加密序列的初值，对于不同的ID产生不同的加密序列，大大增加了图像加密的安全性。在加密分存过程中，充分利用了图像加密分存算法高度并行特性，在Spark框架下实现，提高了加密分存的效率。从实验结果可知，加密分存图像为无序乱码图。下一步工作的重点将围绕可视化图像加密分存这一点展开，将加密分存图像隐藏在载体图像中，进一步提高图像加密分存的安全性。