AES算法中S-box和列混合单元的优化及FPGA实现

+c2在GF(24)上的乘法逆元。各部分的逻辑实现过程可描述如下：

　　(1)有限域GF(28)到复合域GF[(24)2]映射。通过GF(28)上的即约多项式p(x)=x2+Ax+B构造线性变换T，根据式(8)将GF(28)的输入x映射到GF(24)上的元素b，c：

　　式中：B是GF(24)上的常量元素；T是一个8×8的矩阵，矩阵的元素是0或1，T矩阵由B的取值决定；A取1，B取8；

　　(2)GF[(24)2]到GF(28)的逆映射。构造线性变换T-1，GF(24)上的逆p，q映射到GF(28)上的逆元素y，如式(10)所示。其中，线性变换T-1和乘法求递步骤(1)中的线性变换T满足：TT-1=E。

　　(3)通过域GF(24)上的运算，求b，C的逆p，q。首先构建GF(24)，q(x)=x4+x+1作为域GF(24)上的本源多项式，a(x)，d(x)，e(x)∈GF(24)。其中，a(x)=a3x3+a2x2+a1x+a0，d(x)=d3x3+d2x2+d1x+d0，e(x)=e3x3+e2x2+e1x+e0定义域GF(24)上的加法、乘法、逆运算。

　　①加法为按位异或。

　　②乘法为多项式相乘后用q(x)取模，按公式e(x)=a(x)??d(x)mod q(x)进行运算；

　　③求逆根据公式公式a·a-1=1 mod q(x)，计算GF(24)上元素a的逆a-1；

　　构造GF(24)上的一次多项式bx+c，并利用上述GF(24)上的加法、乘法和求逆运算进行运算，得到GF(24)上的元素b，c的逆p，q，由式(7)可得：

　　p，q的计算是S-box中最复杂的逻辑运算，占用了大量的逻辑关系，关于p，q的分量元素计算是由上述算法中的分量元素代入式(13)、式(14)求得。

　　在这种设计方案中，求逆运算模块中所选用的即约多项式p(x)和本源多项式q(x)不同，减低了求逆模块的复杂度。根据理论分析，本文中用到的p(x)和q(x)不会减低AES算法的安全性。

　　2 列混合单元的优化设计

　　在列混合(MixColumn)和逆列混合(InvMixColumn)的操作中，由以下两式定义了两个主要操作：

　　将式(15)和式(16)所做的操作及结果列于表1中，由步骤1～步骤5处理的结果得到outx，接着由outx和w8得到outy。因此，在执行过程中，操作所用到的硬件资源及其所得结果可以应用到步骤9，步骤10中。如图3所示，这种新型结构(字节-列混合模块)仅需8个加法器和4个乘法器。与原方案相比，此设计大大减少了硬件复杂度并显著节省了资源的消耗。

　　图3中：Xt模块(AES中的乘法器)的计算公式为：

　　更进一步，会发现，要建立一个全局的逆选择列混合模块，需要将4个字节一列混合模块集成在一起，形成一个全新的字一列混合模块(Word_MixColumn模块)，如图4所示。

　　这种模块设计可以通过部分分享硬件来同时实现列混合和逆列混合的功能，实现了硬件资源的节省。

　　3 综合结果

　　在同等频率要求的前提下，对S-box及列混合单元进行了优化，目的是减小设计面积。优化后的算法在ModelSimSE 6.2b下进行仿真，并在Xilinx Spartan 3系列FPGA上进行综合验证，时钟频率达到166 MHz，占用3 212个基本逻辑门(一个基本逻辑门等效于两输入／输出的与门)，与参考文献[1]中方法相比节约52％。由于本文中S-box和InvS-box共用求逆电路，与文献[2]中的优化方法相比硬件资源节约66％。

　　其中硬件复杂度为门级电路个数。

　　4 结 语

　　在AES的经典算法中S-box常常采用查找表的形式来实现，这样会占用大量的硬件资源。本文采用S-box与逆S-box组合以及GF(28)到GF(24)同构变换的方法对S-box进行优化，同时，对AES中较复杂的列混合模块进行了集成优化。优化后的方案在不降低密码算法安全性的前提下，较好的降低了硬件复杂度，非常适用于信用卡以及其它对硬件规模要求严格的应用。