一種結(jié)合優(yōu)化后AES與RSA算法的二維碼加密算法

劉海峰, 劉 洋, 梁星亮

(1.陜西科技大學(xué) 文理學(xué)院， 陜西 西安 710021; 2.陜西科技大學(xué) 電子信息與人工智能學(xué)院， 陜西 西安 710021)

0 引言

二維碼作為一種存儲、傳遞和識別信息的技術(shù)現(xiàn)已在多個領(lǐng)域得到了廣泛的使用，例如物流、交通、電子商務(wù)等.但隨著二維碼在市面上的推廣，二維碼的信息泄露危險也日益突出.由于二維碼的生成標(biāo)準(zhǔn)是公開的，且未能在編碼過程中實現(xiàn)信息加密，攻擊者可以通過二維碼截獲到存儲和傳遞的信息，存在著一定安全問題[1].對于未加密的二維碼，任何獲得二維碼的人進行掃描后均可得到二維碼中保存的信息，這對涉及個人隱私敏感信息領(lǐng)域造成使用上的不便.例如在追溯系統(tǒng)中，產(chǎn)品信息生成的未加密的二維碼在傳輸過程中，若被不法分子獲得，便可進行假冒印刷等一系列違法行為，使用加密后的二維碼作為保存、傳遞產(chǎn)品信息的媒介，可以起到規(guī)范市場，打擊假冒的目的.對于二維碼信息進行加密，既保證了它的隱私性，也為使用者的個人安全提供了保障.因此，有關(guān)二維碼的加解密的研究成為一個熱點問題.

目前，國內(nèi)對于二維碼信息安全的研究取得了一些初步進展.2014年，于英政等[2]提出結(jié)合了DES和RC4加密算法，選取DES和RC4兩種算法之一，針對不同階段的二維碼信息進行加密，實現(xiàn)了對二維碼分階段加密；安吉旺等[3]提出對編碼信息采用RSA和key口令的算法進行二維碼混合加密，對明文信息分組加密后，通過key口令對分組明文加密，再使用RSA算法對key口令的密鑰進行加密.在專用的識別軟件上，如果輸入正確的私鑰可解密出相應(yīng)的明文信息.2015年，肖本海等[4]基于SHA512和AES兩種算法對二維碼信息及其密鑰進行了加密，提高了對密文的保護；同年，廖鎮(zhèn)勛等[5]提出一種針對二維碼的不同階段，探究其差異并采用不同的方法進行二維碼的加密，提高了二維碼加密的程度.2017年，龍強等[6]提出一種基于非對稱密碼體制的二維碼加密算法，該算法將非對稱加密算法RSA與Logistic混沌模型相結(jié)合，對二維碼中信息及密鑰進行加密編碼，保證了二維碼中信息可以在不安全的信道中安全地傳輸.2018年，張華[7]探討了利用非對稱 加密算法加密二維碼的可行性和安全性；葛婭敬等[8]提出對二維碼圖片矩陣進行奇異值分解從而加密得到密文，解密得到明文，使基于圖像處理上的二維碼信息安全有了一定進展.楊康等[9]針對不同的信息權(quán)限和屬性集，生成訪問控制樹，通過不同用戶的屬性分配對應(yīng)的不同私鑰，實現(xiàn)了二維碼的分級加密.

綜上，當(dāng)前針對二維碼加密的方式分為對生成的二維碼圖像的加密和對未進行生成二維碼之前的初始明文信息的加密.在對二維碼信息加密的討論中，主要是針對二維碼加密算法安全性的討論，使用RSA非對稱算法為例的加密算法存在著加密或解密算法時間復(fù)雜度高的問題，而使用以DES對稱算法為例的二維碼加密算法，又存在著DES超期服役和密鑰傳輸是否安全的問題.

本文提出一種結(jié)合改進的AES算法和RSA優(yōu)化算法的二維碼加密算法.本算法在生成二維碼之前，對明文信息加密，利用AES對稱密碼算法加密效率快和RSA非對稱算法便于密鑰管理的優(yōu)勢，基于算法安全性的基礎(chǔ)之上實現(xiàn)了對密鑰的安全管理.同時通過對兩種算法的優(yōu)化減少加解密消耗的時間，實驗證明，該算法提高了二維碼加密的效率.

1 算法理論

1.1 二維碼

二維碼，又稱二維條碼或QR Code.在固定好的平面區(qū)域，二維碼通過散落的黑白相間的圖形按一定的規(guī)律排序，從而記錄數(shù)據(jù)信息.QR碼與傳統(tǒng)一維條碼相比：數(shù)據(jù)承載量更大；屬于糾錯編碼；可以引入加密體系；編碼范圍更廣.QR碼的這些特性，決定了其作為載體，在信息時代會有更多的發(fā)展空間.

1.2 AES算法

AES算法是一種新型加密方法，具有更加可靠的加密過程和更加適合的密鑰長度.AES算法包含三大部分：密鑰擴展，加密和解密.密鑰長度有128位、192位、256位3種.密鑰擴展算法的輸入是一個4字的密鑰，輸出是一個44字的一維線性數(shù)組.每輪的密鑰由種子密鑰經(jīng)過擴展得到.128位的AES加解密算法由十輪組成(192位12輪，256位14輪)，每一輪有四個基本步驟：ByteSub變換：用一個S盒完成分組中的按字節(jié)的代換，ShiftRow變換：一個置換過程，MixColumn變換：一個利用在GF(28)上的算術(shù)特性的代換，AddRoundKey變換：當(dāng)前分組按位異或擴展密鑰的一部分.解密算法和加密算法不同，僅僅密鑰擴展形式一樣，但對于加密解密中轉(zhuǎn)換順序是不同的.

1.3 AES算法改進

1.3.1 密鑰擴展改進

在傳統(tǒng)AES算法密鑰擴展部分，使用初始輸入的4字(16字節(jié))的密鑰進行密鑰擴展后，得到44個字(156字節(jié))組成的擴展密鑰數(shù)組W=(w0,w1,…,w43).由輸入的密鑰可直接先得到W的前4個字：w0,w1,w2,w3，W剩余的字由前一字以及前面第四個字進行如下運算操作得到：當(dāng)下標(biāo)數(shù)字不為4的倍數(shù)時，直接進行異或操作，否則，先與前一字進行g(shù)變換，再和前第四字進行異或操作,如圖1所示.這種密鑰擴展算法面臨的主要挑戰(zhàn)是攻擊者若是截取到其中一輪密鑰，便可通過相應(yīng)變換得到剩余所有密鑰.

圖1 傳統(tǒng)AES算法密鑰擴展過程

文獻[10]提出一種密鑰改進算法：在密鑰擴展過程中，初始密鑰不變，在密鑰擴展過程中，使用與初始密鑰無關(guān)的一套新密鑰填充為第一輪擴展密鑰，求解剩余密鑰則繼續(xù)使用AES密鑰擴展算法依據(jù)新密鑰擴展，最終得到全部密鑰.算法原理如圖2所示.

圖2 改進AES算法密鑰擴展過程

由于擴展密鑰都是由新密鑰通過AES算法擴展得到的，與初始密鑰無關(guān)，因此擴展密鑰和初始密鑰不存在代數(shù)關(guān)系，對于攻擊者來說，截取到任一輪擴展密鑰也無法推出初始密鑰，反之，截取到初始密鑰也無法推出擴展密鑰.設(shè)種子密鑰長為kbit，采用窮盡密鑰攻擊平均復(fù)雜度約為2k-1，以10輪AES算法來說，密鑰攻擊者平均需嘗試2127次可能的密鑰，而改進后的密鑰擴展算法使平均需嘗試2225次可能的密鑰，以目前的計算能力很難破解.因此該算法在保證與程序效率不變的基礎(chǔ)上克服了程序被截取一輪密鑰即可破解全部密鑰的漏洞.

在這種密鑰擴展改進算法中，若攻擊者已知算法密鑰擴展改進過程，又成功截取到初始密鑰x0和其后由任一輪由新密鑰或新密鑰擴展得到的密鑰，那么攻擊者依然可根據(jù)密鑰擴展過程由任一輪密鑰窮盡推出新密鑰，進而得到全部密鑰.

面對這種挑戰(zhàn)，本文提出一種在文獻[10]密鑰擴展算法上的改進算法：初始密鑰不變，依照原始密鑰擴展算法進行輪密鑰擴展，增加隨機輪數(shù)k(1

圖3 本文AES算法密鑰擴展過程

對于之前的攻擊者，攻擊分為以下情況：

(1)攻擊者截取到十輪中任兩輪密鑰，但未知隨機輪數(shù)k情況下：①兩輪密鑰均由初始密鑰或新密鑰之一進行密鑰擴展而來，由于開始選取的新密鑰與初始密鑰無關(guān)，則攻擊者無法推得另一密鑰及其擴展密鑰，進而無法獲得全部密鑰；②兩輪密鑰分別由初始密鑰和新密鑰之一密鑰擴展而來，則攻擊者在未知捕獲的兩種密鑰分別屬于新密鑰或初始密鑰和未知分別屬于兩種密鑰擴展的哪一輪密鑰擴展情況下一共有90種可能的密鑰組合，大大增加了破解難度.

(2)若攻擊者截取到隨機數(shù)k和初始密鑰的情況下，由于不知道新密鑰，無法通過計算獲得全部密鑰.

(3)若攻擊者截取到隨機數(shù)和新密鑰，情況和(2)相似.

1.3.2 列混淆變換改進

在傳統(tǒng)AES加密算法中，MixColumn變換即列混淆變換，分為正向列混淆變換和逆向列混淆變換，提供算法的擴散性.列混淆變換的正向列混淆變化對每列獨立地進行操作.每列中每個字節(jié)被映射為新值.式(1)表示GF(28)上正向列混淆變換，用于數(shù)據(jù)加密，式(2)表示GF(28)上逆向列混淆變換，用于數(shù)據(jù)解密.

(1)

(2)

在AES算法中，加密過程中，列混淆變換需要執(zhí)行4次xor加法和2次xtime乘法，而解密過程中逆列混淆變換需要執(zhí)行9次xor加法運算和12次xtime乘法運算[10].加密算法和解密算法因列混淆算法不同，導(dǎo)致加解密耗時不對等，解密算法中需要更多的時間來進行運算.

文獻[10]提供了最簡單形式的正向列混淆運算矩陣和逆向列混淆運算矩陣.

(3)

用M矩陣代替原AES算法中正向列混淆和逆向列混淆運算中矩陣，減少了逆向列混淆運算所消耗時間，使正向列混淆運算和逆向列混淆運算消耗相同的運算資源，均為執(zhí)行4次xor加法和2次xtime乘法，解決了加解密耗時不對等問題.

本文對M矩陣進一步改為：

(4)

這樣改進M后，正向列混淆和逆向列混淆均減少執(zhí)行2次xor加法運算，加密耗時和解密耗時的共同降低使運算速度得到一定提升，章節(jié)4.1中的表1 羅列了對同樣數(shù)據(jù)量加密或解密所用時間的對比.

1.4 RSA算法

RSA是典型的非對稱加密算法，它的特點是使用兩個密鑰的密碼算法，具有方便密鑰管理和傳送的特點.它的基礎(chǔ)是大數(shù)分解的困難性，它的核心是模冪運算.主要包括兩個方面：密鑰的產(chǎn)生和加密解密.

RSA密鑰的生成過程：

(1)首先選出兩個大的素數(shù)p和q，要求p不能等于q，且p和q有一定的差距.

(2)計算出n=p*q.

(3)計算出Ф(n)=(p-1)*(q-1).

(4)選擇e,使得1

(5)計算解密密鑰參數(shù)d時，要求ed=1 mod Ф(n)，可用擴展的歐幾里得算法求解.由此得出，私鑰(d,n)，然后公開n參數(shù)，其中n又被稱為模，保密原始素數(shù)p和q.

其中(e,n)是公鑰，(d,n)是私鑰.d是秘密的，而n是公開的.密文的解密者(或系統(tǒng))將公鑰公開，而將密鑰和系統(tǒng)參數(shù)兩個大素數(shù)p、q藏起來.

對于RSA算法：D(E(M))=(Me)dmodn=(Md)emodn+E(D(M))，其中M為明文，加密公式C=E(M)=Memodn，解密公式M=D(C)=Cdmodn.

1.5 RSA算法優(yōu)化

由于RSA算法中模正整數(shù)次冪的運算過程復(fù)雜，影響算法執(zhí)行效率，是限制RSA發(fā)展的主要難題.而RSA算法的解密者擁有保密的系統(tǒng)參數(shù)p、q和私鑰，可以在解密過程中利用中國剩余定理進行解密優(yōu)化，先對中國剩余定理做簡單介紹.對于同余方程組(5)：

(5)

若滿足：①m1,m2,…,mr為兩兩互素的正整數(shù)；②a1,a2,…,ar為整數(shù)，則同余方程組(5)的模M=m1,m2,…,mr有唯一解(證明過程省略)：

(6)

其中：Mi=M/mi

yiMi≡1 modmi，1≤i≤r

可見，中國剩余定理能夠把高位寬大數(shù)的模冪運算轉(zhuǎn)換為低位寬相對較小的模冪運算.下面敘述運用中國剩余定理改進RSA解密的方法[11].

在RSA算法中，存在兩個互素的數(shù)p、q，由中國剩余定理，可知求解密方程M=D(C)=Cdmodn的運算，等價于求同余方程組(7)，由此，可實現(xiàn)由計算模n的數(shù)量級轉(zhuǎn)化為計算模p和模q的數(shù)量級.

(7)

(費馬小定理)p為素數(shù)，x為滿足x(modp)≠0條件的整數(shù)，則：xp-1≡1(modp).

由費馬小定理，令r=d(modp-1)，則存在k滿足：d=k(p-1)+r.故：

M1=Cd(modp)≡Ck(p-1)+r(modp)≡

(C(p-1)modp)kCr(modp)≡

1kCr(modp)≡Cd mod(p-1)(modp)≡

(Cmodp)d mod (p-1)(modp)

同理，對同余式M2=Cd(modq)，有：M2=(Cmodq)d mod (q-1)(modq).令d1=dmod(p-1),

d2=dmod(q-1).因此，同余方程組(7)轉(zhuǎn)化為低指數(shù)的同余方程組(8).

(8)

又由中國剩余定理和費馬小定理可知其解：

M=((Cmodp)d1q(q-1modp)+

(Cmodq)d2p(p-1modq))modn=

((Cmodp)d1q(qp-2modp)+

(Cmodq)d2p(pp-2modq)modn=

((Cmodp)d1q(qp-2modn)+

(Cmodq)d2p(pq-2modn)modn=

((Cmodp)d1(qp-1modn)+

(Cmodq)d2pq-1modn)modn

將中國剩余定理應(yīng)用在RSA算法解密過程中，遠遠小于直接進行解密所需指數(shù)運算數(shù)量級，而且通過多項式運算代替逆元的求解，進一步減少運算時間，從而提高運算速度.

根據(jù)RSA的快速MMRC解密算法[12]，步驟1-5為快速解密算法.運用這種算法共有1次逆元，2次乘法，1次加法，1次減法和1次k比特模余，RSA算法解密效率得到進一步提升.計算以下各式：

(1)d1←d(modp-1)與d2←d(modq-1)

(2)C1←C(modp)與C2←C(modq)

(3)M1←C1d1(modp)與M2←C1d2(modq)

(4)B←p-1(modp)

(5)m←M1+[(M2-M1)*B(modq)]*p

2 結(jié)合改進后AES和改進后RSA的QR加密算法

方案總體思路：采用以改進后的AES算法為主、改進后的RSA算法為輔的加密算法，將改進后AES算法加密結(jié)果與改進后RSA算法加密結(jié)果結(jié)合作為QR碼算法的輸入，然后進行二維碼編碼.不妨設(shè)Alice是二維碼的生成方和發(fā)送方，Bob是二維碼的接收方和驗證方，明文為M.算法主要分為以下步驟：

(1)系統(tǒng)建立

發(fā)送方Alice選擇AES算法參數(shù)隨機密鑰x0和第一輪密鑰y0，系統(tǒng)利用RSA生成算法及Bob選擇的RSA公鑰K1=(e,n),系統(tǒng)生成私鑰K2=(d,n),并反饋給Bob,將K1公開，將系統(tǒng)初始化系數(shù)傳遞給接收方Bob.

(2)信息加密

Alice采用改進AES加密算法，選定參數(shù)N=(x0,y0,z0)對明文進行加密，即利用改進后的AES密鑰擴展算法，得到AES算法全部密鑰，再利用全部密鑰進行AES加密算法得到密文M′.將參數(shù)信息N用RSA算法公鑰K1進行加密生成N′.

(3)生成二維碼

Alice將明文密文M′和參數(shù)密文N′拼接在一起并進行一系列后續(xù)操作即數(shù)據(jù)分析、數(shù)據(jù)編碼、糾錯編碼、構(gòu)造最終信息、生成掩膜和格式與版本信息等，生成含有加密信息的二維碼.

(4)密文解密

接收方Bob收到二維碼信息后，掃描并通過RSA算法的私鑰K2進行解密得到二維碼參數(shù)密文N，結(jié)合改進后AES解密算法進而得到明文信息M.

算法加密流程如圖4所示，算法解密流程如圖5所示.

圖4 算法加密流程圖

圖5 算法解密流程圖

3 算法實現(xiàn)

算法實現(xiàn)基于PyCharm平臺，編程語言為python.QR二維碼的生成識別采用zxing解析庫、PIL，pillow和qrCode庫.

Alice在線傳輸明文信息給接收方Bob.Alice作為二維碼生成以及發(fā)送方,傳輸M=′iamgladtoseeyous′作為信息明文，進行測試運行.Alice選擇隨機密鑰x0=2345678910111213，新密鑰y0=1520251221521113，z0=2，加密之后密文M′=c059e873b5a60a9104ef499f961a320B，Bob選取RSA算法公鑰后，由系統(tǒng)生成1024位密鑰，RSA算法加密x0得到x0′，加密y0得到y(tǒng)0′，加密z0得到z0′，中間用′//′分隔.x0′=12906416898900598349674

359045029739702606540597，y0′=425420404286

176275383986137492130476820305389897，z0′=8，將M′和N′用′//′拼接后進行后續(xù)二維碼編碼.

如圖6所示，接收方Bob掃描得到：由AES算法加密的密文M′，由RSA算法加密的AES算法初始向量與第一輪密鑰密文N′.首先使用系統(tǒng)建立時的私鑰K2進行RSA解密，得到參數(shù)明文(x0,y0,z0).再利用AES解密算法和參數(shù)N解密由二維碼傳遞的密文M′，最終獲得信息明文M=

′iamgladtoseeyous′.

圖6 帶有密文和參數(shù)密文信息的QR二維碼圖片

4 算法測試

4.1 加密速度比較

程序運行環(huán)境為：Windows 10，CPU2.5 GHz，RAM 4G.測試軟件為PyCharm 2018.1.2.測試采用四種算法對二維碼編碼前明文加密：

(1)文獻[13]提出的AES算法.

(2)文獻[14]提出的3DES算法.

(3)數(shù)據(jù)加密經(jīng)典傳輸方案AES+RSA算法.

(4)本文提出的結(jié)合了改進后的AES與RSA優(yōu)化算法的加密算法.其中3DES使用3個56位的密鑰進行加密.AES密鑰長度均采用最廣泛的128位，二維碼存儲明文字符串，四種算法對相同的48字節(jié)的字符串分別進行1000次加解密，取得加解密的平均時間，算法加密和解密時間測試結(jié)果在表1中列出.

表1 算法加解密時間比較

由表1可以看出，由于使用了RSA算法對AES密鑰參數(shù)加密，結(jié)合AES和RSA的算法比僅使用AES算法耗費的時間長，但依然在加密速度上優(yōu)于3DES算法，而采用綜合改進后的AES和RSA優(yōu)化算法加、解密消耗時間更少.

4.2 安全性比較

3DES算法是DES算法的一個安全變形，以DES為基本模塊，通過組合分組方法設(shè)計出分組加密算法.目前，針對3DES算法的批評主要有：

(1)3DES易受差分和線性密碼分析攻擊.

(2) 3DES使用64位的塊長度，不能滿足大多數(shù)數(shù)據(jù)傳輸?shù)囊?

(3)用軟件實現(xiàn)該算法的速度比較慢.

針對3DES的缺陷[15]，AES算法得到了解決：

(1)AES與3DES相比對差分、截斷差分、線性、插值和平方攻擊具有很強的抵抗力.

(2)AES最小密鑰長度為128 bits，最大密鑰長度為256 bits，目前技術(shù)不存在窮舉破解的可能.并且AES算法的密鑰長度根據(jù)不同加密級別選擇不同密鑰長度，而分組長度同樣可變，設(shè)計的靈活性高.

(3) AES塊長度128位，是3DES塊長度的兩倍 .

(4)AES具有很高的加密效率.

3DES算法和AES算法兩種對稱密鑰密碼體制，密鑰的分配均存在嚴(yán)重的缺陷，即若黑客在密鑰傳輸過程中截取到密鑰，則密文就不再保密.針對這一缺陷，RSA非對稱密碼體制使用兩個獨立的密鑰，密鑰的分配問題得到了解決.

5 結(jié)論

本文提出一種結(jié)合了改進后的AES與RSA優(yōu)化算法的QR加密算法.該算法結(jié)合兩種算法優(yōu)點，特別是對AES密鑰擴展和列混淆變換兩方面的改進實現(xiàn)了對明文的高效加密、通過RSA算法僅對參數(shù)信息加密，將明文信息加密后的信息密文和參數(shù)信息加密后的參數(shù)密文拼接生成二維碼編碼，再傳送給接收方.在解密算法中，又對RSA解密算法使用中國剩余定理進行了優(yōu)化.該算法相對于傳統(tǒng)二維碼傳送信息和密鑰而言，其加解密過程兼顧了效率和安全性，安全性能得到提高，加解密時間得到減少.該算法具有一定的推廣和實用價值.