求任意8比特数在AES的S-Box中的对应值

现在的位置: 首页 > 综合 > 正文

RSS

求任意8比特数在AES的S-Box中的对应值

2014年09月05日 ⁄ 综合 ⁄ 共 5644字 ⁄ 字号小中大 ⁄ 评论关闭

题目要求：

写一个程序，给定任意8比特数，可求其在S-Box中所对应的值。

首先上课的时候，由于老师经常提到查表得出结果什么的，所以一看到这道题我的第一反应就是首先把课本的S-Box表敲进去，然后直接用行号和列号来查。

后来听同学提醒才知道其实是要先求逆元，再用矩阵变换来计算得到S-Box转换结果。好吧，是我头脑太简单了，我认了。

记得以前看别人的程序经常看到一个大矩阵，当时觉得这是一个很酷的事，于是我也很傻逼地照做了。

先来看看这道题的傻瓜式做法：

#include <iostream>
#include <limits> //numeric_limits 
using namespace std;
int charToInt(char c);

int main()
{
	//  -- 构造S-Box --
	char *sbox[16][16]={ 
		{"63", "7C", "77", "7B", "F2", "6B", "6F", "C5", "30", "01", "67", "2B", "FE", "D7", "AB", "76"},
		{"CA", "82", "C9", "7D", "FA", "59", "47", "F0", "AD", "D4", "A2", "AF", "9C", "A4", "72", "C0"},
		{"B7", "FD", "93", "26", "36", "3F", "F7", "CC", "34", "A5", "E5", "F1", "71", "D8", "31", "15"},
		{"04", "C7", "23", "C3", "18", "96", "05", "9A", "07", "12", "80", "E2", "EB", "27", "B2", "75"},
		{"09", "83", "2C", "1A", "1B", "6E", "5A", "A0", "52", "3B", "D6", "B3", "29", "E3", "2F", "84"},
		{"53", "D1", "00", "ED", "20", "FC", "B1", "5B", "6A", "CB", "BE", "39", "4A", "4C", "58", "CF"},
		{"D0", "EF", "AA", "FB", "43", "4D", "33", "85", "45", "F9", "02", "7F", "50", "3C", "9F", "A8"},
		{"51", "A3", "40", "8F", "92", "9D", "38", "F5", "BC", "B6", "DA", "21", "10", "FF", "F3", "D2"},
		{"CD", "0C", "13", "EC", "5F", "97", "44", "17", "C4", "A7", "7E", "3D", "64", "5D", "19", "73"},
		{"60", "81", "4F", "DC", "22", "2A", "90", "88", "46", "EE", "B8", "14", "DE", "5E", "0B", "DB"},
		{"E0", "32", "3A", "0A", "49", "06", "24", "5C", "C2", "D3", "AC", "62", "91", "95", "E4", "79"},
		{"E7", "C8", "37", "6D", "8D", "D5", "4E", "A9", "6C", "56", "F4", "EA", "65", "7A", "AE", "08"},
		{"BA", "78", "25", "2E", "1C", "A6", "B4", "C6", "E8", "DD", "74", "1F", "4B", "BD", "8B", "8A"},
		{"70", "3E", "B5", "66", "48", "03", "F6", "0E", "61", "35", "57", "B9", "86", "C1", "1D", "9E"},
		{"E1", "F8", "98", "11", "69", "D9", "8E", "94", "9B", "1E", "87", "E9", "CE", "55", "28", "DF"},
		{"8C", "A1", "89", "0D", "BF", "E6", "42", "68", "41", "99", "2D", "0F", "B0", "54", "BB", "16"}
	};


	//  -- 输入要替换的字节并进行查表操作 --
	int row=0, column=0, i=0;
	char choose='y', *byte, temp;
	byte=new char[];
	while(choose=='y'||choose=='Y')
	{
		cout<<"请输入要替换的字节（如0E）：";
		cin>>byte[0];
		cin>>byte[1];
		if(cin.get()!=10) // 如果没有输入回车
		{
			cout<<"输入字节长度错误"<<endl;
			cin.ignore(numeric_limits<streamsize>::max(),'\n'); // 清除输入缓冲区中的所有内容
		}
		else 
		{
			row=charToInt(byte[0]); // 行号转换
			column=charToInt(byte[1]); // 列号转换 
			if(row==-1||column==-1)
			{
				cout<<"字节输入错误"<<endl;
			}
			else
			{
				// 执行S-Box查表操作
				char *des=sbox[row][column];
				cout<<"S-Box变换结果为：";
				for(i=0; i<2; i++)
				{
					cout<<des[i];
				}
				cout<<endl;
			}
		}
		
		cout<<endl<<"是否继续查表？y/n:";
		cin>>choose;
	}

	return 0;
}

/* 将输入的字符转换为整数 */
int charToInt(char c)
{
	int x=(int)c;
	if(x>=48&&x<=57) // 0-9
	{
		return x-48;
	}
	else if(x>=65&&x<=70) // A-F
	{
		return x-55;
	}
	else if(x>=97&&x<=102) // a-f
	{
		return x-87;
	}
	else
	{
		return -1;
	}
}

思想很简单，构造S-Box对应的表格，用户输入一个2位十六进制数组例如0E，然后查表格中的第1行第15列也就是求sbox[0][14]，最后输出结果。Run看看：

不能说这种方法错了，只能说是不符合老师的要求吧。

好吧，还是规规矩矩地直接用课本的转换方法做吧（来自CANS第五版5.3.1）：

AES的S盒按如下方式构造：

（1）按字节值升序逐行初始化S盒（16 * 16），共256个。

（2）把S盒中的每个字节映射为它在GF(2^8)中的逆元，{00}被映射为它自身。

（3）记S盒中每个字节的8个构成位为（b7, b6, b5, b4, b3, b2, b1, b0），对S盒中的每个字节的每个位做如下的变换：b[i] ' = b[i] xor b[(i+4)mod8] xor b[(i+5)mod8] xor b[(i+6)mod8] xor b[(i+7)mod8] xor c[i]。其中（c7,c6,c5,c4,c3,c2,c1,c0） =
01100011。

按照以上规则，若输入某个数a，对其进行S-Box转换的方法为：

（1）求 a的逆元a-1。00H的逆元为00H。

（2）对a-1进行矩阵变换，也就是对每一位进行以上（3）的操作。

分析完毕，看代码部分。

int main()
{   
	int a[8], b[8], c[8], i=0, bdec;
	int temp[8];
	char choose='y';
	bool finished;

	while(choose=='y'||choose=='Y')
	{
		//  -- 输入要转换的数a --
		int x=input(a, 'a');
		if(x==0) // 如果输入a没有出错
		{
			finished=false; // 初始设定尚未找到转换结果

			for(bdec=1; bdec<256; bdec++) // 枚举GF(2^8)中的数，寻找a[8]的逆元
			{
				if(finished==true) // 如果已经完成S-Box转换操作，就跳出枚举逆元的for循环
					break;

				//  -- 初始化程序的各个参数 --
				state=0; // 清空当前左移位数
				for(i=0; i<8; i++)
				{
					c[i]=0; // 清空转换结果 
					temp[i]=a[i]; // 为了保存a[i]数组用于下一次循环，将a[8]数组赋予temp[8]
				}
				decToBin(bdec, b); // 将bdec转换为二进制数组b

				//  -- 执行乘法运算a*b，结果存到c中 --
				for(i=7; i>=0; i--)
				{
					if(b[i]==1)
					{
						xor(c, leftshift(temp, 7-i)); // 求和
					}
				}

				//  -- 判断是否逆元，如果是则进行转换并输出结果 --
				if(isInverse(c)==true) // 如果c是1，即b为a的逆元
				{
					matrixTrans(b, temp); // 进行矩阵计算变换
					finished=true; // 完成S-Box转换
				}
			}
		}
		else if(x==-1) // 如果输入了00000000，那么S-Box变换结果为63H
		{
			cout<<"01100011";
		}

		//  -- 是否继续执行程序 --
		cout<<endl<<endl<<"是否继续?y/n:";
		choose=cin.get();
		if(cin.get()==10)
		{
			// 跳过输入y/n后的回车键，防止影响下面的输入
		}
	}

	return 0;
}

主函数的流程很简单：输入数a —— 求a的逆元a-1（如果为0，直接输出01100011） —— 对a-1进行矩阵变换并输出转换结果 —— 是否循环执行。

其中在求a的逆元时，涉及到扩展Euclid算法，那个真心不会，而且光是用手来写表格求都麻烦，更别提用代码实现（个人看法），加上GF(2^8)中最多才256个数（去掉0的话255个），所以决心从1到255枚举GF(2^8)求逆元。

input函数和之前的在GF(2^8)下可做任意两个数乘法的程序（一）略有变化，加上了输入为00000000的返回结果为-1：

/* 
 * 分别输入两个GF(8)内的乘数 
 * 参数temp[]用于保存输入的二进制数组
 * 参数name为变量名称，如a，b
 * 返回结果为输入后的状态，若为0则成功，若为-1表示输入的数为00000000，若非0或-1则出错
 */
int input(int temp[], char name)
{
	char c;
	int i=0;
	cout<<"请按8位二进制格式输入乘数"<<name<<",以回车结束:";
	c=cin.get();
	while(c!=10) // 若输入的不是回车
	{
		switch(c)
		{
		case '0':temp[i++]=0;break;
		case '1':temp[i++]=1;break;
		default:
			cout<<"程序出错：数字输入错误，不是0或1";
			cin.ignore(numeric_limits<streamsize>::max(),'\n'); // 清除输入缓冲区中的所有内容
			return 1;
		}

		c=cin.get();
		if(c==10&&i!=8)
		{
			cout<<"程序出错：输入的数位数不等于8";
			return 2;
		}
	}

	int sum=0;
	for(i=0; i<8; i++)
	{
		sum+=temp[i];
		if(sum>0)
		{
			return 0;
		}
	}
	if(sum==0)
	{
		return -1; // 输入的二进制数为00000000
	}

	return 0;
}

在枚举求a的逆元时，假设该数的十进制形式为bdec，先要转换成二进制数组b，再计算a * b，若结果为00000001，那么b为a的逆元。在这里涉及到十进制转换为二进制decToBin，以及判断是否逆元isInverse两个函数：

/* 将十进制数转换为二进制数组 */
void decToBin(int d, int b[])
{
	int i=7;
	while(i>=0)
	{
		b[i--]=d%2;
		d/=2;
	}
}

/* 在枚举寻找逆元时，判断其乘积结果是否为00000001 */
bool isInverse(int c[])
{
	for(int i=0; i<7; i++)
	{
		if(c[i]!=0)
			return false;
	}

	if(c[7]==1)
	{
		return true;
	}
	else 
	{
		return false;
	}
}

乘法所用到的leftshift， shift1， xor， bitxor函数沿用了在GF(2^8)下可做任意两个数乘法的程序（一）中的函数（感受到了Java老师所说的代码复用的思想）。

在求出逆元后，再对其进行矩阵变换即得到结果，使用了matrixTrans函数：

/* 将二进制数组进行S-Box的矩阵转换 */
void matrixTrans(int b[], int nb[])
{
	// 由于在每次行列求乘积的时候b要保持不变，所以将b复制一份给nb
	for(int i=0; i<8; i++)
	{
		nb[i]=b[i];
	}

	// nb[i]=b[i] xor b[i+1] xor b[i+2] xor b[i+3] xor b[i+4] xor (01100011中的对应位)
	for(i=0; i<8; i++)
	{
		nb[i]=bitxor(nb[i], b[(i+4)%8]);
		nb[i]=bitxor(nb[i], b[(i+3)%8]);
		nb[i]=bitxor(nb[i], b[(i+2)%8]);
		nb[i]=bitxor(nb[i], b[(i+1)%8]);
		if(i==0||i==3||i==4||i==5)
		{
			nb[i]=bitxor(nb[i], 0);
		}
		else
		{
			nb[i]=bitxor(nb[i], 1);
		}
	}

	cout<<"转换结果为：";
	for(i=0; i<8; i++)
	{
		cout<<nb[i];
	}
}

完成。Run一下看看（运行结果可以对比CANS第五版表5.2看看）