AES算法及实现

        AES是美国国家标准技术研究所NIST旨在取代DES的新一代的加密标准。NIST对AES候选算法基本要求是：对称分组密码*；**长度支持128,192,256位；明文分组长度128位；算法应易于各种硬件和软件实现。1998年NIST开始AES第一轮征集、分析、测试、共产生了15个候选算法。1999年8月NIST公布了五种算法（MARS,RC6，Rijindael,Serpent，Twofish）成为候选算法。最后Rijndarl，这个由比利时人设计的算法与其它候选算法在成为高级加密标准（AES）的竞争中取得成功，于2000年10月被NIST宣布成为取代DES的新一代的数据加密标准即AES。尽管人们对AES还有不同的看法，但总体来说Rijndael作为新一代的数据加密标准汇聚了强安全性、高性能、高效率、易用和灵活等优点。AES设计有三个**长度：128,192,256 比特，相对而言，AES的128比特**比DES的56比特**强1021倍。

对称密码算法根据对明文消息加密方式不同科分为两大类，即分组密码和流密码。分组密码将消息分为固定长度的分组，输出的密文分组通常与输入的明文分组长度相同。AES算法属于分组密码算法，它的输入分组、输出分组以及K为128,192,或256比特。用Nk=4,6,8代表**串的字数（1字=32比特）用Nr表示对一个数据分组加密的论数，每一轮读需要一个和输入分组具有相同长度（128比特）的扩展**Ke的参与。由于外部输入的加***K长度有限，所以在AES中要用一个**扩展程序把外部**K在扩展成更长的比特串，以生成各轮的加***。

2.1，**

**（Key）是密码算法中参与运算的数值（或者数值集）。对报文进行加密，我们需要一个加密算法、一个加***以及明文，并由此产生密文。对报文进行解密，我们需要一个解密算法、一个解***以及密文，并由此复原原始的明文。

2.2加密变换

AES的加密和解密框图如图1所示。

1. 加密变换

     设X施AES的128比特明文输入，Y是128比特的密文输出，则AES的密文Y可以用下面的复合变换表示：Y=A k（r+1） R  S  Akr   C  R  S  A k（r1）…… C R S Ak1（X）

其中“”表示复合运算。这里Ak1 表示对X的一个变换Aki （X）=X ⊕KI（KI为第i轮的子**，为比特串的异或运算）。S:S盒置换。即对每一个字节用S-Box做一个置换。S-Box是一个给定的转换表。R：行置换。C：列置换。S’（x）=a（x）S（X）

这里是特殊的乘法运算，将在下面仔细介绍。

 

                     图1

1. 解密变换

     解密变换是加密变换的逆转换。

3.1 分组加密

   表1是三种不同类型的AES加***组大小与相应的加密轮数对照表。

   加密开始时，输入分组的各字节按表2的方式装入一个矩阵State中。如输入ACBDEFGHIJKLMONE则输入块影射到如表2的状态矩阵State中。

AES类型	**长度	分组大小	加密轮数		A	E	I	M
AES-128	4字节	4字	10		B	F	J	O
AES192	6字节	4字	12		C	G	K	N
AES256	8字节	4字	14		D	H	L	E

                 表1                                            表2

加密过程主程序由下面的伪代码描述。其中子程序Subytes（），ShiftRows（），MixColumms（）和AddRounKey（），**扩展程序将在下面介绍。

 

 

3.2 S盒变换（Subyte）

对输入矩阵的任何一个元素A 做如下变换S[A]:

1. 一个元素A从存储角度看都是一个八位的二进制数。算出前四位所代表的十六进制数x和后四位所代表的十六进制数y。如A=11010100时 x=c， y=4
2. 从AES算法给定的S-Box（16行16列其中每个元素为一个字节具体的S-Box略）中找出S[A]=S[x，y]的值。如A=11010100时，S[A]=S[x,y]=S[c,4]={1c}=00011101 。或直接通过下面的公式将A=b7b6b5b4b3b2b1b0变为S[A]=b ’7b’6b’5b’4b’3b’2b’1b’0b’=b′i=bib(i+4)mod8b(i+5)mod8b(i+6)mod8b(i+6)mod8⊕Ci

这里c=(c0,c1,c2,c3,c4,c5,c6,c7)=(0,1,1,0,0,0,1,1）。

3.12  行变换（ShiftRows）

在行变换中，中间状态矩阵State的第一行不变；第二至四行做如下变换，即将表3的状态矩阵变为表四的状态矩阵。

      

3.3 列变换

列变换是堆中间状态矩阵State逐列进行变换，其变换如下的矩阵运算：

                

经过上面的运算，原来的一列就被替换成下面的式子所表达的新列

  

这里的⊕为按位异或运算，其中的乘法X 按照下面介绍的模乘同余规则进行计算

列变换中药用到的模乘同余规则和我们一般用到的乘法有些不同，由于每一个元素都是一个字节于是可以把字节看成一个形式上的七次多项式，即将b7b6b5b4b3b2b1b0视为b7X7 +b6X6+b5X5+b4X4+b3X3+b2X2+b1X+b0 如{11011001}2 ={d9} 16可以被看成是X7+X6+X4+X3+1.列变换希望把一个字节变为一个新的字节，所以需要把两个形式上的的七次多项的乘法结果变为一个新形式上去七次多项式，然后才能将其恢复为一个字节的长度。这里采用模一个八次不可约多项式的同余乘法，即将两七次多项式的乘法结果除以这个八次不可约多项式再取其余式。在AES中这个八次不可约多项式为m（X）=X8+X4+X3+X+1。

3.4 与扩展**的异或运算（AddRoundKey）

   扩展**只参与了这一个变换。根据加密的轮数用相应的扩展**的四个数据项和中间状态矩阵上的列进行按位异或。

 

3.5**扩展程序KeyExpansion

AES算法利用外部输入**K（**串的字数为Nk）通过**扩展程序得到共4（Nr+1）字的扩展**w[4X（Nr+1）]涉及如下三个模块；

 

   这样程序就实现了对一个文件的加密/解密操作。

1. 位置变换Rot（Word）把一个四个字节的序列[a0，a1，a2，a3]左移一个字节变为[a1,a2,a3,a0]。
2. SubWord，对一个四字节的输入字[a0，a1，a2，a3]的每一个字节进行S盒变换，然后作为输出见3.1.1
3. 变换Rcon[].Rcon[i] 表示32比特字符串[xi-1,00,00,00]。这里X=（02），,xi-1   是X=（02）的（i-1）次幂的十六进制表示。
4. 扩展**生成。扩展的前Nk个字就是外部**K；以后的字W[[i]]等于它前一个字W[[i-1]]与前第Nk个字W[[i-Nk]]的异或，即W[[i   -1]]XORw[[i -Nk]]。但是若i为Nk的倍数，则W[i]=W[i -Nk]XORSubWord(RotWord(w[[i -1]]))XORRcon[i/Nk]

5. 4，对文件加密/解密

   在完成DES分组加密算法实现的基础上，现在利用密文分组链接方式将其用于对文件的加密/解密。程序操作步骤如下：

6. 根据文件处理方式选择模块，选择对文件加密、对文件解密或是退出程序
7. 输入K的长度（128比特、192比特、256比特）和**。
8. 用**扩展程序对**加以扩展。128比特192比特256比特**分别对应KeyExpansion128(key），KeyExpansion192(key），KeyExpansion256(key），分别生成72byts，204bytes，236bytes的扩展**。
9. 创建加密/解密文件。文件都是以文本的格式存储的。
10. 从等待加密/解密文件取出16个字节。若是未取得16个字节文件就结束，则在结束处标上文件结束符。把取出的数据放入中间变量（STATE）中。
11. 根据**的长度对STATE中的数据进行加密/解密，128比特、192比特256比特分别对应Cipher128（InvCipher128），Cipher192（InvCipher192），Cipher256（InvCipher256）并把加密/解密后的数据保存在STATE中，把STATE中的数据写入加密/解密文件中。
12. 如果等待加密/解密的文件已经结束，则关闭文件，挥刀操作（1）；否则挥刀操作（5）