AES加密技术简介(23300字)

来源:m.fanwen118.com时间:2021.2.18

AES加密技术

20xx年10月,NIST(美国国家标准和技术协会)宣布通过从15种侯选算法中选出的一项新的密匙加密标准。Rijndael被选中成为将来的AES。 Rijndael是在 1999 年下半年,由研究员 Joan Daemen 和 Vincent Rijmen 创建的。AES 正日益成为加密各种形式的电子数据的实际标准。

美国标准与技术研究院 (NIST) 于 2002 年 5 月 26 日制定了新的高级加密标准 (AES) 规范。

算法原理

AES 算法基于排列和置换运算。排列是对数据重新进行安排,置换是将一个数据单元替换为另一个。AES 使用几种不同的方法来执行排列和置换运算。

AES 是一个迭代的、对称密钥分组的密码,它可以使用128、192 和 256 位密钥,并且用 128 位(16字节)分组加密和解密数据。与公共密钥密码使用密钥对不同,对称密钥密码使用相同的密钥加密和解密数据。通过分组密码返回的加密数据的位数与输入数据相同。迭代加密使用一个循环结构,在该循环中重复置换和替换输入数据。

AES与3DES的比较

AES加密技术简介

---------------------------------------------------------------------------------------

-----------------------------------------------

(/feel22/blog/item/b54d21fa745afe9358ee9069

.html)

关键词:AES算法 DES AVR汇编语言 加密算法 解密算法

引 言

随着对称密码的发展,DES数据加密标准算法由于密钥长度较小(56位),已经不适应当今分布式开放网络对数据加密安全性的要求,因此19xx年NIST公开征集新的数据加密标准,即AES[1]。经过三轮的筛选,比利时Joan Daeman和Vincent Rijmen提交的Rijndael算法被提议为AES的最终算法。此算法将成为美国新的数据加密标准而被广

泛应用在各个领域中。尽管人们对AES还有不同的看法,但总体说,AES作为新一代的数据加密标准汇聚了强安全性、高性能、高效率、易用和灵活等优点。AES设计有三个密钥长度:128,192,256位,相对而言,AES的128密钥比DES的56密钥强1021倍[2]。AES算法主要包括三个方面:轮变化、圈数和密钥扩展。本文以128为例,介绍算法的基本原理;结合AVR汇编语言,实现高级数据加密算法AES。

1 AES加密、解密算法原理和AVR实现

AES是分组密钥,算法输入128位数据,密钥长度也是128位。用Nr表示对一个数据分组加密的轮数(加密轮数与密钥长度的关系如表1所列)。每一轮都需要一个与输入分组具有相同长度的扩展密钥Expandedkey(i)的参与。由于外部输入的加密密钥K长度有限,所以在算法中要用一个密钥扩展程序(Keyexpansion)把外部密钥K扩展成更长的比特串,以生成各轮的加密和解密密钥。

1.1圈变化

AES每一个圈变换由以下三个层组成:

非线性层——进行Subbyte变换;

线行混合层——进行ShiftRow和MixColumn运算;

密钥加层——进行AddRoundKey运算。

① Subbyte变换是作用在状态中每个字节上的一种非线性字节转换,可以通过计算出来的S盒进行映射。

Schange:

ldi zh,$01;将指针指向S盒的首地址

mov zl,r2;将要查找的数据作为指针低地址

ldtemp,z+;取出这个对应的数据

mov r2,temp;交换数据完成查表

.

.

.

ret

② ShiftRow是一个字节换位。它将状态中的行按照不同的偏移量进行循环移位,而这个偏移量也是根据Nb的不同而选择的[3]。 shiftrow:;这是一个字节换位的子程序

mov temp,r3;因为是4×4

mov r3,r7; r2 r6 r10 r14 r2 r6 r10 r14

mov r7,r11; r3 r7 r11 r15---r7 r11 r15 r3

mov r11,r15; r4 r8 r12 r17 r12 r17 r4 r8

mov r15,temp; r5 r9 r13 r18 r18 r5 r9 r13

mov temp,r4

mov temp1,r8

mov r4,r12

mov r8,r17

mov r12,temp

mov r17,temp1

mov temp,r18

mov r18,r13

mov r13,r9

mov r9,r5

mov r5,temp

ret

③ 在MixColumn变换中,把状态中的每一列看作GF(28)上的多项式a(x)与固定多项式c(x)相乘的结果。b(x)=c(x)*a(x)的系数这样计算:*运算不是普通的乘法运算,而是特殊的运算,即

b(x)=c(x)·a(x)(mod x4+1)

对于这个运算

b0=02。a0+03。a1+a2+a3

令xtime(a0)=02。a0

其中,符号“。”表示模一个八次不可约多项式的同余乘法[3]。 mov temp,a0;这是一个mixcolimn子程序

rcall xtime;调用xtime程序

mov a0,temp

mov temp,a1

rcall xtime

eor a0,a1

eor a0,temp

eor a0,a2

eor a0,a3;完成b(x)的计算

.

.

.

xtime:;这是一个子程序

ldi temp1,$1b

lsl temp

brcs next1;如果最高位是1,则转移

next: ret;否则什么也不变化

next1:eor temp,temp1

rjmp next

对于逆变化,其矩阵C要改变成相应的D,即b(x)=d(x)*a(x)。

④ 密钥加层运算(addround)是将圈密钥状态中的对应字节按位“异或”。

⑤ 根据线性变化的性质[1],解密运算是加密变化的逆变化。这里不再详细叙述。

1.2轮变化

对不同的分组长度,其对应的轮变化次数是不同的,如表1所列。

1.3密钥扩展

AES算法利用外部输入密钥K(密钥串的字数为Nk),通过密钥的扩展程序得到共计4(Nr+1)字的扩展密钥。它涉及如下三个模块:

① 位置变换(rotword)——把一个4字节的序列[A,B,C,D]变化成

[B,C,D,A];

② S盒变换(subword)——对一个4字节进行S盒代替;

③ 变换Rcon[i]——Rcon[i]表示32位比特字[xi-1,00,00,00]。这里的x是(02),如

Rcon[1]=[01000000];Rcon[2]=[02000000];

Rcon[3]=[04000000]……

扩展密钥的生成:扩展密钥的前Nk个字就是外部密钥K;以后的字W[[i]]等于它前一个字W[[i-1]]与前第Nk个字W[[i-Nk]]的“异或”,即W[[i]]=W[[i-1]] W[[i- Nk]]。但是若i为Nk的倍数,则W[i]=W[i-Nk] Subword(Rotword(W[[i-1]])) Rcon[i/Nk]。

程序执行的时候,主要调用以上几个子程序,具体实现如下: Keyexpansion:

rcall rotwoed

rcall subword

rcall Rcon

.

.

.

AES的加密与解密流程如图1所示。

图1AES的加密和解密流程

2 AES加密、解密算法的优化

由以上算法的流程中可以清楚地看到,整个算法中程序耗时最多的就是圈变化部分,因此对于算法的优化也就在此;而圈变化部分可以优化的也就是列变化。因为列变化是一个模乘同余规则。由于AES

加密和解密是不对称的,如果不对其进行优化,会使算法的解密速度远远大于加密的速度[1]。

① 加密运算。对列变换(Mixcolumn)可以通过调用xtime子程序进行优化。具体算法[1]实现如下:

另一种有效的优化方法就是离线构造一个表格,即列变化表格。这样只要通过查表的方式就可以提高加密速度。

② 解密算法的优化。由于解密的列变换的系数分别是09、0E、0B和0D。在AVR单片机上实现以上的乘法显然是需要很多的时间,从而导致了解密的性能降低。

优化方法一:对列变化进行分解使倍乘次数降低。

仔细研究解密矩阵的系数,不难发现解密矩阵和加密矩阵有着一定的联系,即解密矩阵等于加密矩阵和一个矩阵的相乘。通过这样的联系,就可以对算法进行优化:

这样一来,只用几个简单的“异或”就可以实现列变化,使倍乘的次数降低,提高解密的速度。

优化方法二:构造表格。

同加密构造方法一样,可以构造四个表格T[ea]=e×a;

T[9a]=9×a;T[9a]=9×a;T[ba]=b×a。这样一来,也只需要进行查表和简单的异或就可以完成解密的任务。虽然这种方法将增加额外的开销,但是它却是一种有效的方法。

3 AES加密与解密的实验仿真

根据以上实验步骤和优化方法得出表2、3所列实验结果。 设主密钥为:000102030405060708090a0b0c0d0e0f(128bit)。 加密明文:00112233445566778899AABBCCDDEEFF。

密文:69C4E0D86A7B0430D8CDB78070B4C55A。

解密密文:69C4E0D86A7B0430D8CDB78070B4C55A。

明文:00112233445566778899AABBCCDDEEFF。

总之,AES密码是一个非对称密码体制,它的解密要比加密复杂和费时。解密优化算法没有增加存储空间的基础上,以列变化为基础进行处理,程序比原始的要小,而且节约了时间。解密优化方法速度最快,效率最高,但要增加系统的存储空间,因此它的程序也是最大的一个。

注:AES128数据加密解密程序见本刊网站(.cn)。

结语

AES高级数据加密算法不管是从安全性、效率,还是密钥的灵活性等方面都优于DES数据加密算法,在今后将逐步代替DES而被广泛应用。本文基于AVR的高速计算性能实现了AES算法,并结合汇编语言进行了算法的优化。根据实际应用的具体需要,可以选用相应的方法。

AES 是一个新的可以用于保护电子数据的加密算法。明确地说,AES 是一个迭代的、对称密钥分组的密码,它可以使用128、192 和 256 位密钥,并且用 128 位(16字节)分组加密和解密数据。与公共密钥密码使用密钥对不同,对称密钥密码使用相同的密钥加密和解密数据。通过分组密码返回的加密数据的位数与输入数据相同。迭代加密使用一个循环结构,在该循环中重复置换(permutations )和替换(substitutions)输入数据。Figure 1 显示了 AES 用192位密钥对一个16位字节数据块进行加密和解密的情形。

Figure 1 部分数据

AES算法概述

AES 算法是基于置换和代替的。置换是数据的重新排列,而代替是用一个单元数据替换另一个。AES 使用了几种不同的技术来实现置换和替换。为了阐明这些技术,让我们用 Figure 1 所示的数据讨论一个具体的 AES 加密例子。下面是你要加密的128位值以及它们对应的索引数组:

00 11 22 33 44 55 66 77 88 99 aa bb cc dd ee ff 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 192位密钥的值是:

00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f 10 11 12 13 14 15 16 17 0 1 2 3 4 5 6 7 8 9 10 1112 13 14 15 16 17 18 19 20 21 22 23

Figure 2 S-盒( Sbox )

当 AES 的构造函数(constructor)被调用时,用于加密方法的两个表被初始化。第一个表是代替盒称为S-盒。它是一个16×16的矩阵。S-盒的前五行和前五列如 Figure 2 所示。在幕后,加密例程获取该密钥数组并用它来生成一个名为w[]的密钥调度表,Figure 3 所示。 Figure 3 密钥调度表(Key Sched)

w[] 最初的 Nk (6) 行被作为种子,用原始密钥值(0x00 到0x17)。剩余行从种子密钥来产生。变量 Nk 代表以 32 位字为单位的种子密钥长度。稍后我分析 AES 实现时你将清楚地看到 w[] 是怎样产生的。关键是这里现在有许多密钥使用而不只是一个。这些新的密钥被称为轮密钥(round keys)以将它们与原始种子密钥区别开来。

Figure 4 State (态)数组

AES 加密例程开始是拷贝 16 字节的输入数组到一个名为 State (态)的 4×4 字节矩阵中。(参见 Figure 4)。AES 加密算法 取名为 Cipher,它操作 State[],其过程描述的伪代码参见 Figure 5 。

在规范中,加密算法实现的一个预备的处理步骤被称为 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)的结果:

1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 XOR 1 0 0 0 0 0 0 0

AES 算法的主循环对 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 表中寻找代替值,如 Figure 2 所示。 ShiftRows 是一个置换操作,它将 State 矩阵中的字节向左旋转。Figure 6 示范了 ShiftRows 如何操作 State[]。State 的第0行被向左旋转0个位置,State 的第1行被向左旋转1个位置,State 的第2行被向左旋转2个位置,而 State 的第3行被向左旋转3个 位置。 Figure 6 对 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,这时乘法的结果就是用值0x1b异或后的值再左移1比特位。它防止了“域溢出”并保持乘法的乘积在范围以内。

一旦你在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)

在加解密算法中,AES MixColumns 例程的其它乘法遵循大体相同的模式,如下所示: 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) { copy the seed key into the first rows of w for each remaining row of w { use two of the previous rows to create a new row } }

“用前面两行来产生一个新行”(“use two of the previous rows to create a new row”)的例程用到了两个子 例程,RotWord 和 SubWord 以及一个名为“Rcon”的常数表(作为“轮常数”)。让我们先来逐个看一下这三东西,然后再回到整个 KeyExpansion 的讨论中来。

RotWord 例程很简单。它接受一个4个字节的数组并将它们向左旋转一个位置。因为轮调度表 w[] 有四列,RotWord 将 w[]的1行左旋。注意 KeyExpansion 使用的这个 RotWord 函数与加密算法使用的 ShiftRows (行位移变换)例程非常相似,只是它 处理的是单行密钥调度 w[],而不是整个加密状态表 State[]。

SubWord 例程使用替换表 Sbox 对一给定的一行密钥调度表 w[] 进行逐字节替换。KeyExpansion 操作中的替换实际上就像在加密算法中的替换一样。被代替的输入字节被分成 (x,y) 对,它被当作进入替换表 Sbox 的索引。举例来说,0x27的代替结果是 x=2 和 y=7,并且 Sbox[2,7] 返回 0xcc。

KeyExpansion 例程使用一个被称为轮常数表的数组 Rcon[]。这些常数都是4个字节,每一个与密钥调度表的某一行相匹配。AES 的 KeyExpansion 例程需要11个轮常数。你可以在 Figure 7 中看到这些常数清单。

每个轮常数的最左边的字节是GF(28)域中2的幂次方。它的另一个表示方法是其每个值是前一个值乘上0x02,正如前一部分讨论 GF(28) 乘法 时所描述的那样。注意 0x80 × 0x02 = 0x36 是 0x80 左移1个比特位后紧接着与 0x1b 进行异或,如前所述。

现在让我们更进一步看看 KeyExpansion 内幕中的循环。这里所用的伪码比以前更为详

细,这个循环是:

for (row = Nk; row < (4 * Nr+1); ++row) { temp = w[row-1] if (row % Nk == 0) temp = SubWord(RotWord(temp)) xor Rcon[row/Nk] else if (Nk == 8 and row % Nk == 4) temp = SubWord(temp) w[row] = w[row-Nk] xor temp }

先不要去看if子句,你将看到密钥调度表 w[] 的每一行都是前面一行与行 Nk 异或的结果(4, 6, 或 8 取决于密钥的长度)。if条件的第一部分用 SubWord、RotWord 以及与轮常数的异或修改密钥调度表的每个第4、第6或第8行,取决于是否密钥的长度是128、192或256位。这个条件的第二部分将修改行 12、20 和 28 等等——对于256位密钥而言——每 一个第8行都将添加密钥调度额外的可变性。

让我们用本文开头所举的例子来考察 KeyExpansion 是如何开始的。种子密钥是192-bit / 6-word 值:

00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f 10 11 12 13 14 15 16 17

密钥调度字节表 w[] 的维数是 4 列并且 Nb × (Nr + 1) 等于 4 × (12 + 1),或 52 行。KeyExpansion 将种子密钥的值拷贝到密钥调度字节表 w[] 的第一行。因为我的种子密钥是 192 位(24字节),并且 w[] 表总是 4 列,在这种情况下KeyExapansion 将种子密钥拷贝到 w[] 的前面 6 行。现在让我们看看 KeyExapansion 例程是如何填充密钥调度表其余部分的。在我的例子里,第一个被计算的行是第 6 行 ,因为第0-5行已被种子密钥的值填上了:

temp = w[row-1] = 14 15 16 17

条件 (row % Nk == 0)为真,因此首先 RotWord 子程序被应用:

temp = 15 16 17 14

这时 SubWord 被应用:

temp = 59 47 f0 fa

用 Rcon[row / Nk] = Rcon[6 / 6] = 01 00 00 00 进行异或:

temp = 58 47 f0 fa

这时用 w[row-Nk] = w[6-6] = 00 01 02 03 异或,产生了下面结果:

w[6] = 58 46 f2 f9

密钥调度表 w[] 中其余所有行来重复这个过程本身。

总而言之,AES 加密和解密的一个重要部分就是从最初的种子密钥中生成多重轮密钥。这个 KeyExapansion 算法生成一个密钥调度并 以某种方式进行替代和置换,在这种方式中,加密和解密算法极其相似。

用 C# 编写 AES 类构造函数

现在我已研究了构成 AES 加密算法的各个成分,我将用 C# 来实现它。官方的 AES 算法规范包含在联邦信息处理标准出版物197 (Federal Information Processing Standards Publication 197)中。我决定尽可能贴切地以它作为我的实现的基础,但是我很快发现这个规范更是一个理论文献而非一个实现的向导。为了将这个官方规范作为资源来使用,我使用 的变量名与标准出版物中所用的相同。(即便它们是那么晦涩,如“Nr”和“W”)。 我的设计使用9个数据成员和一个枚举类型,如下所示:

public enum KeySize { Bits128, Bits192, Bits256 }; private int Nb; private int Nk; private int Nr; private byte[] key; private byte[,] Sbox; private byte[,] iSbox; private byte[,] w; private byte[,] Rcon; private byte[,] State;

因为密钥长度只能是128位、192位或256位比特,它是非常适于用枚举类型: public enum KeySize { Bits128, Bits192, Bits256 };

该规范文档一般用字节作为基本储存单元而不是用4字节的字作为两个重要数据成员

的长度。这两个成员 Nb 和 Nk 代表以字为单位的块长以及以字为单位的密钥长度。Nr代表轮数。块长度总是16字节(或这说是 128 位,即为 AES 的 4个字),因此它可以被声明为一个常量。密钥长度 依照枚举参数 KeySize 的值被赋值为 4、6 或 8。AES 算法强调通过大量轮数来增加加密数据的复杂性。轮数是10、12或14中的任意一个并且是基于密码分析学理论的。它直接取决于密钥长度。

当设计一个类接口时,我喜欢向后来做。我设想从应用程序中调用构造函数和方法。使用这个办法,我决定象下面这样来实例化一个 AES 对象:

Aes a = new Aes(the key size, the seed key)

我调用的加密和解密例程如下:

a.Cipher(plainText, cipherText); a.InvCipher(cipherText, decipheredText);

我选择少许笨拙的方法来命名 Cipher 和 InvCipher,因为它们是用在 AES 规范文档中的。这里是 AES 类构造函数的代码为:

public Aes(KeySize keySize, byte[] keyBytes) { SetNbNkNr(keySize); this.key = new byte[this.Nk * 4]; keyBytes.CopyTo(this.key, 0); BuildSbox(); BuildInvSbox(); BuildRcon(); KeyExpansion(); }

该构造函数首先调用一个辅助方法 SetNbNkNr 给 Nb、Nk 和 Nr 赋值,如 Figure 8 所示。如果考虑到效率,你可能将这些代码直接放入构造函数 以避免方法调用的开销。 接下来,你必须将传入构造函数的字节拷贝到类域变量中。密钥用其它的类域声明,并且用如下方法获得它的值:

this.key = new byte[this.Nk * 4]; keyBytes.CopyTo(this.key, 0);

我决定在构造函数中调用私有辅助方法 BuildSbox 和 BuildInvSbox 来初始化替换表 Sbox[] 和 iSbox[] 。现在密钥扩展例程 、Cipher 方法和 InvCipher 方法各自都需要 Sbox[] 和 iSbox[],因此我本来可以在 Cipher 和 InvCipher 两个方法中初始化 Sbox[] 并调用 KeyExpansion 方法,但是将它们放入构造函数会代码结构更加清晰。在 Figure 9 中 sBox[] 被填充。填充 iSbox[] 代码类似。为了可读性对代码进行了结构化处理。正如后面你将看到的,还有另外一个可供选择的令人惊讶的方法为 Sbox 和 iSbox 表提供值。

在构造函数中声明密钥调度表 w[]、轮常数表 Rcon[] 和状态矩阵 State[],并用私有辅助方法来给 Rcon[] 和 w[] 赋值在我看来似乎是组织它们的最好办法,但那主要还是个风格问题。置换轮常数表 Rcon 的赋值代码参见 Figure 7。

回想一下,GF(28)中,Rcon[] 每一行左边的字节都 2 的幂,因此这个表可用下面的方法建立:

newVal = prevVal * 0x02;

AES 构造函数在建立完密钥调度表 w[] 后结束,而 w[] 是在 KeyExpansion 方法中完成的(参见 Figure 10)。其代码相当简单。规范文档使用一个假设的 4-字节的字数据类型。因为 C# 没有那样的类型,但可以用一个4个字节的数组来模拟。在用 new 操作符为密钥调度 表 w[] 分配空间后,w[] 最初的 Nk(4, 6, 或 8) 行从被传递到构造函数的种子密钥 key[] 数组中获值。

this.w[row,0] = this.key[4*row]; this.w[row,1] = this.key[4*row+1]; this.w[row,2] = this.key[4*row+2]; this.w[row,3] = this.key[4*row+3];

两个字节相互的异或操作在这个代码中频频发生。它需要一些从 byte 到 int 的强制类型转换并转回到 byte,因为异或操作“^”是不能定义在 C# 的 byte 类型上,例如: temp[0] = (byte)( (int)temp[0] ^ (int)this.Rcon[row/Nk,0] );

用来替代:

temp[0] = temp[0] ^ this.Rcon[row/Nk,0];

KeyExpansion 方法有条件地调用私有方法 SubWord 和 RotWord 以保持同规范命名的一致性。此外,因为在C#中没有 word类型,我用 4字节数组实现了一个字。SubWord 和 RotWord 的代码是相当简单,参见本文附带的 AesLib 源代码,它应该很容易理解。 稍微具备有些技巧的部分是在 SubWord 中查找替代值。回想一下,为了寻找代替值,你将输入字节分成最左边的4位比特和最右边的4位比特。对于一个给定字节,用 >> 操作符右移 4 位将得到 x 索引,并且与 0000 1111 进行逻辑与得到 y 值。虽然有些长,但比实际代码更可读,我可以象下面这样:

int x = word[0] >> 4; int y = word[0] & 0x0f; byte substitute = this.Sbox[x,y]; result[0] = substitute;

代替我原来用的代码:

result[0] = this.Sbox[ word[0] >> 4, word[0] & 0x0f ];

总的来说,AES 构造函数接受一个密钥的长度为128,192 或 256 位和一个字节数组种子密钥值。构造函数为输入块长度,种子密钥长度以及加密算法的轮数赋值,并将种子密钥拷贝到一个名为 key 的数据成员中。构造函数还创建了四个表:两个由加密和解密方法使用的替换表,一个轮常数表,和一个轮密钥的密钥调度表。

用C#编写的 AES Cipher 方法

Cipher方法如 Figure 11 所示。它真的非常简单,因为它分出了大部分的工作给私有方法AddRoundKey, SubBytes, ShiftRows 和 MixColumns。

Cipher 方法以拷贝明文输入数组到状态矩阵 State[] 为开始。最初调用 AddRoundKey 之后,Cipher 方法比总轮数少迭代一次。在最后一轮时,正如规范中所说的那样,MixColumns 调用被省略了。

AddRoundKey 和 SubBytes 私有方法的代码如 Figure 12 所示。AddRoundKey 方法需要知道它处在那一轮,以便它正确引用4行密钥调度数组 w[]。请注意 State[r,c] 是用 w[c,r] 来异或并不是w[r,c]。SubBytes 方法从输入字节中提取索引,与 KeyExpansion 方法中所用的右移4位和 0x0f 屏蔽技术相同。

ShiftRows 方法的代码如 Figure 13 所示。回想一下,ShiftRows(可能叫做 RotateRows 更好)将 row[0] 向左旋转 0 个位置,将 row[1] 向左旋转 1 位置等等。

把 State[] 拷贝到 temp[] 矩阵之后,然后用下面的这行代码实现转换:

this.State[r, (c + r) % Nb ] = temp[r,c];

这里利用%操作符的优点抱合一行。

MixColumns 方法(Figure 14)用GF(28)加和乘,以字节列中所有其它值的线性组合对每一个字节进行替换。

乘法所用的常量系数基于域论的,并且是0x01, 0x02或 0x03中的任意一个值。给定某一列 c ,其替代式如下:

State[0,c] = 0x02 * State[0,c] + 0x03 * State[1,c] + 0x01 * State[2,c] + 0x01 * State[3,c] State[1,c] = 0x01 * State[0,c] + 0x02 * State[1,c] + 0x03 * State[2,c] + 0x01 * State[3,c] State[2,c] = 0x01 * State[0,c] + 0x01 * State[1,c] + 0x02 * State[2,c] + 0x03 * State[3,c] State[3,c] = 0x03 * State[0,c] + 0x01 * State[1,c] + 0x01 * State[2,c] + 0x02 * State[3,c]

这些表达式稍微有些长,因此我决定编写返回 GF(28)与 0x01,0x02 和 0x03 之乘积的私有辅助函数。这些辅助函数非常短。例如,一个字节 b 被 0x03 域乘的代码如下: return (byte) ( (int)gfmultby02(b) ^ (int)b );

正如我前面讨论的,被 0x02 乘是所有 GF(28) 乘法的基本操作。我调用了我的 gfmultby02 方法,我改变了使用与规范相同的方法命名惯例,规范上称此例程为 xtime。 Cipher 方法其输入反复应用四个操作来产生加密的输出。AddRoundKey 用源于单个原

始种子密钥的多重轮密钥来替代字节。SubBytes 用某个替换表中的值替代字节。ShiftRows 用移动字节行置换字节,而 MixColumns 用某一列的域加和乘法值来替代字节。 用C#编写 AES InvCipher 方法

AES 解密算法背后的基本原则很简单:解密一个加密块,也就是以反向顺序还原(Undo)每个操作。尽管这是基本概念,但仍有几个细节要处理。

AES规范称解密例程为 InvCipher,而不是 Decipher 或 Decrypt 中的一个。这是 AES 背后的数学基础的反映,它基于可逆的数学操作。

如果你将这个代码和 Cipher 代码比较的话,你会看到它比你预期的漂亮很多,但是有两点例外。首先,在 InvCipher 方法中逆方法调用(如 InvSubBytes)顺序并不完全与在 Cipher 方法中相应调用(如 SubBytes)的逆向顺序正好相同。其次,InvCipher 调用的是一个 AddRoundKey 方法而不是 InvAddRoundKey 方法。值得注意的是 InvCipher 算法用密钥调度表并不是从较高编号的索引处开始向下处理至第0行。

InvSubBytes, InvShiftRows 和 InvMixColumns 方法的代码和与之有关的 SubBytes,ShiftRows和 MixColumns 方法的代码非常接近。InvSubBytes 方法几乎就是 SubBytes 方法,只是它用逆替换表 iSbox[] 而不是 Sbox[] 表。

正如你可能猜测到的,iSbox[] 就是还原任何被 Sbox[] 处理的对应操作。比如,如果你有字节 b 等于 0x20,并在 Sbox[] 中找到其代替值,你得到 0xb7。如果你在 iSbox[] 中找到 0xb7的替代值,你便可得到 0x20。

相似地,InvShiftRows 方法还原 ShiftRows 方法—— row[0] 被右移了 0 个位置,row[1] 被右移了 1个位置,row[2] 被右移了 2 个位置,而 row[3] 被右移了 3个位置。 InvMixColumns 方法还原 MixColumns 的工作,但没有用显而易见的方法。回想一下,MixColumns 用原始字节列中的字节线性组合替换状态矩阵中的每个字节,并且系数是 0x01,0x02,和 0x03,域论再一次得到应用。它证明逆运算是相似的,只是被 0x09,0x0b,0x0d 和 0x0e 乘,如下所示:

State[0,c] = 0x0e * State[0,c] + 0x0b * State[1,c] + 0x0d * State[2,c] + 0x09 * State[3,c] State[1,c] = 0x09 * State[0,c] + 0x0e * State[1,c] + 0x0b * State[2,c] + 0x0d * State[3,c] State[2,c] = 0x0d * State[0,c] + 0x09 * State[1,c] + 0x0e * State[2,c] + 0x0b * State[3,c] State[3,c] = 0x0b * State[0,c] + 0x0d * State[1,c] + 0x09 * State[2,c] + 0x0e * State[3,c]

对于 MixColumns 方法,我决定专门写一个辅助函数,而不是内联展开已经较长的表达式或写一个普通的乘法辅助函数。让我向你展示一下我示如何编写这个任何字节 b 被常数 0x0e (在10进制中的14)乘的函数,像任何数字一样,数字 14 可以被表示成 2 的幂的和,因此,14 等于 2 + 4 + 8。并且 4 等于 2 的平方,8 等于 2 的立方,你可以将14表示为 2 + 22 + 23。记住加法就是 GF(28)中上的异或(^),既然我已经有了 gfmultby02 函数,我可以用它得到我的结果:

return (byte)( (int)gfmultby02(gfmultby02(gfmultby02(b))) ^ /* 23 + */ (int)gfmultby02(gfmultby02(b)) ^ /* 22 + */ (int)gfmultby02(b) ); /* 2 */

用于 AES 加密算法的所有的操作都是可逆的,因此解密算法本质上是加密的所有操作的倒转。

使用 AES 类

用C#实现 AES 的特色之一就简单。看看 Figure 15,它是我用来生成输出 Figure 1 的代码。声明了 16 字节明文输入硬代码值和 24 字节(192位)的种子密钥后,一个 AES 对象被初始化,加密 Cipher 方法 将明文加密成为密文,然后再用 InvCipher 将密文解密。非常清楚和简单。

因为 AES 对象针对字节数组进行处理,你可以轻松地用它处理.NET的其它数据类型。

我创建了一个基于 Windows 的小Demo程序,它接受一个单纯的字符串——有 8 个字符 (16-byte) ,对它进行加密和解密处理。运行画面如 Figure 16。

Figure 16 加密 Demo 程序

因为加密和解密例程都需要知道用户定义的密钥长度,我把它当作一个类范围的变量来声明,像这样:

private Aes.KeySize keysize;

注意种子密钥并不是由用户定义的。这个 demo 程序用一个“空密钥”(null key)作为种子密钥,通过为构造函数提供一个哑参数 new byte[16] 使得它全部由零字节组成。哑参数的长度是不相关的,因为种子密钥还是要被初始化为零。空密钥加密和解密是一个容易和有效的办法来阻止外界对数据偶然的检查。在 System.Text 中的 Encoding.Unicode.GetBytes和Encoding.Unicode.GetString 方法使得将一个.NET 字符串转换成一个字节数组变得非常容易,反之亦然。

实现选择

现在让我们看看本文 AES 实现中出现的一些重要的变量,本文提供的代码可能出现的扩展,以及针对 AES 的密码分析学攻击。

和我曾经处理的任何代码一样,AES 算法也可以用其它可选的途径来实现。为什么这很重要呢?AES 被试图广泛应用于各种系统,从只有很少内存容量的智能卡(smart cards)到大型的多处理器主机系统。在许多情况下,性能是关键因素,并且有时内存或处理器资源是有限的。事实上,AES 的每个例程都能针对非常昂贵的内存资源进行性能优化,反之亦然。比如,为替换表Sbox[] 分配 256 个值看起来好像很简单直白。但是,这些值是基于 GF(28) 理论的,它们都可以用编程方式来生成。逆向替换表和轮常数表也是如此。

可选实现另外一个有趣的可能性是 Cipher 和 InvCipher 方法所用的 GF(28) 乘法。我的实现代码是一个被 0x02 乘的基本函数,而后是六个调用 gfmultby02 的附加函数。另一个可能性应该是写一个一般的乘法函数,并用它代替我目前实现的七个单独函数。另一个极端是你可以用被 0x01, 0x02, 0x03, 0x09, 0x0b, 0x0d 和 0x0e 乘好的所有 256 个可能的字节值构成的一个完整乘积表。此外,实现 GF(28) 乘法另一途径是通过在两个 256 个字节的数组里查找,通常称为 alog[] 和 log[],因为它们在 GF(28)中基于某些类似对数的方法。 虽然这里给出的 AES 类完全能用于加密任何形式的.NET数据,你可能考虑想用各种方法扩展它。首先,因为本文的重点在于清楚地解释 AES,所有 错误检查被剥离掉,以我的经验,为某个象 AES 这样的类添加合理数量的错误检查将会产生三倍的代码量膨胀。因为 AES 使用了这么多的数组,需要做很多索引 边界检查。例如,所给出的构造函数甚至都不检查种子密钥参数的长度。

你可能还考虑通过添加更多的特性来扩展 AES 类。最明显的一个地方是添加加密和解密.NET基本数据类型的方法,比如:System.String 和 System.Int32。更加雄心勃勃的扩展可能会是实现一个 流数据加密类。

AES 的安全性怎样呢?这是一个很难回答的问题,但是一般多数人的意见是:它是目前可获得的最安全的加密算法。AES 已被列为比任何现今其它加密算法更 安全的一种算法。在理论和实践基础上,AES 被认为是“安全的”,因为要破解它的话,唯一有效的方法是强行(brute-force)生成所有可能的密钥。 如果密钥长度为 256 位,还没有已知的攻击可以在一个可接受的时间内破解 AES(即便在当今最快的系统上,它也要花费数年时间)。 注意针对 AES 密码最可能成功的攻击来自一个允许时间选择攻击的弱实现。攻击者用不同的密钥并精确地测量出加密例程所需的时间。如果加密例程被粗心编码,因此执行时间便依赖于密钥值,它就有可能推导出有关密钥的信息。在 AES 中,这种事情最可能发生在

MixColumns 例程中,因为有域乘。针对这种攻击的两个安全措施是加入虚指令,以便所以所有乘法都需要相同数量的指令,或者将域乘实现为一个查询表,就象我前面描述的那样。 AES 有许多种可能的实现,尤其是是使用查询表而不是计算。本文提供的 AES 基本类可以被用于加解密任何形式的.NET数据或 被扩展成一个具有更多功能的类。 结束语

新的 AES 将无疑成为加密所有形式电子信息的事实上的标准,取代 DES。AES 加密的数据在某种意义上是牢不可破的,因为没有已知的密码分析攻击可以解密 AES 密文,除非强行遍历搜索所有可能的 256 位密钥。

我发现在 Microsoft .NET Framework 上实现 AES 类的主要的障碍是官方文档是以一个数学家的观点,而不是以一个软件开发者的观点来写的。尤其是该规范假定读者十分熟悉 GF(28) 域,并省略了几个正确实现 AES 所必需的关于 GF(28) 乘法的关键事实。我在本文中试图努力去掉 AES 的神秘面纱,特别是围绕在 GF(28) 域乘法部分的。

以 .NET Framework 库的形式从 Microsoft 以及第三方供应商处获得对 AES 的广泛支持只是一个时间问题。然而,处于种种理由,让本文代码作为你的技能储备仍然是有价值的。这个实现尤其简单,并且是低资源开销。另外,阅读并理解源代码将使你能定制 AES 类且更有效地使用它的任何实现。

在任何软件设计过程中安全已不再是后顾之忧。AES 是一个重大进步,使用并理解它将大大增加软件系统的可靠性和安全性。

相关文章

* Security: Protect Private Data with the Cryptography Namespaces of the .NET Framework * Exploring Kerberos, the Protocol for Distributed Security in Windows 2000

背景信息

The Design of Rijndael: AES - The Advanced Encryption Standard by Joan Daemen and Vincent Rijmen. (Springer-Verlag, 2002)

Announcing the Advanced Encryption Standard (AES): Federal Information Processing Standards Pub 197

作者简介

James McCaffrey 在Volt Information Sciences Inc公司工作,在那里他管理为 Microsoft 的软件工程师技术培训。他作为一些 Microsoft 产品的承包人工作包括 Internet Explorer 和 MSN Search。可通过 jmccaffrey@volt.com 或

v-jammc@microsoft.com与他联系。

有关AES的一些理解 最近很多密码学的书都包含了最新的AES算法,但由于涉及的数学理论比较多,我也只是明白一些能让我实现他的皮毛。 AES比较牛的地方是速度快,而且明文和密钥的长度可以是128,196,256位,并且可以任意组合,明文和密钥的长度不一定是一样长的。由于采用了模块化设计,算法包含4个步骤:1.字节替换;2.行位移;

3.列混淆;4.密钥加法,这些步骤循环10轮。最让我恶心的第10轮的又不一样,没有列混淆。强烈建议大家看作者的英文论文和书,其中讲到了一种32位平台的快速实现方法。这种方法根据每一步的数学原理,将4步和为一步,那一大堆公式推倒我就不在这重复了。这

种快速实现方法需要构造8个矩阵(加解密各四个),一般都叫他们Tbox。加解密前九轮只需用U替换一下即可,最后一轮还是用Sbox做替换,所以这速度是唰唰的快呀~ 这样一来,实现AES的关键问题就是怎么构造8个矩阵U。其中涉及多项式即算问题。

(1)多项式加法 多项式加法即按位做异或运算。例如0x57 + 0x83 = 01010111 XOR 10000011 = 11010100 = 0xD4。 (2)多项式乘法 GF(2)中的乘法是多项式的模2乘积通过免去进位,再模一个次数为n的不可约多项式约化得到,不可约多项式我理解的和自然数域中的素数相对应,都是有不可再分解的特点。例如下面GF(2)的例子: f(x)*g(x) = (x+x)(x+x+1) mod (x+x+1) = (x+2x+2x+x) mod (x3+x+1) 系数是二的直接约掉,实际上这里是模2加

法 = (x+x) mod (x+x+1) = x+1 Rijindael选用8次不可约多项式x+x+x+x+1,可用元组(100011011)或十六进制数0x11B表示。用这个多项式的理由听起来比较有意思,作者说是在一本书上有一堆8次不可约多项式,第一个是0x11B就用它了,FT吧。f(x)乘以x+1(或‘03’)的乘法分解成f(x)*2+1,最后模m(x)约化: f ^= f << 1; //乘2加1 if(f & 0x100) f ^= 0x11B; //模m(x)约化在GF(2)中的两个多项式f和h的乘法可通过用对数加速:设g(x)为GF(2)的一个生成多项式,所谓生成多项式就是数组的256个元素的值就是0-255的排列,则存在m和n使得f=g,h=g,则f*h=g mod m(x)。有了这个公式我们就可以把多项式乘法转为加法来算,具体说来就是构造对数表和反对数表,如下图: mnm+x888434322223433n

对数表的构造: 1. 构造多项式g(x)=x+1的255个幂存入alog表中 alog[0] = 1; for (i = 1; i < 256; i++) { j = (alog[i-1] << 1) ^ alog[i-1]; //x*3=x*2+1 if ((j & 0x100) != 0) // 如果超过255,需要约化 j ^= ROOT; alog[i] = j; } 2. 在log表中存放对底g(x)的对数 for (i = 1; i < 255; i++) log[alog[i]] = i; 再构造alog和log之后,乘法运算可以一步完成alog[ (log[a]+log[b]) % 255 ] 。 实际上实现多项式乘法的方法有很多种,在m

sdn搜AES可以查到一篇写c#实现的,它的乘法算法也是一种很经典的方法。用对数表的方法好理解,最重要的是查表速度快。

S盒和反向S盒的实现 (1) 初始化S盒,按升序排列的字节表示的所有数,0至255。 (2) 用alog[255-log[x]],把S盒中每个字节映射为它在GF(28)中的逆。0被映射为0。 (3) 计算那个仿射变换,那个公式很恶心,参看作者的文献。其中的矩阵乘法,可以利用前面DES的技巧,把S盒的每个字节按位分离存放在一个256*8的临时矩阵中再计算乘法。 解密用的逆S盒可以用inSbox[Sbox[i] & 0xFF] = i得到。Tbox的构造 for (t = 0; t < 256; t++) { s = Sbox[t]; Tbox1[t] = mul4(s, G[0]); Tbox2[t] = mul4(s, G

[1]); Tbox3[t] = mul4(s, G[2]); Tbox4[t] = mul4(s, G[3]); s = inSbox[t]; Tbox5[t] = mul4(s, iG

[0]); Tbox6[t] = mul4(s, iG[1]); Tbox7[t] = mul4(s, iG[2]); Tbox8[t] = mul4(s, iG[3]); } G矩阵可以在作者的文献中查到,iG是G在GF(28)的逆。 在加解密过程中,加密用Tbox1-4,解密用Tbox5-8,前9轮用T,最后一轮用Sbox。但是要注意调用顺序,为了实现列混淆,具体顺序参看那个列混淆的公式。

更多类似范文
┣ 简介 1200字
┣ 集镇简介 1000字
┣ 树木简介 2200字
┣ 中队简介 600字
┣ 更多简介范文
┗ 搜索类似范文