引用圖片激活擴散的信息加密方法

付熙徐，龔希章

(上海海洋大學 現代信息與教育技術中心，上海 201306)

(*通信作者電子郵箱xxfu@shou.edu.cn)

引用圖片激活擴散的信息加密方法

付熙徐，龔希章*

(上海海洋大學 現代信息與教育技術中心，上海 201306)

(*通信作者電子郵箱xxfu@shou.edu.cn)

對于加密編碼算法而言，復雜性、非線性和正確性是重要的特性。而人類對知識的處理正好具備這些特性，激活擴散理論則描述了人類對知識的處理方法。受到激活擴散理論的啟發，提出一種全新的基于引用圖片的信息編碼方法。該方法中，每個字符都用一個RGB分量的相對位置和偏移量表示，編碼數據則通過激活擴散的方法生成。同一個字符可以用不同的編碼表示，而相同的編碼也可以表示不同的字符。通過引入激活擴散模型，該方法創建了巨大的搜索空間，從而保證了解碼的復雜性；另一方面，該方法也減少了密文和明文間的相關性。

激活擴散；密碼編碼學；動態編碼；參照編碼

0 引言

創建安全的編碼系統一直是密碼編碼學的重要話題之一。安全編碼的本質就是使合法用戶能夠容易地獲得明文，而不讓非法入侵者輕易地破解密文。要達到這個目的通常需要在兩方面作出努力:一方面是增加密文破解的復雜度，另一方面是減少明文和密文之間的關聯性。目前計算機硬件發展迅速，很多復雜的加密算法都可以在可接受的時間內被破譯出來。而明文與密文的相關性通常也能通過對大量明文/密文對的分析被發現。幸運的是我們能從人的認知系統得到一些啟發，得到一些好的解決方案。

我們所處的自然環境是一個極其復雜的系統，復雜到即使是最先進的機器也無法將其表示和存儲，更遑論枚舉每一個元素，但人類卻能自如地認識和使用這個系統。人們建立了大量系統試圖模擬人的認知[1]。激活擴散理論的產生正是為了解釋人在自然系統中的推理過程[2-5]。該模型中知識和場景通常很復雜，沒有合理的背景知識，推理者不可能得到正確的答案。因此，以背景知識作為密碼，用激活擴散模型進行加密，再通過重復執行激活擴散的過程來解密是一種合適的密碼編碼方法。

本文的研究是建立一個激活擴散模型用于編碼數據，模型中使用位圖文件作為密鑰，通過激活擴散對字符進行加密，解密時需要用到加密時的位圖文件。

1 相關工作和研究動機

1.1 加密方法

目前研究者已經提出了大量的加密算法，并對這些算法進行了形式化分析。在文獻[6]中攻擊被分為僅有密文攻擊、已知明文攻擊和選擇明文攻擊，而防止這些攻擊最有效的方法之一就是增加破解的復雜度。

基于此原則，研究者提出了兩類算法：一類是基于邏輯計算的算法，如典型MD5算法[7]。MD5算法通過邏輯計算使得密文理論上要極長時間才能被破解，然而隨著計算機性能的提升，該算法已可以在數小時內被破解[8]。另一類算法是基于替換的算法[9]，這類算法的最大問題就是可以通過明文與密文的關系猜出明文[10]。

演化編碼是一種新的編碼方法，該類方法試圖用不同的方法編碼各個字符，這是一種好的趨勢，然而目前的方法主要還是已有算法的組合[11]。另一種值得借鑒的是隱寫方法，該類方法通常使用大的媒體文件隱藏少量的秘密信息[12-14]。

1.2 激活擴散理論

激活擴散理論首先由心理學和語義處理領域的科學家提出[2]，而激活擴散模型目前已在復雜語義處理領域如推薦系統中得到應用[5]。該理論適合對復雜系統建模，最近就有相關工作用激活擴散模型對復雜的故事進行建模和推理[4]。激活擴散編碼的原理如圖1所示。

圖1 通過激活擴散編碼數據

如圖1所示，輸入數據被送到表示不同函數的節點中進行編碼。這些函數對輸入進行拆分、計算、替換或重排列等操作后將輸出送入下一個節點，直至計算完成輸出密文。由于固定的輸入和背景知識(密鑰)會獲取固定的輸出，因此可以被看作是對稱加密的過程。

1.3 本文研究動機

一張圖片通常有數十到上百萬個像素，每個像素都可以表示為RGB三個分量，對于24位的位圖圖像，每一個分量值都可以用于對應一個字符。即使知道了位圖的形狀要枚舉所有可能的位圖在計算上都是不可行的，因此圖片是適合作為密鑰的。而一種簡易的方式就是用字符的ASCII值在圖片中的位置和分量表示字符，通過激活擴散算法搜索。

2 算法與評價

2.1 用索引位置和偏移表示字符

位圖可以用像素表示，而每個像素的顏色都可以用3個分量RGB來表示。對于一幅24位位圖來說，每個分量都是8位，和字符的ASCII碼位數相同。圖2表示了小寫字母a在圖片Lenna中的分布。

圖2 小寫字母“a”在圖像中的分布

如圖2所示，圖(b)中的點表示該點所在位置的像素有某個分量值與小寫字母a的ASCII碼相同，不同顏色的點對應匹配的分量。顯然，同一個字符可以在一幅圖像中找到多個對應的分量。

很顯然，一個字符可以用三元組〈X,Y,C〉表示，其中X和Y是像素的坐標，C是匹配的分量。由于圖像可能較大，因此X和Y的值也可能較大，對于較長的文件，密文可能很長。因此，可以采用相對位置代替絕對位置，令Xi為表示第i個字符的像素的X軸位置，Yi為該像素Y軸位置，Xi-1和Yi-1分別為上一個字符的對應像素位置。則第i個字符的相對位置(ΔXi，ΔYi)如下所示：

ΔXi=Xi-Xi-1

(1)

ΔYi=Yi-Yi-1

(2)

為進一步減少搜索的范圍并防止圖像中沒有與字符匹配的分量的極端情況，本文引入了偏移量的概念。如式(3)所示，只要分量與字符ASCII值小于偏移量Dev即可，而偏移量在激活擴散的過程中可以逐漸增大。

|P(x,y).C-ASCII(S)|≤Dev

(3)

引入偏移量后，字符可用四元組〈ΔX, ΔY,C,D〉表示，其中D是偏移量，如式(4)所示。

D=P(x,y).C-ASCII(S)

(4)

對文本信息編碼后的密文表示如圖3所示。

圖3 編碼后的密文表示

如圖3所示，頭部注明起始搜索位置和表示一個字符需要的長度，文件體中保存每個字符的加密表示，包括相對位置ΔX，ΔY、分量C和偏移D。為了提高密文的安全性，頭部也可以不和密文放在一起。

2.2 用激活擴散模型編碼數據

可用如圖4所示的激活擴散模型對字符進行編碼。

圖4 用于編碼的激活擴散模型

如圖4所示，模型由4個節點組成:

1)輸入節點獲取輸入的文本，將字符拆分出來，并將字符和它的起始搜索位置發給定位節點，如果輸入已經結束，該節點還將結束符發給編碼節點。

2)尋址節點負責搜索與字符匹配的分量位置，并將分量的位置、名稱和偏移量輸出給編碼節點。在搜索的過程中，如未找到匹配分量，尋址節點還向偏移節點發送偏移增大請求以提高允許的偏移量。字符找到對應位置時，該節點還向輸入節點索要下一個字符。

3)偏移節點的作用較為簡單，只需接收尋址節點的請求并發送改變后的偏移量給尋址節點即可。

4)編碼節點負責將獲得的信息編碼成密文的最終形式，在接到輸入節點的結束指令后等待當前編碼完成后結束編碼輸出密文。

這個過程對應的加密算法如下：

輸入 字符串S，位圖B，起始搜索位置p(x,y)；

輸出 密文編碼E。

步驟1 將起始位置和一個字符的密文長度寫入E作為頭部。

步驟2 對于每一個S中的字符c進行以下步驟編碼：

步驟2.1 重置相對位移Δx,Δy、搜索范圍變量i,j和允許偏移量dev為0。

步驟2.2 搜索像素p周圍坐標在 ([x-i,x+i],[y-i,y+i])之間的點的RGB分量，如果找到像素的某一個分量符合顏色值與字符c的ASCII碼之差的絕對值小于等于允許偏移量dev，則記錄下像素的位置Δx、Δy,分量名稱(R,G或B)以及顏色值與字符c的ASCII碼之差d，將其輸出到E，并以該像素位置為新的起始搜索位置(x,y)編碼下一個字符。如果未找到符合要求的字符則擴大搜索范圍(i=i+1)和增大允許偏移量(dev=dev+1)繼續搜索直至搜索到符合要求的分量為止。

解密的算法較加密更為簡單，只需根據密文找到對應的分量和偏移量即可計算出字符。算法如下：

輸入 密文E,密鑰位圖B；

輸出 明文字符串S。

步驟1 讀入密文頭部，獲取起始搜索位置p(x,y)。

步驟2 根據頭部信息用如下步驟逐個處理加密元組直至密文尾部：

步驟2.1 提取元組中相對位置Δx、Δy，分量c和偏移d；

步驟2.2 獲取像素位置(x+Δx,y+Δy)，取得c對應分量的顏色值color;

步驟2.3 獲取字符ASCII碼:asc=color+d;

步驟2.4 通過ASCII碼得到字符并加入明文S;

步驟2.5 以當前像素位置(x+Δx,y+Δy)作為下個字符搜索起始位置。

2.3 評價與標準

評價加密算法有很多種標準，但所有標準都分為兩個部分：一部分是正常的加密解密需要正確高效地完成，另一部分是沒有密鑰的攻擊者不能輕易地獲取全部或部分明文。若明文和密文間無任何相關關系則可以稱該加密算法是絕對安全的。衡量明文和密文關系的最著名標準就是香農提出的信息熵[8]。

令T表示明文，R表示明文在密文中的表示(在本文中為對應的四元組)，Pi表示第i個字符出現的概率，Pj表示第j個表示出現的概率，Pij表示第i個字符對應第j個表示出現的概率。若式(5)成立則表示明文與密文無關。

(5)

由于事實上式(5)不可能為0，本文用明文自信息和明文與密文互信息之差評價明文和密文之間的不相關性，如式(6)所示。

(6)

D值越大證明密文和明文的相關性越小。易證明文和自身之間以及明文和一對一替換密文之間的D值都為0。

另一個評價標準就是破解的復雜性，根據前文的描述，顯然通過枚舉的方法是無法猜測出用于加密的圖片的。

3 實驗和結果分析

3.1 實驗設計

在本文的實驗中：一篇包含有約66 000字符的英文文本被用作明文；兩張不同的圖像被用作知識環境，其中一張是常用圖像庫中的Lenna(512×512)，另一張是隨機生成的600×600的圖片。第一個字符的初始搜索位置均為(100,100)。文本的字符分布如表1所示。

表1 實驗文本的字符分布情況

經計算，文本中字符的平均熵為3.068。

3.2 實驗結果

對應不同字符的表示數目情況如表2所示。表2中：RFlenna是用圖片“Lenna”作為知識背景時各字符對應的密文表示數目；RFrandom是用隨機生成的圖片作為知識背景時各字符對應的密文表示數目。從該表中可以看出，一個字符可以對應多種加密表示。另一方面，兩個實驗中平均每個表示對應的字符數也分別為3.107和6.954。根據表2可以得知字符和其編碼之間沒有對應關系，明文和密文間的聯系也很弱。

為了更好地說明明文與密文間的無關性，可以用前文中介紹的基于信息熵的方法進行評估。在兩個實驗中，密文與明文的互信息分別為1.948和1.274，根據式(6)計算出信息熵下降值D分別為1.12和1.794，明顯好于直接替換的情況。

編碼一個字符的實際復雜性S可以用式(7)表示：

S≤(|X|×2+1)×(|Y|×2+1)×3

(7)

統計搜索空間內完成匹配的字符數量的結果如表3所示，可以看出，盡管圖像中有海量的候選值，但絕大多數字符還是在搜索了不到50個分量時就完成了編碼。

表2 各字符對應的表示數目

表3 編碼搜索空間情況

4 結語

受到激活擴散理論的啟發，本文提出了一種新的加密編碼方法。該方法使用圖片作為密鑰，通過相對位置索引編碼字符。本文分析表明該算法是正確的、非線性的，可以快速解密，明文和密文的關聯度低，而且無法通過枚舉的方式攻擊。最后實驗結果也顯示該加密算法事實上是高效的。

)

[1]LENATDB.CYC:alarge-scaleinvestmentinknowledgeinfrastructure[J].CommunicationsoftheACM, 1995, 38(11): 33-38.

[2]ANDERSONAR,PIROLLIPL.Spreadofactivation[J].JournalofExperimentalPsychology:Learning,Memory,andCognition, 1984, 10(4): 791-798.

[3]COLLINSAM,LOFTUSEF.Aspreading-activationtheoryofsemanticprocessing[J].PsychologicalReview, 1975, 82(6): 407-428.

[4]FUX,WEIH.Problemsolvingbysoakingtheconceptnetwork[J].ComputerScienceandInformationSystems, 2011, 8(3): 761-778.

[5]YOLANDAB.Exploringsynergiesbetweencontent-basedfilteringandspreadingactivationtechniquesinknowledge-basedrecommendersystems[J].InformationSciences, 2011, 181(21): 4823-4846.

[6]DIFFIEW,HELLMANM.Newdirectionsincryptography[J].IEEETransactionsonInformationTheory, 1976, 22(6): 644-654.

[7]THOMPSONE.MD5collisionsandtheimpactoncomputerforensics[J].DigitalInvestigation, 2005, 2(1): 36-40.

[8]LIANGJ,LAIXJ.ImprovedcollisionattackonhashfunctionMD5 [J].JournalofComputerScienceandTechnology， 2007, 22(1): 79-87.

[9]KAVUTS.Resultsonrotation-symmetricS-boxes[J].InformationSciences, 2012, 201: 93-113.

[10]BORISSOVYL,LEEMH.Boundsonkeyappearanceequivocationforsubstitutionciphers[J].IEEETransactionsonInformationTheory, 2007, 53(6): 2294-2296.

[11]WANGC,ZHANGHG,LIUL.EvolutionarycryptographytheorybasedgeneratingmethodforasecureKoblitzellipticcurveanditsimprovementbyahiddenMarkovmodels[J].ScienceChinaInformationSciences, 2012, 55(4): 911-920.

[12]KUOW.Securemodulusdatahidingscheme[J].KSIITransactionsonInternetandInformationSystems, 2013, 7(3): 600-612.

[13]QINC,CHANGCC,HSUTJ.Effectivefragilewatermarkingforimageauthenticationwithhigh-qualityrecoverycapability[J].KSIITransactionsonInternetandInformationSystems, 2013, 7(11): 2941-2956.

[14]FENGB,WANGZ,WANGD,etal.Anovel,reversible,ChinesetextinformationhidingschemebasedonlookaliketraditionalandsimplifiedChinesecharacters[J].KSIITransactionsonInternetandInformationSystems, 2014, 8(1): 269-281.

[15]SHANNONCE.Communicationtheoryofsecrecysystems[J].BellSystemTechnicalJournal, 1949, 28(4): 656-715.

FU Xixu, born in 1981, Ph.D., engineer.His research interests include artificial intelligence, knowledge system, cognitive computing, data mining.

GONG Xizhang, born in 1963, M.S., senior engineer.His research interests include information management and system.

Spreading activation method to encrypt data with images as references

FU Xixu, GONG Xizhang*

(InstituteofInformationandEducationTechnology,ShanghaiOceanUniversity,Shanghai201306,China)

Complexity, non-linearity and correctness are important features in cryptography.Human beings’s knowledge processing just has these features.Spreading activation theory describes how human beings deal with complex and non-linear knowledge correctly.Inspired by the spreading activation theory, a new method for encoding data with references to a bitmap was advanced.In this method, a symbol was represented with a deviation range and a relative position of a contour.Encrypted data was generated by using a spreading activation process.The same symbol can be represented in different code, and the same code can represent different symbols too.This method can ensure the complexity of deciphering by implementing the spreading activation model to create a mass potential searching space.On the other hand, it can also reduce the relativity between the cipher text and the plaintext.

spreading activation; cryptography; dynamic encryption; referential encryption

2016- 08- 22;

2016- 09- 07。

付熙徐(1981—),男,江西撫州人,工程師,博士,CCF會員,主要研究方向:人工智能、知識系統、認知計算、數據挖掘;龔希章(1963—),男,上海人,高級工程師,碩士,主要研究方向:信息管理與信息系統。

1001- 9081(2017)02- 0408- 04

10.11772/j.issn.1001- 9081.2017.02.0408

TP309.7

A