C：AES加密解密算法

一开学就猝不及防来了个密码学算法程序设计。。。仿佛又回到上学期末被密码学支配的恐惧，最早五月的一科考试，全寝室就我一人考密码学啊喂喂喂。
行8终于码完了AES，猪命要紧， 在 也 不 熬 夜 了 ！！

AES算法原理简单介绍

AES算法中，初始状态矩阵由为128bits明文分组构成，以字节为单位，则总共有16bytes。
AES的基本运算单位是字节（Byte），加密和解密过程都是在一个4*4的字节矩阵上运作，这个矩阵又称为“体（state）”或者“状态”。字节矩阵初始值是一个明文块（块/分组，block）。

加密和解密过程都需要进行密钥扩展：Rijndael算法的密钥同样以字节为单位进行变换，用一个4行的二维矩阵来表示。密钥按照矩阵的列进行分组，密钥比特的总数等于明文分组长度乘以轮数加1。

AES加密算法

字节代替

字节代替（SubBytes）：通过一个非线性的替换函数，用查找S盒表的方式把每个字节替换成对应的字节。S盒是一个16*16的矩阵。

行移位

行移位（ShiftRows）：将矩阵中的每行以字节为单位进行循环左移位。每一行循环左移的偏移量由明文分组的大小和所在行数共同决定。

列混合

列混合（MixColumns）：为了充分混合矩阵中各个直行的操作。这个步骤使用线性转换来混合每行内的四个字节。将输入的状态矩阵的每列与一固定的多项式在有限域GF（2^8）上的相乘，然后模多项式x^4+1。

轮密钥加

轮密钥加（AddRoundKey）：将列混合的输出状态矩阵中的每一个字节都与该次循环的子密钥做异或逻辑运算。

AES解密算法

逆行移位

逆行移位（InvShifrRows）：将矩阵中的每行以字节为单位进行循环右移位。

逆字节替代

逆字节替代（InvSubBytes）：与加密过程的字节替代相似，将输入的状态矩阵的每一个字节通过查表操作替换为表中对应字节，只是查表操作变为查逆S盒。

逆列混合

逆列混合（InMixColumns）：使用另一个常数矩阵乘以矩阵state得到新的state矩阵。

轮密钥加

轮密钥加（AddRoundKey）：矩阵中的每一个字节都与该次循环的子密钥做异或逻辑运算。

核心模块的函数说明和实现方式

密钥扩展

使用二维无符号字符数组k[44][4]来存放每一轮的轮密钥，每一轮轮密钥为128bit。

当k的行数i不是4的倍数时，Ki=Ki-4⊕Ki-1；当k的行数i是4的倍数时，Ki=Ki-4⊕T（Ki-1）。T（）函数的运算方法如下：
（1）将Ki-1列以字节为单位循环左移1字节；
（2）将循环左移之后的输出进性字节代替；
（3）根据Rocn常量表得到Rcon[i/Nk]值；
（4）将步骤2与步骤3的结果异或。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

void extendKey(){
	while(1){
		if( kNum%4 != 0){
			for(j=0; j<4; j++{
				k[kNum][j] = k[kNum-4][j] ^ k[kNum-1][j];
				}
		}else{for(j=0; j<3; j++){//左移动1字节
				tmp[j] = k[kNum-1][j+1];}
			tmp[j] = k[kNum-1][0];	//0->4
			//字节代替
			for(j=0; j<4; j++){
					left = tmp[j] >> 4;
				right = tmp[j] << 4;
				right = right >> 4;
				tmp[j] = Sbox[left][right];
				}
			rc = Rcon[ kNum/4];
			tmp[0] = tmp[0] ^ rc;
			for(j=0; j<4; j++){
				k[kNum][j] = k[kNum-4][j] ^ tmp[j];
				}
			}
		kNum++;
		if(kNum %4 == 0){
			return ;
			}
		}

字节替代

由于定义的数组为4*4矩阵，所以需要取出数组中值的左4个bit作为S盒的列输入，右4个bit作为S盒的行输入。使用C语言中的左移运算符<<及右移运算符>>来获取4bit的值。

1
2
3
4
5
6
7
8
for(i=0; i<4; i++){
	for(j=0; j<4; j++){	
		right = k[(roundNum-1)*4+i][j] >> 4;
		left = k[(roundNum-1)*4+i][j] << 4;
		left = left >> 4;
		resOfSub[i][j] = Sbox[left][right]; 
		}
	}

行移位

第i行循环左移i-1列，shiftnum标记左移列数，resOfSub为前一次字节代替的结果，resOfRows为本次行移位的输出结果。逆行移中，第i行循环右移动i-1列，可看作循环左移4-i列。
这个一开始绕了好久写不出来。。。后来哎嘛不就是两个循环么。。。内层循环是每次左移1位，外层循环是将内层执行i-1次。i=1，2，3，4（行）。每行只需要使用一次tmp存第一个元素，然后执行循环左移1bit，移动完成后再将tmp放入最后一个位置。
加密：

1
2
3
4
5
6
7
shiftnum=0;
	for(i=0; i<4; i++){
		for(j=0; j<4; j++){
			resOfRows[j][i] = resOfSub[(shiftnum+j)%4][i];
			}
		shiftnum++;
		}

解密：
1
2
3
4
5
6
7
shiftnum=4;
	for(i=0; i<4; i++){
		for(j=0; j<4; j++){
				resOfRows[j][i] = resOfKey[(shiftnum+j)%4][i];
				}
			shiftnum--;
		}

列混合

列混合是输入矩阵的每列与固定矩阵每行相乘，元素做域上乘法。由于固定矩阵每一行的元素0x02、0x03、0x01、0x01不变，仅顺序改变，Ki行元素为Ki-1行元素循环右移1列得到，故在进行每一行的运算的时候，没有引入矩阵数组，直接将固定矩阵的元素循环使用。
例如，（i，j）为输入矩阵第i行每个元素乘以固定矩阵的第j列每个元素，（i，j+1）为输入矩阵第j行乘以第j+1列。而固定矩阵的j+1列为j列循环移动1位得到，即可直接将0x02、0x03、0x01、0x01移动一位，再乘以输入矩阵i行。
原本是将输入矩阵与固定矩阵都定义为4*4二维数组来进行运算，但不晓得为啥运算结果老是出错。意识到固定矩阵每行的元素是由上一行循环右移1位得到，所以其实可以不需要列出固定矩阵二维数组。比如在计算第一行的输出结果时，是由矩阵A第一行的每个元素分别与矩阵B第一、二、三、四列每个元素运算得到（1，1）、（1，2）、（1，3）、（1，4），由于固定矩阵的每列元素相同，只是顺序移动1位，（2311->1231->1123->3112），我们可以取第一行值2311作为固定，与输入矩阵的某行做运算时候，输入矩阵的行按照每次移动1位的顺序与2311做运算。
加密：

1
2
3
4
5
for(i=0; i<4; i++){
	for(j=0; j<4; j++){
		resOfCols[i][j] = GF02(resOfRows[i][j%4]) ^ GF03(resOfRows[i][(j+1)%4]) ^ GF01(resOfRows[i][(j+2)%4]) ^ GF01(resOfRows[i][(j+3)%4]);
		}	
	}

解密：
1
2
3
4
5
for(i=0; i<4; i++){
	for(j=0; j<4; j++){
		resOfCols[i][j] = GF0E(resOfKey[i][j%4]) ^ GF0B(resOfKey[i][(j+1)%4]) ^ GF0D(resOfKey[i][(j+2)%4]) ^ GF09(resOfKey[i][(j+3)%4]);
		}
	}

轮密钥加

将输入与当轮轮密钥左异或运算。
加密：

1
2
3
4
5
for(i=0; i<4; i++){
	for(j=0; j<4; j++){
		resOfKey[i][j] = k[kNum-4+i][j] ^ resOfRows[i][j];
		}
	}

解密：
1
2
3
4
5
for(i=0; i<4; i++){
	for(j=0; j<4; j++){
		resOfKey[i][j] = k[44-(roundNum+1)*4+i][j] ^ resOfSub[i][j];
		}
	}

域上乘法

写了多个子函数层层调用，但是最终都是调用GF02函数，即域上乘以0x02的算法。当判断b7为0或者1的时候，思考了三种算法：（1）比较b与0x08的大小，若b>=0x80，则b7=1；反之，得b7=0。（2）判断b&0x08是否为0，若为0，则b7=0；反之，得b7=1。（3）使用移位符，b>>7，将b右移7个bit，若 b>> == 0x01，则b7=1；反之，得b7=0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
unsigned char GF01(unsigned char b){
	return b ;
	}
unsigned char GF02(unsigned char b){
	if (b & 0x80){
		return (b<<1);//&0xff; 
		}else{
		return ((b<<1)^0x1b);//&0xff; 
		}
	}
unsigned char GF03(unsigned char b){
	return  b ^ GF02(b);
	}
unsigned char GF04(unsigned char b){
	return GF02( GF02(b) );
	}
unsigned char GF08(unsigned char b){
	return GF04( GF02(b) );
	}
unsigned char GF09(unsigned char b){
	return b ^ GF08(b);
	}
unsigned char GF0B(unsigned char b){
	return GF03(b) ^ GF08(b);
	}
unsigned char GF0D(unsigned char b){
	return GF04(b) ^ GF08(b) ^ GF01(b);
	}
unsigned char GF0E(unsigned char b){
	return GF04(b) ^ GF08(b) ^ GF02(b);
	}

将数据写入txt文件

由于输入数据时候，每次输入二维数组[4][4]的一个字节，比如0xab、0x0a，而当值小于等于0x0f时候，左4bit的0并不会被存入文件，将导致数据不全，不足32个十六进制数。而从文件读取数据的时候，使用fgets函数将一行数据取出放入数组，使用一个临时数组[32]来存放每1个十六进制数的值，最后在将左4bit与后4bit整合为一个byte放入[4][4]二维矩阵。 但若存入txt的时候，没有将0存放进去，读取文件内容的时候就会读取错误，无法判断缺少的0x00的位置。所以在写数据到txt文件的时候，添加一个判断条件，若值<=0x0f，则向txt文件写入一个0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void write(){
	FILE *fp;//定义文件指针
	fp=fopen("aes.txt","a");
	if(fp==NULL){ //判断指针是否为空，安全检查
		printf("error");
		return ;
		}
	fprintf(fp,"%s",a);	
	for(i=0;i<4;i++){
		for(j=0;j<4;j++){	
			if(plaintext[i][j] <= 0x0f){
				fprintf(fp,"0");}
			fprintf(fp,"%x",plaintext[i][j]); 
			}
		}
	fprintf(fp,"%s",b);
	for(i=0;i<4;i++){
		for(j=0;j<4;j++){
			if(resOfKey[i][j] <= 0x0f){
				fprintf(fp,"0");			
				}
			fprintf(fp,"%x",resOfKey[i][j]); 
			}
		}
	fclose(fp);//关闭文件
//	fp=NULL;//置空指针，否则指向打开原文件的地址

从txt文件读取数据

使用fgets函数将txt内容一行一行的读取打印，并将第一组密文与密钥存入数组，做AES解密测试。由于从txt读取的数值是ASCII码，所以还需要将ASCII码转换为十进制数字。读取密文的时候每次只能将一个字符存入数组，这一个字符仅代表4bit、一个十六进制数。转换成4*4矩阵，将存放了32个十六进制数的数组[32]中，若i%2==0，第i个数字左移4bit，再执行tmp[i]^tmp[i+1]，即将2个4bit存放到同一个1byte空间中。
C语言中，一个中文占2byte，txt文件中固定格式“密文：0x”,所以当取出当前行字符串时，s[0]-s[7]为格式内容，s[8]开始为密文数据，故定义n=8，从第8个数据开始存入密文数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
void read(){
		FILE *rfp;
	rfp=fopen("aes.txt","r");
	if(rfp==NULL){
		printf("error\n");
		return ;
		}
	while (fgets(line, sizeof(line), rfp)) { 
		//fgets逐行读取文件，到达文件尾终止while循环
		sscanf(line, "%s", str);
		printf("%s\n", str); //打印，测试结果
		if( i == 2){
			n=8;
			printf("密文0x：");
			for( j=0; j<4; j++){
				for(k=0; k<8; k++){
					if( str[n] >=48 && str[n] <=57 ){
						tmpcipher[j][k] = (unsigned char)str[n++]-48;
					}else	{
					tmpcipher[j][k] = (unsigned char)str[n++]-97+10;
					}
					printf("%x",ciphertext[j][k] );
					}
				}
				i++;
				}
	for(i=0; i<4; i++){
		for(j=0; j<4; j++){
			right = tmpcipher[i][j*2] << 4;
			ciphertext[i][j] = right ^ tmpcipher[i][j*2+1];
			}
		}
	fclose(rfp);rfp=NULL;
	}