在GF(二^8)下可做任意两个数乘法的程序（一）
作业要求：
GF(2^8)，也就是在一个字节上所做的乘法和加法都封闭的一个有限域。
在GF(2^8)上只有两种运算：异或加运算和乘法运算。
其中异或加运算就是1 xor 1 = 0, 0 xor 0 = 0, 1 xor 0 = 1。（原谅我的啰嗦）
乘法运算的规则就是：
（1）A * 2的时候，A左移一位；A * 4 = (A * 2) * 2，A * 8 = ((A * 2) * 2) * 2，容易看出乘上2的n次幂是一个不断迭代的过程。
（2）那么A * 6的情况有如何？很简单，A * 6 = (A * 2) xor (A * 4)，注意在该域中加法都是xor运算，而不是算术加运算。另外，可能有人会问：A * 4 = (A * 2) xor (A * 2) = 0，这不是和（1）冲突了吗？
原因在于：A * 6 = A * 00000110，其中00000110 = 00000100 xor 00000010，但是A * 4 = A * 00000100，00000100 != 00000010 xor 00000010 (= 00000000)。
（3）在乘法运算中，若乘数左移结果中第8位左边非0，例如10000000 * 00000100 = 10000000 * 2 * 2，其中10000000 * 2 = (1)00000000，结果溢出，所以要再和1BH进行异或加运算，即结果为00000000 xor 00011011 = 00011011。然后00011011 * 2 = 00110110即为结果。
错误做法：10000000 * 4 = (10)00000000 xor 00011011 = 00011011，为什么呢？因为10000000 * 2已经溢出，要先做溢出处理。
注：为什么是1BH？因为在AES的设计中开发者选用了不可约多项式m(x) = x^8 + x^4 + x^3 + x + 1，所以如果结果溢出就要再xor一个00011011（也就是1BH）。
在基本的运算法则搞懂以后，写程序就很简单了。
最近写OC写了很多，Java上学期也一直在写，反而C++好久没写了，突然又用回C++来写程序，还真的差点没转过弯来。所以现在趁着写博客的机会做下笔记。
好吧，回到程序来。
先来看看主函数，大致看看整个程序的流程：
int main()
{
int a[8], b[8], c[8], i=0;
LARGE_INTEGER start_t, stop_t, freq; // start_t表示计时开始时间，stop_t表示计时结束时间，freq为计时器的时钟频率
double exe_time;
QueryPerformanceFrequency(&freq);
// fprintf(stdout, "The frequency of your pc is %d.\n", freq.QuadPart);
char ch='y';
while(ch=='y'||ch=='Y')
{
// -- 清空之前的计算结果 --
for(i=0; i<8; i++)
{
c[i]=0; // 清空结果
}
state=0; // 清空当前左移位数
// -- 输入乘数a和b --
if(input(a, 'a')==0) // 如果输入a没有出错
{
if(input(b, 'b')==0) // 如果输入b没有出错
{
// -- 程序开始执行，开始计时 --
QueryPerformanceCounter(&start_t);
// -- 执行乘法运算 --
for(i=7; i>=0; i--)
{
if(b[i]==1)
{
xor(c, leftshift(a, 7-i)); // 求和
}
}
// -- 输出运算结果 --
cout<<"运算结果为：";
for(i=0; i<8; i++)
{
cout<<c[i];
}
// -- 程序结束执行，结束计时 --
QueryPerformanceCounter(&stop_t);
exe_time = 1e3*(stop_t.QuadPart-start_t.QuadPart)/freq.QuadPart;
cout<<endl;
fprintf(stdout, "计算用时：%fms.\n", exe_time);
}
}
// -- 是否继续执行程序 --
cout<<endl<<"是否继续?y/n:";
ch=cin.get();
if(cin.get()==10)
{
// 跳过输入y/n后的回车键，防止影响下面的输入
}
}
return 0;
}
结构非常清晰：清空之前的运算结果 —— 输入乘数a和b —— 执行乘法运算a * b —— 输出运算结果c以及计算时间 —— 是否循环执行。
首先来看看封装好的输入函数：
/*
* 分别输入两个GF(8)内的乘数
* 参数temp[]用于保存输入的二进制数组
* 参数name为变量名称，如a，b
* 返回类型为输入后的状态，若为0则成功，若非0则出错
*/
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;
}
}
return 0;
}
注意输入的数由于要在GF(2^8)内，所以必须符合要求：8位，每一位都是0或1，例如00000010。
若输入错误可以直接exit程序，这里做成了回调错误状态到主函数并询问是否重新输入的循环形式。
在讲解执行a * b之前，先看看xor运算：
/* 对a和b进行异或求和运算 */
void xor(int a[], int b[])
{
for(int i=0; i<8; i++)
{
a[i]=bitxor(a[i], b[i]);
}
}
/* 按位进行异或求和运算 */
int bitxor(int a, int b)
{
if(a==b)
{
return 0;
}
else
{
return 1;
}
}
xor()是对一个字节的a[8]和b[8]进行xor求和，结果保存到a[8]中。
bitxor()是逐位相与。
再看看求和语句：
// -- 执行乘法运算 --
for(i=7; i>=0; i--)
{
if(b[i]==1)
{
xor(c, leftshift(a, 7-i)); // 求和
}
}
看看关键的leftshift函数：
/*
* 计算a[]乘上2的len次幂的结果, len为左移的位数
* 参数temp[]用于保存移位后的数组，用于迭代进行下一次移位
* 参数len为左移的位数，例如10000000的左移位数为7
* state用于保存temp对应的左移位数
* 返回结果为移位后的数组
*/
int *leftshift(int temp[], int len)
{
if(len==0)
{
state=0;
return temp;
}
// 由于temp保存了之前的位移结果，所以只需要左移len-state位
for(state; state<len; state++)
{
shift1(temp); // 乘2，或者说左移1位（包含溢出处理）
}
return temp;
}
为了说明该算法的思想，首先举个例子：对于a * 00001100 = (a * 00001000) xor (a * 00000100)，这时有两种计算方法（假设一次乘法或一次加法为1次计算）：
（1）计算a * 00000100得结果a left shift 2，再计算a * 00001000得结果a leftshift 3，然后得a = (a left shift 2) xor (a left shift 3)。
计算次数为 2 + 3 + 1 + 溢出的加法次数x = 6 + x。
（2）在（1）的基础上，注意到a left shift 3 = (a left shift 2) * 2，所以我们可以先计算a left shift 2，然后使用a left shift 2的结果乘2（只需要1次乘法）得到结果a left shift 3，这样就避免了在计算a left shift 3时又要从a计算起。
计算次数为 2 + 1 + 1 + 溢出的加法次数y = 4 + y。
明显地，y <= x，也就是方法（2）的运算效率高于方法（1）。
在本程序中，对于a[8] * b[8]，我们从b[7]计算到b[0]，也就是a[8] * 2的次数从0一直计算到7，其中每次乘法都运用了之前乘法运算保存的结果，该结果由temp数组保存，state则保存了temp数组对应的移位次数，len为本次乘法原来需要乘2的次数（这里乘2和左移是一致的，在讲述时忽略溢出的处理情况）。其中state为全局静态变量，初始为0：
static state=0; // 用于记录左移的位数还有左移1位（乘2）的函数shift1：
/* 乘2，左移1位，如果溢出则异或1BH */
void shift1(int a[])
{
int temp=a[0];
for(int i=0; i<7; i++)
{
a[i]=a[i+1];
}
a[7]=0;
if(temp==1) // 溢出处理
{
int mod[8]={0, 0, 0, 1, 1, 0, 1, 1};
xor(a, mod);
}
}
还是Run一下吧，写博客的习惯：
好久没写C++，小小回顾一下：
1.若要在主函数中调用其它函数，必须将该函数放在主函数之前，或者提前做好函数声明，例如：
#include <iostream> #include <limits> // numeric_limits #include <windows.h> using namespace std; int input(int temp[], char name); void xor(int a[], int b[]); int bitxor(int a, int b); int *leftshift(int temp[], int len); void shift1(int a[]);
2.判断输入是否按了回车换行，可以通过以下方法：
c=cin.get();
while(c!=10)
{
}
其中10（0AH）对应的ACII码为换行。
其中语句cin.get()对应一次输入，而不是上一次的输入。
3.如果要强制退出程序，可以直接使用exit(1)退出，而不需要回调数据到main函数再return。
4.调用函数时数组可以直接作为参数传值：int(a[], b[])。
5.当函数的返回类型是数组时，可以首先在函数中声明一个数组指针：
int *shift=new int[8];
在写程序时没有声明长度，结果一直弹出Debug Assertion Failed!的错误。
在函数结束时返回该指针：
return shift;
注意shift必须new，否则返回的指针所指向的数组可能其值全部为负最大值。
函数声明：int *leftshift(int a[], int len);
6.如果要清空输入缓冲区中的内容，可以使用以下方法：
cin.ignore(numeric_limits<streamsize>::max(),'\n'); // 清除输入缓冲区中的所有内容
注意必须导入头文件
#include <limits> // numeric_limits
关于limits的max()和windows.h冲突的解决方法见numeric_limits::max()和windows.h冲突的解决方法。
7.计算程序运行时间的方法：
（1）使用time.h给出的函数
首先导入头文件：
#include <time.h>
time_t start,end,time; // 计时所用的变量名称
开始计时：
// -- 程序开始执行，开始计时 -- start=clock();
// -- 程序结束执行，结束计时 -- end=clock(); time=end-start; // 这里的时间是计算机内部时间 cout<<endl<<"程序用时:"<<time<<endl;
（2）使用windows.h给出的函数
详见C/C++ 各种计时函数总结。
这学期密码学关于编程的作业好像还挺多的，所以专门开个类别写些博客来记录，这篇博客可能还没涉及到密码安全学方面的问题，但随着课程的深入，肯定会有更多与这方面相关的内容（表示压力很大），我会继续写博客更新的。