駱子玉 洪 璇

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

AES算法在多核的安卓平臺下的改進及應用

駱子玉 洪 璇

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

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

AES算法 輪變換 并行計算 SQLite數據庫加密

0 引 言

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

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

1 AES加密算法簡介

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

1.1 AES算法流程

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

圖1 AES算法的流程圖

密鑰擴展即在知道密鑰的前提下對密鑰長度進行擴展以達到加密所需長度。通過Expandkey將密鑰擴展成4行Nrow*(Nround+1)列的擴展密鑰數組。Nkey表示密鑰所含的數據字數，一字等于32 bit，Nround表示輪數，Nround = Nkey+6，所以對于128 bit的密鑰來說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] );

//擴展密鑰的前面4個字由種子密鑰組成

for (i =Nkey; i

{

temp=W[i-1];

if (i % Nkey==0)

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

//i是NeyK的整數倍是要特殊處理

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

}

}

Nkey> 6 的密鑰擴展

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] );

//擴展密鑰的前面4個字由種子密鑰組成

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 輪變換

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

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

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

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

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

AddRoundKey：AES算法的每一次都會需要一個RoundKey即輪變換密鑰,該密鑰由4個Byte組成,AddRoundKey變換是要把通過之前的三個變換得到的結果與這一輪的輪變換密鑰進行異或運算,得到的結果再進行下一輪的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設備中的改進

目前的安卓設備中多核的處理器越來越普及，下文提出2種改進的方案，針對輪變換和明文分組的優(yōu)化，因為沒有改變算法執(zhí)行步驟中的運算細節(jié)，所以安全性可以得到保證。

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

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

Rijndael算法中輪變換每一步都依賴上一步的結構，但是ShiftRows變換依次作用于矩陣的每一行，所以當SubBytes對第一行的變換結束后即可直接執(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 改進后的SubBytes變換及ShiftRows變換

以此類推,Core2可對矩陣的后2行進行Subytes2+ShiftRows2變換。

MixColumns是對矩陣每一列進行操作，同樣可以在一列執(zhí)行完列變換之后直接進行AddRoundKeys操作而不需要等到全部矩陣列變換結束，改進后的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]);

//變換完直接進行AddRoundKey變換

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

}

}

順序如圖3所示。

圖3 改進后的SubBytes變換及ShiftRows變換

Core2可對矩陣的后2行進行MixColumns2+AddRoundKey2變換。

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

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

Ci=Ek(Pi)

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

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

圖4 ECB模式流程圖

通過對明文數據的分解，利用多核多線程的優(yōu)勢，對分好塊的明文同時進行加密操作。

假設處理器為N核，則可以將明文分為N塊，對這N塊數據同時進行加密，流程如圖5所示。

偽代碼如下：

//encrypt為加密函數，Msg1為明文塊1

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

//encrypt為加密函數，Msg1為明文塊2

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

圖5 明文分組方案流程圖

3 實驗分析與應用

最后將改進后的AES算法在Android平臺下進行速度分析，并將加密算法用用于原生SQLite數據庫中使其具有加密功能。

3.1 算法改進后的實驗分析

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

表1 基于輪變換的改進實驗結果

表2 基于明文數據分解的改進實驗結果

表3 兩種方案的改進后的AES算法實驗結果

3.2 改進的算法在SQLite數據庫中的應用

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

SQLite的加密方案:

數據庫管理系統(tǒng)層加密，加密解密過程對用戶與應用透明，數據在物理存取之前完成加解密工作。

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

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

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

圖5 數據庫加密接口實現

圖6 修改后的數據庫訪問

4 結 語

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

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

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

[2] 劉樹杰．Android下SQLite數據庫安全機制的設計與實現[OL].http://www.paper.edu.cn.

[3] 柯元旦, 宋銳. Android程序設計[M]. 北京：北京航空航天大學出版社, 2010.

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

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

[6] 楊豐盛. Android技術內幕[M].北京：機械工業(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] 許小龍. 基于多核平臺橢圓曲線算法和AES算法的并行化研究[D].成都：電子科技大學, 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。上海市自然科學基金項目(14ZR1431 000)。駱子玉，碩士生，主研領域：信息安全。洪璇，副教授。

TP3

A

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