本文主要是介绍在GF(2^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;
}首先来看看封装好的输入函数：
/* * 分别输入两个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;
}若输入错误可以直接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; // 用于记录左移的位数/* 乘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)
{
}其中语句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++ 各种计时函数总结。
这学期密码学关于编程的作业好像还挺多的，所以专门开个类别写些博客来记录，这篇博客可能还没涉及到密码安全学方面的问题，但随着课程的深入，肯定会有更多与这方面相关的内容（表示压力很大），我会继续写博客更新的。
这篇关于在GF(2^8)下可做任意两个数乘法的程序的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
