基于QR碼模塊邊界偏移的信息植入與提取方法

(1. 福建工程學(xué)院 信息科學(xué)與工程學(xué)院，福建 福州 350118；2. 福建師范大學(xué) 數(shù)學(xué)與信息學(xué)院，福建 福州 350007)

隨著移動智能終端和互聯(lián)網(wǎng)技術(shù)的迅猛發(fā)展，二維條碼以空前的速度占領(lǐng)了信息時代的至高點。作為二維條碼技術(shù)的典型代表，快速響應(yīng)(quick response，QR)碼被廣泛應(yīng)用于各行各業(yè)，從移動支付[1]到身份認證[2-3]。人們在享受QR碼帶來的便捷服務(wù)時，對敏感信息的安全問題卻感到不安，因為任何人都可以通過遵循開放標準的解碼軟件輕松獲取標準QR碼的編碼信息。因此，如何實現(xiàn)QR碼編碼信息的篡改檢測，是一個值得研究的問題，具有重要的社會和經(jīng)濟價值。

與直接加密編碼信息或?qū)⒄J證信息與編碼信息一同編碼的傳統(tǒng)方法不同，在基于QR碼模塊邊界多方向偏移的信息植入與提取方法中，編碼信息的數(shù)字簽名將通過所提出的植入方法與QR碼一同分發(fā)，并在解碼的同時被提取出來用于編碼信息的篡改檢測。

1 國內(nèi)外相關(guān)工作

1.1 QR碼

QR碼是目前應(yīng)用最為廣泛的二維條碼技術(shù)之一，具有較高的編碼容量、較小的打印尺寸、豐富的編碼字符集、強大的自糾錯能力、任意角度可讀等特點。盡管QR碼具有諸多優(yōu)點，但其遵循開放設(shè)計原則因而沒有對編碼信息的安全性做出明確規(guī)定，加之制作和傳播成本極為低廉，使其常常成為不法分子的攻擊目標。文獻[4]深入分析了與QR碼有關(guān)的信息安全問題。

1.2 現(xiàn)狀分析

針對QR碼的信息安全問題，國內(nèi)外學(xué)者紛紛給出了不同的解決方案。其中，傳統(tǒng)方法包括利用各種加密技術(shù)對編碼信息進行加、解密[5-8]以確保編碼信息的安全性，該方法雖有效，但需要對終端用戶(即執(zhí)行解碼操作的用戶)進行身份認證。讓編碼信息不可見雖可以實現(xiàn)其認證功能，卻有悖認證信息公開的原則。另外有一類問題的關(guān)注點是實現(xiàn)與QR碼所關(guān)聯(lián)對象的認證[9]，而非研究涉及的QR碼自身編碼信息的認證研究。在不改變編碼信息的情況下，Yao等人[10]提出利用第三方知識庫實現(xiàn)編碼信息的認證。顯然，該方法對第三方知識庫的依賴性是其主要的局限所在。

另一種思路是使用額外的認證信息(例如消息認證碼、數(shù)字簽名)來實現(xiàn)編碼信息的防偽，其關(guān)鍵在于設(shè)計切實有效的認證信息分發(fā)策略?，F(xiàn)有方法雖未對編碼信息進行修改，但大多將認證信息同樣編碼到QR碼中[11-12]，而編碼信息的增加往往意味著編碼容量需求的增加，以及解碼效率的降低。與之相比，空間域[13-14]以及頻率域[15]數(shù)字水印技術(shù)可以在不改變給定QR碼編碼內(nèi)容的條件下實現(xiàn)認證信息的植入。前者的缺點是不能用于印刷媒體傳播的QR碼，因為數(shù)字水印信息無法在經(jīng)歷打印、掃描操作之后正確還原；后者的計算開銷對于計算資源和電力儲備有限的移動設(shè)備非常不利。

除使用傳統(tǒng)的數(shù)字水印技術(shù)進行數(shù)據(jù)植入外，Barmawi等人[14]以犧牲QR碼自身糾錯能力為代價提出了一種基于模塊操作的數(shù)據(jù)植入方法，其植入容量為糾錯碼字容量的1/2。在文獻[14]方法的基礎(chǔ)上，Lin等人[16]提出了一種植入容量更優(yōu)的私密信息分發(fā)方法。文獻[17]通過對Lin等人的方法進行分析研究得出結(jié)論，其信息植入容量取決于所采用QR碼糾錯碼的長度。文獻[18]認為，由于采用LSB方法進行數(shù)據(jù)植入，Lin等人所提出的方法確實較之前的方法具有更高的植入容量。但同時，文獻[19]也指出，由于使用標準QR碼中的部分模塊進行信息植入，該信息植入方法是以犧牲標準QR碼的糾錯能力為代價的。

受上述方法的啟發(fā)，提出一種基于模塊邊界多方向偏移的信息植入及提取方法，并將其應(yīng)用于QR碼編碼信息的認證。本方法具有植入信息容量高、抗干擾能力強等優(yōu)點，適用于通過數(shù)字媒體、印刷媒體傳播的QR碼場景。

2 提出方法

2.1 問題描述及解決思路

給定原始信息E1，遵照開放標準(如ISO/IEC 18004:2006[20]等)對E1進行編碼得QR碼，令其為Q1。Q1通過印刷、互聯(lián)網(wǎng)等媒體進行分發(fā)以后被終端用戶獲取，令用戶獲得的QR碼為Q2，解碼所得信息為E2?！癚R碼編碼信息認證”問題可以理解為：如何有效實現(xiàn)QR碼編碼信息的認證，即確認E2是否與E1一致。以此為動機，提出一種基于數(shù)字簽名植入的QR碼編碼信息認證框架，核心方法為基于模塊邊界多方向偏移的信息植入及提取，以實現(xiàn)認證信息和QR碼的關(guān)聯(lián)，主要針對的問題包括(1)信息植入階段的容量設(shè)計方法，以保證大容量的植入需求；(2)信息提取階段的糾錯機制設(shè)計，以保證方法的魯棒性。

本方法基于以下觀察：標準QR碼是由一系列隨機排列的黑、白模塊構(gòu)成的矩形區(qū)域，不同色塊之間存在一條明顯的分界線。如賦予某些分界線以“偏移”能力，則可通過其偏移或非偏移來表達二進制0或者1。這些分界線稱作可偏移邊界，并定義如下：

定義1可偏移邊界

對于QR碼Q中任意兩相鄰模塊M1和M2之間的邊界b來說，當(dāng)且僅當(dāng)M1、M2代表Q中不同的二進制信息(或者說具有不同的顏色)時b為可偏移邊界。

假設(shè)圖1(a)中的黑、白矩形區(qū)域為某QR碼中兩相鄰模塊，則箭頭所指位置即為滿足定義1的一個可偏移邊界，其“偏移”行為定義如下：

定義2邊界偏移

定義2所述的R(M2)選取問題，在實際操作中可以有多種設(shè)計方案。其共同的步驟為對每個模塊進一步作3×3等分，如圖1(a)中B0-B8和W0-W8所示。差別在于：對只存在一個方向偏移的情況來說，將R(M2)設(shè)計為如圖1中區(qū)域W1、W8和W7的合集(此時W0-W8為M2)。

定義3二進制0/1數(shù)據(jù)植入或提取

對于可偏移邊界b來說，在某個方向上植入(或提取)二進制信息1被定義為在該方向上對b執(zhí)行邊界偏移(或檢測到存在邊界偏移)；在某個方向上植入(或提取)二進制信息0被定義為在該方向上不執(zhí)行邊界偏移(或檢測到不存在邊界偏移)。

在上述定義的基礎(chǔ)上，提出信息植入和提取方法：根據(jù)定義1找到給定標準QR碼的可偏移邊界集合B；根據(jù)定義3將給定二進制信息應(yīng)用于B中特定的可偏移邊界以實現(xiàn)信息植入，或者通過檢測B中特定可偏移邊界的偏移狀態(tài)以實現(xiàn)信息提取。例如，在圖1(b)中，可以通過置W1、W8和W7為黑色來植入1；通過保留W1、W8和W7為白色來植入數(shù)值0。

圖1 可偏移邊界及其信息植入方法展示Fig.1 Boundary offset and information embedding method

值得指出的是，本方法的可行性是建立在以下幾點假設(shè)的基礎(chǔ)上：(1)QR碼模塊所對應(yīng)的區(qū)域通常大于1個像素大小；(2)在保證模塊中心位置像素不變的情況下對其他區(qū)域進行修改，通常不會影響QR碼編碼信息的正常讀取[21]；(3)可偏移邊界的數(shù)量是穩(wěn)定的。其中，假設(shè)(1)用于保證模塊能夠進一步細分。鑒于過小的模塊將導(dǎo)致識別效率偏低的問題，假設(shè)(1)在實際應(yīng)用中是普遍存在性。假設(shè)(2)用于保證模塊邊界偏移不會影響原始QR碼的正常讀取，其論證可參考文獻[21]；假設(shè)(3)用于為植入數(shù)據(jù)的容量提供保證，其有效性可由QR標準所定義的掩碼(Mask)操作予以證實[20]，該操作確保標準QR碼中不同色塊在數(shù)量和空間分布上較為平均，而可偏移邊界即與之相關(guān)。

2.2 信息植入方法

2.2.1 容量設(shè)計

植入容量是信息植入方法設(shè)計中的一個重要問題，為獲得更多的植入容量，可以將圖1(b)所示單方向偏移情況擴展至多方向。這是由于矩形模塊存在4條邊，所以模塊邊界偏移可以同時出現(xiàn)在上下左右4個方向上。顯然，多方向偏移比單方向偏移能夠表達更多的二進制數(shù)，即提供更大的植入容量。

為應(yīng)對可偏移邊界在兩個相反方向上同時存在可偏移性的情況，將使用如圖2所示的方案來替代圖1方案。即使用W1和B5分別表示定義2中所述向右和向左方向上的“局部區(qū)域”，其顏色是否改變依植入信息的不同而異。

圖2 多方向信息植入方法展示Fig.2 Multidirectional information embedding method

在有多個可偏移方向可選的情況下采用哪幾個方向進行偏移是實際應(yīng)用中遇到的另一個問題。顯然，這是一個排列組合問題，一共有N(N滿足公式1)種可能性。

(1)

受QR碼中版本和糾錯等級設(shè)計的啟發(fā)，按照上述多方向偏移可能性以及等級越高、容量越大的原則將植入容量劃分為15個等級，供用戶以選擇的權(quán)力。

2.2.2 方法流程

如圖3所示，給定QR碼Q1，二進制植入信息S1，首先按照定義1識別Q1中所有的可偏移邊界B，然后采取相關(guān)措施防止植入數(shù)據(jù)溢出。具體來說，令CB為可偏移邊界的個數(shù)，LS1為S1的長度，那么只要CB不小于LS1，就可以繼續(xù)執(zhí)行下一步驟；否則，需要通過提升QR碼版本等方式獲得更大的植入容量。接下來，從頭到尾依次遍歷S1中的每一個二進制數(shù)，并依照定義3所述的規(guī)則在對應(yīng)的可偏移邊界位置逐個進行植入，直至S1中的所有數(shù)都遍歷完為止。為保證后續(xù)植入信息提取的順利進行，在信息植入環(huán)節(jié)將引入糾錯編碼環(huán)節(jié)。任意一種塊碼(block code)技術(shù)都可用作糾錯編碼，RS編碼即其中的典型代表。圖4展示了該方法的效果，其中左側(cè)是給定的標準QR碼，中間是在向右和向下兩個方向上植入信息后的結(jié)果，右側(cè)對兩者的差異進行了標記。

圖3 基于多方向偏移的信息植入方法流程圖Fig.3 Workflow of the multidirectional offset based information embedding method

圖4 植入效果展示Fig.4 Embedding result

2.3 信息提取方法

2.3.1 糾錯機制設(shè)計

對上述多級偏移方式所植入的信息進行提取并非簡單的逆向操作，因為即使在未遭受惡意攻擊的情況下，噪聲、遮擋、污損等干擾也會導(dǎo)致終端用戶獲取的QR碼遭到破壞。標準QR碼中采用RS糾錯機制來保障數(shù)據(jù)的正確性，本方法同樣將利用糾錯碼技術(shù)，但面臨的問題比標準QR碼多。

本方法面臨的挑戰(zhàn)在于：既要考慮ERA(Erasure，即將0識別為1或者將1識別為0)錯誤，又要應(yīng)對ERR(Error，即數(shù)據(jù)位丟失，例如由于遮擋等原因錯將圖5中左側(cè)實心箭頭所示的4位數(shù)據(jù)識別為右側(cè)實心箭頭所示的2位數(shù)據(jù))錯誤。標準QR碼只需要考慮ERA錯誤，因為一旦確定其版本和尺寸，就可以獲得其模塊大小，亦即編碼數(shù)據(jù)的長度不會丟失。植入信息提取的關(guān)鍵是識別可偏移邊界及其偏移情況。一旦有一個偏移邊界沒有被正確識別到，就會產(chǎn)生一個ERR。例如，圖5左為標準QR碼中5個黑白相間、左右相鄰的模塊，假設(shè)由于遮擋干擾的發(fā)生，所識別到的對應(yīng)模塊如圖5右側(cè)所示，此時QR碼編碼信息的總位數(shù)并沒有變，僅產(chǎn)生1個ERA(右側(cè)空心箭頭標識)。相比之下，由于部分可偏移邊界的消失，原本嵌入的4位二進制數(shù)(左側(cè)箭頭標識，從左向右單向偏移)最終只識別到2位(右側(cè)實心箭頭標識)，即產(chǎn)生2個ERR。與此同時，記t為RS糾錯碼的長度，就可糾錯的數(shù)量來說，ERA與ERR的上限分別為t和?t/2」。也就是說，在RS碼長度確定的情況下，ERR對糾錯能力的消耗更大。因此單純依靠RS碼來實現(xiàn)糾錯很難達到理想的效果。

為增強方法的糾錯能力，提出一種準確識別攜帶植入信息QR碼中所有可偏移邊界的方法，以消除所有的ERR，具體流程如下：

2.3.2 方法流程

如圖6所示，令Q2表示終端用戶獲取到的攜帶植入信息的QR碼，從中解碼得到E2，本方法的糾錯策略是：重新對E2進行編碼，得到標準QR碼Q1'，從Q1'中(而非Q2中)獲取所有的可偏移邊界B'，然后結(jié)合B'以及Q2來提取植入信息S2，最后采用植入信息環(huán)節(jié)相同的糾錯碼技術(shù)對S2進行糾錯，實現(xiàn)植入信息的準確提取。

值得說明的是，上述流程中借助了標準QR的糾錯機制，從而保證B'與2.2.2節(jié)所述的B一致。因此，方法以標準QR碼的正常解碼為前提，這也正好切合本研究實現(xiàn)編碼信息認證的出發(fā)點，因為在編碼信息無法正常獲取的情況下談其認證是毫無意義的。另外，S2中雖然消去了所有的ERR，但可能存在ERA，因此最后仍然需要對其進行糾錯處理。

圖5 同一遮擋攻擊下標準QR碼的消除錯誤與本方法的數(shù)據(jù)位丟失錯誤比較Fig.5 Comparison between the erasure error for standard QR code and the missing digits error for this method under the same occlusion attack

圖6 多方向偏移植入信息提取流程圖Fig.6 Workflow of the extraction of message embedded by the proposed multidirectional offset

2.4 編碼信息認證框架

基于上述多級偏移的信息植入及提取方法來實現(xiàn)QR碼編碼信息的認證功能，其主要流程如圖7所示。給定QR碼Q1，其編碼信息為E1，為實現(xiàn)編碼信息的認證，在生成環(huán)節(jié)將對E1進行簽名操作(包括生成摘要及其加密)，并將得到的簽名信息通過所提出的方法植入Q1中。然后該帶簽名信息的QR碼將進入傳播環(huán)節(jié)直至其被終端用戶獲取到。

由于傳播環(huán)節(jié)的未知性，令獲取到的QR碼為Q2，通過常規(guī)解碼方法將得到編碼信息E2。在認證環(huán)節(jié)，將E2與E1的一致性問題轉(zhuǎn)化為摘要D1和D2的一致性問題予以解決，其中D1、D2分別是對E2進行哈希和對Q2中的簽名信息解密所得到的。一方面，數(shù)字簽名技術(shù)確保了該認證方法的有效性，另一方面，所提出的多級偏移信息植入方法為植入高容量的認證信息及其準確提取提供了可靠的解決方案。

圖7 基于多級偏移植入數(shù)字簽名的QR碼編碼信息認證方法框架Fig.7 Authentication framework of encoded message of QR code based on hierarchical offset digital signature embedding

3 實驗

為驗證所提出方法的可行性和有效性，進行了各種類型的實驗，主要對其中的植入數(shù)據(jù)容量評估和裁剪攻擊測試結(jié)果進行闡述和討論。

3.1 實驗數(shù)據(jù)及環(huán)境

實驗是在一臺具有Intel Core i5(3.3 Hz)CPU、8G內(nèi)存的普通臺式電腦上進行的，編程環(huán)境為MATLAB。實驗采用ZXing庫的標準QR碼編碼和解碼，其編碼信息、植入信息均為隨機生成，QR碼的個數(shù)、編碼/植入信息的長度、糾錯等級等設(shè)置因?qū)嶒災(zāi)康牟煌?/p>

3.2 植入數(shù)據(jù)容量評估

植入容量的大小是衡量數(shù)據(jù)植入算法的核心指標之一。該方法的植入容量與給定的QR碼模塊分布及所使用的方向數(shù)有關(guān)。為保證評估的客觀性，隨機生成4 000個標準QR碼作為輸入信息(其編碼信息由包含于ASCII碼中的字符組成，長度在9～2 900之間的，覆蓋所有4個糾錯等級以及40個版本號)，分別測試使用1、2、3、4個方向進行信息植入情況下的植入容量(分別記為“本方法-1、2、3、4”)。以給定QR碼的編碼信息容量(單位為比特)為基準，將該方法與Barmawi等人[14]的方法及Lin等人[16]的方法進行比較，其結(jié)果繪制于圖8中?？梢姡灾踩肴萘孔鳛楹饬繕藴?，該方法明顯優(yōu)于另外兩種方法。如果使用2個方向進行信息植入，該方法將具備與QR碼編碼信息相當(dāng)?shù)娜萘浚蝗绻捎?個方向進行植入，該方法的平均植入容量是QR碼編碼容量的2.2倍、Lin等人方法的6.4倍、Barmawi等人方法的6.7倍。

3.3 裁剪攻擊實驗

為測試方法的魯棒性，進行了兩組裁剪攻擊實驗。鑒于所提出的糾錯方法是建立在QR碼自身糾錯機制的基礎(chǔ)上，因此實驗對象選取為糾錯等級H(即最高等級)、版本號4的1 000個標準QR碼。為模擬QR碼在實際應(yīng)用中可能遭遇的各種遮擋情況，在第一組實驗中，使用以圖9所示為代表的裁剪攻擊進行測試，實驗結(jié)果表明本方法具有良好的植入信息提取能力。

圖9 裁剪攻擊示例Fig.9 Demonstration of different kinds of occlusion attacks

為進一步量化方法的糾錯性能，在第二組實驗中，將352比特的信息(其中128比特為有效信息，其余為糾錯碼)植入給定的1 000個QR碼中。然后將遮擋區(qū)域定義為不同尺寸(占QR碼圖片面積從5%至30%不等)的矩形區(qū)域，同時將其以滑動窗口的形式依次遮蓋QR碼的不同區(qū)域，然后執(zhí)行提取操作，并通過公式2計算得到植入信息提取的成功率R。

(2)

其中Ncor是植入信息被成功提取的次數(shù)，Ntot是窗口滑動的次數(shù)。最終的平均成功率Ravg是對1 000個QR碼進行測試所得結(jié)果的平均值。

表1展示了在不同方向上進行植入的提取成功率結(jié)果，該結(jié)果是在對應(yīng)QR碼能夠成功解碼的前提下得到的。此外，表中還記錄了相同實驗情況下，對應(yīng)QR碼自身編碼信息解碼的成功率，用以作為本方法成功率的參照基準。從表1可知，遮擋面積越小，植入信息提取的成功率越高。另外，由于使用1個方向進行植入較4個方向的植入數(shù)據(jù)分布更為分散，因此提取的成功率也更高。

4 結(jié)語

提出一種基于多級模塊邊界偏移的信息植入和提取方法，將其與數(shù)字簽名技術(shù)相結(jié)合，可以在不改變給定QR碼編碼信息的情況下，實現(xiàn)QR碼編碼信息的篡改檢測功能，從而保證用戶的財產(chǎn)信息安全。該方法的創(chuàng)新點在于：1)提出了一種多級模塊邊界偏移的QR碼信息植入方法；2)實現(xiàn)了一種有效應(yīng)對數(shù)據(jù)位丟失錯誤的糾錯策略；3)將信息植入和提取方法與數(shù)字簽名技術(shù)相結(jié)合，構(gòu)建出一套QR碼編碼信息認證框架。通過實驗驗證了方法的可行性和有效性。但受限于QR碼自身糾錯性能，該方法中植入信息的提取成功率仍有待進一步提升，需要更加深入研究。

表1 不同摘擋尺寸情況下的植入信息平均提取成功率