欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

AES加密之 有限域GF(2^n)算术 / xtime

程序员文章站 2022-04-06 14:11:34
有限域算术是AES加密算法的必备知识。本文包括,定义,加法,乘法,总结。...

有限域算术是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) 是哪来的?

博主只找到这个的解释,期待大佬解惑。

AES加密之 有限域GF(2^n)算术 / xtime

总之,m(x)是人为选取的。 O,O
.
.

总结

加法 = 对位异或

乘法:

  1. 乘完以后,结果不超过GF,直接乘。
  2. 乘完以后,结果超过GF,再将结果与(1 0001 1011)异或。

注:多项式f * x 在计算机里可直接调用函数 xtime(f)。

.
.
考研阶段,边学边写边复习,数学功底不好,如有错误和不足,欢迎指出。
.
.
.

本文地址:https://blog.csdn.net/weixin_43289702/article/details/108993898