基于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框架下實現，提高了加密分存的效率。從實驗結果可知，加密分存圖像為無序亂碼圖。下一步工作的重點將圍繞可視化圖像加密分存這一點展開，將加密分存圖像隱藏在載體圖像中，進一步提高圖像加密分存的安全性。