现代密码学实验3 AES加密算法

赞赏码 & 联系方式 & 个人闲话

【实验名称】AES加密算法的实现

【实验目的】

1、详细理解AES算法的相关结构及基础理论；

2、设计AES加密和解密软件系统。

【实验原理】

AES加密过程是在一个4×4的字节矩阵上运作，这个矩阵又称为“状态（state）”，其初值就是一个明文区块（矩阵中一个元素大小就是明文区块中的一个Byte）。（Rijndael加密法因支持更大的区块，其矩阵行数可视情况增加）加密时，各轮AES加密循环（除最后一轮外）均包含4个步骤：

1、AddRoundKey — 矩阵中的每一个字节都与该次轮秘钥（round key）做XOR运算；每个子密钥由密钥生成方案产生。

2、SubBytes — 通过非线性的替换函数，用查找表的方式把每个字节替换成对应的字节。

3、ShiftRows — 将矩阵中的每个横列进行循环式移位。

4、MixColumns — 为了充分混合矩阵中各个直行的操作。这个步骤使用线性转换来混合每列的四个字节。

【实验内容】

实验内容：编程实现AES加密/解密算法。

代码：（代码解释见代码中注释）

#include<stdio.h>
//S盒
static int S[16][16] = 
{/*0*/ 0x63, 0x7c, 0x77, 0x7b, 0xf2, 0x6b, 0x6f, 0xc5, 0x30, 0x01, 0x67, 0x2b, 0xfe, 0xd7, 0xab, 0x76,
/*1*/0xca, 0x82, 0xc9, 0x7d, 0xfa, 0x59, 0x47, 0xf0, 0xad, 0xd4, 0xa2, 0xaf, 0x9c, 0xa4, 0x72, 0xc0,
/*2*/0xb7, 0xfd, 0x93, 0x26, 0x36, 0x3f, 0xf7, 0xcc, 0x34, 0xa5, 0xe5, 0xf1, 0x71, 0xd8, 0x31, 0x15,
/*3*/0x04, 0xc7, 0x23, 0xc3, 0x18, 0x96, 0x05, 0x9a, 0x07, 0x12, 0x80, 0xe2, 0xeb, 0x27, 0xb2, 0x75,
/*4*/0x09, 0x83, 0x2c, 0x1a, 0x1b, 0x6e, 0x5a, 0xa0, 0x52, 0x3b, 0xd6, 0xb3, 0x29, 0xe3, 0x2f, 0x84,
/*5*/0x53, 0xd1, 0x00, 0xed, 0x20, 0xfc, 0xb1, 0x5b, 0x6a, 0xcb, 0xbe, 0x39, 0x4a, 0x4c, 0x58, 0xcf,
/*6*/0xd0, 0xef, 0xaa, 0xfb, 0x43, 0x4d, 0x33, 0x85, 0x45, 0xf9, 0x02, 0x7f, 0x50, 0x3c, 0x9f, 0xa8,
/*7*/0x51, 0xa3, 0x40, 0x8f, 0x92, 0x9d, 0x38, 0xf5, 0xbc, 0xb6, 0xda, 0x21, 0x10, 0xff, 0xf3, 0xd2,
/*8*/0xcd, 0x0c, 0x13, 0xec, 0x5f, 0x97, 0x44, 0x17, 0xc4, 0xa7, 0x7e, 0x3d, 0x64, 0x5d, 0x19, 0x73,
/*9*/0x60, 0x81, 0x4f, 0xdc, 0x22, 0x2a, 0x90, 0x88, 0x46, 0xee, 0xb8, 0x14, 0xde, 0x5e, 0x0b, 0xdb,
/*10*/0xe0, 0x32, 0x3a, 0x0a, 0x49, 0x06, 0x24, 0x5c, 0xc2, 0xd3, 0xac, 0x62, 0x91, 0x95, 0xe4, 0x79,
/*11*/0xe7, 0xc8, 0x37, 0x6d, 0x8d, 0xd5, 0x4e, 0xa9, 0x6c, 0x56, 0xf4, 0xea, 0x65, 0x7a, 0xae, 0x08,
/*12*/0xba, 0x78, 0x25, 0x2e, 0x1c, 0xa6, 0xb4, 0xc6, 0xe8, 0xdd, 0x74, 0x1f, 0x4b, 0xbd, 0x8b, 0x8a,
/*13*/0x70, 0x3e, 0xb5, 0x66, 0x48, 0x03, 0xf6, 0x0e, 0x61, 0x35, 0x57, 0xb9, 0x86, 0xc1, 0x1d, 0x9e,
/*14*/0xe1, 0xf8, 0x98, 0x11, 0x69, 0xd9, 0x8e, 0x94, 0x9b, 0x1e, 0x87, 0xe9, 0xce, 0x55, 0x28, 0xdf,
/*15*/0x8c, 0xa1, 0x89, 0x0d, 0xbf, 0xe6, 0x42, 0x68, 0x41, 0x99, 0x2d, 0x0f, 0xb0, 0x54, 0xbb, 0x16 };

//逆S盒
static int S2[16][16];


void S_ni()
{
 int i, j;
 for (i = 0; i < 16; i++)
 {
  for (j = 0; j < 16; j++)
  {
   int temp1, temp2;
   temp1 = S[i][j] & 0xf0;
   temp1 = temp1 >> 4;
   temp2 = S[i][j] & 0x0f;
   S2[temp1][temp2] = (i << 4) + j;
  }
 }
 /*
 for (i = 0; i < 16; i++)
 {
  for (j = 0; j < 16; j++)
  {
   printf("%x ", S2[i][j]);
  }
  printf("\n");
 }
 */
}

//128bits的明文和密钥
char key[17];
char input[17];


int SubBytes(int num) 
{//单个字符替换
 int row = (num & 0xf0) >> 4;
 int col = num & 0x0f;
 return S[row][col];
}


int SubBytes_ni(int num)
{//单个字符逆替换
 int row = (num & 0xf0) >> 4;
 int col = num & 0x0f;
 return S2[row][col];
}


void translate(int *in)
{//16字符替换
 int i;
 for (i = 0; i <= 3; i++)
 {
  int t[4];
  t[0] = (in[i] & 0xff000000) >> 24;
  t[1] = (in[i] & 0xff0000) >> 16;
  t[2] = (in[i] & 0xff00) >> 8;
  t[3] = in[i] & 0xff;
  t[0] = SubBytes(t[0]) << 24;
  t[1] = SubBytes(t[1]) << 16;
  t[2] = SubBytes(t[2]) << 8;
  t[3] = SubBytes(t[3]);
  in[i] = t[0] + t[1] + t[2] + t[3];
 }
 return;
}


void translate_ni(int *in)
{//16字符逆替换
 int i;
 for (i = 0; i <= 3; i++)
 {
  int t[4];
  t[0] = (in[i] & 0xff000000) >> 24;
  t[1] = (in[i] & 0xff0000) >> 16;
  t[2] = (in[i] & 0xff00) >> 8;
  t[3] = in[i] & 0xff;
  t[0] = SubBytes_ni(t[0]) << 24;
  t[1] = SubBytes_ni(t[1]) << 16;
  t[2] = SubBytes_ni(t[2]) << 8;
  t[3] = SubBytes_ni(t[3]);
  in[i] = t[0] + t[1] + t[2] + t[3];
 }
 return;
}


int x_mul(int a, int b)
{//x乘法
 int mi;
 int i;
 int result[8];
 int R = 0;
 int number = 128;
 for (mi = 7; mi >= 0; mi--)
 {
  if ((b & number) == number)
  {
   result[mi] = a;
   for (i = mi; i >= 1; i--)
   {
    if ((result[mi] & 128) == 128)
    {
     result[mi] = result[mi] << 1;
     result[mi] = result[mi] ^ 27;
    }
    else
    {
     result[mi] = result[mi] << 1;
    }
   }
  }
  else
  {
   result[mi] = 0;
  }
  number = number / 2;
 }
 //异或
 for (i = 0; i <= 7; i++)
 {
  R = R ^ result[i];
 }
 //int为4字节，此处置前三字节为0，避免之前左移的影响
 R = R & 0xff;
 return R;
}


void lineshift(int *in)
{//行移位
 int temp[16];
 int i;
 for (i = 0; i <= 3; i++)
 {
  temp[4 * i + 0] = (in[i] & 0xff000000);
  temp[4 * i + 1] = (in[i] & 0xff0000);
  temp[4 * i + 2] = (in[i] & 0xff00);
  temp[4 * i + 3] = in[i] & 0xff;
 }
 in[0] = temp[0] + temp[5] + temp[10] + temp[15];
 in[1] = temp[4] + temp[9] + temp[14] + temp[3];
 in[2] = temp[8] + temp[13] + temp[2] + temp[7];
 in[3] = temp[12] + temp[1] + temp[6] + temp[11];
}


void lineshift_ni(int *in)
{//逆行移位
 int temp[16];
 int i;
 for (i = 0; i <= 3; i++)
 {
  temp[4 * i + 0] = (in[i] & 0xff000000);
  temp[4 * i + 1] = (in[i] & 0xff0000);
  temp[4 * i + 2] = (in[i] & 0xff00);
  temp[4 * i + 3] = in[i] & 0xff;
 }
 in[0] = temp[0] + temp[13] + temp[10] + temp[7];
 in[1] = temp[4] + temp[1] + temp[14] + temp[11];
 in[2] = temp[8] + temp[5] + temp[2] + temp[15];
 in[3] = temp[12] + temp[9] + temp[6] + temp[3];
}


void mixcolumn(int *in)
{//列混合
 int temp[4][4];
 int s[4][4];
 int i;
 for (i = 0; i <= 3; i++)
 {
  temp[0][i] = (in[i] & 0xff000000) >> 24;
  temp[1][i] = (in[i] & 0xff0000) >> 16;
  temp[2][i] = (in[i] & 0xff00) >> 8;
  temp[3][i] = in[i] & 0xff;
 }
 
 for (i = 0; i <= 3; i++)
 {
  s[0][i] = (x_mul(temp[0][i], 2)) ^ (x_mul(temp[1][i], 3)) ^ temp[2][i] ^ temp[3][i];
  s[1][i] = temp[0][i] ^ (x_mul(temp[1][i], 2)) ^ (x_mul(temp[2][i], 3)) ^ temp[3][i];
  s[2][i] = temp[0][i] ^ temp[1][i] ^ (x_mul(temp[2][i], 2)) ^ (x_mul(temp[3][i], 3));
  s[3][i] = (x_mul(temp[0][i], 3)) ^ temp[1][i] ^ temp[2][i] ^ (x_mul(temp[3][i], 2));
 }

 in[0] = (s[0][0] << 24) + (s[1][0] << 16) + (s[2][0] << 8) + s[3][0];
 in[1] = (s[0][1] << 24) + (s[1][1] << 16) + (s[2][1] << 8) + s[3][1];
 in[2] = (s[0][2] << 24) + (s[1][2] << 16) + (s[2][2] << 8) + s[3][2];
 in[3] = (s[0][3] << 24) + (s[1][3] << 16) + (s[2][3] << 8) + s[3][3];

 return;

}


void mixcolumn_ni(int *in)
{//逆列混合
 int temp[4][4];
 int s[4][4];
 int i;
 for (i = 0; i <= 3; i++)
 {
  temp[0][i] = (in[i] & 0xff000000) >> 24;
  temp[1][i] = (in[i] & 0xff0000) >> 16;
  temp[2][i] = (in[i] & 0xff00) >> 8;
  temp[3][i] = in[i] & 0xff;
 }

 for (i = 0; i <= 3; i++)
 {
  s[0][i] = (x_mul(temp[0][i], 0xe)) ^ (x_mul(temp[1][i], 0xb)) ^ (x_mul(temp[2][i], 0xd)) ^ (x_mul(temp[3][i], 0x9));
  s[1][i] = (x_mul(temp[0][i], 0x9)) ^ (x_mul(temp[1][i], 0xe)) ^ (x_mul(temp[2][i], 0xb)) ^ (x_mul(temp[3][i], 0xd));
  s[2][i] = (x_mul(temp[0][i], 0xd)) ^ (x_mul(temp[1][i], 0x9)) ^ (x_mul(temp[2][i], 0xe)) ^ (x_mul(temp[3][i], 0xb));
  s[3][i] = (x_mul(temp[0][i], 0xb)) ^ (x_mul(temp[1][i], 0xd)) ^ (x_mul(temp[2][i], 0x9)) ^ (x_mul(temp[3][i], 0xe));
 }

 in[0] = (s[0][0] << 24) + (s[1][0] << 16) + (s[2][0] << 8) + s[3][0];
 in[1] = (s[0][1] << 24) + (s[1][1] << 16) + (s[2][1] << 8) + s[3][1];
 in[2] = (s[0][2] << 24) + (s[1][2] << 16) + (s[2][2] << 8) + s[3][2];
 in[3] = (s[0][3] << 24) + (s[1][3] << 16) + (s[2][3] << 8) + s[3][3];

 return;

}



void extendkey(int *w)
{//扩展密钥
 //W[0]~W[3]的初始化
 int result[4];
 int i;
 for (i = 0; i <= 3; i++)
 {
  result[0] = (int)key[i * 4 + 0] & 0xff;
  result[1] = (int)key[i * 4 + 1] & 0xff;
  result[2] = (int)key[i * 4 + 2] & 0xff;
  result[3] = (int)key[i * 4 + 3] & 0xff;
  w[i] = (result[0] << 24) + (result[1] << 16) + (result[2] << 8) + result[3];
 }
 //扩展密钥
 for (int i = 4, j = 0; i < 44; i++) 
 {
  int Rcon[10] = {/*0*/ 0x01000000, 0x02000000,
   /*1*/0x04000000, 0x08000000,
   /*2*/0x10000000, 0x20000000,
   /*3*/0x40000000, 0x80000000,
   /*4*/0x1b000000, 0x36000000 };
  if (i % 4 == 0)
  {
   int temp = w[i - 1];
   //循环左移
   int temp1 = (temp & 0xff000000) >> 24;
   temp = temp << 8;
   temp = temp + temp1;
   //字节替代
   int t[4];
   t[0] = (temp & 0xff000000) >> 24;
   t[1] = (temp & 0xff0000) >> 16;
   t[2] = (temp & 0xff00) >> 8;
   t[3] = temp & 0xff;
   t[0] = SubBytes(t[0]); t[1] = SubBytes(t[1]);
   t[2] = SubBytes(t[2]); t[3] = SubBytes(t[3]);
   temp = (t[0] << 24) + (t[1] << 16) + (t[2] << 8) + t[3];
   //与轮常量rc[n]相加
   temp = temp ^ Rcon[j];
   //异或
   w[i] = w[i - 4] ^ temp;
   j++;//下一轮
  }
  else
  {
   w[i] = w[i - 4] ^ w[i - 1];
  }
 }
}


void addround(int *w, int *in, int i)
{//轮密钥加
 in[0] = in[0] ^ w[i];
 in[1] = in[1] ^ w[i + 1];
 in[2] = in[2] ^ w[i + 2];
 in[3] = in[3] ^ w[i + 3];
 return;
}



void beginin(int *in)
{//输入的字符串转化为矩阵
 int result[4];
 int i;
 for (i = 0; i <= 3; i++)
 {
  result[0] = (int)input[i * 4 + 0] & 0xff;
  result[1] = (int)input[i * 4 + 1] & 0xff;
  result[2] = (int)input[i * 4 + 2] & 0xff;
  result[3] = (int)input[i * 4 + 3] & 0xff;
  in[i] = (result[0] << 24) + (result[1] << 16) + (result[2] << 8) + result[3];
 }
}

int main()
{
 S_ni();
 //freopen("in.txt", "r", stdin);
 printf("请输入16个字符的待加密的明文：\n");
 scanf("%s", input);
 printf("请输入16个字符的密钥：\n");
 scanf("%s", key);

 int w[44];
 int in[4];

 printf("\n\n**************  加密中  ***************\n\n\n");
 //AES加密
 int i;
 extendkey(w);
 beginin(in);
 addround(w, in, 0);
 for (i = 1; i < 10; i++) 
 {//1-9轮

  translate(in);//字节代换
  lineshift(in);//行移位
  mixcolumn(in);//列混合
  addround(w, in, 4 * i);//轮密钥加

 }
 //第10轮
 translate(in);//字节代换
 lineshift(in);//行移位
 addround(w, in, 40);//轮密钥加

 //输出密文信息

 printf("...... AES加密后的密文的ASCCI码为 ......\n\n");
 for (i = 0; i <= 3; i++)
 {
  int t[4];
  t[0] = (in[i] & 0xff000000) >> 24;
  t[1] = (in[i] & 0xff0000) >> 16;
  t[2] = (in[i] & 0xff00) >> 8;
  t[3] = in[i] & 0xff;
  printf("0x%2x 0x%2x 0x%2x 0x%2x ", t[0], t[1], t[2], t[3]);
  if (i == 1)printf("\n");
 }
 printf("\n........................................\n\n");
 printf(".......... AES加密后的密文为 ...........\n\n");
 for (i = 0; i <= 3; i++)
 {
  int t[4];
  t[0] = (in[i] & 0xff000000) >> 24;
  t[1] = (in[i] & 0xff0000) >> 16;
  t[2] = (in[i] & 0xff00) >> 8;
  t[3] = in[i] & 0xff;
  printf("%c%c%c%c", t[0], t[1], t[2], t[3]);
 }
 printf("\n........................................\n");

 printf("\n\n\n**************  解密中  ***************\n\n");

 //AES解密
 addround(w, in, 40);//轮密钥加
 //1-9轮
 for (i = 9; i >= 1; i--)
 {
  lineshift_ni(in);//逆行移位
  translate_ni(in);//逆字节代换
  addround(w, in, 4 * i);//轮密钥加
  mixcolumn_ni(in);//逆列混合
 }
 //第10轮
 lineshift_ni(in);//逆行移位
 translate_ni(in);//逆字节代换
 addround(w, in, 0);//轮密钥加
 
 
 //输出解密后明文信息
 printf("\n\n...... AES解密后的明文的ASCCI码为 ......\n\n");
 for (i = 0; i <= 3; i++)
 {
  int t[4];
  t[0] = (in[i] & 0xff000000) >> 24;
  t[1] = (in[i] & 0xff0000) >> 16;
  t[2] = (in[i] & 0xff00) >> 8;
  t[3] = in[i] & 0xff;
  printf("0x%2x 0x%2x 0x%2x 0x%2x ", t[0], t[1], t[2], t[3]);
  if (i == 1)printf("\n");
 }
 printf("\n........................................\n\n");
 printf(".......... AES解密后的明文为 ...........\n\n");
 for (i = 0; i <= 3; i++)
 {
  int t[4];
  t[0] = (in[i] & 0xff000000) >> 24;
  t[1] = (in[i] & 0xff0000) >> 16;
  t[2] = (in[i] & 0xff00) >> 8;
  t[3] = in[i] & 0xff;
  printf("%c%c%c%c", t[0], t[1], t[2], t[3]);
 }
 printf("\n........................................\n\n");

 return 0;
}

运行演示：

英文加密解密：

中文加密解密：

【小结和讨论】

AES算法是高级加密标准，是一种对称密码，但是这一次的对称密码比以往的实验都要复杂的多。我在这一次实验上也花了很多的时间。

AES算法主要由四个不同的变换组成，包括一个置换和三个替代：字节代替，用一个S盒完成分组的字节到字节的代替；行移位，一个比较简单的置换；列混淆，利用域GF(28)上的算术特性的一个代替；轮密钥加，当前分组和扩展密钥的一部分进行按位XOR(异或)。

我觉得这次实验最难的一个功能模块是列混淆。因为首先列混淆的乘法不是一般的乘法，而是x乘法，即GF（2^8）上的乘法。其次这个模块涉及到矩阵运算，我们知道矩阵运算是比较复杂，比较麻烦的。好在本次实验矩阵的大小是4*4固定的，而且课程PPT中还给出了推导后的矩阵计算公式，使得我们不必要真的去写一个x乘法矩阵运算，只需要套用一堆固定的公式，这带来了一定程度上的方便，这里我写了x_mul、mixcolumn两个函数来实现此功能，其中还要注意矩阵行、列计算的转换，所以还是很复杂的，很考验逻辑思维能力。

还有一个难点就是密钥扩展，所以我借此弄清楚了这其中的原理。把每轮的密钥看成四个w[i]，这一轮的第一个w[i]总是最难生成的。我们首先第n-1组第3列的4个字节循环左移1个字节；再对每个字节进行字节替代变换；再与轮常量rc[n]相加；最后再与前一组该列相加。这里比较弯弯绕绕的，一不小心就会搞糊涂。

这次实验很复杂、比较费时间，我前前后后花了差不多整整一天的时间才完成所有代码的编写和调试，一共写了400多行代码。经过这次实验，感觉自己对AES算法的理解、对字符字节的控制、对整体代码的debug上都有所进步，收获良多。