一、伽罗瓦域

如果m等于一个素数p的n次幂（n为正整数），即：m = p^n时，才存在一个m阶的域。

n等于1时,叫做素域(Prime Field)
n >= 2时，叫做扩展域(Field Extension)
这两种情况加法单位元都为0，乘法单位元1.

都是循环群
素域的运算为模加，模乘
扩展域的运算为模加、素多项式基础上的多项式运算

1、为何必须是这种形式？

同樣大小的兩個有限域一定是同構的。

当m=p为素数时，才能保证集合中的所有的元素都有乘法逆元(0除外)。即对于域中的任一个元素a，总能在域中找到另外一个元素b，使得a*b mod p 等于1。

m = p^n时,使用多项式运算来保证域的条件

因為域與域之間的函數一定是單射，所以F_p一定是嵌在F_p^r裡的，於是他張開了一個線性空間。
$$GF(2^8)$$如果是F_2上一個域的話，就可以很簡單看成一個八次元的向量，每個坐標都是0或1。

2、$$G(2^n)$$

G(2),加减法 xor、 乘法 and
$$G(2^n)$$,加减法 xor 、 乘法 扩展欧几里得算法(利用生成元乘除)

二、扩展域

1、用多项式表达的扩展域

对于$$GF(2^8)$$来说，我们并不能直接用0-255这256个数字来表示了，取而代之的方法，是使用多项式。$$GF(2^8)$$中的每一个元素，都用形如：
$$a_7x^7 + a_6x^6 + a_5x^5 + ... + a_1x + a_0$$
这样的多项式表达。其中，$$a_0 - a_7$$是多项式的系数，它们只能从GF(2)中取值。这样，$$a_0 - a_7$$ 就代表了一个字节中的对应bit。并且，这些系数的运算法则，也使用刚才GF(2)中提到的加法和乘法法则。来看个例子：下面这两个，都是$$GF(2^8)$$中的元素：
$$A(x) = x^7 + x^5 + x^3 + 1$$
$$B(x) = x^2 + 1$$

2、多项式加法

按照之前的约定，它们分别表示二进制数的10101001和00000101。接下来，为了在$$GF(2^8)$$中计算A(x) + B(x)，我们只要按位依次执行GF(2)中的加法（计算机中的xor）就好了，也就是说它等于：

  1 0 1 0 1 0 0 1
+ 0 0 0 0 0 1 0 1
------------------
  1 0 1 0 1 1 0 0

把这个结果对应到多项式，就是$$x^7 + x^5 + x^3 + x^2$$而这个多项式对应的字节，是0xab。

3、多项式减法等于加法，因为逆元就是自己

无所谓的减法(减法就等于加法)，或者负系数。所以，$$x^4 - x^4$$就等于$$x^4 + x^4$$。$$-x^3$$就是$$x^3$$。

4、多项式乘法

但$$GF(2^8)$$多项式的乘法，就麻烦一些了。为了计算A(x)B(x)，我们先按照普通代数的计算方法展开多项式：
$$A(x)B(x) = (x^7 + x^5 + x^3 + 1)(x^2 + 1)$$
$$\quad = x^9 + x^7 + x^5 + x^2 + x^7 + x^5 + x^3 + 1$$
$$\quad = x^9 + 2x^7 + 2x^5 + x^3 + x^2 + 1$$
然后，把这个多项式的系数对2取模：

    x^9 + 2x^7 + 2x^5 + x^3 + x^2 + 1
mod 2
--------------------------------------
    x^9                 x^3 + x^2 + 1

这样，就可以得到$$x^9 + x^3 + x^2 + 1$$。但问题是$$x^9$$已经超过了$$GF(2^8)$$可以表达的范围，它也对应不到计算机的一个字节中的bit。显然这个结果是不对的，怎么办呢？
其实，思路和刚才在处理GF(2)加法结果的时候是类似的。既然我们要把结果限定在$$x^8$$以内，那就把多项式对$$x^8$$取模不就行了。道理是这么个道理，不过这个取模的多项式，可不是随便选的。
AES的设计者Vincent Rijmen 使用了一个经典的不可约多项式：$$P(x) = x^8 + x^4 + x^3 + x + 1$$。
什么是不可约呢？就是说，$$P(x)$$不能表示为$$GF(2^8)$$域中两个多项式的乘积。这和自然数中的素数是类似的，因此，$$P(x)$$也叫素多项式。
由于P(x)的最高次幂是8，因此对P(x)取模，结果就一定会落在$$GF(2^8)$$里了，我们来算一下。先算$$xP(x)$$让P(x)升到9次幂：
$$xP(x) = x^9 + x^5 + x^4 + x^2 + x$$
其次，用$$x^9 + x^3 + x^2 + 1 - x(Px)$$

  x^9 +             x^3 + x^2     + 1
- x^9 + x^5 + x^4 +       x^2 + x
--------------------------------------
        x^5 + x^4 + x^3       + x + 1

这样，得到的结果就落在$$GF(2^8)$$里了，它表示的二进制数是00111011，这就是$$GF(2^8)$$中$$A(x)B(x)$$的运算结果。
这个过程，数学上使用多项式长除法，形如：


简化计算的方法，避免长除法，如下，因为：
$$ x^8\ (mod\ P(x)) = P(x) -x^8 = x^4+ x^3 +x^2 + x1$$
将高次多项式的$$x^8$$替换为$$x^4 + x^3 + x^2 +1$$而不用进行除法取模计算
虽然可以通过替换减少除法计算，但还是过于复杂。因此通过生成元查表来计算。

int table[256];
int i;

table[0] = 1;//g^0
for(i = 1; i < 255; ++i)//生成元为x + 1
{
    //下面是m_table[i] = m_table[i-1] * (x + 1)的简写形式
    table[i] = (table[i-1] << 1 ) ^ table[i-1];
 
    //最高指数已经到了8，需要模上m(x)
    if( table[i] & 0x100 )
    {
        table[i] ^= 0x11B;//用到了前面说到的乘法技巧-替换
    }
}

详见下节

5、求多项式的逆元（用于计算乘除法）

在域GF(2^w)中2总是生成元。

了解了多项式乘法之后，我们就能计算$$GF(2^8)$$中任意一个多项式A(x)的逆元了，AES加密算法需要这个值。要说明的是，选取的素多项式不同，$$GF(2^8)$$中元素的逆元也不同。这里，我们就用刚才说到的P(x)举例了。
对于给定的一个$$GF(2^8)$$中的多项式A(x)，如果A(x)B(x)的结果对P(x)取模等于1，那么B(x)就是A(x)的逆元了。那该怎么计算这个B(x)呢？
第一种方法，当然就是暴力穷举。用$$GF(2^8)$$中的每一个元素分别和A(x)计算；
第二种方法，来自于一个有趣的现象。$$GF(2^8)$$中的每一个非0多项式，都可以表示成(x+1)的n次幂，这里0<=n<=254，例如：
$$(x+1)^0 = 1$$
$$(x+1)^1 = x+1$$
$$(x+1)^2 = x^2+1$$
...
$$(x+1)^{254} = x^7+x^6+x^5+x^4+x^3+x^2+x$$
注意这里我们执行的是GF(2)中的加法和乘法。并且，当n从255开始，就又会用和之前同样的顺序遍历$$GF(2^8)$$中的多项式。
$$(x+1)^{255} = 1$$
$$(x+1)^{256} = x+1$$
...
正是由于这种特性，(x+1)有了一个形象的名字，叫做生成元。有了生成元之后，我们可以把$$GF(2^8)$$中的每一个多项式和它对应的生成元的幂保存成一个映射表。接下来，对于给定的A(x)，如果B(x)是A(x)的逆元，则一定有下面的关系成立：
$$A(x)B(x) = (x+1)^a (x+1)^b = (x+1)^(a+b) = 1 (mod\ P(x))$$
于是，我们只要根据之前创建的映射表，查到A(x)对应的幂a，然后用255-a计算出b，再从表中查出b对应的多项式，就是A(x)的逆元了。

6、利用生成元，查表计算乘除法

乘除法同理，只要查表获取指数，指数相加减mod255后，反查的原数即可。
常用本原多项式 ：
$$GF(2^3) : \ x^3+x+1$$
$$GF(2^4) : \ x^4+x+1$$
$$GF(2^8) : \ x^8+x^4+x^3+x^2+1$$
$$GF(2^{16}) : \ x^{16}+x^{12}+x^3+x+1$$
$$GF(2^{32}) : \ x^{32}+x^{22}+x^2+x+1$$
$$GF(2^{64}) : \ x^{64}+x^4+x^3+x+1$$

通过本原多项式生成元素
设P(x)是$$GF(2^w)$$上的某一个本原多项式，$$GF(2^w)$$的元素产生步骤是：
1、给定一个初始集合，包含0,1和元素x，即 {0,1,x}；
2、将这个集合中的最后一个元素，即x，乘以x，如果结果的度大于等于w，则将结果mod P(x)后加入集合；
3、直到集合有2^w个元素，此时最后一个元素乘以x再mod P(x)的值等于1。

例如，GF(2^4)含有16个元素，本原多项式为P(x)=x^4+x+1，除了 0、1外，另外14个符号均由本原多项式生成。
注意到x^14=x^3+1，此时计算x^15=x^14x=(x^3+1)x=x^4+x=1，生成结束。

注意：多项式0 ，是无法用生成元生成的。$$g^0$$等于多项式1，而不是 0。
根据上文的$$GF(2^4)$$的元素表示，生成gflog表和gfilog表如下：

查表进行乘法和除法运算的例子
在$$GF(2^4)$$域上的乘法和除法，已知$$2^w-1 = 2^4 -1 = 15$$：
乘法：

7 * 9 = gfilog[gflog[7] + gflog[9]] = gfilog[10 + 14]
   = gfilog[24 mod 15] = gfilog[9] = 10

除法：

13 / 11 = gfilog[gflog[13] - gflog[11]] =  gfilog[13 - 7] = gfilog[6] = 12

生成gflog,gfilog的python 代码

# coding=UTF-8
# key : value => w : primitive_polynomial
primitive_polynomial_dict = {4: 0b10011,                            # x**4  + x     + 1
                             8: (1 << 8) + 0b11101,                 # x**8  + x**4  + x**3 + x**2 +1
                             16: (1 << 16) + (1 << 12) + 0b1011,    # x**16 + x**12 + x**3 + x    + 1
                             32: (1 << 32) + (1 << 22) + 0b111,     # x**32 + x**22 + x**2 + x    + 1
                             64: (1 << 64) + 0b11011                # x**64 + x**4  + x**3 + x    + 1
                             }

def make_gf_dict(w):
    gf_element_total_number = 1 << w
    primitive_polynomial = primitive_polynomial_dict[w]

    gfilog = [1]  # g(0) = 1
    for i in xrange(1, gf_element_total_number - 1):
        temp = gfilog[i - 1] << 1  # g(i) = g(i-1) * g
        if temp & gf_element_total_number:  # if overflow, then mod primitive polynomial
            temp ^= primitive_polynomial  # mod primitive_polynomial in GF(2**w) == XOR
        gfilog.append(temp)
 
    assert (gfilog[gf_element_total_number - 2] << 1) ^ primitive_polynomial
    gfilog.append(None)
 
    gflog = [None] * gf_element_total_number
    for i in xrange(0, gf_element_total_number - 1):
        gflog[gfilog[i]] = i
 
    print "{:>8}\t{:>8}\t{:>8}".format("i", "gfilog[i]", "gflog[i]")
    for i in xrange(0, gf_element_total_number):
        print "{:>8}\t{:>8}\t{:>8}".format(i, gfilog[i], gflog[i])

if __name__ == "__main__":
   make_gf_dict(4)

来源参考：
https://boxueio.com/series/let-us-build-an-apn-provider/ebook/562
https://blog.csdn.net/shelldon/article/details/54729687

• dx版本、openGL、Vulkan与游戏
• vc++小贴士
• MinHook--CCKa_max 的Directx-11-example(64)
• c++ hookd3d imgui 一步步操作（艾鱼）
• mediapipe win10 编译、运行命令说明

发表新评论 取消回复

发送