题目要求:
写一个程序,给定任意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。
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看看)
比较两种方法,明显第一种方法运行效率更高,是用开发者的开发效率换来的。很可惜不符合老师要求。
第二种方法用了枚举方法来求逆元,由于GF(2^8)最多才256个数,所以对程序运行效率影响不大,但是如果该域数量变得很大,那就只能用其它方法来求逆元了。
好吧,AES的S-Box会做了(尽管算法并不够好),等我学到了新东西再更新吧。