AES算法在多核的安卓平台下的改进及应用

骆子玉 洪 璇

(上海师范大学信息与机电工程学院 上海200234)

AES算法在多核的安卓平台下的改进及应用

骆子玉 洪 璇

(上海师范大学信息与机电工程学院 上海200234)

Android已经是主流移动操作系统，硬件方面多核处理器成为Android设备的主要配置，多核处理器实现了真正意义上的多线程，可以做到软件层面的并行计算。针对Android操作系统和多核处理器的特性，提出一种改进的AES(Advanced Encryption Standard)算法的方案，在轮变换的环节将矩阵分割同时合并可并行执行的变换，在Qualcomm骁龙801四核2.5 GHz处理器，Android 4.4.4系统的配置的手机中进行了实验测试，测试结果表明加密速度有了较为明显的提高。最后将改进的算法应用到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算法的并行优化，提出了基于多核处理器的数据流分解方式的AES并行优化。

传统的AES加密算法均是在PC端、单核处理器条件下使用的，面对移动互联网的兴起，多核处理器技术的发展，AES算法并行化的方案成为可能。现有的并行AES算法效率提高有限，并且缺少移动端的并行方案测试。本文针对AES算法中的轮变换环节，给出了一种新的并行执行的改进方案，结合明文分组的并行方案，在保证安全性不变的前提下，经多核的Android系统设备下的测试，明显提高了算法效率。同时给出了改进后算法在Android系统中的具体应用。

1 AES加密算法简介

AES安全性强，能对抗差分攻击、线性攻击等已知明文明文攻击。AES算法的工作常见工作模式有CBC(密码分组模式)、CFB(密码反馈模式)、ECB(电子密码本模式)、OFB(输出反馈模式)，CRC(计数器模式)。ECB模式适合并行计算，易于标准化，速度快，故本文选用ECB模式。

1.1 AES算法流程

AES算法是一个密钥分组加密的算法，分组长度为128 bit。AES首先将128 bit的明文映射到4×4的矩阵，每四个字节构成一列。其加密和解密的所有操作都在被称为state(状态)的结果中进行。加密过程：首先进行扩展密钥异或(AddRoundKey)，然后进行Nround-1次轮变换，包括S盒变换(SubBytes)、行变换(ShiftRows)、列变换(MixColmuns)、扩展密钥异或(AddRoundKey)。最后分别执行一次S盒变换，行变换和扩展密异或。本文中基于轮变换的改进方案是对轮变换环节的修改，算法流程如图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变换主要是对状态字节进行SBox运算。先求出每个字节在GF(28)中的乘法逆元素；然后将其字节做GF(28)上的放射变换，变换如下：

ShiftRows是一个行移位变换，将其中的行按照不同的偏移量进行循环移位，128位的Rijndael算法每一行的偏移量是0、1、2、3。

MixColumns变换把上一步状态的每一列看做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种改进的方案，针对轮变换和明文分组的优化，因为没有改变算法执行步骤中的运算细节，所以安全性可以得到保证。

2.1 针对轮变换的优化方案

文中的AES算法以Rijndael为例，密钥长度选择128位。128位的密钥长度需要10轮的迭代变换。每一轮涉及4种变换：SubBytes、ShiftRows、MixColumns、AddRoundKey，最后一轮没有MixColumns变换。明文块和经过扩展过后的密钥经过变换输出密文块。

Rijndael算法中轮变换每一步都依赖上一步的结构，但是ShiftRows变换依次作用于矩阵的每一行，所以当SubBytes对第一行的变换结束后即可直接执行第一行的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是对矩阵每一列进行操作，同样可以在一列执行完列变换之后直接进行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 明文分组优化方案

ECB(Electronic Code Book)电子密码本模式是分组密码的一种最基本的工作模式。在该模式下，待处理信息被分为大小合适的分组，然后分别对每一分组独立进行加密或解密处理。ECB模式的加密变换公式是：

Ci=Ek(Pi)

解密变换是：Pi=Ek-1(Ci)

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

图4 ECB模式流程图

通过对明文数据的分解，利用多核多线程的优势，对分好块的明文同时进行加密操作。

假设处理器为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 算法改进后的实验分析

实验环境：Qualcomm骁龙801四核2.5 GHz处理器，Android 4.4.4系统，时间为微秒，AES算法密钥长度128 bit。实验结果如表1-表3所示。

表1 基于轮变换的改进实验结果

表2 基于明文数据分解的改进实验结果

表3 两种方案的改进后的AES算法实验结果

3.2 改进的算法在SQLite数据库中的应用

SQLite是一个轻量级的针对嵌入式系统设计的数据库，它占用的内存低，处理速度优于Mysql、Oracle等大型数据库。SQLite可以支持高达2 TB大小，其中数据库都是以一个文件的形式存在，这些数据都是以B树的数据结构的方式存储在设备的存储介质上。目前Android和IOS两大主流移动设备操作系统中均使用SQLite作为自己的数据库。

SQLite的加密方案:

数据库管理系统层加密，加密解密过程对用户与应用透明，数据在物理存取之前完成加解密工作。

这种加解密方式的优点是功能强大，并且加密功能集成为数据库管理系统层的功能，可以实现加密功能与数据库管理系统层之间的无缝对接。对于数据库应用来说，库内加密方式是完全透明的。本文选择改进后的AES加密算法，实现原生SQLite数据库的加密接口。加密密钥的选择：对用户口令的存储，通常通过hash(散列)函数处理后将其hash值进行存储。由于生成的hash值无法逆向解密，从而是口令的安全性有了保证。常用的散列函数有 MD5、SHA 等，SHA 比 MD5 更安全，因此，选择SHA作为密钥的生成函数。

SQLite 中加密相关的接口有4个：sqlite3_key()、sqlite3_rekey()主要用来设置和重置用户密码，他们定义在sqlite3.h头文件中，sqlite3CodecAttach()的作用是将密钥与sqlite关联。

通过Android Native Development Kit (NDK)将修改后的 SQLite代码编译成libsqlite.so库，并使用 Android 调试工具adb将编译好的libsqlite.so加载到 Android 手机或模拟器的动态库中。通过Java Native Interface接口把Sqlite3_key()、sqlite3_rekey()封装后的API 分别为 SQLiteDataKey()和 SQLiteDataRekey()。接口实现和修改后数据库访问如图5和图6所示，改进后的数据库无法通过软件打开，但可以通过数据库操作查看到内容。

图5 数据库加密接口实现

图6 修改后的数据库访问

4 结 语

本文针对多核处理器的特点，分别针对明文分块和轮变换提出了改进的方案，在安卓平台下进行了实验分析。在保证了安全性的前提下，提高了算法的速度，最后针对安卓系统的不足，用改进后的AES算法对原生SQLite数据中的加密接口进行了补充，增强了其安全性。

AES的改进还存在许多不足之处，如CTR模式下的并行方案，AES算法中S盒的优化，针对安卓系统的算法改进都是日后需要做的研究工作。

[1] 姜攀. 并行计算机的比较分析[J]. 软件导刊, 2010,9(6):3-4.

[2] 刘树杰．Android下SQLite数据库安全机制的设计与实现[OL].http://www.paper.edu.cn.

[3] 柯元旦, 宋锐. Android程序设计[M]. 北京：北京航空航天大学出版社, 2010.

[4] 钱晓捷, 师攀攀, 王建辉. 基于多核的Rijndael算法的并行优化与实现[J].计算机工程与设计,2012,33(6):2197-2202,2235.

[5] 陈国良. 并行算法的设计与分析[M].北京：高等教育出版社,2002:31-35.

[6] 杨丰盛. Android技术内幕[M].北京：机械工业出版社, 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