鄭志學(xué)，李長(zhǎng)云，倪 偉

（湖南工業(yè)大學(xué) 計(jì)算機(jī)與通信學(xué)院，湖南 株洲 412007）

一種基于多線程加密的防偽二維碼的生成方法

鄭志學(xué)，李長(zhǎng)云，倪 偉

（湖南工業(yè)大學(xué) 計(jì)算機(jī)與通信學(xué)院，湖南 株洲 412007）

針對(duì)運(yùn)用RSA算法生成防偽二維碼過(guò)程中，因大數(shù)的模冪運(yùn)算導(dǎo)致效率低下的問(wèn)題，利用GPU在多線程并行計(jì)算中的優(yōu)勢(shì)，將大數(shù)的模冪運(yùn)算轉(zhuǎn)化為小整數(shù)的多階段的并行模冪運(yùn)算，采用多線程技術(shù)對(duì)分解后的小數(shù)進(jìn)行處理，最終合并運(yùn)算結(jié)果，生成相應(yīng)的防偽二維碼。通過(guò)一系列實(shí)驗(yàn)對(duì)改進(jìn)前后的二維碼生成時(shí)間進(jìn)行對(duì)比，結(jié)果表明改進(jìn)后的方案能有效地提升防偽二維碼系統(tǒng)的運(yùn)行效率。

GPU；RSA加密；并行運(yùn)算；二維碼

0 引言

二維碼是一種新興的信息數(shù)據(jù)的載體，自20世紀(jì)80年代產(chǎn)生以來(lái)以其獨(dú)特的便利特性得到了廣泛的應(yīng)用。隨著科學(xué)技術(shù)和理論研究的不斷發(fā)展，二維碼的種類和表現(xiàn)形式呈現(xiàn)多態(tài)特性，其中比較流行的有PDF417、QR Code、Data Matrix、Maxi Code等[1]。而QR Code以其良好的兼容性和糾錯(cuò)性在支付和數(shù)據(jù)傳輸方面得到了更為廣泛的關(guān)注和運(yùn)用。在商業(yè)活動(dòng)中對(duì)產(chǎn)品信息的保護(hù)非常重要，而QR Code的低成本、易生成和便攜帶的特點(diǎn)使其成為商業(yè)活動(dòng)中的重要信息攜帶載體[2]。傳統(tǒng)的二維碼信息極易被仿造和復(fù)制，在一些較為重要商品信息的流通過(guò)程中此問(wèn)題尤為突出。因此，針對(duì)二維碼的防偽加密研究已經(jīng)成為國(guó)內(nèi)的研究熱點(diǎn)，而基于RSA非對(duì)稱加密技術(shù)的防偽二維碼生成方式，以其密匙傳輸?shù)谋憷匦院蜆O高的安全性得到了廣泛的應(yīng)用[3]。然而隨著計(jì)算機(jī)硬件的快速發(fā)展和加密技術(shù)的理論研究不斷深入，對(duì)加密數(shù)據(jù)進(jìn)行攻擊和破解的技術(shù)也在快速地提升。因此，以大數(shù)分解難度作為其安全性保證的RSA加密算法，需不斷地提升其密匙長(zhǎng)度來(lái)適應(yīng)不同環(huán)境下的安全要求。雖然大數(shù)分解作為數(shù)學(xué)界至今未解的難題，但是通過(guò)不斷提升模長(zhǎng)來(lái)保證數(shù)據(jù)信息的安全性則成為制約RSA加密算法應(yīng)用的瓶頸。目前768 b模長(zhǎng)的RSA體制已經(jīng)不再安全，一般采用1 024 b或2 048 b的模長(zhǎng)體制才能保證信息的安全性[4]，但與此同時(shí)，增大模長(zhǎng)體制的加密方式也使得產(chǎn)生密文的時(shí)間成倍增長(zhǎng)，由此導(dǎo)致了防偽二維碼的生成效率極為低下。

因此本文提出了一種基于多線程的防偽二維碼生成方法，借助GPU在并行計(jì)算上的優(yōu)勢(shì)，將RSA加密算法中的極大整數(shù)進(jìn)行分解，利用多線程的小整數(shù)模冪運(yùn)算來(lái)縮短加密時(shí)間，達(dá)到提升防偽二維碼生成效率的目的。

1 傳統(tǒng)防偽二維碼加密方式

由于非對(duì)稱加密算法中產(chǎn)生了2種不同的密匙，即公匙和私匙，而私匙的保密性和公匙的可分發(fā)性使得非對(duì)稱加密算法的應(yīng)用范圍極為廣泛，而非對(duì)稱加密算法中的RSA算法在經(jīng)歷了30多年發(fā)展和驗(yàn)證之后，其安全性和穩(wěn)定性得到了廣泛的認(rèn)可。隨著二維碼技術(shù)的逐漸成熟和流行，在商業(yè)活動(dòng)中運(yùn)用二維碼進(jìn)行防偽的方法得到越來(lái)越廣泛的關(guān)注，而RSA非對(duì)稱的加密算法以其良好的安全性和穩(wěn)定性逐漸成為二維碼加密防偽的主要方式。

1.1 RSA加密算法原理描述

RSA加密算法是在1977年由美國(guó)麻省理工學(xué)院R. Rives、A. Shamir、L. Adleman 3位學(xué)者提出的[5]。經(jīng)過(guò)多年的實(shí)踐驗(yàn)證，RSA算法以其算法的完善性、安全性和便于實(shí)現(xiàn)等特性得到了廣泛的應(yīng)用[6]。其基本實(shí)現(xiàn)方法如下。

1）為了保證加密的可靠性，先隨機(jī)獲取2個(gè)極大的素?cái)?shù)p和q。

2）通過(guò)公式n=pq和gcd(e, (n))=1計(jì)算出響應(yīng)的函數(shù)值。

3）隨機(jī)選取極大整數(shù)公匙e使其滿足gcd(e, (n))= 1。

4）通過(guò)公式ed≡1(mod (n))來(lái)求解密匙L。

5）保留從上面獲取公匙e，私匙d和模長(zhǎng)n，以(e, n)作為加密公匙，以(d, n)作為加密私匙。

6）通過(guò)加密算法c=E(m)=me(mod n)和解密算法m=D(c)=cd(mod n)來(lái)對(duì)數(shù)據(jù)信息進(jìn)行加密和解密操作。

大數(shù)分解依然是數(shù)論中一個(gè)未解的難題，因此破譯RSA的難度幾乎與大數(shù)的分解難度等價(jià)[7]。RSA加密算法作為目前最優(yōu)秀也是應(yīng)用最廣泛的公匙方案，在過(guò)去的幾十年中經(jīng)歷了各種破譯考驗(yàn)而逐漸被人們所接受和認(rèn)可[8]。RSA算法加密和解密的流程如圖1所示[9]。

圖1 RSA加密和解密流程圖Fig. 1 Flow chart of RSA encryption and decryption

1.2 傳統(tǒng)基于非對(duì)稱加密的防偽二維碼存在的問(wèn)題

RSA算法的安全性建立在以大數(shù)分解困難的基礎(chǔ)上，雖然大數(shù)分解的是數(shù)論中一個(gè)未解的難題，但是隨著計(jì)算機(jī)硬件和密碼學(xué)理論不斷地發(fā)展，以RSA為代表的非對(duì)稱加密算法的安全性不斷地受到新的威脅。1994年彼得·秀爾證明一臺(tái)量子計(jì)算機(jī)可以在多項(xiàng)式時(shí)間內(nèi)進(jìn)行因數(shù)分解。1999年，數(shù)百臺(tái)電腦合作分解了一個(gè)512 b的密碼，從而導(dǎo)致需要不斷地增長(zhǎng)密匙的長(zhǎng)度。到目前為止公認(rèn)較為安全的密匙長(zhǎng)度為1 024 b，而在一些對(duì)安全要求極為嚴(yán)格的領(lǐng)域，密匙長(zhǎng)度甚至達(dá)到2 048 b。隨著密匙長(zhǎng)度的不斷增加，密匙產(chǎn)生的效率也在不斷地下降，加密時(shí)間也在不斷地增長(zhǎng)，從而影響防偽二維碼生成系統(tǒng)的整體效率。由此可知，如何縮短加密時(shí)間是提升防偽二維碼生成系統(tǒng)的整體效率的關(guān)鍵所在。圖2為不同密匙長(zhǎng)度條件下加密大小分別為200 B，2 kB，10 kB數(shù)據(jù)的加密時(shí)間對(duì)比。

圖2 不同密匙長(zhǎng)度下數(shù)據(jù)加密時(shí)間Fig.2 Data Encryption Time under Different Key Lengths

2 GPU多線程并行運(yùn)算技術(shù)

當(dāng)前社會(huì)信息量呈現(xiàn)爆炸式增長(zhǎng)，從而導(dǎo)致數(shù)據(jù)計(jì)算量不斷提升，傳統(tǒng)的基于CPU的串行計(jì)算方式已經(jīng)無(wú)法滿足人們對(duì)高效數(shù)據(jù)處理的要求，而GPU在多線程并行數(shù)據(jù)處理方面的先天優(yōu)勢(shì)則越來(lái)越受到廣泛的關(guān)注?；贕PU的多線程并行運(yùn)算的CUDA（compute unified device architecture）框架則是在這種需求條件下產(chǎn)生的，它以成本低廉、易于實(shí)現(xiàn)和無(wú)需掌握復(fù)雜的圖像編程方法而逐漸被人們所認(rèn)可。其架構(gòu)的基本原理為：以CPU作為Host端來(lái)控制整體復(fù)雜的計(jì)算任務(wù)流程，以GPU作為Device端，利用其多核多線程的優(yōu)勢(shì)，根據(jù)Host端的任務(wù)調(diào)度進(jìn)行高密度的并行數(shù)學(xué)計(jì)算，最終將計(jì)算結(jié)果反饋到Host端從而大大縮短數(shù)據(jù)計(jì)算的時(shí)間，為數(shù)據(jù)的后續(xù)操作提供了便利。通過(guò)CUDA框架實(shí)現(xiàn)多線程高并發(fā)的流程如圖3所示。

圖3 CUDA框架實(shí)現(xiàn)多線程高并發(fā)的流程Fig. 3 Flowchart of the multi-threading high concurrency achieved under CUDA framework

3 基于多進(jìn)程的RSA加密算法生成防偽二維碼方案

3.1 基本原理

傳統(tǒng)防偽二維碼的生成效率低下的原因在于：采用非對(duì)稱的RSA算法進(jìn)行加密操作時(shí)，為了保證信息的安全性故而采用了較長(zhǎng)的密匙，而大數(shù)的模冪運(yùn)算在串行方式情況下不僅效率低下而且對(duì)系統(tǒng)的資源要求也十分苛刻。因此假設(shè)需要加密的明文信息為某一大整數(shù)X，而X可以分解為多個(gè)小整數(shù)的乘積，即X=X1×X2×…×Xn，由此可知原本的計(jì)算密文的算法就改為Y=(X1×X2×…×Xn)e(mod n)。進(jìn)一步可以轉(zhuǎn)化為。從而將大數(shù)的模冪運(yùn)算轉(zhuǎn)換成小整數(shù)的運(yùn)算，通過(guò)基于CUDA架構(gòu)的多線程并行運(yùn)算來(lái)提升加密的效率。

3.2 實(shí)現(xiàn)步驟

1）首先獲取500以內(nèi)的素?cái)?shù)作為基本的小整數(shù)。

2）設(shè)需要加密的明文信息為一大整數(shù)X，根據(jù)因式分解的性質(zhì)可知如果小素?cái)?shù)a和b均為X的因子，那么素?cái)?shù)a和b的乘積也必然是X的因子。因此，假設(shè)獲取的素?cái)?shù)個(gè)數(shù)為N，并行線程數(shù)為M則每一個(gè)線程中分配的因子個(gè)數(shù)S為N/M個(gè)，為了避免進(jìn)程中的素?cái)?shù)大小分配不均導(dǎo)致個(gè)別線程計(jì)算效率低下的問(wèn)題，在分配素?cái)?shù)之前需要先對(duì)基本N個(gè)小整數(shù)進(jìn)行排序，按照兩端各自取數(shù)的分配方式來(lái)使得素?cái)?shù)能夠平均分配在不同的線程中。

3）在各個(gè)線程中對(duì)所分配的基本小素進(jìn)行整除運(yùn)算，保留那些能夠整除X的基本小數(shù)（以X1X2…Xn為例），對(duì)保留的小數(shù)就進(jìn)行如下運(yùn)算X=X/(X1× X2×…×Xn)，之后重復(fù)步驟2，直至沒(méi)有能夠被整除的素?cái)?shù)為止。

4）通過(guò)以上步驟保留的小整數(shù)即可作為多線程并行運(yùn)算的最終小整數(shù)，按照步驟2中對(duì)基數(shù)排序的方式對(duì)小整數(shù)進(jìn)行排序，再次將這些小整數(shù)平均地分配到不同的線程中，在不同的線程中計(jì)算不同的密文信息，如線程1中分配的小整數(shù)為X1X2…Xm，線程2中分配的小整數(shù)為Xm+1Xm+2…Xn,則根據(jù)密文的計(jì)算公式線程1中的最終整數(shù)即為，線程2的最終整數(shù)為,之后的線程以此類推從而最終的密文信息Y=Y1Y2…Yn(mod n)。

5）根據(jù)密文信息Y生成相對(duì)應(yīng)的二維碼。

整體流程如圖4所示。

圖4 多線程防偽二維碼生成流程Fig. 4 Generation process of multi-threading counterfeit-proof two-dimensional codes

4 實(shí)驗(yàn)與結(jié)果分析

本文按照文中所述的實(shí)現(xiàn)方式，采用配置為Intel酷睿雙核2.0 GHz，2 G內(nèi)存，500 G硬盤(pán)，GT420M顯卡為主要硬件平臺(tái)，以Windows 7系統(tǒng)作為系統(tǒng)測(cè)試平臺(tái)，以CUDA架構(gòu)作為數(shù)據(jù)多線程并行加密的實(shí)現(xiàn)方式，以Visual Studio 6.0為開(kāi)發(fā)工具，采用尺寸為256×256容錯(cuò)等級(jí)為L(zhǎng)的二維碼進(jìn)行測(cè)試和驗(yàn)證。

當(dāng)數(shù)據(jù)量較小時(shí)，采用多線程并行運(yùn)算對(duì)單次的數(shù)據(jù)加密時(shí)間極短，從而無(wú)法統(tǒng)計(jì)較為準(zhǔn)確的單次防偽二維碼生成時(shí)間。考慮到實(shí)際情況下二維碼的信息存儲(chǔ)量限制，產(chǎn)品防偽數(shù)據(jù)大小一般不會(huì)超過(guò)500 B，因此本文采用數(shù)據(jù)量為100, 300, 500 B的明文信息分別在模數(shù)長(zhǎng)度為512, 1 024, 2 048 b的條件下進(jìn)行測(cè)試，將傳統(tǒng)防偽二維碼和改進(jìn)后的二維碼生成時(shí)間進(jìn)行對(duì)比，實(shí)驗(yàn)統(tǒng)計(jì)如表1和表2所示。實(shí)驗(yàn)結(jié)果表明，在明文數(shù)據(jù)量相同的情況下，改進(jìn)后的多線程并行產(chǎn)生防偽二維碼的產(chǎn)生的時(shí)間比傳統(tǒng)串行加密生成防偽二維碼的時(shí)間縮短了近60%，而且當(dāng)數(shù)據(jù)量增加時(shí)候，防偽二維碼的產(chǎn)生效率也有明顯的提升。以上結(jié)果說(shuō)明，本文提出的基于多線程的并行加密方式生成二維碼的方法，能有效地改進(jìn)傳統(tǒng)防偽二維碼生成效率低下的問(wèn)題。

表1 傳統(tǒng)防偽二維碼生成時(shí)間Table 1 Generation time of conventional counterfeitproof two-dimensional codes

表2 改進(jìn)后的防偽二維碼生成時(shí)間Table 2 Generation time of improved counterfeitproof two-dimensional codes

5 結(jié)語(yǔ)

傳統(tǒng)防偽二維碼因?yàn)槭腔贑PU的串行加密方式，當(dāng)數(shù)據(jù)量較大時(shí)，生成防偽二維碼的時(shí)間大部分消耗在對(duì)明文數(shù)據(jù)處理的階段，從而大大降低了整體二維碼的生成效率。然而由于加密方式的不同，到目前為止還沒(méi)有一個(gè)較為系統(tǒng)的提升防偽二維碼生成效率的方案。因此本文在分析傳統(tǒng)基于RSA加密的防偽二維碼生成方式的基礎(chǔ)上，借鑒并行運(yùn)算對(duì)數(shù)據(jù)處理的高效特性，提出基于GPU的多線程并行加密運(yùn)算生成防偽二維碼的方法來(lái)改善防偽二維碼的生成效率問(wèn)題，提升系統(tǒng)整體穩(wěn)定性。同時(shí)由于多線程并行運(yùn)算中因數(shù)據(jù)分布不均從而影響系統(tǒng)的整體效率，以后將在多線程并行運(yùn)算中線程數(shù)的選擇以及小素?cái)?shù)平均分配問(wèn)題上作進(jìn)一步的研究。

[1]于英政. QR二維碼相關(guān)技術(shù)的研究[D]. 北京：北京交通大學(xué)，2014．YU Yingzheng. Research on QR Code Correlation Technique [D]. Beijing：Beijing Jiaotong University，2014.

[2]陳 君. 二維碼技術(shù)在移動(dòng)終端的安全應(yīng)用研究[D]. 廣州：廣東工業(yè)大學(xué)，2015. CHEN Jun. QR-Code Technology in the Mobile Terminal Security Application Research[D]. Guangzhou：Guangdong University of Technology，2015.

[3]王立新. 基于移動(dòng)物聯(lián)網(wǎng)的溯源與防偽系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D]. 成都：電子科技大學(xué)，2015. WANG Lixin. Design and Implementation of Traceability and Anti-Counterfeiting System Based on Mobile Internet of Things[D]. Chengdu：University of Electronic Science and Technology of China，2015.

[4] 胡 云. RSA算法研究與實(shí)現(xiàn)[D]. 北京：北京郵電大學(xué)，2010. HU Yun. Research and Implementation of RSA Algorithm [D]. Beijing：Beijing University of Posts and Telecommunications，2010.

[5] 張永建. RSA算法和SM2算法的研究[D]. 贛州：江西理工大學(xué)，2015. ZHANG Yongjian. Research on RSA Algorithm and SM2 Algorithm[D]. Ganzhou：Jiangxi University of Science and Technology，2015.

[6]YANG C C，CHANG T S，JEN C W. A New RSA Cryp,tosystem Hardware Design Based on Montgomerys Algorithm[J]. IEEE Trans Circuits and Systems，1998，45 (7) ：908-913.

[7] 錢亞彬. 基于RSA算法的二維碼防偽技術(shù)在生鮮產(chǎn)品領(lǐng)域的設(shè)計(jì)與應(yīng)用[D]. 開(kāi)封：河南大學(xué)，2015. QIAN Yabin. QR-code Anti-Counterfeiting Technology Based on RSA Algorithm Design and Application in the Field of Fresh Products[D]. Kaifeng：Henan University, 2015.

[8]宋 琦. 基于RSA的一般訪問(wèn)結(jié)構(gòu)的秘密共享研究[D].合肥：合肥工業(yè)大學(xué)，2015. SONG Qi. General Access Structure Based on RSA Secret Sharing Research[D]. Hefei：Hefei University of Technology，2015.

[9]孫 偉. 公鑰RSA加密算法的改進(jìn)與實(shí)現(xiàn)[D]. 合肥：安徽大學(xué)，2014. SUN Wei. Improvement and Implementation of a Public Key RSA Encryption Algorithm[D]. Hefei：Anhui University，2014.

（責(zé)任編輯：申 劍）

A Generation Method of Counterfeit-Proof Two-Dimensional Codes Based on Multi-Threading Encryption

ZHENG Zhixue，LI Changyun，NI Wei
（School of Computer and Communication，Hunan University of Technology，Zhuzhou Hunan 412007，China）

In view of the inefficiency resulting from modular exponentiation of large numbers in the generation process of counterfeit-proof two-dimensional codes by using RSA algorithm, the modular exponentiation of large numbers can be transformed into the small integer stage parallel modular exponentiation by taking advantage of GPU in the multithreading parallel computing process. The fractional decimals can be processed by adopting the multi-threading technique, with the final calculation result merged together, to generate the corresponding counterfeit-proof two-dimensional code. A comparison has been made between the generation time of the two-dimensional codes before and after they are improved. The experimental results show that the improved scheme helps to improve the efficiency of the two-dimensional code system effectively.

GPU；RSA encryption；parallel arithmetic；two-dimensional codes

TP301.6

A

1673-9833(2016)05-0041-04

10.3969/j.issn.1673-9833.2016.05.009

2016-07-17

鄭志學(xué)（1989-），男，河南濟(jì)源人，湖南工業(yè)大學(xué)碩士生，主要研究方向?yàn)閿?shù)據(jù)加密與防偽，E-mail：sunfree@qq.com