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

本文主要是介绍求任意8比特数在AES的S-Box中的对应值，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目要求：

写一个程序，给定任意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复制一份给nbfor(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看看）