(10)申请公布号 (43)申请公布日 2013.11.13C N 103391186 A (21)申请号 201310261809.5
(22)申请日 2013.06.27
H04L 9/06(2006.01)
(71)申请人清华大学
地址100084 北京市海淀区100084信箱82
分箱清华大学专利办公室
(72)发明人李树国 覃晓草
(74)专利代理机构西安智大知识产权代理事务
所 61215
代理人
贾玉健
(54)发明名称
法
(57)摘要
一种实现AES 算法中S 盒和逆S 盒替换的方
法，根据AES 算法标准中给出的S 盒与逆S 盒，得
到16个真值表；将每个真值表都表示为一个最小
在化简后得到的函数表达式中，将表达式改写为
“与非与非”即为“与或”的两次取反的形式；将改
写后的函数表达式之间能够公用的逻辑电路单元
单独提出来，使得这些函数表达式实现电路资源
得以公用，上述公用单元提取后的表达式与提取
前的表达式相比，公用单元提取后的表达式对应
的电路面积变小，扇出变少，从而使得延时减小，
本发明相比于普遍使用的查表法，其延时减小了
8.5%，面积减小了27.4%，功耗减小了17%。
(51)Int.Cl.
权利要求书1页 说明书4页 附图1页
(19)中华人民共和国国家知识产权局(12)发明专利申请权利要求书1页 说明书4页 附图1页(10)申请公布号CN 103391186 A
*CN103391186A*
1/1页
1.一种实现AES 算法中S 盒和逆S 盒替换的方法，其特征在于，包括如下步骤：
步骤一，根据AES 算法标准中给出的S 盒与逆S 盒，写出输出变量的真值表，由于S 盒与逆S 盒都是8位输出变量，可以得到16个真值表；
步骤二，将每个真值表都表示为一个最小项表达式，得到16个最小项表达式；
步骤三，对每个最小项表达式进行逻辑化简得到化简后的函数表达式；
步骤四，在化简后得到的16个函数表达式中，将表达式改写为“与非与非”即为“与或”的两次取反的形式；
步骤五，将改写后的16个函数表达式之间能够公用的逻辑电路单元单独提出来，使得这些函数表达式实现电路资源得以公用，上述公用单元提取后的表达式与提取前的表达式相比，公用单元提取后的表达式对应的电路面积变小，扇出变少，从而使得延时减小。
2.根据权利要求1所述的实现AES 算法中S 盒和逆S 盒替换的方法，其特征在于，所述步骤三中逻辑化简采用改进的Q-M 化简法实现，具体包括如下步骤：
第一步：将函数表示成最小项表达式；
第二步：出函数的全部质蕴涵项；
第三步：出必要质蕴涵项，输出结果；
第四步：去除必要质蕴涵项以及各个必要质蕴涵项所对应的最小项后，得到一个新的表；
第五步：在新的表中到包含最小项个数最多的那一个质蕴涵项，若是有多个质蕴涵项包含最小项个数最多，则任选其一，输出这个质蕴涵项；
第六步：去除第五步输出的这个质蕴涵项以及该质蕴涵项所对应的最小项后，得到一个新的表；
第七步：重复第五步和第六步，直到没有能够再合并的最小项为止，循环结束。权 利 要 求 书CN 103391186 A
一种实现AES算法中S盒和逆S盒替换的方法
技术领域
[0001] 本发明属于信息安全技术领域，特别涉及一种实现AES算法中S盒和逆S盒替换的方法。
背景技术
[0002] AES算法是一种对称分组密码算法，应用于金融、电子政务、电子商务及国民经济的各个领域，
目前已经研制了系列芯片、智能IC卡、智能密码钥匙、加密卡、加密机、加密U 盘、硬盘以及正在研究的金融IC卡等安全产品。而AES算法中的S盒替换与逆S盒替换是该算法唯一的非线性变换，因此S盒替换与逆S盒替换是AES算法的核心部分，同时这也是提高AES算法性能的主要瓶颈。
[0003] 现有的S盒替换与逆S盒替换普遍采用的是查表法实现。所谓查表法中的“表”指的是AES算法中的两个盒子，分别用于加密时的S盒替换与解密时的逆S盒替换。当前，普遍的查表法不管是S盒替换还是逆S盒替换，都是根据输入值通过AES算法标准规定的表格来查出对应的输出值。这种查表法原理简单，实现容易，但是这种方法实际上是一个大的256选一多路选择器，其电路的延时较长，面积较大，是一种低效的实现方式。
发明内容
[0004] 为了克服上述现有技术的缺点，本发明的目的在于提供一种实现AES算法中S盒和逆S盒替换的方法，减小了时延、面积和功耗。
[0005] 为了实现上述目的，本发明采用的技术方案是：
[0006] 一种实现AES算法中S盒和逆S盒替换的方法，包括如下步骤：
[0007] 步骤一，根据AES算法标准中给出的S盒与逆S盒，写出输出变量的真值表，由于S盒与逆S盒
都是8位输出变量，可以得到16个真值表；
[0008] 步骤二，将每个真值表都表示为一个最小项表达式，得到16个最小项表达式；[0009] 步骤三，对每个最小项表达式进行逻辑化简得到化简后的函数表达式；[0010] 步骤四，在化简后得到的16个函数表达式中，将表达式改写为“与非与非”即为“与或”的两次取反的形式；
[0011] 步骤五，将改写后的16个函数表达式之间能够公用的逻辑电路单元单独提出来，使得这些函数表达式实现电路资源得以公用，上述公用单元提取后的表达式与提取前的表达式相比，公用单元提取后的表达式对应的电路面积变小，扇出变少，从而使得延时减小。[0012] 所述步骤三中逻辑化简采用改进的Q-M化简法实现，具体包括如下步骤：[0013] 第一步：将函数表示成最小项表达式；
[0014] 第二步：出函数的全部质蕴涵项；
[0015] 第三步：出必要质蕴涵项，输出结果；
[0016] 第四步：去除必要质蕴涵项以及各个必要质蕴涵项所对应的最小项后，得到一个新的表；
[0017] 第五步：在新的表中到包含最小项个数最多的那一个质蕴涵项，若是有多个质蕴涵项包含最小项个数最多，则任选其一，输出这个质蕴涵项；
[0018] 第六步：去除第五步输出的这个质蕴涵项以及该质蕴涵项所对应的最小项后，得到一个新的表；
[0019] 第七步：重复第五步和第六步，直到没有能够再合并的最小项为止，循环结束。[0020] 与现有技术相比，本发明的有益效果是：在优化Q-M化简法基础上，提出了一种实现AES算法中S盒替换和逆S盒替换的表达式方法，用C语言编程实现了改进的Q-M化简法，借助于计算机来求得函数表达式的逻辑化简结果，这种表达式方法相比于普遍使用的查表法，其延时减小了8.5%，面积减小了27.4%，功耗减小了17%。
附图说明
[0021] 图1是按照本发明一种有效实现AES算法中S盒替换与逆S盒替换的电路结构图。
具体实施方式
[0022] 下面结合图1和实施例详细说明本发明的实施方式。
[0023] 本发明利用改进的Q-M化简法，求得AES算法中S盒替换和逆S盒替换的函数表达式的逻辑化简结果，从而有效实现了AES算法中S盒替换和逆S盒替换。
[0024] 具体包括如下步骤：
[0025] 1）据AES算法标准中给出的S盒与逆S盒，写出输出变量的真值表，由于S盒与逆S盒都是8位输出变量，可以得到16个真值表；
[0026] 2）将每个真值表都表示为一个最小项表达式，得到16个最小项表达式；[0027] 3）采用改进的Q-M化简法对每个最小项表达式进行逻辑化简得到化简后的函数表达式。
[0028] 由于S盒与逆S盒的输入变量有8个，通过手工进行逻辑化简获取S盒替换和逆S盒替换的表达式几乎是做不到的，因此用C语言编程实现了改进的Q-M化简法，借助于计算机来求得函数表达式的逻辑化简结果。
[0029] 4）在化简后得到的16个函数表达式中，将表达式改写为“与非与非”即为“与或”的两次取反的形式而不是单纯的“与或”的形式。这是基于“与非”门的延时要小于“与”门的延时的事实，本发明的实验结果也验证了这一点。
[0030] 以S盒替换的S-Box函数表达式SBox[7:0]为例，设输入变量为a，其逻辑表达式如下：
[0031] 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])))
[0032] 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]))&……
[0033] &(～(a[7]&～a[6]&a[5]&a[4]&～a[1]&a[0])))
[0034] .
[0035] .
[0036] .
[0037] 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]))&……
[0038] &(～(～a[7]&a[6]&a[3]&～a[2]&a[1]&～a[0])))
[0039] 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])))
[0040] 5）通过研究这16个函数表达式，发现这些函数表达式之间含有很多可以公用的逻辑电路单元，因此，将这些能够公用的逻辑电路单元单独提出来，使得这些函数表达式实现电路资源得以公用。
[0041] 下面是单独提出来的公用逻辑电路单元，其中，a为S盒与逆S盒的输入变量，变量c,d,e,f,g,h为中间变量。
[0042] c[0]=～a[1]&～a[0]，c[1]=～a[1]&a[0]，c[2]=a[1]&～a[0]，c[3]=a[1]&a[0]，
[0043] d[0]=～a[3]&～a[2]，d[1]=～a[3]&a[2]，d[2]=a[3]&～a[2]，d[3]=a[3]&a[2]，
[0044] e[0]=～a[5]&～a[4]，e[1]=～a[5]&a[4]，e[2]=a[5]&～a[4]，e[3]=a[5]&a[4]，
[0045] f[0]=～a[7]&～a[6]，f[1]=～a[7]&a[6]，f[2]=a[7]&～a[6]，f[3]=a[7]&a[6]，
[0046] g[0]=d[0]&c[0]，g[1]=d[0]&c[1]，g[2]=d[0]&c[2]，g[3]=d[0]&c[3]，[0047] g[4]=d[1]&c[0]，g[5]=d[1]&c[1]，g[6]=d[1]&c[2]，g[7]=d[1]&c[3]，[0048] g[8]=d[2]&c[0]，g[9]=d[2]&c[1]，g[10]=d[2]&c[2]，g[11]=d[2]&c[3]，[0049] g[12]=d[3]&c[0]，g[13]=d[3]&c[1]，g[14]=d[3]&c[2]，g[15]=d[3]&c[3]，[0050] h[0]=f[0]&e[0]，h[1]=f[0]&e[1]，h[2]=f[0]&e[2]，h[3]=f[0]&e[3]，[0051] h[4]=f[1]&e[0]，h[5]=f[1]&e[1]，h[6]=f[1]&e[2]，h[7]=f[1]&e[3]，[0052] h[8]=f[2]&e[0]，h[9]=f[2]&e[1]，h[10]=f[2]&e[2]，h[11]=f[2]&e[3]，[0053] h[12]=f[3]&e[0]，h[13]=f[3]&e[1]，h[14]=f[3]&e[2]，h[15]=f[3]&e[3]。[0054] 基于这些公用单元，对S盒替换的S-Box函数表达式SBox[7:0]进一步化简，得到其表达式如下，
[0055] SBox[7]=～((～(h[0]&d[3]&～a[0]))&(～(a[6]&e[1]&g[6]))&……&(～(h[7]&c[1])))
[0056] SBox[6]=～((～(h[12]&g[7]))&(～(～a[7]&e[0]&g[6]))&……&(～(h[11]&c[1])))
[0057] .
[0058] .
[0059] .
[0060] SBox[1]=～((～(h[12]&g[0]))&(～(a[6]&e[1]&g[10]))&……&(～(f[1]&g[10])))
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议