一种实现AES算法中S盒和逆S盒替换的方法

技术领域

本发明属于信息安全技术领域，特别涉及一种实现AES算法中S盒和逆S 盒替换的方法。

背景技术

AES算法是一种对称分组密码算法，应用于金融、电子政务、电子商务 及国民经济的各个领域，目前已经研制了系列芯片、智能IC卡、智能密码钥 匙、加密卡、加密机、加密U盘、硬盘以及正在研究的金融IC卡等安全产品。 而AES算法中的S盒替换与逆S盒替换是该算法唯一的非线性变换，因此S 盒替换与逆S盒替换是AES算法的核心部分，同时这也是提高AES算法性能 的主要瓶颈。

现有的S盒替换与逆S盒替换普遍采用的是查表法实现。所谓查表法中 的“表”指的是AES算法中的两个盒子，分别用于加密时的S盒替换与解密 时的逆S盒替换。当前，普遍的查表法不管是S盒替换还是逆S盒替换，都 是根据输入值通过AES算法标准规定的表格来查出对应的输出值。这种查表 法原理简单，实现容易，但是这种方法实际上是一个大的256选一多路选择 器，其电路的延时较长，面积较大，是一种低效的实现方式。

发明内容

为了克服上述现有技术的缺点，本发明的目的在于提供一种实现AES算法 中S盒和逆S盒替换的方法，减小了时延、面积和功耗。

为了实现上述目的，本发明采用的技术方案是：

一种实现AES算法中S盒和逆S盒替换的方法，包括如下步骤：

步骤一，根据AES算法标准中给出的S盒与逆S盒，写出输出变量的真 值表，由于S盒与逆S盒都是8位输出变量，可以得到16个真值表；

步骤二，将每个真值表都表示为一个最小项表达式，得到16个最小项表 达式；

步骤三，对每个最小项表达式进行逻辑化简得到化简后的函数表达式；

步骤四，在化简后得到的16个函数表达式中，将表达式改写为“与非与 非”即为“与或”的两次取反的形式；

步骤五，将改写后的16个函数表达式之间能够公用的逻辑电路单元单独 提出来，使得这些函数表达式实现电路资源得以公用，上述公用单元提取后 的表达式与提取前的表达式相比，公用单元提取后的表达式对应的电路面积 变小，扇出变少，从而使得延时减小。

所述步骤三中逻辑化简采用改进的Q-M化简法实现，具体包括如下步骤：

第一步：将函数表示成最小项表达式；

第二步：找出函数的全部质蕴涵项；

第三步：找出必要质蕴涵项，输出结果；

第四步：去除必要质蕴涵项以及各个必要质蕴涵项所对应的最小项后， 得到一个新的表；

第五步：在新的表中找到包含最小项个数最多的那一个质蕴涵项，若是 有多个质蕴涵项包含最小项个数最多，则任选其一，输出这个质蕴涵项；

第六步：去除第五步输出的这个质蕴涵项以及该质蕴涵项所对应的最小 项后，得到一个新的表；

第七步：重复第五步和第六步，直到没有能够再合并的最小项为止，循 环结束。

与现有技术相比，本发明的有益效果是：在优化Q-M化简法基础上，提出 了一种实现AES算法中S盒替换和逆S盒替换的表达式方法，用C语言编程实 现了改进的Q-M化简法，借助于计算机来求得函数表达式的逻辑化简结果，这 种表达式方法相比于普遍使用的查表法，其延时减小了8.5%，面积减小了27.4%， 功耗减小了17%。

附图说明

图1是按照本发明一种有效实现AES算法中S盒替换与逆S盒替换的电路 结构图。

具体实施方式

下面结合图1和实施例详细说明本发明的实施方式。

本发明利用改进的Q-M化简法，求得AES算法中S盒替换和逆S盒替换的 函数表达式的逻辑化简结果，从而有效实现了AES算法中S盒替换和逆S盒替 换。

具体包括如下步骤：

1）据AES算法标准中给出的S盒与逆S盒，写出输出变量的真值表，由于 S盒与逆S盒都是8位输出变量，可以得到16个真值表；

2）将每个真值表都表示为一个最小项表达式，得到16个最小项表达式；

3）采用改进的Q-M化简法对每个最小项表达式进行逻辑化简得到化简后 的函数表达式。

由于S盒与逆S盒的输入变量有8个，通过手工进行逻辑化简获取S盒替换 和逆S盒替换的表达式几乎是做不到的，因此用C语言编程实现了改进的Q-M 化简法，借助于计算机来求得函数表达式的逻辑化简结果。

4）在化简后得到的16个函数表达式中，将表达式改写为“与非与非”即为 “与或”的两次取反的形式而不是单纯的“与或”的形式。这是基于“与非”门的 延时要小于“与”门的延时的事实，本发明的实验结果也验证了这一点。

以S盒替换的S-Box函数表达式SBox[7:0]为例，设输入变量为a，其逻辑 表达式如下：

SBox[7]=～((～(～a[7]&～a[6]&～a[5]&～a[4]&a[3]&a[2]&～a[0]))&(～(a[6]&～a [5]&a[4]&～a[3]&a[2]&a[1]&～a[0]))&……&(～(～a[7]&a[6]&a[5]&a[4]&～a[1]& a[0])))

SBox[6]=～((～(a[7]&a[6]&～a[5]&～a[4]&～a[3]&a[2]&a[1]&a[0]))&(～(～a[7] &～a[5]&～a[4]&～a[3]&a[2]&a[1]&～a[0]))&……

&(～(a[7]&～a[6]&a[5]&a[4]&～a[1]&a[0])))

.

.

.

SBox[1]=～((～(a[7]&a[6]&～a[5]&～a[4]&～a[3]&～a[2]&～a[1]&～a[0]))&(～(a [6]&～a[5]&a[4]&a[3]&～a[2]&a[1]&～a[0]))&……

&(～(～a[7]&a[6]&a[3]&～a[2]&a[1]&～a[0])))

SBox[0]=～((～(a[7]&～a[6]&～a[5]&a[4]&～a[3]&～a[2]&～a[1]&a[0]))&(～(～a [7]&～a[6]&～a[5]&～a[3]&a[2]&～a[1]&a[0]))&……&(～(a[7]&a[6]&a[5]&a[3]& ～a[2]&～a[0])))

5）通过研究这16个函数表达式，发现这些函数表达式之间含有很多可以 公用的逻辑电路单元，因此，将这些能够公用的逻辑电路单元单独提出来， 使得这些函数表达式实现电路资源得以公用。

下面是单独提出来的公用逻辑电路单元，其中，a为S盒与逆S盒的输入 变量，变量c,d,e,f,g,h为中间变量。

c[0]=～a[1]&～a[0]，c[1]=～a[1]&a[0]，c[2]=a[1]&～a[0]，c[3]=a[1]&a[0]，

d[0]=～a[3]&～a[2]，d[1]=～a[3]&a[2]，d[2]=a[3]&～a[2]，d[3]=a[3]&a[2]，

e[0]=～a[5]&～a[4]，e[1]=～a[5]&a[4]，e[2]=a[5]&～a[4]，e[3]=a[5]&a[4]，

f[0]=～a[7]&～a[6]，f[1]=～a[7]&a[6]，f[2]=a[7]&～a[6]，f[3]=a[7]&a[6]，

g[0]=d[0]&c[0]，g[1]=d[0]&c[1]，g[2]=d[0]&c[2]，g[3]=d[0]&c[3]，

g[4]=d[1]&c[0]，g[5]=d[1]&c[1]，g[6]=d[1]&c[2]，g[7]=d[1]&c[3]，

g[8]=d[2]&c[0]，g[9]=d[2]&c[1]，g[10]=d[2]&c[2]，g[11]=d[2]&c[3]，

g[12]=d[3]&c[0]，g[13]=d[3]&c[1]，g[14]=d[3]&c[2]，g[15]=d[3]&c[3]，

h[0]=f[0]&e[0]，h[1]=f[0]&e[1]，h[2]=f[0]&e[2]，h[3]=f[0]&e[3]，

h[4]=f[1]&e[0]，h[5]=f[1]&e[1]，h[6]=f[1]&e[2]，h[7]=f[1]&e[3]，

h[8]=f[2]&e[0]，h[9]=f[2]&e[1]，h[10]=f[2]&e[2]，h[11]=f[2]&e[3]，

h[12]=f[3]&e[0]，h[13]=f[3]&e[1]，h[14]=f[3]&e[2]，h[15]=f[3]&e[3]。

基于这些公用单元，对S盒替换的S-Box函数表达式SBox[7:0]进一步化 简，得到其表达式如下，

SBox[7]=～((～(h[0]&d[3]&～a[0]))&(～(a[6]&e[1]&g[6]))&……&(～(h[7]&c[ 1])))

SBox[6]=～((～(h[12]&g[7]))&(～(～a[7]&e[0]&g[6]))&……&(～(h[11]&c[1])) )

.

.

.

SBox[1]=～((～(h[12]&g[0]))&(～(a[6]&e[1]&g[10]))&……&(～(f[1]&g[10])) )

SBox[0]=～((～(h[9]&g[1]))&(～(f[0]&～a[5]&g[5]))&……&(～(f[3]&a[5]&d[ 2]&～a[0])))

上述公用单元提取后的表达式与提取前的表达式相比，公用单元提取后 的表达式对应的电路面积变小，扇出变少，从而使得延时减小。

用上述改进Q-M化简法得到S盒替换的8个函数表达式和逆S盒替换的8 个函数表达式，分别用于加密和解密模式，电路结构如图1所示，S盒替换与 逆S盒替换的输入变量为a，输出变量为b。通过MUX二选一的选择信号Encrypt 进行选择，Encrypt为1时，即为加密模式，输出变量b选择输出S盒函数表达 式，而Encrypt为0时，即为解密模式，输出变量b选择输出逆S盒函数表达式。

本发明对于表达式结果的功能验证，将8位输入变量a由00000000遍历到 11111111的这256个值进行了功能性的完全验证，结果与AES算法标准的S盒 和逆S盒完全一致。由此说明得到化简后的表达式是正确的，本发明是可行 的。同时，本发明基于SMIC0.18um工艺对改进Q-M化简法得到的实现S盒替 换与逆S盒替换的16个函数表达式进行综合，相比于普遍应用的查表法，本 发明使得延时减小了8.5%，面积减小了27.4%，功耗减小了17%。

以上实施方式仅用于说明本发明，而并非对本发明的限制，有关技术领 域的普通技术人员，在不脱离本发明的精神和范围的情况下，还可以做出各 种变化和变型，因此所有等同的技术方案也属于本发明的范畴，本发明的专 利保护范围应由权利要求限定。