基于选择空间的AES密钥扩展算法

摘 要： 传统AES密钥扩展算法在已知某轮子密钥的情况下容易遭受攻击，为了避免这种情况的发生，通过采用单向性思路，使用轮密钥常驻内存的工作方式以提高数据吞吐率，并提出基于选择空间的AES密钥扩展算法，对原有算法的加密强度进行了改善。通过FPGA仿真实现，实验结果表明，该方法既能保证密钥扩展算法的安全性，亦能充分结合FPGA设计高效并行的特点，提高其运行效率。

关键词： AES； 密钥扩展算法； 选择空间； FPGA

中图分类号： TN911?34； TP309 文献标识码： A 文章编号： 1004?373X（2013）20?0027?04

0 引 言

AES算法由于自身结构简单并能够允许128位、192位、256位可变密钥长度，且能够在不同的硬件上高效工作，目前已得到广泛的应用。目前对于AES算法的研究主要集中于其自身安全性的分析[1?2]，以及对于专用硬件实现方案的改进及分析[3?4]。

传统的AES算法实现方案在设计初期即确定了固定的密钥扩展算法，特别是专用的硬件加密模块[5]，为了获得更高的数据加密吞吐能力，一般采用扩展密钥常驻工作内存的方式，一方面减少了密钥编排方案的计算代价，另一方面单一的加密方式避免了出错的概率。但如果加密模块中的密钥扩展算法已被攻击方获取，或者本身结构较为简单，一旦一轮子密钥被攻击方获知，那么对方只需要通过有限的运算即可获取全部密钥，继而知悉所有明文详情。在这种情况下为保证加密通信的安全性，传统的方法是必须通过更换密钥以达到通信的再次安全，但在密钥扩展算法已被敌方获取的情况下，密钥更换的信道只有在被确保绝对安全的情况下才是有效的。本文在研究AES算法加密过程以及密钥扩展算法特征的基础上，提出了利用原有子密钥空间的基于选择空间的密钥扩展算法，通过这种方式间接的达到了更换密钥的效果。针对子密钥被敌方获取的情况，这种设计方式可以有效的保证整个加解密过程的安全性，同时也充分的利用到了传统设计方式中扩展密钥常驻工作内存的特点，直接对扩展密钥加工以产生新的轮密钥，并通过FPGA进行仿真验证。该算法充分利用FPGA并行高效的特点，与传统单一FPGA?AES加密算法相比具有更高的安全性和实用性。

1 传统 AES的密钥扩展算法分析

AES的密钥扩展算法又称密钥编排方案，由密钥的扩展和轮密钥选取组成。而密钥的扩展指的是如何由现有密码密钥产生新一轮Expand?Key的过程，同时它必须根据以下准则[5]进行设计。

（1）效 率

①工作内存：应当能用少量的工作内存来执行密钥编排方案。

②性能：在多种处理器上均应具有高性能。

（2）对称消除：应当使用轮常量来消除对称性。

（3）扩散：应当将密码密钥的差分有效地扩散到扩展密钥中。

（4）非线性：应该具有足够的非线性，以便有效的抵御差分和线性密码分析。

针对AES的密钥扩展算法[6]，以10轮128位初始密钥长度为例，由于加密的过程要求一个轮密钥用于初始密钥加法，而且每轮都需要一个轮密钥，因此Expanded?Key（扩展密钥）中的全部比特数等于分组长度乘以轮数加1，即总共需要11轮密钥。将128位初始密钥排成一个4×4的字节矩阵，因此在这个矩阵附加40列后产生扩展密钥空间。将第i列定义为W（i），那么前4个列即为W（0），W（1），W（2），W（3）。依据初始密钥循环产生下一轮子密钥，密钥扩展规则如式（1）所示[7]：

[Wi=Wi-4Wi-1， if i%4！=0Wi=Wi-4TWi-1， if i%4=0] （1）

式中T（W（i-1））是W（i-1）经过循环移位，并借助S-盒进行字节替换，以达到增大其非线性关系，最终对W（4i）进行复杂化。依次扩展得到了第i轮循环的循环密钥W（4i），W（4i+1），W（4i+2），W（4i+3）。以初始密钥产生第1轮密钥为例，如图1所示，由于子密钥的生成过程仅是对每轮首字节进行处理但这并不影响轮密钥之间的关系，假设现在已经知道了某一轮子密钥W（4i），W（4i+1），W（4i+2），W（4i+3），那么由图1可知，可以通过W（4i+2），W（4i+3）知道W（4i-1），通过W（4i+1），W（4i+2）知道W（4i?2），通过W（4i），W（4i+1）知道W（4i-3），再通过W（4i-1），W（4i）知道W（4i-4），这样便得到了前一轮的全部子密钥。也可以通过W（4i），W（4i+3）知道W（4i+4），通过W（4i+1），W（4i+4）知道W（4i+5），通过W（4i+2），W（4i+5）知道W（4i+6），通过W（4i+3），W（4i+6）知道W（4i+7），从而得到了后一轮子密钥。

由此可以看出，子密钥的扩展算法一旦遭到破解，密文的安全就是非常脆弱的，而且固有硬件加密模块主要是通过及时更换密钥来保证密文的安全，但通过上述讨论证明密钥的更换并不能确保密文的安全。因此单纯更换密钥的方式是不可靠的。假设现在针对的是某通信数据加密，一旦密钥遭到泄露，考虑到直接更换密钥一方面可能引发原有更换密钥信道遭受攻击的可能，而一旦新的更换的密钥被截获通信的安全就会丧失，另一方面由于密钥扩展算法并没有即时改变，那么新的密钥也将更容易遭受破解。

图1 密钥破解

2 基于选择空间的密钥扩展方法

针对传统密钥扩展算法[8]的不足，目前主要的改进方式主要集中于改变传统的轮密钥之间的强依赖关系，使得攻击者一旦得到一轮密钥无法通过有效途径得到包括种子密钥在内的全部子密钥[9]。与此同时，新的密钥生成算法必须满足上文中提到的密钥扩展算法的设计准则，这就要求密钥的生成过程必须高效可行，且具有足够的非线性特点。

胡亮等将密钥扩展过程不可逆的思想称为单向性思路[10]，在原有的密钥扩展算法基础上，通过利用单向性思路交换轮密钥的顺序以达到不可逆的特点。而杨小东等则通过对原有的轮密钥进行移位异或操作，并通过随机性函数对其进行变换[11]，这样便增大了其破解的难度。这两种方法虽然解决了传统密钥扩展算法的不足，但对于固化的专用硬件逻辑设计而言，一旦其密钥扩展算法遭到破解，而当前的加解密模块由于采用了固定的扩展算法，而这种扩展算法在专用硬件逻辑上是与整个加密算法逻辑高效整合的，也就产生了无法扩展的问题，必须重新进行设计以满足安全性的要求。因此在面向专用硬件逻辑（或FPGA）设计时，密钥扩展算法在保证单向性的前提下还要能够满足可扩充的特性。

本文在单向性思路的基础上，结合FPGA设计的特点通过引入可替换的选择空间模块进行改进设计。同样以10轮的AES算法为例，首先通过传统的密钥扩展算法生成种子密钥之外的10轮子密钥，假定以32位的字为单位，那么11轮子密钥将产生11×4的子密钥空间，选择空间模块设计成一个向量矩阵，如式（2）所示：

通过子密钥空间与选择空间的结合，将原有子密钥空间的字顺序进行改变。假设只是将第2轮子密钥与第4轮子密钥进行调换，通过第1节对传统子密钥扩展的分析知道下一轮子密钥是通过上一轮子密钥产生的，那么如果攻击方获取了一轮子密钥，要对更改后的子密钥进行攻击的话，假设获取的只是除第2轮和第4轮外的轮密钥的话，那么必将导致至少第2轮和第4轮是错误的，从而保证了密文的安全。而如果一旦获得的是第2轮或者第4轮的密钥，那么其余9轮势必是错误的，这样破解的结果也就必然是错误的。同时也可在选择空间中定义运算方式对现有子密钥空间进行加工，这样将使得新产生的子密钥组在上述场景中更加难以破解。

通过改变原有以128位明文为加密的基本单位，引入单元块的概念，定义一个N个单元分组的单元块，而每个单元分组为128位。具体的设计思想如图2所示。

以单元块为加/解密的基本单位一方面相当于在原有加/解密基础上进行了二次加密，使得密文具有更高的安全性，另一方面这种思路可用于解决相同明文加密结果相同的问题，这是由于每一个子密钥分组均由初始子密钥空间扩展而来，其相当于由初始密钥扩展产生了新的11轮密钥，而每一个子密钥分组是由选择空间中不同的行列与子密钥空间进行组合产生的，这样选择空间不同的行列值保证了子密钥组之间的差异性，使得单元块中相同明文分组的加密结果不同。单从效果上来讲，这种基于选择空间的密钥扩展算法的加密效果与不同密钥组合的加密效果相一致。新的子密钥分组的安全性也是得到保证的。以字为单位的情况下，新的子密钥空间相当于原有子密钥空间全排列（（11×4）！=2.658×1054）的一种，而单元块化的设计又相当于在这种全排列的基础上产生一个序列N的组合，在N=4时这种密钥加强强度已经达到了4.991×10217，针对于这样设计的有效攻击方式也就只能采取穷举的方式。同时为了使得产生的子密钥分组能够满足更好的非线性要求，可以对新的子密钥分组采取移位或异或等简单操作的非线性化处理，在增强其安全性的前提下并没有增加多少时间消耗，满足了其本身的高效性。

将已有的子密钥空间保存于FPGA的RAM中，选择空间模块采用LUT（查找表）的方式，在统一时钟的作用下，每一次时钟的上升沿便产生了新的轮密钥，这种硬连接的方式使得新的轮密钥的产生与上一轮加密过程得以并行执行[12]，同时由于单元块中各分组明文的加/解密过程相互独立，这样可以通过使用流水线的方式提高数据的吞吐能力。选择空间的模块化设计使得可以通过预留数据的更新端口，这样只需要更新选择空间模块中向量矩阵的数据便可以产生新的选择空间，由于AES加/解密算法整体采用模块化的设计方法，如图3所示，各模块之间只是通过互联的方式整合在一起，单一模块的数据更新并不会影响到其他模块，这样确保了硬件加解密逻辑的可扩充性，同时新的选择空间的产生保证了子密钥分组的差异化，从而增强信息的安全性。

3 FPGA实现与仿真

综合考虑资源与速度等问题，算法的设计采用统一时钟下的模块互联，利用状态机的方式进行设计实现，所有的算法模块均采用Verilog HDL实现，在ISE 12.4下进行综合设计，在Isim下完成了功能仿真和时序仿真。加解密模块所处理的基本单位为128 b数据，通过引入num控制信号，使得选择空间模块产生不同的子密钥分组，图4阐述了num控制信号在kld使能信号作用下产生的有效选择空间序列，对于原始的明文数据以128 b为加密单位，每个单元块为128×4 b，单元块内各明文分组数值相同。图5给出了其加解密统一进行下的仿真结果，结果表明单元块内每个明文分组最终的加密结果均不相同，但解密后的结果均与原明文分组一致，验证了基于选择空间密钥扩展算法的正确性以及FPGA设计的可行性。同时在多个模块之间设置全局的使能信号和复位信号进行控制，当使能或者复位信号禁止时，整个系统进入休眠状态，这样的设计方式使得控制简单，系统对环境的适应度增强，也确保了整个设计的稳定与一致。

对于Xilinx Virtex 5系列的xc5vfx70t?1ff1136 FPGA，整个系统模块占用资源可以从表1中看出，其占用的资源并未达到FPGA瓶颈，且资源占用率较低，而Virtex 5系列的FPGA在整个Xilinx的FPGA产品中目前只处于中低端，因此这种设计方案在FPGA上是完全可行的。

4 结 语

基于单向性思路提出的选择空间下的AES加解密的设计，增强了加密的强度，同时达到了单一密钥下多个密钥加密效果。通过在统一时钟触发下并行化设计，有效的减少了资源的利用率，并通过仿真验证了方案的可行性，而且这种方案可以设计成专用芯片，在民用通信、军事通信、文件加密等领域均有着广泛的应用前景。

参考文献

[1] 毛明.分组迭代密码函数的安全性研究[D].成都：电子科技大学，2012.

[2] 王薇.分组密码CLEFIA与基于四圈AES消息认证码的安全性分析[D].济南：山东大学，2009.

[3] 韩津生，林家骏，周文锦，等.基于FPGA的AES核设计[J].计算机工程与科学，2013，35（3）：80?84.

[4] 宁乃东，王岩国.基于FPGA的Rijndael可配置密钥系统优化设计[J].宇航计测技术，2008，28（6）：35?38.

[5] 鲁艳蓉.分组密码算法的设计与分析研究[D].西安：西安电子科技大学，2011.

[6] 胡亮，闫智佳，初剑峰，等.IDEA子密钥扩展算法的分析与改进[J].吉林大学学报：工学版，2012，42（6）：25?32.

[7] 弟宇鸣，陈荣桦，左光霞.基于AES算法的加密模块设计[J].电子设计工程，2013，21（2）：53?55.

[8] 曹华平，罗守山，温巧燕.AES算密钥与种子密钥之间的关系研究[J].北京邮电大学学报，2002，25（4）：47?50.

[9] 吴文玲，贺也平，冯登国.Mars和Rijndael的能量攻击[J].软件学报，2002，13（4）：532?536.

[10] 胡亮，袁巍，于孟涛，等.单向性策略与AES密钥生成算法的改进[J].吉林大学学报：工学版，2009，39（1）：137?142.

[11] 杨小东，.AES密钥扩展新方法[J].微电子学与计算机，2012，29（1）：102?105.

[12] 师攀攀.基于多核的AES算法的并行优化与实现[D].郑州：郑州大学，2012.