付熙徐，龔希章

(上海海洋大學(xué) 現(xiàn)代信息與教育技術(shù)中心，上海 201306)

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

引用圖片激活擴(kuò)散的信息加密方法

付熙徐，龔希章*

(上海海洋大學(xué) 現(xiàn)代信息與教育技術(shù)中心，上海 201306)

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

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

激活擴(kuò)散；密碼編碼學(xué)；動(dòng)態(tài)編碼；參照編碼

0 引言

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

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

本文的研究是建立一個(gè)激活擴(kuò)散模型用于編碼數(shù)據(jù)，模型中使用位圖文件作為密鑰，通過激活擴(kuò)散對(duì)字符進(jìn)行加密，解密時(shí)需要用到加密時(shí)的位圖文件。

1 相關(guān)工作和研究動(dòng)機(jī)

1.1 加密方法

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

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

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

1.2 激活擴(kuò)散理論

激活擴(kuò)散理論首先由心理學(xué)和語義處理領(lǐng)域的科學(xué)家提出[2]，而激活擴(kuò)散模型目前已在復(fù)雜語義處理領(lǐng)域如推薦系統(tǒng)中得到應(yīng)用[5]。該理論適合對(duì)復(fù)雜系統(tǒng)建模，最近就有相關(guān)工作用激活擴(kuò)散模型對(duì)復(fù)雜的故事進(jìn)行建模和推理[4]。激活擴(kuò)散編碼的原理如圖1所示。

圖1 通過激活擴(kuò)散編碼數(shù)據(jù)

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

1.3 本文研究動(dòng)機(jī)

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

2 算法與評(píng)價(jià)

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

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

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

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

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

ΔXi=Xi-Xi-1

(1)

ΔYi=Yi-Yi-1

(2)

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

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

(3)

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

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

(4)

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

圖3 編碼后的密文表示

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

2.2 用激活擴(kuò)散模型編碼數(shù)據(jù)

可用如圖4所示的激活擴(kuò)散模型對(duì)字符進(jìn)行編碼。

圖4 用于編碼的激活擴(kuò)散模型

如圖4所示，模型由4個(gè)節(jié)點(diǎn)組成:

1)輸入節(jié)點(diǎn)獲取輸入的文本，將字符拆分出來，并將字符和它的起始搜索位置發(fā)給定位節(jié)點(diǎn)，如果輸入已經(jīng)結(jié)束，該節(jié)點(diǎn)還將結(jié)束符發(fā)給編碼節(jié)點(diǎn)。

2)尋址節(jié)點(diǎn)負(fù)責(zé)搜索與字符匹配的分量位置，并將分量的位置、名稱和偏移量輸出給編碼節(jié)點(diǎn)。在搜索的過程中，如未找到匹配分量，尋址節(jié)點(diǎn)還向偏移節(jié)點(diǎn)發(fā)送偏移增大請(qǐng)求以提高允許的偏移量。字符找到對(duì)應(yīng)位置時(shí)，該節(jié)點(diǎn)還向輸入節(jié)點(diǎn)索要下一個(gè)字符。

3)偏移節(jié)點(diǎn)的作用較為簡(jiǎn)單，只需接收尋址節(jié)點(diǎn)的請(qǐng)求并發(fā)送改變后的偏移量給尋址節(jié)點(diǎn)即可。

4)編碼節(jié)點(diǎn)負(fù)責(zé)將獲得的信息編碼成密文的最終形式，在接到輸入節(jié)點(diǎn)的結(jié)束指令后等待當(dāng)前編碼完成后結(jié)束編碼輸出密文。

這個(gè)過程對(duì)應(yīng)的加密算法如下：

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

輸出 密文編碼E。

步驟1 將起始位置和一個(gè)字符的密文長(zhǎng)度寫入E作為頭部。

步驟2 對(duì)于每一個(gè)S中的字符c進(jìn)行以下步驟編碼：

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

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

解密的算法較加密更為簡(jiǎn)單，只需根據(jù)密文找到對(duì)應(yīng)的分量和偏移量即可計(jì)算出字符。算法如下：

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

輸出 明文字符串S。

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

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

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

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

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

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

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

2.3 評(píng)價(jià)與標(biāo)準(zhǔn)

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

令T表示明文，R表示明文在密文中的表示(在本文中為對(duì)應(yīng)的四元組)，Pi表示第i個(gè)字符出現(xiàn)的概率，Pj表示第j個(gè)表示出現(xiàn)的概率，Pij表示第i個(gè)字符對(duì)應(yīng)第j個(gè)表示出現(xiàn)的概率。若式(5)成立則表示明文與密文無關(guān)。

(5)

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

(6)

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

另一個(gè)評(píng)價(jià)標(biāo)準(zhǔn)就是破解的復(fù)雜性，根據(jù)前文的描述，顯然通過枚舉的方法是無法猜測(cè)出用于加密的圖片的。

3 實(shí)驗(yàn)和結(jié)果分析

3.1 實(shí)驗(yàn)設(shè)計(jì)

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

表1 實(shí)驗(yàn)文本的字符分布情況

經(jīng)計(jì)算，文本中字符的平均熵為3.068。

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

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

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

編碼一個(gè)字符的實(shí)際復(fù)雜性S可以用式(7)表示：

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

(7)

統(tǒng)計(jì)搜索空間內(nèi)完成匹配的字符數(shù)量的結(jié)果如表3所示，可以看出，盡管圖像中有海量的候選值，但絕大多數(shù)字符還是在搜索了不到50個(gè)分量時(shí)就完成了編碼。

表2 各字符對(duì)應(yīng)的表示數(shù)目

表3 編碼搜索空間情況

4 結(jié)語

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

)

[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會(huì)員,主要研究方向:人工智能、知識(shí)系統(tǒng)、認(rèn)知計(jì)算、數(shù)據(jù)挖掘;龔希章(1963—),男,上海人,高級(jí)工程師,碩士,主要研究方向:信息管理與信息系統(tǒng)。

1001- 9081(2017)02- 0408- 04

10.11772/j.issn.1001- 9081.2017.02.0408

TP309.7

A