AES加密之 有限域GF(2^n)算术 / xtime
有限域算术是AES加密算法的必备知识。
本文包括,定义,加法,乘法,总结。
定义
含有2n个元素的有限域,被称为GF(2n)。
GF(2n)也可以表示成多项式:f (x) = an-1xn-1 + an-2xn-2 + …… + a1x + a0
(ai = 0,1)。
GF(2n)还可以表示成二进制数:(an-1,an-2,……,a1,a0)。
举两个栗子:GF(23)
.
多项式: x2+1
二进制数(101).
多项式: x
二进制数(010)
.
.
.
加法
系数运算以2为模,加法(减法)等于各项异或。
举两个栗子:
.
多项式表示:(x + 1) + x = 1
二进制表示: (011) ⊕ (010) = (001)
.多项式表示: (x2 + x + 1) + (x + 1) = x2
二进制表示: (111) ⊕ (011) = (100)
.
.
.
.
乘法(重点)
- 乘法稍微复杂一点
举几个栗子:
.
设在GF(28)内计算,此域中最高次项为x7。
.
乘法栗子1:
多项式表示: (x5+x4+x2+x+1) * x = (x6+x5+x3+x2+x)
二进制表示: (0011 0111) * (0000 0010) = (0110 1110) 【相当于左移一位】
.
乘法栗子2:多项式表示: (x5+x4+x2+x+1) * x2 = (x6+x5+x3+x2+x) * x = (x7+x6+x4+x3+x2)
二进制表示: (0011 0111) * (0000 0100) = (1101 1100) 【相当于左移二位】
.
乘法栗子3:
先找一个不可约多项式 m(x) = x8+x4+x3+x+1,后面详细解释m(x)
.
多项式表示:
.(x5+x4+x2+x+1) * x3
= (x7+x6+x4+x3+x2) * x
= (x8+x7+x6+x5+x3) 【出现了x8,超出GF(28),必须用模m(x)约化】
= (x8+x7+x6+x5+x3) mod m(x)
= (x8+x7+x6+x5+x3) mod (x8+x4+x3+x+1)
= x7+x5+x+1二进制表示:
.(0011 0111) * (0000 0100)
= (1 1011 1000) 【等于左移三位,但它超过了8个位,需要取模】
= (1 1011 1000) mod(1 0001 1011)
= (1 1011 1000) ⊕ (1 0001 1011)
= (1010 0011)
.乘法栗子4:(综合例子)
多项式表示:
.(x5+x4+x2+x+1) * (x3 +x)
= (x5+x4+x2+x+1) * x3 +(x5+x4+x2+x+1) * x
= (x7+x5+x+1) + (x6+x5+x3+x2+x)
= x7+x6+x3+x2+1
解释下 m(x) 是哪来的?
博主只找到这个的解释,期待大佬解惑。
总之,m(x)是人为选取的。 O,O
.
.
总结
加法 = 对位异或
乘法:
- 乘完以后,结果不超过GF,直接乘。
- 乘完以后,结果超过GF,再将结果与(1 0001 1011)异或。
注:多项式f * x 在计算机里可直接调用函数 xtime(f)。
.
.
考研阶段,边学边写边复习,数学功底不好,如有错误和不足,欢迎指出。
.
.
.
本文地址:https://blog.csdn.net/weixin_43289702/article/details/108993898
上一篇: 历史上最后一位丞相是谁?他最后结局如何?