喬婉妮

（蘭州交通大學(xué)電子與信息工程學(xué)院，蘭州 730070）

0 引言

二維碼又稱二維條碼，最常見的形式是QR Code，QR 全稱Quick Response，是一個近幾年來移動設(shè)備上十分流行的一種編碼方式，它能比傳統(tǒng)的Bar Code 條形碼儲存更多的信息，也能表示更多的數(shù)據(jù)類型。

二維碼（2-dimensional bar code）是在一維碼的基礎(chǔ)上，使用某種特定的幾何圖形按照一定的規(guī)律在水平和垂直方向存儲數(shù)據(jù)符號信息的黑白相間圖形[1-2]，二維碼具有可表示漢字圖像等多種文字信息、存儲信息容量大、可靠性強(qiáng)等優(yōu)點(diǎn)。使用構(gòu)成計算機(jī)內(nèi)部邏輯的“0”和“1”位流的概念，對應(yīng)于二進(jìn)制系統(tǒng)的各個集合對象來表示文本數(shù)字信息[3-4]。通過圖像輸入裝置或光電掃描裝置實現(xiàn)自動信息處理。由于其具有高密度、大容量等特點(diǎn)，因此可以用來表示發(fā)送內(nèi)容[5-7]。它還具有條碼技術(shù)的一些共性，如每種碼制有其特定的字符集、每個字符占有一定的寬度、具有一定的校驗功能等。同時還具有對不同行的信息自動識別功能及處理圖形旋轉(zhuǎn)變化點(diǎn)。QR 碼已在社交生活的許多領(lǐng)域中得到廣泛使用，并已成為連接現(xiàn)實和虛擬的最強(qiáng)大工具之一。

截止到目前，有關(guān)QR 碼信息隱藏技術(shù)的研究很多。但是，在國內(nèi)外，大多數(shù)方法都是通過加密算法或比較和識別大量私鑰來編碼和修改基礎(chǔ)數(shù)據(jù)的[8]。前者具有低便捷性，后者由于解析速度慢、識別時間長和成本高而難以使用。基于以上問題，本文設(shè)計了一種高度可移植、快速、可靠的二維碼信息加密系統(tǒng)和解密系統(tǒng)。

國內(nèi)市場上功能類似的商業(yè)設(shè)計主要是通過數(shù)據(jù)庫檢索的方式隱藏信息，即通過QR 碼攜帶一段字符串，用戶端識別QR 碼的時候只能識別字符串。企業(yè)端通過地址字符串搜索預(yù)先建立的信息數(shù)據(jù)庫。通過使用用戶的個人信息來實現(xiàn)加密用戶信息的目的。這種方法本質(zhì)上不會加密任何信息。這意味著，只要訪問數(shù)據(jù)庫，所有用戶的個人信息實際上就是完全公開的。這種方式存在巨大的安全缺陷。

本文介紹了一種新的加密算法。該算法使用雙方都必須同意的私鑰，首先將要發(fā)送的數(shù)據(jù)編碼為QR 碼，然后使用簡單但非常有效的過程對QR 碼進(jìn)行加密。將私鑰（KeyQR）和接收方數(shù)據(jù)（DataQR）進(jìn)行異或運(yùn)算以生成偽裝QR 碼，并建立數(shù)據(jù)讀取設(shè)備。私鑰匹配后以恢復(fù)有效信息。在確定了固定點(diǎn)之后，根據(jù)私鑰設(shè)置將QR 碼的非定位區(qū)域劃分為m塊等面積四邊形，并確定分割區(qū)域的等效點(diǎn)，即相對中心點(diǎn)。根據(jù)等價類原理，分段的m塊等距四邊形是根據(jù)其位置到等效點(diǎn)的弧之間的距離進(jìn)行校準(zhǔn)，每組分配相同值的四邊形都有4個塊。通過選擇左手或右手模式，等效的四邊形位置被交換以形成新的圖像。

1 處理

1.1 QR碼的基本結(jié)構(gòu)

QR碼是一種黑白圖形，它在具有特定幾何圖案的平面（二維方向）上被巧妙的編碼以記錄數(shù)據(jù)符號信息。構(gòu)成計算機(jī)內(nèi)部邏輯的“0”和“1”為流的概念通過使用對應(yīng)于二進(jìn)制的多個幾何形狀來表示文字和數(shù)字信息，這些形狀由圖像自動讀取設(shè)備或光電掃描設(shè)備輸入。自動信息處理具有條形碼技術(shù)的一些共性，每個代碼系統(tǒng)都有自己特定的字符集。每個字符占據(jù)一定的寬度，其具有一定的檢查功能，同時還具有針對不同行信息的自動識別功能，并處理圖形的旋轉(zhuǎn)變化點(diǎn)。QR碼基本結(jié)構(gòu)如圖1所示。

圖1 QR碼基本結(jié)構(gòu)

1.2 密碼分組鏈接模式（Chipher Block Chaining）

密碼分組鏈接模式（CBC）是將前一個密文分組與當(dāng)前明文分組的內(nèi)容混合起來進(jìn)行加密，這樣就可以避免明文被主動攻擊。當(dāng)加密第一個明文分組時，由于不存在“第一個密文分組”，因此需要事先準(zhǔn)備一個長度為一個分組的比特序列來代替“前一個密文分組”，這個比特序列稱作初始化向量（Initialization Vector），每次加密時都會隨機(jī)產(chǎn)生一個不同的比特序列來作為初始化向量。在CBC 模式中，首先將明文分組與前一個密文分組進(jìn)行異或操作，然后再進(jìn)行加密，如圖2所示。

圖2 CBC模式加密流程

1.3 算法流程

預(yù)傳播信息用于生成QR 碼圖像，將QR 碼放置在識別幀中，然后獲得圖像幀。進(jìn)行包括灰度和中值濾波器的圖像預(yù)處理，并且通過識別位置點(diǎn)來獲得正方形圖像。通過按位進(jìn)行異或計算以生成加密圖像TransmissionQR。最后偽裝后的圖像由識別編碼算法相對應(yīng)的解碼算法處理。QR解碼過程完成后，獲得預(yù)傳播信息。算法流程如圖3所示。

圖3 算法流程

1.4 加密數(shù)學(xué)模型

異或操作具有可逆性的獨(dú)特屬性。由于異或算法是按位執(zhí)行的，因此運(yùn)算速度非?？?，加密和解密耗費(fèi)的時間也很短。這使得異或算法在加密和解密算法當(dāng)中十分受歡迎。

1.4.1 證明1

下面證明系統(tǒng)可以從TransmissionQR 和KeyQR 中生成DataQR。用“D”代表DataQR，“K”代表KeyQR，“T”代表TransmissionQR。

第一步：傳送方。TransmissionQR 由DataQR 和Key-QR二者按位異或生成，因此，T=D⊕K。

第二步：接收方。DataQR 由TransmissionQR 和Key-QR 通過異或產(chǎn)生。令G代表接收端產(chǎn)生的QR。則G=T⊕K，并且T=D⊕K，因此G=G(D⊕K)⊕K，由于異或運(yùn)算是相關(guān)的，有G=D⊕(K⊕K)。由于元素自身異或等于0，化簡為G=D⊕(0)。元素與0 進(jìn)行異或值不變，最終化簡為G=D。

這證明了上面的假設(shè)，即DataQR 可以從TransmissionQR和KeyQR生成，反之亦然。

1.4.2 證明2

下面利用矛盾法證明只能有一個私鑰可以解密TransmissionQR 以重新生成DataQR。

令K1為第一個對QR 進(jìn)行解密以生成DataQR 的私鑰KeyQR。因此，T⊕K1=D，在等式兩邊取T的異或：

令K2作為第二個KeyQR，它對TransmissionQR 進(jìn)行解密以生成DataQR。因此，T⊕K2=D，同樣在兩側(cè)取T的異或：

然而式（1）和（2）與假設(shè)的K1和K2是不同的值相矛盾。因此通過矛盾，證明K1和K2是相同的密鑰，因此只有一個密鑰可以解密TransmissionQR 來生成DataQR。

1.5 算法與QR碼結(jié)合

由于QR 碼是一幅圖像，而圖像是像素的集合，因此可以分別對每個像素進(jìn)行操作以分別生成TransmissionQR 和DataQR。QR 碼是黑白像素的集合，可以使用此圖像的二進(jìn)制形式將黑色表示0，將白色表示為1。這將會確保按位異或的時候可以應(yīng)用于每個像素，以此分別生成TransmissionQR 和DataQR。像素級異或的圖形表示如圖4所示。

2 非對稱加密算法

2.1 RSA概述

RSA 是一種傳統(tǒng)的非對稱密鑰加密算法，它是由RIRivest、AShamir 和M Adleman 在1978 年在MIT 上提出的。RSA 是基于大素數(shù)證書分解的指數(shù)函數(shù)，被認(rèn)為是陷阱門單向函數(shù)。之所以將其稱為“活板門”，是因為一旦系統(tǒng)知道某個“活板門”信息，其逆函數(shù)就很容易被計算。之所以稱它是單向的，是因為其在一個方向上易于計算，而在另一個方向上卻難以計算。在RSA 中，純文本和密文被視為從0～n-1 的整數(shù)（通常n的大小為1 024 ）。

2.1.1 生成Pri-Pub密鑰對

（1）選擇兩個素數(shù)整數(shù)p和q（每個1 024位），其中p≠q；

（2）計算模量n=q·p；

（3）計算n′=(p- 1)·(q- 1)并找出私有指數(shù)，使其gcd(d,n′) = 1；

（4）計算公共指數(shù)e：e·d= 1(mod(p- 1)·(q- 1))，它是乘法的逆運(yùn)算；

（5）因此，公鑰為（n，e），私鑰為（n，d）。

2.1.2 加密和解密

為了加密密文，首先將明文表示為正整數(shù)M。然后使用公鑰（n，e）進(jìn)行計算，E(M) =Me(modn)，然后發(fā)送方將E（M）發(fā)送給接收方。解密密文類似于加密。接收方使用自己的私鑰（n，d） 進(jìn)行計算，D(E(M)) =E(M)d(modn) =M。然后可以從整數(shù)M中獲取到明文。

2.2 RSA算法的實施

2.2.1 密鑰生成

（1）生成512位的隨機(jī)素數(shù)

生成一個512 位長的奇數(shù)隨機(jī)數(shù)后使用RabinMiller算法[80]檢驗測試素數(shù)。ACK=1 表示這個數(shù)字是素數(shù)，生成出一對512位的素數(shù)p和q。

（2）生成公鑰（n，e）和私鑰（d，e）

計算n，n=p·q，Φ(n) =(p- 1)·(q- 1)。計算e時，使用歐幾里得算法找到GCD，為了計算公鑰，狀態(tài)Inc_PubKey 將 變 量PubKey+1，狀 態(tài)Cherck_Large 查 找Phi 和PubKey 中較大的一個。為此，利用歐幾里得算法通過重復(fù)減法，通過狀態(tài)GCD_CAL_MOD 和GCD_CAL_MOD2 計算出GCD。當(dāng)較小的數(shù)（除Phi 和PubKey 之外）減少到0 時，就會找到GCD。狀態(tài)GCD 會檢查tgcd 是否等于1，如果等于1，則當(dāng)前狀態(tài)返回到Inc_pubKey狀態(tài)。

狀態(tài)Prv_cond 檢查余數(shù)是否為0。如果不是，則k+1，當(dāng)前狀態(tài)返回到Prv_Mul 狀態(tài)。這種情況一直持續(xù)到(1+(k·φ(n)))對于k的某個值完全能被e整除。計算出的d對應(yīng)的值是私鑰指數(shù)d。一旦計算出公鑰指數(shù)e和私鑰指數(shù)e就可以分別進(jìn)行加密和解密。

2.2.2 加密

計算公式為：c=me(modn)

式中：m為待加密的明文或消息；e和n分別時密鑰生成模塊生成的公鑰指數(shù)和模。

因為n的值非常大，所以不能計算這么大的值，在下文中將解決這一問題。

（1）模塊化的乘法

模乘意味著計算(A·B)modn。實現(xiàn)模乘有各種技術(shù)。32 位乘法運(yùn)算采用移位加技術(shù)。使用32 位乘法是因為灰度圖像的像素值不能大于255。當(dāng)k=32 時，被乘數(shù)和乘數(shù)都是k位二進(jìn)制數(shù)。模塊化乘法算法如下：

P=0

For i=0 to k-1

P = 2P + A*Bk-1-i

P=P mod n

Return P

（2）模冪運(yùn)算

密碼c=me(modn)只是重復(fù)的模積。模塊化產(chǎn)品（A·B）modn被部署在重復(fù)模乘技術(shù)中以執(zhí)行模求冪。用一個例子來解釋重復(fù)模乘技術(shù)：

令m=85，e=5，n=497。

對于e′= 1,c′=(1× 85)mod497= 85mod497= 85；

對于

e′= 2,c′=(85× 85)mod497=7 225mod497= 267；

對于

e′= 3,c′=(267× 85)mod497= 22 695mod497= 330；

對于

e′= 4,c′=(330 × 85)mod497= 28 050mod497= 218；

對于

e′= 5,c′=(218× 85)mod497= 18 530mod497= 141。

（3）解密

與加密不同，這里的私鑰本身值很大。因此，采用左向右二值法，假設(shè)d為k位長，解密算法如下：

輸入：c，d，n

輸出：Decmg:= cd(modn)

if dk-1= 1，then Decmsg=c else Decmsg=1

for i=k-2

Decmsg =(Decmsg*Decmsg)mod n

if di= 1,then Decmsg =(Decmsg*c)mod n

Return Decmsg

2.3 RSA算法的改進(jìn)

利用文獻(xiàn)[80]中提到的方法來對3 個素數(shù)因子進(jìn)行加密，并消除密鑰中的n。通過加入3 個素數(shù)因子的方案，其優(yōu)點(diǎn)是減少了素數(shù)因子的長度，但是卻增加了算法中素數(shù)因子的總個數(shù)，通過本文的消除密鑰中n的設(shè)計后，可以讓破壞者不輕易的破解密碼，因此提高了系統(tǒng)的安全性。本文設(shè)計的算法共包含3 個部分，分別是：產(chǎn)生內(nèi)部密鑰、加密信息以及解密信息。

（1）步驟1：生成密鑰

選擇3個素數(shù)a1、a2、a3，a1≠a2≠a3。計算三者的乘積n=a1×a2×a3，得到歐拉函數(shù)：

φ(n) =(a1- 1) ×(a2- 1) ×(a3- 1)

隨機(jī)選擇一個整數(shù)k1，使得：

GCD(k1,φ(n)) = 1且n≤k1≤φ(n)

根據(jù)a1、a2、a3的大小關(guān)系，計算出X來替代n。

如果a1＞a2＞a3或者a1＞a3＞a2，解X得：

GCD(X,n) = 1,n-a1＜X＜n

如果a2＞a1＞a3或者a2＞a3＞a1，解X得：

GCD(X,n) = 1,n-a2＜X＜n

如果a3＞a1＞a2或者a3＞a2＞a1，解X得：

GCD(X,n) = 1,n-a3＜X＜n

將求得的X代入下式中，求解k2：

k2=k-11Mod(X)

此時，私鑰是(k2，X)，公鑰是(k1，X)。

（2）步驟2：加密消息

發(fā)送方通過私鑰(k2，X)來加密消息M，其公式為：

C=Mk1Mod(X)

式中：C為加密后產(chǎn)生的密文。

（3）步驟3：解密消息

接收方通過私鑰(k2，X)來解密密文C：

式中：M為加密前的消息。

改進(jìn)RSA算法的加密步驟如圖5所示。

圖5 改進(jìn)RSA算法的加密步驟

通過用X替換n成功消除掉了n。由于攻擊方無法通過X分解得到a1、a2、a3，這使得算法變得更加難以被破解。在加強(qiáng)安全性的另一方面，本文通過添加一種新的加密手段來加密RSA 算法，但是這種方法具有局限性，即只能用于只有二因子的RSA 算法中，其他類型的RSA算法無法使用，這也是后續(xù)需要改進(jìn)的方面。

下面進(jìn)行復(fù)雜度的分析。密鑰生成算法根據(jù)a1、a2、a3的大小和復(fù)雜度o(2φ(n))以及加密算法的時間復(fù)雜度o(k1)，添加替換n的X的計算。 解密算法將平方根函數(shù)添加到模塊化擴(kuò)展函數(shù)的輸出中。這是因為二次運(yùn)算的時間復(fù)雜度是固定的序列所以解密算法的時間復(fù)雜度是o(k2)。

3 算法功能演示

讓雙方都接受私鑰KeyQR，如圖6 所示。掃描二維碼后將不會得到正確信息，并彈出如圖7所示的界面。

圖6 私鑰KeyQR

圖7 通過掃描演示二維碼獲得的信息

將“username:aaa@aaa.com password：qweasdzxc”作為傳遞信息寫入DataQR 中，如圖8 所示。通過加密后傳輸?shù)腝R如圖9所示。

圖8 發(fā)送的數(shù)據(jù)DataQR

圖9 TransmissionQR

最終接收方解密后的QR 如圖10 所示。對TransmissionQR 碼進(jìn)行圖像處理，并讀取正確的信息“username:aaa@aaa.com password：qweasdzxc”，如圖11所示。

圖10 RetrievedQR

圖11 QR碼信息還原示例

4 結(jié)束語

本文提供并實現(xiàn)了一種基于國家標(biāo)準(zhǔn)代碼系統(tǒng)的特殊QR 碼加密算法。提出了一種將圖像幾何處理與QR 碼信息加密相結(jié)合的新思路。該算法的加密級別可以根據(jù)用戶自己的要求靈活更改。基本功能是只有特定的掃描讀取系統(tǒng)才能讀取加密的二維碼中有效信息，而傳統(tǒng)的讀取系統(tǒng)只能獲取加密的加密信息。本文算法考慮生成大小為128×128 像素的QR 碼。加密的KeyQR 中的每個像素都有兩個選擇：黑色和白色。因此對于128×128 像素，有2（128×128）個選擇。任何現(xiàn)代計算機(jī)都需要花費(fèi)比Universe 更長的時間來生成和檢查所有的組合，以找出正確的KeyQR。因此算法的安全性受到時間的限制。未來的工作中，嘗試添加一些本地物理信息。為了使識別端通過物理信息匹配而不是內(nèi)置密鑰獲得密鑰，以此方法降低生產(chǎn)成本和技術(shù)門檻。