基于密碼算法的壓縮感知測量矩陣構造

謝 冬， 郭東升， 葉四軍

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

引 言

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

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

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

1 基礎理論

1.1 壓縮感知

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

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

Y=Φα=ΦΨx=Ax。

(1)

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

(2)

當測量矩陣A滿足約束等距特性時[17]，可以將(2)式等價地轉換為最小化l1范數(shù)問題：

(3)

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

1.2 常見的密碼算法

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

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

2 基于密碼算法的測量矩陣構造

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

2.1 AES、DES算法構造的隨機測量矩陣

基于分組密碼的測量矩陣構造方法可通過如下形式進行：

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

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

圖1 基于DES或AES構造測量矩陣方法

2.2 M序列構造的隨機測量矩陣

基于序列密碼體制的測量矩陣構造方法可通過如下形式進行：

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

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

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

3 實驗分析

3.1 正確性

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

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

表1 構造DES測量矩陣的具體參數(shù)(16進制)

表2 構造AES測量矩陣的具體參數(shù)

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

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

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

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

(4)

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

表3 不同測量矩陣加密后恢復圖像的PSNR值

3.2 密鑰的敏感性

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

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

3.3 測量次數(shù)對PSNR影響

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

圖4 測量次數(shù)對重構效果的影響

4 結 論

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