密码学：AES的实现与分析-课程设计

背景说明密码学中的高级加密标准（AdvancedEncryptionStandard，AES），又称高级加密标准Rijndael加密法，是美国联邦政府采用的一种区块加密标准。这个标准用来替代原先的DES，已经被多方分析且广为全世界所使用。经过五年的甄选流程，高级加密标准由美国国家标准与技术研究院（NIST）于2001年11月26日发布于FIPSPUB197，并在2002年5月26日成为有效的标准。2006年，高级加密标准已然成为对称密钥加密中最流行的算法之一。美国美国国家标准与技术研究院(NIST)于2001年引入了AES加密算法，取代老旧的DES(数字加密标准)，后者当时应用非常广泛，但屡屡被证明已变得相当脆弱。AES现在广泛用于金融财务、在线交易、无线通信、数字存储等领域，经受了最严格的考验。AES提供128位密钥，因此，128位AES的加密强度是56位DES加密强度的1021倍还多。假设可以制造一部可以在1秒内破解DES密码的机器，那么使用这台机器破解一个128位AES密码需要大约149亿万年的时间。AES有一个固定的128位的块大小和128，192或256位大小的密钥大小，并且用128位(16字节)分组加密和解密数据。与公共密钥密码使用密钥对不同，对称密钥密码使用相同的密钥加密和解密数据。通过分组密码返回的加密数据的位数与输入数据相同。迭代加密使用一个循环结构，在该循环中重复置换(permutations)和替换(substitutions)输入数据。该算法为比利时密码学家JoanDaemen和VincentRijmen所设计，结合两位作者的名字，以Rijndael之命名之，投稿高级加密标准的甄选流程。（Rijdael的发音近于"Rhinedoll"。）AES在软体及硬件上都能快速地加解密，相对来说较易于实作,且只需要很少的记忆体。作为一个新的加密标准,目前正被部署应用到更广大的范围。

系统展示图2.1图2.2系统功能原理字节替换SubByte图3.1行移位ShiftRow图3.2列混合MixColumn图3.3轮密钥加AddRoundKey图3.4逆字节替换InvByteSub通过逆S盒的映射变换得到。逆行移位InvShiftRow图3.6逆列混淆InvMixColumn图3.7加密流程图图3.8解密流程图图3.9系统程序设计字节替换字节代换是非线性变换，独立地对状态的每个字节进行查表代换。代换表（S盒）是可逆的，由以下两个变换合成得到：首先，将字节看作GF（28）上的元素，映射到自己的乘法逆元。b(x)=a(x)modm(x)其中m(x)=x8+x4+x3+x+1，当a(x)=0时，其逆元素也为0，即’00’映射到自己。其次，对字节作如下的（GF（2）上的，可逆的）仿射变换，如图4.1所示。图4.1S盒仿射变换将从00到FF的十六进制数经过上述运算就可以得到一个16*16的字节代换表，也就是用于加密的S盒。代码：voidSubBytes(inta[4][4],ints_box[256])/*s_box[256]是s盒*/{ inti,j; for(i=0;i<4;i++) for(j=0;j<4;j++) a[i][j]=s_box[a[i][j]];}行位移行移位是根据不同的分组长度将状态矩阵中的各行进行相应循环移位。在加密过程中，状态矩阵的后三行要按字节进行左移位。在解密过程中则要进行逆行移位，即将状态矩阵中的后三行按字节进行右移位。表3给出了在分组不同的情况下移位量，即在后三行的第1行要移位c1个字节，第2行要移位c2个字节，第3行要移位c3个字节。代码：voidShiftRows(inta[4][4],intdecrypt){ inti,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;} } }列混合在列混合变换中，将状态矩阵中的一列看作在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）上的乘法，代码实现如下：intmul(inta,intb) { return(a!=0&&b!=0)?alog[(log[a&0xFF]+log[b&0xFF])%255]:0; }采用查对数表和反对数表的方法，可以简单方便的找到元素的逆元。代码：voidMixColumns(inta[4][4],intb[4][4])/*b[4][4]为列混合时的固定矩阵*/{ inttemp[4][4]={0}; intd[3]={0x80,0x1B,0x02}; inti,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];}密钥加密钥加是将轮密钥简单地与状态进行逐比特异或。轮密钥由种子密钥通过密钥编排算法得到，轮密钥长度等于分组长度Nb。代码：voidAddRoundKey(inta[4][4],introundKey[4][4]){ inti,j; for(i=0;i<4;i++) for(j=0;j<4;j++) a[i][j]=a[i][j]^roundKey[i][j];}密钥扩展扩展密钥用数组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]))。代码：voidKeyExpansion(introundkey[4][4],ints_box[256],inttemp[4][44]){ inti,j,n,m,a,b,x,y; intw[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]; } }}获取RoundKey轮密钥i（即第i个轮密钥）由轮密钥缓冲字W[Nb*i]到W[Nb*(i+1)-1]给出，如图4.6所示。W0W1W2W3W4W5W6W7W8W9W10W11W12W13W14…轮密钥0轮密钥1……图4.6Nb=6且Nk=4时的密钥扩展与轮密钥选取代码：voidGetRoundKey(introundKey[4][4],inttemp[4][44],intn){ inti,j; for(i=0;i<4;i++) for(j=0;j<4;j++) roundKey[i][j]=temp[i][j+4*n];}逆字节替换与字节代替类似，逆字节代替基于逆S盒实现。代码：voidInvSubBytes(inta[4][4],intInverS_box[256])/*InverS_box[256]是逆S盒*/{ inti,j; for(i=0;i<4;i++) for(j=0;j<4;j++) a[i][j]=InverS_box[a[i][j]];}逆行位移与行移位相反，逆行移位将态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;} } }}逆列混合逆列混淆的处理办法与MixColumns（）类似，每一列都通过与一个固定的多项式d(x)相乘进行交换。代码：voidInvMixColumns(inta[4][4],intc[4][4])/*c[4][4]为逆列混合时的固定矩阵*/{ inttemp[4][4]={0}; intd[7]={0x80,0x1B,0x02,0x0e,0x0b,0x0d,0x09}; inti,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];}加密AES加密算法由初始轮密钥加和Nr轮的轮变换组成，它的输入为初始状态矩阵和轮密钥，执行加密算法后产生一个输出状态矩阵，输入明文和输出密文均为128比特。代码：voidEncrypt(inta[4][4],introundKey[4][4],inttemp[4][44]){ inti,j,n; intdecrypt=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"); } }}解密解密算法和加密算法类似，只是在解密算法中使用的变换为加密时相应变换的逆变换，并且在第一轮到地Nr-1轮之间逆字节替代与逆行移位，逆列混合和逆轮密钥加交换了位置。代码：voidDecrypt(inta[4][4],introundKey[4][4],inttemp[4][44]){ inti,j,n,m; intdecrypt=1; intr[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"); } }}总结与分析在选择课程设计题目的时候，当看到“DES的实现与分析”这个课题的时候，我就非常想选，因为DES历史悠久，而且参考的资料也非常多。到考虑到随着时代的发展，DES被穷举破解的