密码学学习笔记（三）——AES的查表加速

文章目录S盒生成T表生成主要函数高级加密标准（Advanced Encryption Standard，AES），又称Rijndael加密法，是美国联邦政府采用的一种分组加密标准。若按算法描述进行加解密运算，就会出现计算量大、耗时长之类的问题，为解决这个问题，我们将一些复杂的过程通过查表运算代替，这样就可以通过增加存储复杂度来减少时间复杂度，从而达到在时间程度上优化算法的目的。在AES算法中，整个

梓丶城

5044人浏览 · 2021-07-13 16:25:03

梓丶城 · 2021-07-13 16:25:03 发布

文章目录

S盒生成
T表生成
主要函数

高级加密标准（Advanced Encryption Standard，AES），又称Rijndael加密法，是美国联邦政府采用的一种分组加密标准。若按算法描述进行加解密运算，就会出现计算量大、耗时长之类的问题，为解决这个问题，我们将一些复杂的过程通过查表运算代替，这样就可以通过增加存储复杂度来减少时间复杂度，从而达到在时间程度上优化算法的目的。
在AES算法中，整个加解密的过程可以归纳为字节替代（SubBytes）、行移位（ShiftRows）、列混合（MixColumns）和轮密钥加（AddRoundKey）这四种变换，如图：

在这里插入图片描述
其中，字节代替和列混合都可以通过查表的方式实现。

S盒生成

根据资料，AES的S盒的通过下式生成的：
在这里插入图片描述
而b₀到b₇则是原位置通过有限域GF(2⁸)上的求逆运算得到的结果（如果想深入了解，可以学习近世代数），由于数据量较小，我们就不使用欧几里得算法求逆，而是直接利用域上逆元的定义进行求解，所以这里先定义GF(2⁸)上的乘法运算：

word_8 mul(word_8 a,word_8 b)
{
	word_8 data[8],dat;
	data[0] = a;
	data[1] = data[0] << 1;
	if((data[0] & 0x80) == 0x80) data[1] ^= 0x1b;
	data[2] = data[1] << 1;
	if((data[1] & 0x80) == 0x80) data[2] ^= 0x1b;
	data[3] = data[2] << 1;
	if((data[2] & 0x80) == 0x80) data[3] ^= 0x1b;
	data[4] = data[3] << 1;
	if((data[3] & 0x80) == 0x80) data[4] ^= 0x1b;
	data[5] = data[4] << 1;
	if((data[4] & 0x80) == 0x80) data[5] ^= 0x1b;
	data[6] = data[5] << 1;
	if((data[5] & 0x80) == 0x80) data[6] ^= 0x1b;
	data[7] = data[6] << 1;
	if((data[6] & 0x80) == 0x80) data[7] ^= 0x1b;
	
	dat = 0x00;
	if((b & 0x01) == 0x01) dat ^= data[0];
	if((b & 0x02) == 0x02) dat ^= data[1];
	if((b & 0x04) == 0x04) dat ^= data[2];
	if((b & 0x08) == 0x08) dat ^= data[3];
	if((b & 0x10) == 0x10) dat ^= data[4];
	if((b & 0x20) == 0x20) dat ^= data[5];
	if((b & 0x40) == 0x40) dat ^= data[6];
	if((b & 0x80) == 0x80) dat ^= data[7];
	
	return dat;
}

接着就是通过遍历求逆元的运算：

word_8 tr(word_8 a)
{
	word_8 i;
	if(a == 0x00)
		return 0x00;
	else
		for(i = 0x01;i <= 0xff && i != 0x00;i++)
			if(mul(a,i) == 0x01)
				return i;
}

然后是主程序，这里我们将S盒生成到文件S.txt中：

int main()
{
	word_8 a[8] = {0xf1,0xe3,0xc7,0x8f,0x1f,0x3e,0x7c,0xf8},
			b = 0x63,x1,x,y,z,i = 0x00;
	FILE *p;
	int j,k;
	p = fopen("S.txt","wb");
	fprintf(p,"{");
	do
	{
		z = 0x00;
		x = tr(i);
		for(j = 0;j < 8;j++)
		{
			z = z >> 1;
			y = a[j] & x;
			x1 = 0x00;
			for(k = 0;k < 8;k++)
			{
				x1 ^= y & 0x80;
				y = y << 1;
			}
			z ^= x1;
		}
		z ^= b;
		fprintf(p,"0x%02x",z);
		if(i % 16 != 15)
			fprintf(p,",");
		if((i | 0xf0) == 0xff && i != 0xff)
			fprintf(p,",\n");
		i++;
	}while(i != 0x00);
	fprintf(p,"}");
	fclose(p);
	return 0;
}

这里只给出了生成正向S盒的算法，逆向S盒Un_S[]只需通过

word_8 i = 0x00;
do{
	Un_S[S[i]] = i;
}while(i != 0x00);

即可生成。

T表生成

如图，在AES中，列混合是计算复杂度最高的一个模块，矩阵中的乘法运算都是有限域GF(2⁸)上的运算，如果能通过查表实现，那么算法的执行速度就会大大提升。
在这里插入图片描述
由于如果存一个大表的话，其所需的存储空间就会超出正常电脑的内存，所以这里我们先将如图列混合按列拆成四部分

可以证明，将每一个4*1的列向量左乘4*4的矩阵得到的4*1的矩阵按顺序拼接，最终得到的4*4矩阵就是所要求的矩阵，即：
在这里插入图片描述
由于这里的乘法运算只有在有限域GF(2⁸)上任意数与01，02，03的乘法运算，所以这里我们只用建一个3*256的表进行查找即可：

void make_list()
{
	word_8 i = 0x00,j;
	do
	{
		mul_list[0][i] = i;
		j = i << 1;
		if((i & 0x80) == 0x80) j ^= 0x1b;
		mul_list[1][i] = j;
		mul_list[2][i] = i ^ j;
		i++;
	}while(i != 0x00);
}

接着我们接公式，遍历每一列的所有值，得到这一列对应的T表T₁ ，T₂ ，T₃ ，T₄ ，分别存入List_1.txt到List_4.txt中：

int main()
{
	word_8 i,j,k;
	make_list();
	FILE *p1,*p2,*p3,*p4;
	p1 = fopen("List_1.txt","wb");
	p2 = fopen("List_2.txt","wb");
	p3 = fopen("List_3.txt","wb");
	p4 = fopen("List_4.txt","wb");
	fprintf(p1,"{");
	fprintf(p2,"{");
	fprintf(p3,"{");
	fprintf(p4,"{");
	for(j = 0;j < 256;j++)//list_1
	{
		fprintf(p1,"{");
		for(i = 0;i < 4;i++)
		{
			k = mul_list[mix[i][0] - 1][j] ^
				mul_list[mix[i][1] - 1][0] ^
				mul_list[mix[i][2] - 1][0] ^
				mul_list[mix[i][3] - 1][0];
			fprintf(p1,"0x%02x",k);
			if(i != 3)
				fprintf(p1,",");
		}
		fprintf(p1,"}");
		if(j != 0xff)
			fprintf(p1,",\n");
		else
			break;
	}
	for(j = 0;j < 256;j++)//list_2
	{
		fprintf(p2,"{");
		for(i = 0;i < 4;i++)
		{
			k = mul_list[mix[i][0] - 1][0] ^
				mul_list[mix[i][1] - 1][j] ^
				mul_list[mix[i][2] - 1][0] ^
				mul_list[mix[i][3] - 1][0];
			fprintf(p2,"0x%02x",k);
			if(i != 3)
				fprintf(p2,",");
		}
		fprintf(p2,"}");
		if(j != 0xff)
			fprintf(p2,",\n");
		else
			break;
	}
	for(j = 0;j < 256;j++)//list_3
	{
		fprintf(p3,"{");
		for(i = 0;i < 4;i++)
		{
			k = mul_list[mix[i][0] - 1][0] ^
				mul_list[mix[i][1] - 1][0] ^
				mul_list[mix[i][2] - 1][j] ^
				mul_list[mix[i][3] - 1][0];
			fprintf(p3,"0x%02x",k);
			if(i != 3)
				fprintf(p3,",");
		}
		fprintf(p3,"}");
		if(j != 0xff)
			fprintf(p3,",\n");
		else
			break;
	}
	for(j = 0;j < 256;j++)//list_4
	{
		fprintf(p4,"{");
		for(i = 0;i < 4;i++)
		{
			k = mul_list[mix[i][0] - 1][0] ^
				mul_list[mix[i][1] - 1][0] ^
				mul_list[mix[i][2] - 1][0] ^
				mul_list[mix[i][3] - 1][j];
			fprintf(p4,"0x%02x",k);
			if(i != 3)
				fprintf(p4,",");
		}
		fprintf(p4,"}");
		if(j != 0xff)
			fprintf(p4,",\n");
		else
			break;
	}
	fprintf(p1,"}");
	fprintf(p2,"}");
	fprintf(p3,"}");
	fprintf(p4,"}");
	fclose(p1);
	fclose(p2);
	fclose(p3);
	fclose(p4);
	return 0;
}

同理可得解密的T表生成算法：

#include <stdio.h>
#include <stdlib.h>

typedef unsigned char word_8;

word_8 mul_list[4][256];//9,b,d,e
word_8 cipher[4][4];
int mix[4][4] = {
	{4,2,3,1},
	{1,4,2,3},
	{3,1,4,2},
	{2,3,1,4}};

word_8 mul(word_8 a,word_8 b)
{
	word_8 data[8],dat;
	data[0] = a;
	data[1] = data[0] << 1;
	if((data[0] & 0x80) == 0x80) data[1] ^= 0x1b;
	data[2] = data[1] << 1;
	if((data[1] & 0x80) == 0x80) data[2] ^= 0x1b;
	data[3] = data[2] << 1;
	if((data[2] & 0x80) == 0x80) data[3] ^= 0x1b;
	data[4] = data[3] << 1;
	if((data[3] & 0x80) == 0x80) data[4] ^= 0x1b;
	data[5] = data[4] << 1;
	if((data[4] & 0x80) == 0x80) data[5] ^= 0x1b;
	data[6] = data[5] << 1;
	if((data[5] & 0x80) == 0x80) data[6] ^= 0x1b;
	data[7] = data[6] << 1;
	if((data[6] & 0x80) == 0x80) data[7] ^= 0x1b;
	
	dat = 0x00;
	if((b & 0x01) == 0x01) dat ^= data[0];
	if((b & 0x02) == 0x02) dat ^= data[1];
	if((b & 0x04) == 0x04) dat ^= data[2];
	if((b & 0x08) == 0x08) dat ^= data[3];
	if((b & 0x10) == 0x10) dat ^= data[4];
	if((b & 0x20) == 0x20) dat ^= data[5];
	if((b & 0x40) == 0x40) dat ^= data[6];
	if((b & 0x80) == 0x80) dat ^= data[7];
	
	return dat;
}
	
void make_list()
{
	word_8 i = 0x00;
	do
	{
		mul_list[0][i] = mul(0x09,i);
		mul_list[1][i] = mul(0x0b,i);
		mul_list[2][i] = mul(0x0d,i);
		mul_list[3][i] = mul(0x0e,i);
		i++;
	}while(i != 0x00);
}

int main()
{
	word_8 i,j,k;
	make_list();
	FILE *p1,*p2,*p3,*p4;
	p1 = fopen("DeList_1.txt","wb");
	p2 = fopen("DeList_2.txt","wb");
	p3 = fopen("DeList_3.txt","wb");
	p4 = fopen("DeList_4.txt","wb");
	fprintf(p1,"{");
	fprintf(p2,"{");
	fprintf(p3,"{");
	fprintf(p4,"{");
	for(j = 0;j < 256;j++)//list_1
	{
		fprintf(p1,"{");
		for(i = 0;i < 4;i++)
		{
			k = mul_list[mix[i][0] - 1][j] ^
				mul_list[mix[i][1] - 1][0] ^
				mul_list[mix[i][2] - 1][0] ^
				mul_list[mix[i][3] - 1][0];
			fprintf(p1,"0x%02x",k);
			if(i != 3)
				fprintf(p1,",");
		}
		fprintf(p1,"}");
		if(j != 0xff)
			fprintf(p1,",\n");
		else
			break;
	}
	for(j = 0;j < 256;j++)//list_2
	{
		fprintf(p2,"{");
		for(i = 0;i < 4;i++)
		{
			k = mul_list[mix[i][0] - 1][0] ^
				mul_list[mix[i][1] - 1][j] ^
				mul_list[mix[i][2] - 1][0] ^
				mul_list[mix[i][3] - 1][0];
			fprintf(p2,"0x%02x",k);
			if(i != 3)
				fprintf(p2,",");
		}
		fprintf(p2,"}");
		if(j != 0xff)
			fprintf(p2,",\n");
		else
			break;
	}
	for(j = 0;j < 256;j++)//list_3
	{
		fprintf(p3,"{");
		for(i = 0;i < 4;i++)
		{
			k = mul_list[mix[i][0] - 1][0] ^
				mul_list[mix[i][1] - 1][0] ^
				mul_list[mix[i][2] - 1][j] ^
				mul_list[mix[i][3] - 1][0];
			fprintf(p3,"0x%02x",k);
			if(i != 3)
				fprintf(p3,",");
		}
		fprintf(p3,"}");
		if(j != 0xff)
			fprintf(p3,",\n");
		else
			break;
	}
	for(j = 0;j < 256;j++)//list_4
	{
		fprintf(p4,"{");
		for(i = 0;i < 4;i++)
		{
			k = mul_list[mix[i][0] - 1][0] ^
				mul_list[mix[i][1] - 1][0] ^
				mul_list[mix[i][2] - 1][0] ^
				mul_list[mix[i][3] - 1][j];
			fprintf(p4,"0x%02x",k);
			if(i != 3)
				fprintf(p4,",");
		}
		fprintf(p4,"}");
		if(j != 0xff)
			fprintf(p4,",\n");
		else
			break;
	}
	fprintf(p1,"}");
	fprintf(p2,"}");
	fprintf(p3,"}");
	fprintf(p4,"}");
	fclose(p1);
	fclose(p2);
	fclose(p3);
	fclose(p4);
	return 0;
}

主要函数

最后，我们通过查表实现AES算法的加解密：

#include <stdio.h>
#include <stdlib.h>
#include "Lists.h"

word_8 RoundK[11][16];
word_32 Key[4] = {0x2b7e1516,0x28aed2a6,0xabf71588,0x09cf4f3c};

void Look(word_8 Str[])
{
	int i;
	for(i = 0;i < 16;i++)
		printf("%02x",Str[i]);
	printf("\n");
}

void Make_Key()
{
	word_32 k[44] = {0};
	int i,j;
	for(i = 0;i < 4;i++)
		k[i] = Key[i];
	for(;i < 4 * 11;i++)
	{
		if(i % 4 == 0)
			k[i] = k[i - 4] ^ (
			(S_box[(k[i - 1] >> 16) & 0x000000ff] << 24) ^
			(S_box[(k[i - 1] >> 8) & 0x000000ff] << 16) ^
			(S_box[(k[i - 1]) & 0x000000ff] << 8) ^
			(S_box[(k[i - 1] >> 24) & 0x000000ff])) ^ Rcon[(i / 4) - 1];
		else
			k[i] = k[i - 4] ^ k[i - 1];
	}
	for(i = 0;i < 11;i++)
		for(j = 0;j < 16;j++)
			RoundK[i][j] = k[i * 4 + j / 4] >> (((3 - (j % 4)) * 8) & 0x000000ff);
}

void Sub_Bytes(word_8 plain[],word_8 cipher[])
{
	int i = 0;
	for(i = 0;i < 16;i++)
		cipher[i] = S_box[plain[i]];
}

void De_Sub_Bytes(word_8 cipher[],word_8 plain[])
{
	int i = 0;
	for(i = 0;i < 16;i++)
		plain[i] = De_S_box[cipher[i]];
}

void Shift_Rows(word_8 plain[],word_8 cipher[])
{
	cipher[0] = plain[0];
	cipher[1] = plain[5];
	cipher[2] = plain[10];
	cipher[3] = plain[15];
	cipher[4] = plain[4];
	cipher[5] = plain[9];
	cipher[6] = plain[14];
	cipher[7] = plain[3];
	cipher[8] = plain[8];
	cipher[9] = plain[13];
	cipher[10] = plain[2];
	cipher[11] = plain[7];
	cipher[12] = plain[12];
	cipher[13] = plain[1];
	cipher[14] = plain[6];
	cipher[15] = plain[11];
}

void De_Shift_Rows(word_8 cipher[],word_8 plain[])
{
	plain[0] = cipher[0];
	plain[1] = cipher[13];
	plain[2] = cipher[10];
	plain[3] = cipher[7];
	plain[4] = cipher[4];
	plain[5] = cipher[1];
	plain[6] = cipher[14];
	plain[7] = cipher[11];
	plain[8] = cipher[8];
	plain[9] = cipher[5];
	plain[10] = cipher[2];
	plain[11] = cipher[15];
	plain[12] = cipher[12];
	plain[13] = cipher[9];
	plain[14] = cipher[6];
	plain[15] = cipher[3];
}

void Mix_Columns(word_8 plain[],word_8 cipher[])
{
	word_8 a[4];
	int i,j;
	for(i = 0;i < 4;i++)
	{
		for(j = 0;j < 4;j++)
			a[j] = T1[plain[i * 4]][j] ^
					T2[plain[i * 4 + 1]][j] ^
					T3[plain[i * 4 + 2]][j] ^
					T4[plain[i * 4 + 3]][j];
		for(j = 0;j < 4;j++)
			cipher[i * 4 + j] = a[j];
	}
}

void De_Mix_Columns(word_8 cipher[],word_8 plain[])
{
	word_8 a[4];
	int i,j;
	for(i = 0;i < 4;i++)
	{
		for(j = 0;j < 4;j++)
			a[j] = De_T1[cipher[i * 4]][j] ^
					De_T2[cipher[i * 4 + 1]][j] ^
					De_T3[cipher[i * 4 + 2]][j] ^
					De_T4[cipher[i * 4 + 3]][j];
		for(j = 0;j < 4;j++)
			plain[i * 4 + j] = a[j];
	}
}

void Add_Round_Key(word_8 plain[],word_8 cipher[],int k)
{
	int i;
	for(i = 0;i < 16;i++)
		cipher[i] = plain[i] ^ RoundK[k][i];
}

void Encrypt(word_8 plain[],word_8 cipher[])
{
	int i;
	Make_Key();
//	Look(plain);
	Add_Round_Key(plain,cipher,0);
//	Look(cipher);
	for(i = 1;i <= 9;i++)
	{
		Sub_Bytes(cipher,plain);
//		Look(plain);
		Shift_Rows(plain,cipher);
//		Look(cipher);
		Mix_Columns(cipher,plain);
//		Look(plain);
		Add_Round_Key(plain,cipher,i);
//		Look(cipher);
	}
	Sub_Bytes(cipher,plain);
//	Look(plain);
	Shift_Rows(plain,cipher);
//	Look(cipher);
	Add_Round_Key(cipher,plain,i);
//	Look(plain);
	for(i = 0;i < 16;i++)
		cipher[i] = plain[i];
}

void Decrypt(word_8 cipher[],word_8 plain[])
{
	int i;
	Make_Key();
//	Look(cipher);
	Add_Round_Key(cipher,plain,10);
//	Look(plain);
	for(i = 9;i >= 1;i--)
	{
		De_Shift_Rows(plain,cipher);
//		Look(cipher);
		De_Sub_Bytes(cipher,plain);
//		Look(plain);
		Add_Round_Key(plain,cipher,i);
//		Look(cipher);
		De_Mix_Columns(cipher,plain);
//		Look(plain);
	}
	De_Shift_Rows(plain,cipher);
//	Look(cipher);
	De_Sub_Bytes(cipher,plain);
//	Look(plain);
	Add_Round_Key(plain,cipher,i);
//	Look(cipher);
	for(i = 0;i < 16;i++)
		plain[i] = cipher[i];
}

其中 Lists.h 头文件中存放的是所有的表。
加解密分别调用Encrypt与Decrypt即可。

注：若觉得速度还是不够快，可以将所有的函数调用都去掉，所有循环全部写开，虽然这样不利于阅读，但算法的运行速度又会有一个显著的提升。

开放原子开发者工作坊

开放原子开发者工作坊旨在鼓励更多人参与开源活动，与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动，如meetup、训练营等，主打技术交流，干货满满，真诚地邀请各位开发者共同参与！

更多推荐

一维高斯分布与多维高斯分布及 matlab 实现

一维高斯分布与多维高斯分布一维高斯分布高斯分布（Gaussian distribution），又称正态分布（Normal distribution）。若随机变量X服从一个数学期望为μ、方差为σ^2的正态分布，记为N(μ，σ^2)。其概率密度函数为正态分布的期望值μ决定了其位置，其标准差σ决定了分布的幅度。当μ = 0,σ = 1时的正态分布是标准正态分布。正态分布使用下列参数：参数说明范围mu (

开放原子开发者工作坊

图像传感器与信号处理——自动曝光算法

图像传感器与信号处理——自动曝光算法图像传感器与信号处理——自动曝光算法1. 如何实现自动曝光？2. 基于直方图统计的算法2.1 Automatic Camera Exposure Control，20073. 基于熵的算法4. 基于梯度的算法图像传感器与信号处理——自动曝光算法在很久之前我和一位视觉SLAM大佬交流过，视觉SLAM难以落地原因有很多，其中之一就是环境光照对SLAM系统有较大的..