摘 要：基于二維細(xì)胞自動(dòng)機(jī)提出了一種新的秘密圖像共享方案，該方案把秘密圖像作為細(xì)胞自動(dòng)機(jī)的一個(gè)初始配置，通過(guò)利用二維n階可逆存貯細(xì)胞自動(dòng)機(jī)進(jìn)行分解成n為份的影子圖像，再利用其逆細(xì)胞自動(dòng)機(jī)進(jìn)行反向迭代來(lái)重構(gòu)所共享的秘密圖像。分析表明，該方案實(shí)現(xiàn)簡(jiǎn)單，在計(jì)算上是安全的，并且是一個(gè)完備的(n，n)方案。

關(guān)鍵詞：秘密圖像；影子圖像；二維細(xì)胞自動(dòng)機(jī)；秘密圖像共享

中圖分類號(hào)：TN918.1 文獻(xiàn)標(biāo)識(shí)碼：B

文章編號(hào)：1004373X(2008)0309103

A Secret Image Sharing Scheme Based on Bidimensional Cellular Automata

WANG Liqin1，CHEN Guiqiang2，3

(1.Zhangjiakou Voca.Colle.of Tech.，Zhangjiakou，075000，China;2.Colle.of Comput.Sci.and Tech.，Beijing Univ.of Tech.，Beijing，100022，China;

3.Hebei North Univ.，Zhangjiakou，075000，China)

Abstract：Based on the bidimensional cellular automata，a new secret image sharing scheme is proposed in this paper.The secret image is considered as one of the initial configurations of the bidimensional cellular automata，The n shadow images of the secret image are made by the bidimensional reversible cellular automata with memory of order n.The backward iteration of the bidimensional reversible cellular automata with memory of order n is used to recover the shared secret image.Analysis show the proposed scheme can be implemented easily，and is a computationally secure and perfect (n，n) scheme.

Keywords：secret image；shadow image；the bidimensional cellular automata；secret image sharing

1 引 言

秘密圖像共享是現(xiàn)代密碼學(xué)的一個(gè)重要部分，已被廣泛應(yīng)用于信息安全中。Shamir[1]和Blakley[2]最早提出秘密共享的概念，并分別給出了一個(gè)(k，n)門限秘密共享方案。Shamir的門限方案是一個(gè)完備的秘密共享方案[3]，即在訪問(wèn)結(jié)構(gòu)上的任意合格子集都可以恢復(fù)所共享的秘密，而任意不合格子集都得不到關(guān)于所共享秘密的任何信息。Naor和Shamir提出了可視密碼學(xué)[3](Visual Cryptography，VC)的概念，后來(lái)基于灰度和彩色圖像的VC方案都被構(gòu)造出來(lái)。雖然VC具有一些優(yōu)點(diǎn)，但由于VC本身的條件所限，共享的圖像恢復(fù)之后所能達(dá)到的視覺(jué)效果和原始圖像有較大差距，因此在一些對(duì)圖像質(zhì)量有較高要求的場(chǎng)合，VC就不太適用了。Chang和Lin[4—6]提出的共享彩色圖像的(t，n)門限圖像隱藏方案，Lukac和Plataniotis[7]提出的彩色秘密圖像共享的方案，雖然其恢復(fù)圖像可以達(dá)到和原圖一樣，但由于其利用了(2，2)VC方案的思想，故生成的影子秘密圖像是原圖大小的4倍，呂超等人[8]提出的一種圖像秘密共享方案能夠較好地保證恢復(fù)圖像的質(zhì)量，生成的影子秘密圖像和原圖的大小也相同。然而，他還是有損于圖像的質(zhì)量而不是完備的方案，且他們的方案需要應(yīng)用Lagrange插值操作，當(dāng)n很大時(shí)(其中n代表共享的參與者數(shù)量)，其計(jì)算量仍然比較大。細(xì)胞自動(dòng)機(jī)的概念最早是由Von Neumann于1948年提出的[8]。在1985年美洲密碼學(xué)年會(huì)上，Wolfram首次提出了將細(xì)胞自動(dòng)機(jī)的初始狀態(tài)作為密鑰，使用細(xì)胞自動(dòng)機(jī)前向迭代產(chǎn)生的偽隨機(jī)序列作為序列密碼[9]，從而開(kāi)創(chuàng)了細(xì)胞自動(dòng)機(jī)在密碼學(xué)領(lǐng)域的應(yīng)用研究。細(xì)胞自動(dòng)機(jī)具有組成單元的簡(jiǎn)單規(guī)則性、單元之間作用的局部互連性和信息處理的高度并行性，并表現(xiàn)出復(fù)雜的全局特性等特點(diǎn)[10]，使得他尤其適合密碼學(xué)中的應(yīng)用。本文作者的創(chuàng)新點(diǎn)是基于一個(gè)n階二維可逆細(xì)胞自動(dòng)機(jī)RCAM提出了一個(gè)新的秘密圖像共享方案。分析表明，本文方案是一個(gè)完備的(n，n)方案，在計(jì)算上是安全的，也是一個(gè)簡(jiǎn)單實(shí)用的方案，易于在軟件和硬件上得以實(shí)現(xiàn)。

2 二維細(xì)胞自動(dòng)機(jī)原理

二維細(xì)胞自動(dòng)機(jī)(Bidimensional cellular automata)是由r×s矩陣的細(xì)胞單元構(gòu)成的一種離散的動(dòng)態(tài)系統(tǒng)[9]，簡(jiǎn)稱為CA。令代表CA的第i行、第j列的細(xì)胞(其中0≤i≤r-1，0≤j≤s-1)，他具有一定狀態(tài)aij∈Zc={0，1，…，c-1}(其中Zc是細(xì)胞的狀態(tài)空間)。令C(t)表示CA的所有細(xì)胞在t時(shí)刻的狀態(tài)即C(t)=(a(t)ij)，在t+1時(shí)刻，細(xì)胞的轉(zhuǎn)移狀態(tài)a(t+1)ij由局部轉(zhuǎn)移函數(shù)f 和該單元鄰域內(nèi)9個(gè)細(xì)胞單元在t時(shí)刻的狀態(tài)來(lái)確定。令Vij={，，，，，，，，}表示細(xì)胞鄰域內(nèi)的9個(gè)細(xì)胞單元，其在t時(shí)刻的狀態(tài)為:

V(t)ij={a(t)i－1，j－1，a(t)i－1，j，a(t)i－1，j+1，a(t)i，j－1，a(t)i，j，a(t)i，j+1，

a(t)i+1，j－1，a(t)i+1，j，a(t)i+1，j+1}

因此，CA的局部轉(zhuǎn)移函數(shù)f具有以下形式：

當(dāng)t=0時(shí)，C(0)表示CA的初始配置，則{C(0)，C(1)，…，C(k)}為CA的k階進(jìn)化序列。若令C表示CA所有可能的狀態(tài)集合，則|C|=2r×s。在CA中的細(xì)胞數(shù)目是有限的，為了保證CA具有良好的動(dòng)態(tài)性必須限定一些邊界條件。在本文中，考慮周期邊界條件，即如果i≡u(píng)(mod r)和j≡v(mod s)，那么a(t)ij=a(t)uv。CA進(jìn)化過(guò)程中的下一時(shí)刻的狀態(tài)由一個(gè)線性全局轉(zhuǎn)移函數(shù)Φ：C→C來(lái)產(chǎn)生，即C(t+1)=Φ(C(t))，如果Φ是一個(gè)雙射函數(shù)，那么他有逆函數(shù)Φ-1，存在另一個(gè)細(xì)胞自動(dòng)機(jī)以Φ-1為全局函數(shù)[11]，他稱為CA的逆，記為RCA。當(dāng)一個(gè)CA存在逆，那么他是可逆的，即他可以反向進(jìn)化。

一般情況下，在CA中每個(gè)細(xì)胞在t+1時(shí)刻的狀態(tài)依賴于他鄰域內(nèi)細(xì)胞在t時(shí)刻的狀態(tài)。若CA中每個(gè)細(xì)胞在t+1時(shí)刻的狀態(tài)不僅跟某些細(xì)胞在t時(shí)刻的狀態(tài)有關(guān)，而且還跟其他一些細(xì)胞在t-1，t-2等時(shí)刻的狀態(tài)有關(guān)，這種細(xì)胞自動(dòng)機(jī)稱為存貯細(xì)胞自動(dòng)機(jī)(Cellular Automata with Memeory，CAM)[11]。一個(gè)n階CAM是每次進(jìn)化都依靠t，t-1，t-2，…，t-n-1時(shí)刻的狀態(tài)。因此n階CAM的局部轉(zhuǎn)移函數(shù)具有以下形式：

其中fm (1≤m≤n)是n個(gè)CA的局部轉(zhuǎn)移函數(shù)，在這種情況下，n階CAM的初始配置具有n個(gè)CA的初始配置即C(0)，C(1)，…，C(n-1)。

定義[12]:如果fn(V(t－n+1)ij)=a(t－n+1)ij，那么由式(2)給出的n階RCAM是一個(gè)可逆的細(xì)胞自動(dòng)機(jī)，并具有以下局部轉(zhuǎn)移函數(shù):

他的逆仍然為一個(gè)n階RCAM，也具有以下局部轉(zhuǎn)移函數(shù):

基于定義給出的RCAM，我們提出了一個(gè)新的圖像共享方案，他可以對(duì)黑白圖像、灰色圖像、彩色圖像進(jìn)行共享。

3 秘密圖像共享方案

3.1 系統(tǒng)參數(shù)

假設(shè)系統(tǒng)中有n個(gè)參與者，他們構(gòu)成的集合記為Q={P1，P2，…，Pn}，D(DQ)表示一個(gè)秘密圖像分發(fā)者，在本文中，假設(shè)秘密圖像分發(fā)者是一個(gè)可信的第三方。令I(lǐng)表示共享的秘密圖像，具有r×s個(gè)象素，每個(gè)象素的具有c個(gè)象素值(c=2b且b的取值為{1，8，24})。把圖像I看作矩陣M，矩陣元素的系數(shù)(i，j)代表象素的位置，矩陣M的元素值a代表圖像I的象素值。因此，矩陣M看作是n階RCAM的初始配置之一，n階RCAM的局部狀態(tài)轉(zhuǎn)換函數(shù)是式(3)給出的形式。

3.2 秘密圖像的分發(fā)

秘密圖像分發(fā)者D執(zhí)行以下步驟實(shí)現(xiàn)秘密圖像分發(fā):

(1) 秘密圖像分發(fā)者D構(gòu)造在狀態(tài)空間Zc上的n階RACM，c是圖像I的色彩值(即c=2b且b的取值為{1，8，24})，并定義式(3)中的局部狀態(tài)轉(zhuǎn)移函數(shù)fm，即：

其中λα，β∈Zc是隨機(jī)選擇，1≤m≤n－1。

(2) 秘密圖像分發(fā)者D構(gòu)造的n階RACM的初始狀態(tài)，在狀態(tài)空間Zc上隨機(jī)選擇n-1個(gè)r×s大小矩陣C(0)，C(1)，…，C(n-2)和C(n-1)=M作為n階RACM的初始狀態(tài)n個(gè)CA的初始配置。

(3) 秘密圖像分發(fā)者D隨機(jī)選擇一個(gè)整數(shù)k，從n階RACM的初始配置C(0)，C(1)，…，C(n-2)，C(n-1)計(jì)算所構(gòu)造n階RCAM的(n+k+1)階進(jìn)化序列：C(n)，C(n+1)，…，C(n+k+1)，…，C(2n+k)。

(4) 令最后n個(gè)配置作為參與者的份額，即Y1=C(n+k+1)，Y2= C(n+k+2)，…，Yn=C(2n+k)。

(5) 將每個(gè)份額Yi通過(guò)安全信道發(fā)送給參與者Pi(1≤i≤n)。

3.3 秘密圖像的重構(gòu)

秘密圖像的重構(gòu)需要所有參與者提供的n個(gè)連續(xù)的份額，即Y1=C(n+k+1)，Y2= C(n+k+2)，…，Yn=C(2n+k)，令(0)=C(2n+k)，(1)=C(2n+k－1)，…，(n－1)=C(n+k+1)作為n階逆RCAM的初始配置，利用其局部狀態(tài)轉(zhuǎn)換函數(shù)式(4)進(jìn)行k+2次進(jìn)化(迭代)得到的配置(n+k+1)=C(n－1)=M，即原始秘密圖像得以重構(gòu)。

4 實(shí) 例

假設(shè)參與者數(shù)n=3，原始秘密圖像I表如圖1所示lena，具有120×120個(gè)象素，每個(gè)象素的具有256個(gè)象素值(即c=2b=256且b的取值為8)。隨機(jī)選擇k=3，經(jīng)過(guò)n+k+1=7次進(jìn)化將最后的3個(gè)配置如圖1的影子圖像1、影子圖像2、影子圖像3分配給參與者。在重構(gòu)過(guò)程中，必須所有的參與者提供其影子圖像，運(yùn)用n階二維可逆細(xì)胞自動(dòng)機(jī)RCAM能恢復(fù)出和原始秘密圖像完全一致的秘密圖像。

圖1 實(shí)驗(yàn)結(jié)果

5 安全性分析

在本文方案中構(gòu)造了一個(gè)n階二維可逆細(xì)胞自動(dòng)機(jī)RCAM，只要知道n個(gè)連續(xù)的配置C(t)，C(t-1)，…，C(t-n+2)，C(t-n+1)，就可以計(jì)算出C(t+1)，但如果僅知道其中n-1個(gè)或更少的配置，將無(wú)法計(jì)算出C(t+1)。不失一般性，這里假設(shè)僅知道C(t)，C(t-1)，…，C(t-n+2)，不知道配置C(t-n+1)，即不知道a( t - k)，a(t－n+1)ij，0≤i≤r－1，0≤j≤s－1的值，由上面可知，n階二維可逆細(xì)胞自動(dòng)機(jī)RCAM是根據(jù)以下局部轉(zhuǎn)移函數(shù)反向進(jìn)化：

這樣重構(gòu)者就必須解r×s個(gè)線性方程組成的如下方程組：

這里bij=∑n－1m=1fn－m(V(t－m+1)ij)是已知，但還有2×r×s個(gè)未知量a(t+1)ij，a(t－n+1)ij，(0≤i≤r－1，0≤j≤s－1)，顯然未知量的個(gè)數(shù)大于方程的個(gè)數(shù)，即由方程組無(wú)法確定這些未知數(shù)，從而得不到關(guān)于C(t+1)={a(t+1)ij}，(0≤i≤r－1，0≤j≤s－1)的任何信息。由上面的分析可知，任意連續(xù)的n個(gè)份額可以重構(gòu)所共享秘密圖像，而n-1個(gè)或更少的份額得不到關(guān)于所共享秘密圖像的任何信息。因此，本文方案是一個(gè)計(jì)算上安全的方案，并且是一個(gè)完備的方案。

6 結(jié) 語(yǔ)

本文作者的創(chuàng)新點(diǎn)是基于一個(gè)n階二維可逆細(xì)胞自動(dòng)機(jī)RCAM提出了一個(gè)新的秘密圖像共享方案。該方案把秘密圖像作為細(xì)胞自動(dòng)機(jī)的一個(gè)初始配置，通過(guò)利用二維n階可逆存貯細(xì)胞自動(dòng)機(jī)進(jìn)行分解成n份完備的影子圖像，再利用其逆n階二維細(xì)胞自動(dòng)機(jī)RCAM進(jìn)行反向迭代來(lái)重構(gòu)所共享的秘密圖像。在秘密圖像分發(fā)和秘密圖像重構(gòu)過(guò)程中，僅需簡(jiǎn)單的迭代操作，因此本文方案實(shí)現(xiàn)簡(jiǎn)單。另外，在本文方案中的訪問(wèn)結(jié)構(gòu)與一般的(k，n)門限訪問(wèn)結(jié)構(gòu)不同，其包含的合格的集合是全部參與者的連續(xù)全集，所以是一個(gè)(n，n)方案。分析表明，本方案是一個(gè)計(jì)算上安全的方案，并且是一個(gè)完備的秘密圖像(n，n)共享方案。

參考文獻(xiàn)

[1]Maor M Shamir.Visual Cryptography[J].Lecture Notes in Computer Science，1995:1—12.

[2]Blundo C，De Santis A，Naor M.Visual Cryptography for Grey Level Images[J].Information Processing Letters，2000，75(6):255—259.

[3]Hou Y C.Visual Cryptography for Color Images[J].Pattern Recognition，2003，36(7):1 619—1 629.

[4]Chang C C，Lin I C.A New (t，n) Threshold Image Hiding Scheme for Sharing a Secret Color Image[A].In: Proceedings of the International Conference on Communication Technology[C].2003，1:196—202.

[5]Chang C C，Chuang J C.An Image Intellectual Property Protection Scheme For Gray Level Images Using Visual Secret Sharing Strategy [J].Pattern Recognition Letters，2002，23(8):931—941.

[6]Yang C C，Chang T Y，Hwang M S.A(t，n) Multi—secret Sharing Scheme[J].Applied Mathematics and Computations，2004，151(2):483—490.

[7]Lukac R，Plataniotis K N.Color Image Secret Sharing[J].Electronics Letters，2004，40(9):529—531.

[8]呂超，余梅生，劉艷芳.基于拉格朗日插值多項(xiàng)式的秘密圖像共享方案[J].華中科技大學(xué)學(xué)報(bào)，2005，33(12):285—289.

[9]Wolfram S.Cryptography with Cellular Automata[A].Proc Advances in Cryptology (Crypto′85)[C].Lecture Notes in Computer Sciences，Berlin:Srpinger Verlag，1986，429—432.

[10]Wolfram S.Origins of Randomness in Physical System [J].Physical Review Letters，1985，55(5):449—452.

[11]Toffoli T，Margolus N.Invertible Cellular Automata:Areview.Physica D，1990:229—253.

[12]Martin del Rey A，Pereira Mateus J，Rodriguez Sanchez G.A Secret Sharing Scheme Based on Cellular Automata[J].Applied Mathematics and Computation，2005，170(2):1 356—1 364.

[13]潘志君，嚴(yán)壯志，張猛.一種基于元胞自動(dòng)機(jī)的圖像拼接方法[J].微計(jì)算機(jī)信息，2006，22(30)：245—247.

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文。