课程设计
课程名称 密码学
题目名称 AES的实现与分析
学生学院 应用数学学院
专业班级 11信息安全1班
学 号
学生姓名
指导教师 李锋
20##年 12月 25日
广东工业大学课程设计任务书
一、课程设计的内容
美国美国国家标准与技术研究院(NIST)于20##年引入了AES加密算法，取代老旧的DES(数字加密标准)，后者当时应用非常广泛，但屡屡被证明已变得相当脆弱。AES现在广泛用于金融财务、在线交易、无线通信、数字存储等领域，经受了最严格的考验。
AES提供128位密钥，因此，128位AES的加密强度是56位DES加密强度的1021倍还多。假设可以制造一部可以在1秒内破解DES密码的机器，那么使用这台机器破解一个128位AES密码需要大约149亿万年的时间。
本课程设计就根据AES的基本原理，在课本介绍的基础上，进行更进一步的探索与思考，通过编程制作一个加密解密系统，从而实现AES加密。
二、课程设计的要求与数据
1、AES密码算法明文输入长度，密文输出长度及密钥长度的思考。
2、AES的加密算法和解密算法在实现上的区别。
3、AES算法的字节替代的实现。
4、行移位、密钥扩展、列混合等算法的实现。
三、课程设计应完成的工作
1、查阅大量相关资料，了解AES的背景及应用。
2、理解AES的实现过程及原理。
3、根据算法原理编写程序。
4、测试程序并完成课程设计报告。
四、课程设计进程安排
五、应收集的资料及主要参考文献
《现代密码学——原理与协议》
发出任务书日期： 年 月 日 指导教师签名：
计划完成日期： 年 月 日 基层教学单位责任人签章：
主管院长签章：
目录
1. 背景说明... 1
2. 系统展示... 2
3. 系统功能原理... 2
3.1. 字节替换SubByte. 2
3.2. 行移位ShiftRow.. 2
3.3. 列混合MixColumn. 2
3.4. 轮密钥加AddRoundKey. 3
3.5. 逆字节替换InvByteSub. 3
3.6. 逆行移位InvShiftRow.. 3
3.7. 逆列混淆InvMixColumn. 4
3.8. 加密流程图... 4
3.9. 解密流程图... 5
4. 系统程序设计... 5
4.1. 字节替换... 5
4.2. 行位移 6
4.3. 列混合 7
4.4. 密钥加 9
4.5. 密钥扩展... 9
4.6. 获取RoundKey. 10
4.7. 逆字节替换... 11
4.8. 逆行位移... 11
4.9. 逆列混合... 12
4.10. 加密... 14
4.11. 解密... 16
5. 总结与分析... 19
1. 背景说明
密码学中的高级加密标准（Advanced Encryption Standard，AES），又称高级加密标准Rijndael加密法，是美国联邦政府采用的一种区块加密标准。这个标准用来替代原先的DES，已经被多方分析且广为全世界所使用。经过五年的甄选流程，高级加密标准由美国国家标准与技术研究院 （NIST）于20##年11月26日发布于FIPS PUB 197，并在20##年5月26日成为有效的标准。20##年，高级加密标准已然成为对称密钥加密中最流行的算法之一。
美国美国国家标准与技术研究院(NIST)于20##年引入了AES加密算法，取代老旧的DES(数字加密标准)，后者当时应用非常广泛，但屡屡被证明已变得相当脆弱。AES现在广泛用于金融财务、在线交易、无线通信、数字存储等领域，经受了最严格的考验。
AES提供128位密钥，因此，128位AES的加密强度是56位DES加密强度的1021倍还多。假设可以制造一部可以在1秒内破解DES密码的机器，那么使用这台机器破解一个128位AES密码需要大约149亿万年的时间。
AES 有一个固定的128位的块大小和128，192或256位大小的密钥大小，并且用128位(16字节)分组加密和解密数据。与公共密钥密码使用密钥对不同，对称密钥密码使用相同的密钥加密和解密数据。通过分组密码返回的加密数据的位数与输入数据相同。迭代加密使用一个循环结构，在该循环中重复置换(permutations)和替换(substitutions)输入数据。
该算法为比利时密码学家Joan Daemen和Vincent Rijmen所设计，结合两位作者的名字，以Rijndael之命名之，投稿高级加密标准的甄选流程。（Rijdael的发音近于 "Rhine doll"。）AES在软体及硬件上都能快速地加解密，相对来说较易于实作,且只需要很少的记忆体。作为一个新的加密标准,目前正被部署应用到更广大的范围。
2. 系统展示
图 2.1
图 2.2
3. 系统功能原理
1.
2.
3.
1.
2.
3.
3.1. 字节替换SubByte
图 3.1
3.2. 行移位ShiftRow
图 3.2
3.3. 列混合MixColumn
图 3.3
3.4. 轮密钥加AddRoundKey
图 3.4
3.5. 逆字节替换InvByteSub
通过逆S盒的映射变换得到。
3.6. 逆行移位InvShiftRow
图 3.6
3.7. 逆列混淆InvMixColumn
图 3.7
3.8. 加密流程图
图 3.8
3.9. 解密流程图
图 3.9
4. 系统程序设计
4.
4.1. 字节替换
字节代换是非线性变换，独立地对状态的每个字节进行查表代换。代换表（S盒）是可逆的，由以下两个变换合成得到：
首先，将字节看作GF（28）上的元素，映射到自己的乘法逆元。
b(x)=a(x) mod m(x)
其中m(x)=x8+x4+x3+x+1，当a(x)=0时，其逆元素也为0，即’00’映射到自己。
其次，对字节作如下的（GF（2）上的，可逆的）仿射变换，如 图 4.1 所示。
图4.1 S盒仿射变换
将从00到FF的十六进制数经过上述运算就可以得到一个16*16的字节代换表，也就是用于加密的S盒。
代码：
void SubBytes(int a[4][4],int s_box[256])/*s_box[256]是s盒*/
{
int i,j;
for (i = 0; i < 4; i++)
for (j = 0; j < 4; j++)
a[i][j] =s_box[a[i][j]];
}
4.2. 行位移
行移位是根据不同的分组长度将状态矩阵中的各行进行相应循环移位。在加密过程中，状态矩阵的后三行要按字节进行左移位。在解密过程中则要进行逆行移位，即将状态矩阵中的后三行按字节进行右移位。表3给出了在分组不同的情况下移位量，即在后三行的第1行要移位c1个字节，第2行要移位c2个字节，第3行要移位c3个字节。
代码：
void ShiftRows(int a[4][4],int decrypt)
{
int i,j,b;
if(decrypt==0)
{ /* 此时实现加密行移位功能 */
for(i=1;i<4;i++)
{
if(i==1)
{
j=a[i][0];
a[i][0]=a[i][1];
a[i][1]=a[i][2];
a[i][2]=a[i][3];
a[i][3]=j;}
if(i==2)
{
j=a[i][0];
b=a[i][1];
a[i][0]=a[i][2];
a[i][1]=a[i][3];
a[i][2]=j;
a[i][3]=b;}
if(i==3)
{
j= a[i][3];
a[i][3]=a[i][2];
a[i][2]=a[i][1];
a[i][1]=a[i][0];
a[i][0]=j;}
}
}
4.3. 列混合
在列混合变换中，将状态矩阵中的一列看作在GF（28）上的多项式，与一个常数多项式c(x)相乘并模x4+1。其中，
c(x)=’03’x3+’01’x2+’01’x+’02’（系数用十六进制表示）
c(x)是与x4+1互素的，因此模x4+1是可逆的。列混合预算也可写为矩阵乘法（图 4.3）。设b(x)=c(x)?a(x)，则
图 4.3 列混合的矩阵表示
这个运算需要做GF（28）上的乘法，代码实现如下：
int mul(int a, int b)
{
return (a != 0 && b != 0)? alog[(log[a & 0xFF] + log[b & 0xFF]) % 255]:0;
}
采用查对数表和反对数表的方法，可以简单方便的找到元素的逆元。
代码：
void MixColumns(int a[4][4],int b[4][4]) /*b[4][4]为列混合时的固定矩阵*/
{
int temp[4][4]={0};
int d[3]={0x80,0x1B,0x02};
int i,j,m,k;
for(m=0;m<4;m++)
for (i = 0; i<4;i++)
for (j = 0;j<4;j++)
{
if(b[i][j]==1)
temp[i][m]=a[j][m]^temp[i][m];
else
if(b[i][j]==2)
if(a[j][m]<d[0])
temp[i][m]=(b[i][j]*a[j][m])^temp[i][m];
else
{
k=a[j][m]^d[0];
temp[i][m]=((b[i][j]*k)^d[1])^temp[i][m];}
else
{ if(a[j][m]<d[0])
temp[i][m]=((a[j][m]*d[2])^a[j][m])^temp[i][m];
else
{
k=a[j][m]^d[0];
temp[i][m]=(((k*d[2])^d[1])^a[j][m])^temp[i][m];}}}
for(i=0;i<4;i++)
for(j=0;j<4;j++)
a[i][j]=temp[i][j];
}
4.4. 密钥加
密钥加是将轮密钥简单地与状态进行逐比特异或。轮密钥由种子密钥通过密钥编排算法得到，轮密钥长度等于分组长度Nb。
代码：
void AddRoundKey(int a[4][4],int roundKey[4][4])
{
int i,j;
for (i = 0;i < 4; i++)
for (j = 0; j < 4; j++)
a[i][j] = a[i][j] ^ roundKey[i][j];
}
4.5. 密钥扩展
扩展密钥用数组w(Nb*(Nr+1))表示，前Nk个字是种子密钥，其它的密钥字通过递归定义生成。SubByte(w)是一个返回4个字节的函数，每个字节都是它输入字中相应位置字节通过S盒作用后的结果；而函数RobByte(w)返回的是这4个字节经循环置换后的字，即将该字循环左移一个字节。扩展密钥的前Nk个字由种子密钥构成，随后的字w[i]等于字w[i-1]经一些变换后得到的字temp和字w[i-Nk]异或而成；而且对位置为Nk倍数的字变换中不仅运用了循环左移变换RotByte和子字节变换SubByte，还运用了轮常数Rcon对变换后的字temp进行异或。
对轮常数的定义为：Rocn[i]=(Rc[i],’00’,’00’,’00’);
而Rc[i]便是在有限域GF(28)中的xi-1的值，即：
Rc[1]=1(即’01’)
Rc[i]=x?(Rc[i-1])= xi-1 (即’02’?(Rc[i-1]))。
代码：
void KeyExpansion(int roundkey[4][4],int s_box[256], int temp[4][44])
{
int i,j,n,m,a,b,x,y;
int w[4],r[4],q[4];
for(i=0;i<4;i++)
for(j=0;j<4;j++)
{
temp[i][j]= roundkey[i][j];}
for(i=4;i<44;i++)
{
a=i-4;b=i-1;
if(i%4!=0)/*i不是4的倍数*/
{
for(j=0;j<4;j++)
q[j]=temp[j][a]^temp[j][b];
for(y=0;y<4;y++)
temp[y][i]=q[y];}
else
{
for(x=0;x<4;x++)
w[x]=temp[x][b];
n=w[0]; /*左移一位*/
w[0]= w[1];
w[1]= w[2];
w[2]= w[3];
w[3]=n;
for(j=0;j<4;j++)
w[j]=s_box[w[j]];/*字节替代*/
w[0]= rcon[(i-4)/4]^w[0];
for(m=0;m<4;m++)
r[m]=temp[m][a]^w[m];
for(y=0;y<4;y++)
temp[y][i]=r[y];
}
}
}
4.6. 获取RoundKey
轮密钥i（即第i个轮密钥）由轮密钥缓冲字W[Nb*i]到W[Nb*(i+1)-1]给出，如 图4.6 所示。
图 4.6
Nb=6且Nk=4时的密钥扩展与轮密钥选取
代码：
void GetRoundKey(int roundKey[4][4], int temp[4][44],int n)
{
int i,j;
for(i=0;i<4;i++)
for(j=0;j<4;j++)
roundKey[i][j]=temp[i][j+4*n];
}
4.7. 逆字节替换
与字节代替类似，逆字节代替基于逆S盒实现。
代码：
void InvSubBytes(int a[4][4],int InverS_box[256])/* InverS_box[256]是逆S盒*/
{
int i,j;
for (i = 0; i < 4; i++)
for (j = 0; j < 4; j++)
a[i][j] = InverS_box [a[i][j]];
}
4.8. 逆行位移
与行移位相反，逆行移位将态state的后三行按相反的方向进行移位操作，即第0行保持不变，第1行循环向右移一个字节，第2行循环向右移动两个字节，第3行循环向右移动三个字节。
代码：
if(decrypt==1)
{ /* 此时实现解密行移位功能 */
for(i=1;i<4;i++)
{
if(i==1)
{
j=a[i][3];
a[i][3]=a[i][2];
a[i][2]=a[i][1];
a[i][1]=a[i][0];
a[i][0]=j;}
if(i==2)
{
j=a[i][0];
b=a[i][1];
a[i][0]=a[i][2];
a[i][1]=a[i][3];
a[i][2]=j;
a[i][3]=b;}
if(i==3)
{
j=a[i][0];
a[i][0]=a[i][1];
a[i][1]=a[i][2];
a[i][2]=a[i][3];
a[i][3]=j;}
}
}
}
4.9. 逆列混合
逆列混淆的处理办法与MixColumns（）类似，每一列都通过与一个固定的多项式d(x)相乘进行交换。
代码：
void InvMixColumns(int a[4][4],int c[4][4]) /*c[4][4]为逆列混合时的固定矩阵*/
{
int temp[4][4]={0};
int d[7]={0x80,0x1B,0x02,0x0e,0x0b,0x0d,0x09};
int i,j,m,n,e,k,p,q,x,y;
for(m=0;m<4;m++)
for (i = 0; i<4;i++)
for (j = 0;j<4;j++)
{
e=a[j][m];y=a[j][m];
if(c[i][j]==d[3])
{
for(n=0;n<3;n++)
{
if(y<d[0])
y=y*d[2];
else
{
k=y^d[0];
y=(k*d[2])^d[1];}
if(n==0)
{
p=y;}
else
if(n==1)
{ q=y;}
else
{ x=y;}}
temp[i][m]=p^q^x^temp[i][m];}
if(c[i][j]==d[4])
{
for(n=0;n<3;n++)
{
if(y<d[0])
y=y*d[2];
else
{
k=y^d[0];
y=(k*d[2])^d[1];}
if(n==0)
q=y;
if(n==2)
x=y;}
temp[i][m]=e^q^x^temp[i][m];}
if(c[i][j]==d[5])
{
for(n=0;n<3;n++)
{
if(y<d[0])
y=y*d[2];
else
{
k=y^d[0];
y=(k*d[2])^d[1];}
if(n==1) {q=y;}
if(n==2) {x=y;}}
temp[i][m]=e^q^x^temp[i][m];}
if(c[i][j]==d[6])
{
for(n=0;n<3;n++)
{
if(y<d[0])
y=y*d[2];
else
{
k=y^d[0];
y=(k*d[2])^d[1];}
}
temp[i][m]=e^y^temp[i][m];}
}
for(i=0;i<4;i++)
for(j=0;j<4;j++)
a[i][j]=temp[i][j];
}
4.10. 加密
AES加密算法由初始轮密钥加和Nr轮的轮变换组成，它的输入为初始状态矩阵和轮密钥，执行加密算法后产生一个输出状态矩阵，输入明文和输出密文均为128比特。
代码：
void Encrypt(int a[4][4],int roundKey[4][4],int temp[4][44])
{
int i,j,n;
int decrypt = 0;
AddRoundKey(a,roundKey);/* 轮密钥加*/
for(n=1;n<=10;n++)
{
if(n==10)
{
SubBytes(a,s_box); /* 字节替代*/
ShiftRows(a,decrypt); /*行移位*/
GetRoundKey(roundKey,temp,n); /* 获取轮密钥*/
printf("\n");
printf("第%d轮加密密钥为：\n",n);
for(i=0;i<4;i++)
{
for(j=0;j<4;j++)
{
if(roundKey[i][j]<16)
printf("0%x ", roundKey[i][j]);
else
printf("%x ", roundKey[i][j]);}
printf("\n");}
printf("\n\n");
AddRoundKey(a,roundKey); /* 轮密钥加*/
printf("\n");
printf("第10轮加密结果为: \n");
for(i=0;i<4;i++)
{
for(j=0;j<4;j++)
{
if(a[i][j]<16)
printf("0%x ",a[i][j]);
else
printf("%x ",a[i][j]);}
printf("\n");}
printf("第10轮加密结束 \n");
printf("\n\n");
}
else
{
SubBytes(a,s_box); /* 字节替代*/
ShiftRows(a,decrypt); /*行移位*/
MixColumns(a,b); /* 列混合*/
GetRoundKey(roundKey,temp,n); /* 获取轮密钥*/
printf("\n");
printf("第%d轮加密密钥为：\n",n);
for(i=0;i<4;i++)
{
for(j=0;j<4;j++)
{
if(roundKey[i][j]<16)
printf("0%x ", roundKey[i][j]);
else
printf("%x ", roundKey[i][j]);}
printf("\n");}
printf("\n\n");
AddRoundKey(a,roundKey); /* 轮密钥加*/
printf("\n");
printf("第%d轮加密结果为: \n",n);
for(i=0;i<4;i++)
{
for(j=0;j<4;j++)
{
if(a[i][j]<16)
printf("0%x ",a[i][j]);
else
printf("%x ",a[i][j]);}
printf("\n");}
printf("第%d轮加密结束 \n",n);
printf("\n\n");
}
}
}
4.11. 解密
解密算法和加密算法类似，只是在解密算法中使用的变换为加密时相应变换的逆变换，并且在第一轮到地Nr-1轮之间逆字节替代与逆行移位，逆列混合和逆轮密钥加交换了位置。
代码：
void Decrypt(int a[4][4],int roundKey[4][4],int temp[4][44])
{
int i,j,n,m;
int decrypt = 1;
int r[10]={0,9,8,7,6,5,4,3,2,1};
m=10;
GetRoundKey(roundKey, temp,m);
AddRoundKey(a,roundKey);
for(n=1;n<=10;n++)
{
if(n==10)
{
ShiftRows(a,decrypt);
InvSubBytes(a,Invers_box);
m=0;
GetRoundKey(roundKey, temp,m);
printf("\n");
printf("第10轮解密密钥为：\n");
for(i=0;i<4;i++)
{
for(j=0;j<4;j++)
{
if(roundKey[i][j]<16)
printf("0%x ",roundKey[i][j]);
else
printf("%x ",roundKey[i][j]);}
printf("\n");}
printf("\n\n");
AddRoundKey(a,roundKey);
printf("\n");
printf("第10轮解密结果为: \n");
for(i=0;i<4;i++)
{
for(j=0;j<4;j++)
{
if(a[i][j]<16)
printf("0%x ",a[i][j]);
else
printf("%x ",a[i][j]);}
printf("\n");}
printf("第10轮解密结束\n");
printf("\n\n");}
else
{ ShiftRows(a,decrypt);
InvSubBytes(a,Invers_box);
m=r[n];
GetRoundKey(roundKey, temp,m);
printf("\n");
printf("第%d轮解密密钥为：\n",n);
for(i=0;i<4;i++)
{
for(j=0;j<4;j++)
{
if(roundKey[i][j]<16)
printf("0%x ",roundKey[i][j]);
else
printf(" %x ",roundKey[i][j]);}
printf("\n");}
printf("\n\n");
AddRoundKey(a,roundKey);
InvMixColumns(a,c);
printf("\n");
printf("第%d轮解密结果为: \n",n);
for(i=0;i<4;i++)
{
for(j=0;j<4;j++)
{
if(a[i][j]<16)
printf("0%x ",a[i][j]);
else
printf("%x ",a[i][j]);}
printf("\n");}
printf("第%d轮解密结束 \n",n);
printf("\n\n");
}
}
}
5. 总结与分析
在选择课程设计题目的时候，当看到“DES的实现与分析”这个课题的时候，我就非常想选，因为DES历史悠久，而且参考的资料也非常多。到考虑到随着时代的发展，DES被穷举破解的例子越来越多，其安全性也显得越来越不能满足我们的要求了。而AED的前景性吸引了我，AES是美国联邦政府采用的商业及政府数据加密标准，预计将在未来几十年里代替DES在各个领域中得到广泛应用。AES提供128位密钥，128位AES的加密强度是56位DES加密强度的1021倍还多。假设可以制造一部可以在1秒内破解DES密码的机器，那么使用这台机器破解一个128位AES密码需要大约149亿万年的时间。所以我选择了“AES的实现与分析”这个课题。
既然选择了这个课题，需要做的准备也是非常多的。首先要对AES实现的原理要有一个清晰的了解，通过各个方面资料的整合，AES加密数据块分组长度必须为128比特，密钥长度可以是128比特、192比特、256比特中的任意一个（如果数据块及密钥长度不足时，会补齐）。AES加密有很多轮的重复和变换。大致步骤如下：1、密钥扩展（KeyExpansion），2、初始轮（Initial Round），3、重复轮（Rounds），每一轮又包括：SubBytes、ShiftRows、MixColumns、AddRoundKey，4、最终轮（Final Round），最终轮没有MixColumns。
在这个程序中处理的AES分组大小和密钥长度都为128位，迭代轮数为10轮。加密解密系统的制作真的并不是想象中的那么简单，条理性和周密性都需要很强，程序还有很多不足之处，很多代码都是根据原理，借鉴了资料上的，有些资料上的代码其实没有太弄懂，只能说是完成了AES的最基本功能，能做一个加密解密的架构出来。我也尝试着根据自己的想法把它在细节上优化一下，但多次修改后均没有成功。
通过这次课程设计，我对AES的主要过程：SubBytes、ShiftRows、MixColumns、AddRoundKey等加密过程；InvMixColumns、InvShiftRows、InvSubBytes等解密过程有了更清晰的了解，对算法、密码保密性和安全性有了新的认识，收获很多。
在查阅资料的过程中，我看到了一则消息：AES(先进加密标准)一向被认为是牢不可破的加密算法，但世界上没有不透风的墙，来自微软和比利时鲁汶天主教大学(欧洲顶级高校)的研究人员们近日就发现了一种可以攻破AES的方法。这种新型攻击方法破解AES密钥所需的时间只有此前方法的三分之一到五分之一，而且对任何版本的AES加密算法都适用。
攻击只会越来越猛，从来不会变弱。一切的系统也不能永久的安全，所以我觉得我们在学习先进算法的同时，还要不断思考和不断创新，去发现更安全的算法。