謝 冬， 郭東升， 葉四軍

(1.安徽師范大學(xué) 計(jì)算機(jī)與信息學(xué)院，安徽 蕪湖 241003;2.安徽省新蕪經(jīng)濟(jì)開發(fā)區(qū) 管理委員會(huì)，安徽 蕪湖 241000)

引 言

壓縮感知理論(Compressed Sensing,CS)是由E.J.Candes、J.Romberg、T.Tao和D.L.Donoho等科學(xué)家于2004年提出[1]，其已被應(yīng)用于各個(gè)相關(guān)領(lǐng)域，如圖像處理[2]、醫(yī)學(xué)成像[3]、地質(zhì)勘探[4]、密碼學(xué)[5]以及人臉識(shí)別[6]當(dāng)中。CS的核心思想基于以下兩點(diǎn)：(1)信號(hào)的可稀疏化結(jié)構(gòu)特征。傳統(tǒng)意義上的Shannon信號(hào)表示方法只利用了最少采樣信號(hào)的先驗(yàn)信息[7]，并沒有考慮到信號(hào)的稀疏結(jié)構(gòu)。(2)信號(hào)的可壓縮特性。在信號(hào)稀疏性的基礎(chǔ)上，以遠(yuǎn)低于Nyquist采樣率的隨機(jī)采樣來獲取信號(hào)的離散樣本，然后通過非線性優(yōu)化算法來重構(gòu)信號(hào)[8]。

測(cè)量矩陣在CS中的數(shù)據(jù)采樣和信號(hào)重建步驟都起著至關(guān)重要的作用，它的性質(zhì)幾乎決定了原始信號(hào)的全局信息能否保存下來[1,7,8]。測(cè)量矩陣的構(gòu)造方法主要分為隨機(jī)性構(gòu)造[9]和確定性構(gòu)造[10]兩種。常用的隨機(jī)測(cè)量矩陣有高斯隨機(jī)測(cè)量矩陣[11]、貝努利隨機(jī)測(cè)量矩陣[12]等，其特點(diǎn)是元素都是獨(dú)立地服從某種隨機(jī)分布。隨機(jī)測(cè)量矩陣具有不確定性，且浪費(fèi)存儲(chǔ)資源，使得其實(shí)際應(yīng)用受到限制。在保證準(zhǔn)確重構(gòu)的前提下，確定性構(gòu)造方法可以大大地降低系統(tǒng)的存儲(chǔ)空間。Haupt等人提出托普利茲矩陣[13]與循環(huán)矩陣[14]兩個(gè)確定性測(cè)量矩陣的構(gòu)造方法,它們是通過有限個(gè)確定性向量循環(huán)構(gòu)造而成。Devore提出多項(xiàng)式確定性測(cè)量矩陣[10]，其利用多項(xiàng)式系數(shù)在有限域中遍歷取值的結(jié)果來構(gòu)造矩陣。然而，與隨機(jī)測(cè)量矩陣相比，確定性測(cè)量矩陣在重建效果上存在一定差距，同時(shí)對(duì)信號(hào)的稀疏度也有較高要求。

CS不但具有壓縮特性，而且具有一定的加密屬性[15]。但是，本文的目標(biāo)并不是運(yùn)用壓縮感知來構(gòu)造密碼算法，而是從一個(gè)相反的角度，即運(yùn)用常見的密碼算法(如分組密碼DES與AES算法)來構(gòu)造CS的測(cè)量矩陣。具體地，首先運(yùn)用這些密碼算法產(chǎn)生偽隨機(jī)序列，然后將這些偽隨機(jī)序列按照一定的方法依次填充到測(cè)量矩陣之中。其次，運(yùn)用密碼算法構(gòu)造的壓縮感知測(cè)量矩陣來壓縮圖像信號(hào)得到測(cè)量圖像。最后，通過經(jīng)典的OMP算法來重構(gòu)原始圖像[16]。實(shí)驗(yàn)結(jié)果表明，與傳統(tǒng)的測(cè)量矩陣(如高斯矩陣、混沌矩陣)一樣，基于DES、AES以及M序列等密碼算法產(chǎn)生的測(cè)量矩陣具有較好的重構(gòu)效果。

1 基礎(chǔ)理論

1.1 壓縮感知

基于自然界大多數(shù)信號(hào)可稀疏化的特點(diǎn)，壓縮感知理論突破了傳統(tǒng)的尼奎斯特采樣定理，在保證完美重構(gòu)的前提下，以更小的采樣率來采樣信號(hào)，在采樣的同時(shí)就拋棄了冗余信息。其具體過程如下：

設(shè)信號(hào)α∈Rn，在某組正交基Ψ∈R(n×n)下是稀疏的，即α=Ψx，其中x∈Rn是稀疏的。若向量x中有k個(gè)非零實(shí)體，則稱x是k稀疏的。可用測(cè)量矩陣Φ∈R(m×n)(m

Y=Φα=ΦΨx=Ax。

(1)

其重構(gòu)可用最小化l0范數(shù)來求解：

(2)

當(dāng)測(cè)量矩陣A滿足約束等距特性時(shí)[17]，可以將(2)式等價(jià)地轉(zhuǎn)換為最小化l1范數(shù)問題：

(3)

對(duì)于最小化l1范數(shù)問題，已有相關(guān)算法對(duì)其求解，如OMP算法[16]。

1.2 常見的密碼算法

DES是一種常用的分組密碼算法，其明文分組、密文以及密鑰均為64位(有效密鑰長(zhǎng)為56位，其中密鑰有8位是奇偶校驗(yàn)碼)。其核心思想是采用Feistel網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行16輪迭代，從而達(dá)到混淆與擴(kuò)散的效果。為了克服DES短密鑰的缺陷，NIST于2001年發(fā)布了AES算法。AES的分組長(zhǎng)度為128位，密鑰長(zhǎng)度分別為128位、192位、256位。本文采用128位密鑰的AES算法，共需10輪迭代運(yùn)算。

線性反饋移位寄存器是構(gòu)造序列密碼體制的常用工具。M序列是指能夠達(dá)到線性反饋移位寄存器最大周期的序列。若n1為移存器級(jí)數(shù)，則最大周期為2n1-1。一個(gè)M序列由線性遞推式與初始狀態(tài)兩個(gè)因素決定。

2 基于密碼算法的測(cè)量矩陣構(gòu)造

本文將基于分組密碼算法(DES與AES)與序列密碼算法，來構(gòu)造CS的測(cè)量矩陣。通過這些密碼算法產(chǎn)生偽隨機(jī)序列，然后將這些偽隨機(jī)序列按照一定的規(guī)則依次填充到測(cè)量矩陣之中。

2.1 AES、DES算法構(gòu)造的隨機(jī)測(cè)量矩陣

基于分組密碼的測(cè)量矩陣構(gòu)造方法可通過如下形式進(jìn)行：

①根據(jù)測(cè)量矩陣的維數(shù)，隨機(jī)產(chǎn)生等長(zhǎng)的分組密碼密文。若測(cè)量矩陣A為m×n階矩陣，則需要隨機(jī)選擇分組密碼的密鑰以及長(zhǎng)度為mn的明文比特，通過分組加密產(chǎn)生mn個(gè)密文比特輸出。

②將生成的隨機(jī)密文比特在矩陣中依次排列，如果超過A中行的長(zhǎng)度，就下移到下一行，不斷填充，直至A填滿為止，如圖1所示。

圖1 基于DES或AES構(gòu)造測(cè)量矩陣方法

2.2 M序列構(gòu)造的隨機(jī)測(cè)量矩陣

基于序列密碼體制的測(cè)量矩陣構(gòu)造方法可通過如下形式進(jìn)行：

①根據(jù)測(cè)量矩陣的維數(shù)，隨機(jī)產(chǎn)生等長(zhǎng)的M序列。若測(cè)量矩陣A為m×n階矩陣，則需要隨機(jī)選擇一個(gè)可產(chǎn)生M序列的n1級(jí)非線性反饋移位寄存器f(x)，其中n滿足2n1≥mn+1。

②隨機(jī)選擇初始狀態(tài)s0，由f(x)與s0產(chǎn)生mn個(gè)比特位。

③將生成的隨機(jī)比特串在矩陣A中依次排列，如果超過A中行的長(zhǎng)度，就下移到下一行，不斷填充，直至A填滿為止。

3 實(shí)驗(yàn)分析

3.1 正確性

選擇三個(gè)256×256的原始圖像，分別是(a)海螺、(g)赫本以及(m)青竹。選用的測(cè)量矩陣分別是標(biāo)準(zhǔn)的高斯隨機(jī)矩陣、Logistic混沌矩陣以及本文提出的DES測(cè)量矩陣、AES測(cè)量矩陣與M序列測(cè)量矩陣。其中Logistic混沌矩陣中初始值為x0=0.2915826302。產(chǎn)生M序列測(cè)量矩陣的反饋移存器的本原多項(xiàng)式系數(shù)是

[1000000000000001]，初始值為[0000000000000001]。在電碼本工作模式(ECB)下，隨機(jī)選擇DES與AES的明文信息。DES測(cè)量矩陣和AES測(cè)量矩陣的具體參數(shù)如表1和表2所示。

表1 構(gòu)造DES測(cè)量矩陣的具體參數(shù)(16進(jìn)制)

表2 構(gòu)造AES測(cè)量矩陣的具體參數(shù)

發(fā)送端將原始圖像通過壓縮感知進(jìn)行壓縮加密處理，接收端運(yùn)用OMP重構(gòu)算法對(duì)密文圖像進(jìn)行解密重構(gòu)，得到的圖像如圖2所示。

圖2 不同測(cè)量矩陣的重構(gòu)效果(a),(g),(m)原始圖像；(b),(h),(n)M序列測(cè)量矩陣恢復(fù)圖像；(c),(i),(o)DES測(cè)量矩陣恢復(fù)圖像；(d),(j),(p)AES測(cè)量矩陣恢復(fù)圖像；(e),(k),(q)高斯隨機(jī)矩陣恢復(fù)圖像；(f),(l),(r)Logistic混沌矩陣恢復(fù)圖像。

從視覺的角度可以看出，基于分組密碼與序列密碼體制構(gòu)造的矩陣與傳統(tǒng)的測(cè)量矩陣一樣，均能被用作壓縮感知的測(cè)量矩陣。為了定性的表示圖像的恢復(fù)性能，本文通過峰值信噪比(Peak Signal to Noise Ratio,PSNR)來評(píng)價(jià)圖像重構(gòu)的效果。PSNR的公式計(jì)算如下：

PSNR=10×log10((2n-1)2/MSE),

(4)

其中n是每個(gè)采樣值的比特?cái)?shù)，MSE是原圖像與處理圖像之間均方誤差。由表3可知，M序列、DES算法、AES算法、Logistic混沌系統(tǒng)以及高斯分布產(chǎn)生的隨機(jī)測(cè)量矩陣，都具有較好的重構(gòu)圖像的能力。

表3 不同測(cè)量矩陣加密后恢復(fù)圖像的PSNR值

3.2 密鑰的敏感性

為了防止敵手的猜測(cè)攻擊，密碼系統(tǒng)應(yīng)當(dāng)具備密鑰敏感性。在提出的方案中，消息發(fā)送端與接收端均運(yùn)用密鑰K產(chǎn)生DES測(cè)量矩陣、AES測(cè)量矩陣以及M序列測(cè)量矩陣來加解密圖像。假設(shè)明文是正確性實(shí)驗(yàn)中的(m)青竹，DES密鑰是KDES=0E6A03CE647D513C。若公開信道存在一個(gè)攻擊者，猜測(cè)的密鑰KDES*與真實(shí)值KDES差2比特，即KDES*=0E6A03CE647D513E。其重構(gòu)效果如圖3所示。圖3同時(shí)展示了若AES測(cè)量矩陣與M序列測(cè)量矩陣改變密鑰1bit時(shí)的重構(gòu)效果。結(jié)果表明M序列測(cè)量矩陣、DES測(cè)量矩陣以及AES測(cè)量矩陣三種加密算法具備密鑰敏感性。

圖3 不同算法的真假密鑰重構(gòu)圖像的效果：(a)-(c)M序列、DES算法以及AES算法密鑰為假密鑰的重構(gòu)圖；(d)-(f)M序列、DES算法以及AES算法密鑰為真密鑰的重構(gòu)圖。

3.3 測(cè)量次數(shù)對(duì)PSNR影響

在壓縮感知理論中，測(cè)量次數(shù)影響著重構(gòu)效果。本實(shí)驗(yàn)選擇“青竹”作為明文，運(yùn)用M序列、DES算法以及ECB、CBC、OFB這三種模式的AES算法來研究測(cè)量次數(shù)對(duì)PSNR的影響。針對(duì)明文“青竹”，采用4.1節(jié)的參數(shù)，實(shí)驗(yàn)結(jié)果表明密碼學(xué)測(cè)量矩陣的重構(gòu)效果最好的是DES測(cè)量矩陣，AES次之，M序列相對(duì)最差。但總體說來，隨著測(cè)量次數(shù)的增大，PSNR整體逐步上升。

圖4 測(cè)量次數(shù)對(duì)重構(gòu)效果的影響

4 結(jié) 論

與傳統(tǒng)的基于壓縮感知來構(gòu)造密碼方案不同，本文基于對(duì)稱密碼算法AES與DES以及M序列等密碼學(xué)本原，提出了一種構(gòu)造壓縮感知測(cè)量矩陣的方法。其主要的理論依據(jù)是這些密碼學(xué)本原都可以產(chǎn)生偽隨機(jī)的序列，若我們將這些偽隨機(jī)序列填充到矩陣?yán)铮仃嚵信c列之間的相關(guān)性均較低，其滿足壓縮感知測(cè)量矩陣的基本特征。實(shí)驗(yàn)結(jié)果表明，提出的密碼學(xué)測(cè)量矩陣對(duì)圖像信號(hào)具有良好的重構(gòu)能力。