使用乘法表计算GF(2^8)中的乘法
作业要求:构造256字节的表格X2,使得X2[i] ={02}*i,i是GF(2^8)中的元素。将此表运用于GF(2^8)的乘法,与之前作业的乘法对比,看谁的速度快?
直奔主题吧。先看看主函数:
直接乘法运算时间结果:
首先有一点要强调的是,由于CPU每个时刻工作的速度和时钟频率等都处于动态变化当中,所以以上数据不能算绝对准确,加上程序员不同的算法也会导致程序运行的时间出现差异,因此以上数据仅仅用于对比,而且也不能算得上绝对准确。
比较之下,乘法表运算多了一些转换的工作(包括leftshift函数,因为其中的异或运算必须要使用二进制数组,而且输出结果形式也是二进制形式),也就是在乘法表的条件差于移位乘法的情况下其效率仍然高于后者,所以也得出了老师想向我们传递的信息:GF(2^8)中的乘法运算查表运算的效率高于直接运算。当初AES的设计者就是用该方法来对乘法进行加速(另外乘法可能会受到时间分析攻击),另外表所使用的空间开销并不大,用查表计算乘法结果的方法优于直接使用乘法。
最后,小结一个问题:对于调用函数,如果传入参数的是数组指针并且在函数中修改了参数的值,那么数组的值将相应变化。如果传入参数的是基本类型并且在函数中修改了参数的值,基本类型变量的值却不会相应发生变化。例如:
道理很简单,因为在传入指针到参数后,若参数值被修改,那么指针所指向的内存块的值也相应被修改。而基本类型变量的参数传入则是另外复制一份传值。