AES算法中S-box和列混合单元的优化及FPGA技术实现
时间：2010-05-04 12:32:50
手机看文章
扫描二维码
随时随地手机看文章
[导读]AES算法中S-box和列混合单元的优化及FPGA技术实现
1 S-box的优化设计
在AES标准算法中定义了两个较大的列表。S-box和逆S-box。将S-box用于两个应用：字节替代和密钥扩展。而逆S-box则用于逆字节替代。这两个列表是不相同的，因此必须建立两个不同的ROM(256×8 b)，用以存储这两个列表。另外，在AES设计中使用平行结构，这就需要用到多个列表，这样会使硬件过于复杂，需要对其进行优化。以下主要对S-box模块进行结构优化。
1.1 S-box和逆S-box的组合
在一个高速128 b的AES设计中，一般需要总共20个S-box模块和16个逆S-box模块。其中，16个S-box模块用于实现字节替代的功能，4个S-box用于实现密钥扩展的功能，而16个逆S-box模块用于实现逆字节替代功能。在这种情形下，如果字节替代和逆字节替代时使用不同的列表，就会占用大量的硬件资源。所以非常需要一种减少硬件复杂性的方法。
就如AES标准所描述的那样，S-box的操作过程可以表示为：
因为multiplicative_inverse(乘法求逆)是一个相当复杂的方程，最常用的实现S-box的方法是运用look-up列表来由x得到y。等式(1)的逆等式如下：
因为multiplicative_inverse-1和multiplicative_inverse是相同的，所以等式(3)可以表述为：
最后，必须找到M-1，即矩阵M的有限域逆矩阵。由有限域逆矩阵的运算方法可知，可以计算出矩阵M的逆矩阵，命名为M’，如式(5)所示：
在式(1)和式(6)中，只使用了一个普通的look-up列表，从而将S-box和逆S-box集成，大大减少了字节替代和逆字节替代的硬件需求。图1展示了集成的S-box／逆S-box模块，可应用于AES的加密和解密。
1.2 S-box单元中乘法求逆电路的优化
由第1.1节可知，S-box盒的生成电路由加密仿射电路(实现out=(in+c)M-1等式功能)，解密仿射电路(实现out=in·M+c等式功能)以及乘法求逆电路三个模块组成。要减少组合逻辑的复杂度，需要对乘法求逆电路进行优化。下面说明求逆电路的优化过程。
S-box硬件实现时的主要部件是乘法求逆。在有限域GF(28)上，乘法求逆是一种相当复杂的函数，直接在域GF(28)上生成S-box盒，组合逻辑复杂度高，会使电路中逻辑电路的门数大大增加。根据有限域的性质，利用域GF(28)与GF[(24)2]的同构变换，把GF(28)上的求逆转化在GF[(24)2]上的求逆运算，从而生成S-box单元，可以降低逻辑关系运算的复杂度，优化S-box的面积。
所采用有限域GF(28)上的乘法求逆电路模块优化过程如图2所示。优化的乘法求逆过程可表述如下：
(1)通过线性变换T将GF(28)的输入X映射到域GF(24)上的元素b，c；
(2)构建相应的域GF(24)的一次多项式，定义域GF(24)上的加法、乘法和求逆运算。利用域GF(24)上的加法、乘法和求逆运算，得到域GF(24)上元素b，c的逆元素p，q；
(3)构建线性变换T-1，将域GF(24)上的元素p，q映射到域GF(28)上，得到域GF(28)上的元素x的逆元素y=T-1(p，q)。
由有限域的知识可知，复合域GF[(24)2]中每个元素都可表示为系数在GF(24)上的一次多项式bx+c。设定义有限域GF[(24)2]的乘法的二次不可约多项式x2+Ax+B，可验证此时GF[(24)2]中的任一元素bx+c的乘逆元素是：
式中：(b2B+bcA+c2)-1是b2B+bcA+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；
[!--empirenews.page--]
(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个乘法器。与原方案相比，此设计大大减少了硬件复杂度并显著节省了资源的消耗。
[!--empirenews.page--]
图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中较复杂的列混合模块进行了集成优化。优化后的方案在不降低密码算法安全性的前提下，较好的降低了硬件复杂度，非常适用于信用卡以及其它对硬件规模要求严格的应用。
在AES标准算法中定义了两个较大的列表。S-box和逆S-box。将S-box用于两个应用：字节替代和密钥扩展。而逆S-box则用于逆字节替代。这两个列表是不相同的，因此必须建立两个不同的ROM(256×8 b)，用以存储这两个列表。另外，在AES设计中使用平行结构，这就需要用到多个列表，这样会使硬件过于复杂，需要对其进行优化。以下主要对S-box模块进行结构优化。
1.1 S-box和逆S-box的组合
在一个高速128 b的AES设计中，一般需要总共20个S-box模块和16个逆S-box模块。其中，16个S-box模块用于实现字节替代的功能，4个S-box用于实现密钥扩展的功能，而16个逆S-box模块用于实现逆字节替代功能。在这种情形下，如果字节替代和逆字节替代时使用不同的列表，就会占用大量的硬件资源。所以非常需要一种减少硬件复杂性的方法。
就如AES标准所描述的那样，S-box的操作过程可以表示为：
因为multiplicative_inverse(乘法求逆)是一个相当复杂的方程，最常用的实现S-box的方法是运用look-up列表来由x得到y。等式(1)的逆等式如下：
因为multiplicative_inverse-1和multiplicative_inverse是相同的，所以等式(3)可以表述为：
最后，必须找到M-1，即矩阵M的有限域逆矩阵。由有限域逆矩阵的运算方法可知，可以计算出矩阵M的逆矩阵，命名为M’，如式(5)所示：
在式(1)和式(6)中，只使用了一个普通的look-up列表，从而将S-box和逆S-box集成，大大减少了字节替代和逆字节替代的硬件需求。图1展示了集成的S-box／逆S-box模块，可应用于AES的加密和解密。
1.2 S-box单元中乘法求逆电路的优化
由第1.1节可知，S-box盒的生成电路由加密仿射电路(实现out=(in+c)M-1等式功能)，解密仿射电路(实现out=in·M+c等式功能)以及乘法求逆电路三个模块组成。要减少组合逻辑的复杂度，需要对乘法求逆电路进行优化。下面说明求逆电路的优化过程。
S-box硬件实现时的主要部件是乘法求逆。在有限域GF(28)上，乘法求逆是一种相当复杂的函数，直接在域GF(28)上生成S-box盒，组合逻辑复杂度高，会使电路中逻辑电路的门数大大增加。根据有限域的性质，利用域GF(28)与GF[(24)2]的同构变换，把GF(28)上的求逆转化在GF[(24)2]上的求逆运算，从而生成S-box单元，可以降低逻辑关系运算的复杂度，优化S-box的面积。
所采用有限域GF(28)上的乘法求逆电路模块优化过程如图2所示。优化的乘法求逆过程可表述如下：
(1)通过线性变换T将GF(28)的输入X映射到域GF(24)上的元素b，c；
(2)构建相应的域GF(24)的一次多项式，定义域GF(24)上的加法、乘法和求逆运算。利用域GF(24)上的加法、乘法和求逆运算，得到域GF(24)上元素b，c的逆元素p，q；
(3)构建线性变换T-1，将域GF(24)上的元素p，q映射到域GF(28)上，得到域GF(28)上的元素x的逆元素y=T-1(p，q)。
由有限域的知识可知，复合域GF[(24)2]中每个元素都可表示为系数在GF(24)上的一次多项式bx+c。设定义有限域GF[(24)2]的乘法的二次不可约多项式x2+Ax+B，可验证此时GF[(24)2]中的任一元素bx+c的乘逆元素是：
式中：(b2B+bcA+c2)-1是b2B+bcA+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；
[!--empirenews.page--]
(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个乘法器。与原方案相比，此设计大大减少了硬件复杂度并显著节省了资源的消耗。
[!--empirenews.page--]
图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中较复杂的列混合模块进行了集成优化。优化后的方案在不降低密码算法安全性的前提下，较好的降低了硬件复杂度，非常适用于信用卡以及其它对硬件规模要求严格的应用。
下载文档
