駱子玉 洪 璇

(上海師范大學(xué)信息與機(jī)電工程學(xué)院 上海200234)

AES算法在多核的安卓平臺(tái)下的改進(jìn)及應(yīng)用

駱子玉 洪 璇

(上海師范大學(xué)信息與機(jī)電工程學(xué)院 上海200234)

Android已經(jīng)是主流移動(dòng)操作系統(tǒng)，硬件方面多核處理器成為Android設(shè)備的主要配置，多核處理器實(shí)現(xiàn)了真正意義上的多線程，可以做到軟件層面的并行計(jì)算。針對(duì)Android操作系統(tǒng)和多核處理器的特性，提出一種改進(jìn)的AES(Advanced Encryption Standard)算法的方案，在輪變換的環(huán)節(jié)將矩陣分割同時(shí)合并可并行執(zhí)行的變換，在Qualcomm驍龍801四核2.5 GHz處理器，Android 4.4.4系統(tǒng)的配置的手機(jī)中進(jìn)行了實(shí)驗(yàn)測(cè)試，測(cè)試結(jié)果表明加密速度有了較為明顯的提高。最后將改進(jìn)的算法應(yīng)用到SQLite數(shù)據(jù)庫(kù)加密中，提高Android原生數(shù)據(jù)庫(kù)的安全性。

AES算法 輪變換 并行計(jì)算 SQLite數(shù)據(jù)庫(kù)加密

0 引 言

AES算法由美國(guó)國(guó)家標(biāo)準(zhǔn)技術(shù)研究所NIST提出，并且成為加密標(biāo)準(zhǔn)，目的在于代替DES。NIST對(duì)AES候選算法的基本要求是:對(duì)稱分組密碼體制;密鑰長(zhǎng)度支持128 192 256位;明文分組長(zhǎng)度128 位;算法應(yīng)易于各種硬件和軟件實(shí)現(xiàn)。AES算法的并行改進(jìn)的研究在國(guó)內(nèi)外的進(jìn)展有:2011年，Tran 等人[7]提出在GPU上用擴(kuò)展塊大小的方法來(lái)進(jìn)行AES-CTR算法，同粗粒度的GPU并行AES-CTR算法對(duì)比，獲得了接近9倍的加速。2012年，錢曉捷等人[4]基于多核的Rijndael算法的并行優(yōu)化，提出了基于多核處理器的數(shù)據(jù)流分解方式的AES并行優(yōu)化。

傳統(tǒng)的AES加密算法均是在PC端、單核處理器條件下使用的，面對(duì)移動(dòng)互聯(lián)網(wǎng)的興起，多核處理器技術(shù)的發(fā)展，AES算法并行化的方案成為可能?，F(xiàn)有的并行AES算法效率提高有限，并且缺少移動(dòng)端的并行方案測(cè)試。本文針對(duì)AES算法中的輪變換環(huán)節(jié)，給出了一種新的并行執(zhí)行的改進(jìn)方案，結(jié)合明文分組的并行方案，在保證安全性不變的前提下，經(jīng)多核的Android系統(tǒng)設(shè)備下的測(cè)試，明顯提高了算法效率。同時(shí)給出了改進(jìn)后算法在Android系統(tǒng)中的具體應(yīng)用。

1 AES加密算法簡(jiǎn)介

AES安全性強(qiáng)，能對(duì)抗差分攻擊、線性攻擊等已知明文明文攻擊。AES算法的工作常見(jiàn)工作模式有CBC(密碼分組模式)、CFB(密碼反饋模式)、ECB(電子密碼本模式)、OFB(輸出反饋模式)，CRC(計(jì)數(shù)器模式)。ECB模式適合并行計(jì)算，易于標(biāo)準(zhǔn)化，速度快，故本文選用ECB模式。

1.1 AES算法流程

AES算法是一個(gè)密鑰分組加密的算法，分組長(zhǎng)度為128 bit。AES首先將128 bit的明文映射到4×4的矩陣，每四個(gè)字節(jié)構(gòu)成一列。其加密和解密的所有操作都在被稱為state(狀態(tài))的結(jié)果中進(jìn)行。加密過(guò)程：首先進(jìn)行擴(kuò)展密鑰異或(AddRoundKey)，然后進(jìn)行Nround-1次輪變換，包括S盒變換(SubBytes)、行變換(ShiftRows)、列變換(MixColmuns)、擴(kuò)展密鑰異或(AddRoundKey)。最后分別執(zhí)行一次S盒變換，行變換和擴(kuò)展密異或。本文中基于輪變換的改進(jìn)方案是對(duì)輪變換環(huán)節(jié)的修改，算法流程如圖1所示。

圖1 AES算法的流程圖

密鑰擴(kuò)展即在知道密鑰的前提下對(duì)密鑰長(zhǎng)度進(jìn)行擴(kuò)展以達(dá)到加密所需長(zhǎng)度。通過(guò)Expandkey將密鑰擴(kuò)展成4行Nrow*(Nround+1)列的擴(kuò)展密鑰數(shù)組。Nkey表示密鑰所含的數(shù)據(jù)字?jǐn)?shù)，一字等于32 bit，Nround表示輪數(shù)，Nround = Nkey+6，所以對(duì)于128 bit的密鑰來(lái)說(shuō)Nround=10。

KeyExpansion (byteKey[4*Nkey] , W[Nrow*(Nround+1)])

{

for (int i =0; i < Nkey; i ++)

W[i]=(Key[4* i],Key[4* i +1],Key[4* i +2],Key[4* i +3] );

//擴(kuò)展密鑰的前面4個(gè)字由種子密鑰組成

for (i =Nkey; i

{

temp=W[i-1];

if (i % Nkey==0)

temp=SubByte (RotByte (temp))^Rcon[i /Nkey];

//i是NeyK的整數(shù)倍是要特殊處理

W[i]=W[i-Nkey]^ temp;

}

}

Nkey> 6 的密鑰擴(kuò)展

KeyExpansion (byte Key[4*Nkey] , W[Nrow*(Nr+1)])

{

for (int i=0; i < Nkey; i ++)

W[i]=(Key[4* i], Key[4* i +1], Key[4* i +2], Key[4* i +3] );

//擴(kuò)展密鑰的前面4個(gè)字由種子密鑰組成

for (int i =Nkey; i

{

temp=W[i -1];

if (i % Nkey==0)

temp=SubByte (RotByte (temp))^Rcon[i /Nk];

else if (i % Nkey==4)

temp=SubByte (temp);

W[i]=W[i - Nkey]^ temp;

}

}

1.2 輪變換

輪變換主要由四個(gè)步驟組成:S盒變換、行變換、列變換、擴(kuò)展密鑰異或，即SubBytes、ShiftRows、MixColumns、AddRoundKey。

SubBytes變換主要是對(duì)狀態(tài)字節(jié)進(jìn)行SBox運(yùn)算。先求出每個(gè)字節(jié)在GF(28)中的乘法逆元素；然后將其字節(jié)做GF(28)上的放射變換，變換如下：

ShiftRows是一個(gè)行移位變換，將其中的行按照不同的偏移量進(jìn)行循環(huán)移位，128位的Rijndael算法每一行的偏移量是0、1、2、3。

MixColumns變換把上一步狀態(tài)的每一列看做GF(28)上的多項(xiàng)式與一個(gè)固定多項(xiàng)式的模乘:

c(x)=b(x)·a(x)(modx4+1),矩陣形式表示如下：

AddRoundKey：AES算法的每一次都會(huì)需要一個(gè)RoundKey即輪變換密鑰,該密鑰由4個(gè)Byte組成,AddRoundKey變換是要把通過(guò)之前的三個(gè)變換得到的結(jié)果與這一輪的輪變換密鑰進(jìn)行異或運(yùn)算,得到的結(jié)果再進(jìn)行下一輪的AddRoundKey變換。用公式表示如下：

[d0,i,d1,i,d2,i,d3,i]=[c0,i,c1,i,c2,i,c3,i]⊕[wround×Nb+i]

0≤i≤Nb

2 AES算法在Android設(shè)備中的改進(jìn)

目前的安卓設(shè)備中多核的處理器越來(lái)越普及，下文提出2種改進(jìn)的方案，針對(duì)輪變換和明文分組的優(yōu)化，因?yàn)闆](méi)有改變算法執(zhí)行步驟中的運(yùn)算細(xì)節(jié)，所以安全性可以得到保證。

2.1 針對(duì)輪變換的優(yōu)化方案

文中的AES算法以Rijndael為例，密鑰長(zhǎng)度選擇128位。128位的密鑰長(zhǎng)度需要10輪的迭代變換。每一輪涉及4種變換：SubBytes、ShiftRows、MixColumns、AddRoundKey，最后一輪沒(méi)有MixColumns變換。明文塊和經(jīng)過(guò)擴(kuò)展過(guò)后的密鑰經(jīng)過(guò)變換輸出密文塊。

Rijndael算法中輪變換每一步都依賴上一步的結(jié)構(gòu)，但是ShiftRows變換依次作用于矩陣的每一行，所以當(dāng)SubBytes對(duì)第一行的變換結(jié)束后即可直接執(zhí)行第一行的ShiftRows變換。以雙核2線程為例，將SubBytes1記為矩陣第一行的SubBytes變換，ShiftRows1記為矩陣第一行的行變換合并后的偽代碼及流程如圖2所示。

unsigned char t[4];

int r, c;

for (r = 0; r < 2; r++) {

for (c = 0; c < 4; c++) {

state[r][c] = Sbox[state[r][c]];

}

if (r != 0) {

for (c = 0; c < 4; c++) {

t[c] = state[r][(c + r) % 4];

}

for (c = 0; c < 4; c++) {

state[r][c] = t[c];

}

}

}

圖2 改進(jìn)后的SubBytes變換及ShiftRows變換

以此類推,Core2可對(duì)矩陣的后2行進(jìn)行Subytes2+ShiftRows2變換。

MixColumns是對(duì)矩陣每一列進(jìn)行操作，同樣可以在一列執(zhí)行完列變換之后直接進(jìn)行AddRoundKeys操作而不需要等到全部矩陣列變換結(jié)束，改進(jìn)后的MixColumns與AddRoundKeys變換偽代碼如下:

unsigned char t[4];

int r, c;

for (c = 2; c < 4; c++) {

for (r = 0; r < 4; r++) {

t[r] = state[r][c];

}

for (r = 0; r < 4; r++) {

//FFmul列混合變換

state[r][c] = FFmul(0x02, t[r]) ^ FFmul(0x03, t[(r + 1) % 4])^ FFmul(0x01, t[(r + 2) % 4]) ^ FFmul(0x01, t[(r + 3) % 4]);

//變換完直接進(jìn)行AddRoundKey變換

state[r][c] ^= k[r][c];

}

}

順序如圖3所示。

圖3 改進(jìn)后的SubBytes變換及ShiftRows變換

Core2可對(duì)矩陣的后2行進(jìn)行MixColumns2+AddRoundKey2變換。

2.2 明文分組優(yōu)化方案

ECB(Electronic Code Book)電子密碼本模式是分組密碼的一種最基本的工作模式。在該模式下，待處理信息被分為大小合適的分組，然后分別對(duì)每一分組獨(dú)立進(jìn)行加密或解密處理。ECB模式的加密變換公式是：

Ci=Ek(Pi)

解密變換是：Pi=Ek-1(Ci)

ECB模式工作流程如圖4所示。

圖4 ECB模式流程圖

通過(guò)對(duì)明文數(shù)據(jù)的分解，利用多核多線程的優(yōu)勢(shì)，對(duì)分好塊的明文同時(shí)進(jìn)行加密操作。

假設(shè)處理器為N核，則可以將明文分為N塊，對(duì)這N塊數(shù)據(jù)同時(shí)進(jìn)行加密，流程如圖5所示。

偽代碼如下：

//encrypt為加密函數(shù)，Msg1為明文塊1

pthread_create(&t1, NULL, encrypt, Msg1);

//encrypt為加密函數(shù)，Msg1為明文塊2

pthread_create(&t2, NULL, encrypt, Msg2);

圖5 明文分組方案流程圖

3 實(shí)驗(yàn)分析與應(yīng)用

最后將改進(jìn)后的AES算法在Android平臺(tái)下進(jìn)行速度分析，并將加密算法用用于原生SQLite數(shù)據(jù)庫(kù)中使其具有加密功能。

3.1 算法改進(jìn)后的實(shí)驗(yàn)分析

實(shí)驗(yàn)環(huán)境：Qualcomm驍龍801四核2.5 GHz處理器，Android 4.4.4系統(tǒng)，時(shí)間為微秒，AES算法密鑰長(zhǎng)度128 bit。實(shí)驗(yàn)結(jié)果如表1-表3所示。

表1 基于輪變換的改進(jìn)實(shí)驗(yàn)結(jié)果

表2 基于明文數(shù)據(jù)分解的改進(jìn)實(shí)驗(yàn)結(jié)果

表3 兩種方案的改進(jìn)后的AES算法實(shí)驗(yàn)結(jié)果

3.2 改進(jìn)的算法在SQLite數(shù)據(jù)庫(kù)中的應(yīng)用

SQLite是一個(gè)輕量級(jí)的針對(duì)嵌入式系統(tǒng)設(shè)計(jì)的數(shù)據(jù)庫(kù)，它占用的內(nèi)存低，處理速度優(yōu)于Mysql、Oracle等大型數(shù)據(jù)庫(kù)。SQLite可以支持高達(dá)2 TB大小，其中數(shù)據(jù)庫(kù)都是以一個(gè)文件的形式存在，這些數(shù)據(jù)都是以B樹(shù)的數(shù)據(jù)結(jié)構(gòu)的方式存儲(chǔ)在設(shè)備的存儲(chǔ)介質(zhì)上。目前Android和IOS兩大主流移動(dòng)設(shè)備操作系統(tǒng)中均使用SQLite作為自己的數(shù)據(jù)庫(kù)。

SQLite的加密方案:

數(shù)據(jù)庫(kù)管理系統(tǒng)層加密，加密解密過(guò)程對(duì)用戶與應(yīng)用透明，數(shù)據(jù)在物理存取之前完成加解密工作。

這種加解密方式的優(yōu)點(diǎn)是功能強(qiáng)大，并且加密功能集成為數(shù)據(jù)庫(kù)管理系統(tǒng)層的功能，可以實(shí)現(xiàn)加密功能與數(shù)據(jù)庫(kù)管理系統(tǒng)層之間的無(wú)縫對(duì)接。對(duì)于數(shù)據(jù)庫(kù)應(yīng)用來(lái)說(shuō)，庫(kù)內(nèi)加密方式是完全透明的。本文選擇改進(jìn)后的AES加密算法，實(shí)現(xiàn)原生SQLite數(shù)據(jù)庫(kù)的加密接口。加密密鑰的選擇：對(duì)用戶口令的存儲(chǔ)，通常通過(guò)hash(散列)函數(shù)處理后將其hash值進(jìn)行存儲(chǔ)。由于生成的hash值無(wú)法逆向解密，從而是口令的安全性有了保證。常用的散列函數(shù)有 MD5、SHA 等，SHA 比 MD5 更安全，因此，選擇SHA作為密鑰的生成函數(shù)。

SQLite 中加密相關(guān)的接口有4個(gè)：sqlite3_key()、sqlite3_rekey()主要用來(lái)設(shè)置和重置用戶密碼，他們定義在sqlite3.h頭文件中，sqlite3CodecAttach()的作用是將密鑰與sqlite關(guān)聯(lián)。

通過(guò)Android Native Development Kit (NDK)將修改后的 SQLite代碼編譯成libsqlite.so庫(kù)，并使用 Android 調(diào)試工具adb將編譯好的libsqlite.so加載到 Android 手機(jī)或模擬器的動(dòng)態(tài)庫(kù)中。通過(guò)Java Native Interface接口把Sqlite3_key()、sqlite3_rekey()封裝后的API 分別為 SQLiteDataKey()和 SQLiteDataRekey()。接口實(shí)現(xiàn)和修改后數(shù)據(jù)庫(kù)訪問(wèn)如圖5和圖6所示，改進(jìn)后的數(shù)據(jù)庫(kù)無(wú)法通過(guò)軟件打開(kāi)，但可以通過(guò)數(shù)據(jù)庫(kù)操作查看到內(nèi)容。

圖5 數(shù)據(jù)庫(kù)加密接口實(shí)現(xiàn)

圖6 修改后的數(shù)據(jù)庫(kù)訪問(wèn)

4 結(jié) 語(yǔ)

本文針對(duì)多核處理器的特點(diǎn)，分別針對(duì)明文分塊和輪變換提出了改進(jìn)的方案，在安卓平臺(tái)下進(jìn)行了實(shí)驗(yàn)分析。在保證了安全性的前提下，提高了算法的速度，最后針對(duì)安卓系統(tǒng)的不足，用改進(jìn)后的AES算法對(duì)原生SQLite數(shù)據(jù)中的加密接口進(jìn)行了補(bǔ)充，增強(qiáng)了其安全性。

AES的改進(jìn)還存在許多不足之處，如CTR模式下的并行方案，AES算法中S盒的優(yōu)化，針對(duì)安卓系統(tǒng)的算法改進(jìn)都是日后需要做的研究工作。

[1] 姜攀. 并行計(jì)算機(jī)的比較分析[J]. 軟件導(dǎo)刊, 2010,9(6):3-4.

[2] 劉樹(shù)杰．Android下SQLite數(shù)據(jù)庫(kù)安全機(jī)制的設(shè)計(jì)與實(shí)現(xiàn)[OL].http://www.paper.edu.cn.

[3] 柯元旦, 宋銳. Android程序設(shè)計(jì)[M]. 北京：北京航空航天大學(xué)出版社, 2010.

[4] 錢曉捷, 師攀攀, 王建輝. 基于多核的Rijndael算法的并行優(yōu)化與實(shí)現(xiàn)[J].計(jì)算機(jī)工程與設(shè)計(jì),2012,33(6):2197-2202,2235.

[5] 陳國(guó)良. 并行算法的設(shè)計(jì)與分析[M].北京：高等教育出版社,2002:31-35.

[6] 楊豐盛. Android技術(shù)內(nèi)幕[M].北京：機(jī)械工業(yè)出版社, 2011.

[7] Tran N P, Lee M, Hong S, et al. Parallel Execution of AES-CTR Algorithm Using Extended Block Size[C]//Proceedings of IEEE 14th International Conference on Computational Science and Engineering, 2011:191-198.

[8] 許小龍. 基于多核平臺(tái)橢圓曲線算法和AES算法的并行化研究[D].成都：電子科技大學(xué), 2010.

[9] Nickolls J, Dally W J. The GPU Computing Area[J].IEEE Micro,2010,30(2):56-69.

[10] DiMarzio J F. Android: A Programer’s Guide[M].Chicago: McGraw-Hill Osborne Media, 2008.

[11] Enck W, Ongtang M, McDaniel P. Understanding Android Security[J]. IEEE Security and Privacy, 2009,7(1):50-57.

[12] Dalvik Technical Information[EB/OL]. http://source.android.com/tech/dalvik/index.html.

[13] Ferguson N，Kelsey J，Lucks C, et al．Improved Cryptanalysis of Rijndael[C]//Proceedings of the 7th International Conference on Fast Software Encryption, 2001:213-230．

[14] Chin E, Felt A P, Greenwood K, et al. Analyzing inter-application communication in Android[C]//Proceedings of the 9th International Conference on Mobile Systems, Applications, and Services, 2011:239-252.

IMPROVEMENT AND APPLICATION OF THE AES ALGORITHM ON THE MULTI-CORE ANDROID PLATFORM

Luo Ziyu Hong Xuan

(CollegeofInformation，MechanicalandElectricalEngineering,ShanghaiNormalUniversity,Shanghai200234,China)

Android has become the main mobile operating system, and in the aspect of hardware,multi-core processor has become the dominating configuration of Android equipment. It realizes the real sense of multi-thread which is capable to do parallel computing in software level.According to the characteristics of Android operating system and multi-core processor,an improved AES algorithm for the scheme is proposed,including the feasibility of the parallel analysis,parallel implementation in rounds link.Then a test on Android 4.4.4 OS and Qualcomm 801 quad core 2.5 GHz CPU is given.The test results show that the encryption speed has been improved obviously. Aiming at the shortage of SQlite database in Android system, the improved algorithm is applied to SQLite database encryption, and the security of Android database is improved.

AES algorithm Round transformation Parallel computing SQLite database encryption

2015-10-26。上海市自然科學(xué)基金項(xiàng)目(14ZR1431 000)。駱子玉，碩士生，主研領(lǐng)域：信息安全。洪璇，副教授。

TP3

A

10.3969/j.issn.1000-386x.2017.01.038