搜索
AES算法分析及实现1引言信息社会的兴起，给全球带来了信息技术飞速发展的契机：信息技术的应用，引起了人们生产方式、生活方式和思想观念的巨大变化，极大地推动了人类社会的发展和人类文明的进步。随着人类进入知识经济时代，网络和信息已主见成为人们从事社会活动的基本工具，但是，由于计算机和网络系统的发放性带来的信息与信息系统的安全问题也拓展到前所未有的程度。日益增多的对信息系统的非法入侵和破坏活动正在以惊人的速度在全世界蔓延，给各国信息系统带来巨大的经济损失和安全威胁。随着信息技术的不断发展，信息安全，网络安全的概念正在与时俱进，逐渐从早期的通信保密发展到关注信息的保密、完整、可用、可控和不可否认的信息安全。信息与信息系统，网络与网络系统安全并重，保证信息系统能够安全、可靠、不间断的运行，以提供必要的服务。近年来，我国在发展知识经济、建设信息基础设施以及中国互联网的建设和应用方面都有相当大的进步。计算机网络的广泛应用已经对经济、文化、教育、科学的发展和人类生活质量的提高产生了重要影响，但也带来了一些新的问题。信息系统的的安全总是面临着日益严重的威胁。一方面是由于互联网的开放性及安全性不足，另一方面是众多的攻击手段。为了保证信息系统的安全，需要完整的安全保障体系，应具有保护功能、检测手段、工具的反应以及事故恢复能力。因而，除了不断完善相应的法律和监督措施，我们更需要自我保护。理论和事实都说明，密码技术是一种经济、实用而有效的方法，这也是密码技术得到快速发展和广泛应用的原因。2AES算法分析2.1AES算法产生背景1、AES是美国国家标准技术研究所NIST旨在取代DES的新一代的加密标准。NIST对AES候选算法的基本要求是:对称分组密码体制;密钥长度支持128,192,256位;明文分组长度128位;算法应易于各种硬件和软件实现。2、1998年NIST开始AES第一轮征集、分析、测试,共产生了15个候选算法。1999年3月完成了第二轮AES的分析、测试。1999年8月NIST公布了五种算法(MARS,RC6,Rijndael,Serpent,Twofish)成为候选算法。最后,Rijndael,这个由比利时人设计的算法与其它候选算法在成为高级加密标准(AES)的竞争中取得成功,于2000年10月被NIST宣布成为取代DES的新一代的数据加密标准,即AES。3、Rijndael作为新一代的数据加密标准汇聚了强安全性、高性能、高效率、易用和灵活等优点。4、AES设计有三个密钥长度:128,192,256比特2.2AES算法原理AES算法是基于置换和代替的。置换是数据的重新排列，而代替是用一个单元数据替换另一个。AES使用了几种不同的技术来实现置换和替换。为了阐明这些技术，让我们用Figure1所示的数据讨论一个具体的AES加密例子。下面是你要加密的128位值以及它们对应的索引数组：00112233445566778899aabbccddeeff0123456789101112131415192位密钥的值是：000102030405060708090a0b0c0d0e0f101112131415161701234567891011121314151617181920212223Figure2S-盒（Sbox）当AES的构造函数（constructor）被调用时，用于加密方法的两个表被初始化。第一个表是代替盒称为S-盒。它是一个16×16的矩阵。S-盒的前五行和前五列如Figure2所示。在幕后，加密例程获取该密钥数组并用它来生成一个名为w[]的密钥调度表，Figure3所示。Figure3密钥调度表（KeySched）w[]最初的Nk(6)行被作为种子，用原始密钥值（0x00到0x17）。剩余行从种子密钥来产生。变量Nk代表以32位字为单位的种子密钥长度。稍后我分析AES实现时你将清楚地看到w[]是怎样产生的。关键是这里现在有许多密钥使用而不只是一个。这些新的密钥被称为轮密钥（roundkeys）以将它们与原始种子密钥区别开来。Figure4State（态）数组AES加密例程开始是拷贝16字节的输入数组到一个名为State（态）的4×4字节矩阵中。。AES加密算法取名为Cipher，它操作State[]，其过程描述的伪代码参见Figure5。在规范中，加密算法实现的一个预备的处理步骤被称为AddRoundKey（轮密钥加）。AddRoundKey用密钥调度表中的前四行对State矩阵实行一个字节一个字节的异或（XOR）操作，并用轮密钥表w[c,r]异或输入State[r,c]。举个例子，如果State矩阵的第一行保存的字节是{00,44,88,cc}，第一列密钥调度表是{00,04,08,0c}，那么新的State[0,2]值是用w[2,0](0x08或0x80)异或State[0,2](0x88)的结果：1000100000001000XOR10000000AES算法的主循环对State矩阵执行四个不同的操作，在规范中被称为SubBytes（字节替换）、ShiftRows（行位移变换）、MixColumns（列混合变换）和AddRoundKey。除了每次循环AddRoundKey都被调用并使用密钥调度表的下面四行外，AddRoundKey与预备处理步骤中的AddRoundKey相同。SubBytes例程是一个代替操作，它将State矩阵中的每个字节替换成一个由Sbox决定的新字节。比如，如果State[0,1]的值是0x40如果你想找到它的代替者，你取State[0,1]的值(0x40)并让x等于左边的数字(4)并让y等于右边的数字(0)。然后你用x和y作为索引进到Sbox表中寻找代替值，如Figure2所示。ShiftRows是一个置换操作，它将State矩阵中的字节向左旋转。Figure6示范了ShiftRows如何操作State[]。State的第0行被向左旋转0个位置，State的第1行被向左旋转1个位置，State的第2行被向左旋转2个位置，而State的第3行被向左旋转3个位置。Figure6对State进行ShiftRows操作MixColumns是一个代替操作，它是理解AES算法时最具技巧（或者说是最需要动脑筋的部分）的部分。它用State字节列的值进行数学域加和域乘的结果代替每个字节。我将在下一节中详细解释专门的域加和域乘细节。假设State[0,1]的值是0x09，并且列1上的其它值分别为0x60，0xe1和0x04，那么State[0,1]的新值计算如下：State[0,1]=(State[0,1]*0x01)+(State[1,1]*0x02)+(State[2,1]*0x03)+(State[3,1]*0x01)=(0x09*0x01)+(0x60*0x02)+(0xe1*0x03)+(0x04*0x01)=0x57此处加法和乘法是专门的数学域操作，而不是平常整数的加法和乘法。SubBytes、ShiftRows、MixColumns和AddRoundKey四个操作在一个执行Nr次的循环里被调用，Nr为给定密钥大小的轮数减1。加密算法使用的轮数要么是10，12，要么是14，这依赖于种子密钥长度是128位、192位还是256位。在这个例子中，因为Nr等于12，则这四个操作被调用11次。该迭代完成后，在拷贝State矩阵到输出参数前，加密算法调用SubBytes、ShiftRows和AddRoundKey后结束。大致说来，AES加密算法的核心有四个操作。AddRoundKey使用从种子密钥值中生成的轮密钥代替4组字节。SubBytes替换用一个代替表替换单个字节。ShiftRows通过旋转4字节行的4组字节进行序列置换。MixColumns用域加和域乘的组合来替换字节。有限域GF(28)的加法和乘法正如你所看到的，AES加密算法使用相当简单明了的技术来代替和置换，除MixColumns例程以外。MixColumns使用特殊的加法和乘法。AES所用的加法和乘法是基于数学（译者注：近世代数）的域论。尤其是AES基于有限域GF(28)。GF(28)由一组从0x00到0xff的256个值组成，加上加法和乘法，因此是(28)。GF代表伽罗瓦域，以发明这一理论的数学家的名字命名。GF(28)的一个特性是一个加法或乘法的操作的结果必须是在{0x00...0xff}这组数中。虽然域论是相当深奥的，但GF(28)加法的最终结果却很简单。GF(28)加法就是异或（XOR）操作。然而，GF(28)的乘法有点繁难。正如你稍后将在C#实现中所看到的，AES的加密和解密例程需要知道怎样只用七个常量0x01、0x02、0x03、0x09、0x0b、0x0d和0x0e来相乘。所以我不全面介绍GF(28)的乘法，而只是针对这七种特殊情况进行说明。在GF(28)中用0x01的乘法是特殊的；它相当于普通算术中用1做乘法并且结果也同样—任何值乘0x01等于其自身。现在让我们看看用0x02做乘法。和加法的情况相同，理论是深奥的，但最终结果十分简单。只要被乘的值小于0x80，这时乘法的结果就是该值左移1比特位。如果被乘的值大于或等于0x80，这时乘法的结果就是左移1比特位再用值0x1b异或。它防止了“域溢出”并保持乘法的乘积在范围以内。一旦你在GF(28)中用0x02建立了加法和乘法，你就可以用任何常量去定义乘法。用0x03做乘法时，你可以将0x03分解为2的幂之和。为了用0x03乘以任意字节b，因为0x03=0x02+0x01，因此：b*0x03=b*(0x02+0x01)=(b*0x02)+(b*0x01)这是可以行得通的，因为你知道如何用0x02和0x01相乘和相加，同哩，用0x0d去乘以任意字节b可以这样做：b*0x0d=b*(0x08+0x04+0x01)=(b*0x08)+(b*0x04)+(b*0x01)=(b*0x02*0x02*0x02)+(b*0x02*0x02)+(b*0x01)在加解密算法中，AESMixColumns例程的其它乘法遵循大体相同的模式，如下所示：b*0x09=b*(0x08+0x01)=(b*0x02*0x02*0x02)+(b*0x01)b*0x0b=b*(0x08+0x02+0x01)=(b*0x02*0x02*0x02)+(b*0x02)+(b*0x01)b*0x0e=b*(0x08+0x04+0x02)=(b*0x02*0x02*0x02)+(b*0x02*0x02)+(b*0x02)总之，在GF(28)中，加法是异或操作。其乘法将分解成加法和用0x02做的乘法，而用0x02做的乘法是一个有条件的左移1比特位。AES规范中包括大量有关GF(28)操作的附加信息。密钥扩展AES加密和解密算法使用了一个由种子密钥字节数组生成的密钥调度表。AES规范中称之为密钥扩展例程（KeyExpansion）。从本质上讲，从一个原始密钥中生成多重密钥以代替使用单个密钥大大增加了比特位的扩散。虽然不是无法抵御的困难，但理解KeyExpansion仍是AES算法中的一个难点。KeyExpansion例程高级伪代码如下所示：KeyExpansion(byte[]key,byte[][4]w){copytheseedkeyintothefirstrowsofwforeachremainingrowofw{usetwoofthepreviousrowstocreateanewrow}}“用前面两行来产生一个新行”（“usetwoofthepreviousrowstocreateanewrow”）的例程用到了两个子例程，RotWord和SubWord以及一个名为“Rcon”的常数表（作为“轮常数”）。让我们先来逐个看一下这三东西，然后再回到整个KeyExpansion的讨论中来。RotWord例程很简单。它接受一个4个字节的数组并将它们向左旋转一个位置。因为轮调度表w[]有四列，RotWord将w[]的1行左旋。注意KeyExp