AES-Rijndael有限域(Galois Field)GF(2^8)运算的介绍与实现

1.前言

最近群里有同学问了AES加密相关的问题,因为他在做微信小程序开发,小程序里面对敏感数据的加密采用了 AES -128-CBC的对称加密方式。所以想写一篇介绍AES-Rijndael算法的文章,此篇文章为AES作铺垫,因为它的列混淆算法的运算操作用到了有限域的概念。

2.有限域的介绍

Galois Field 在国内有两个翻译别名:伽罗华域、伽罗瓦域(我也不知道为什么没能统一一个翻译)。在数学中,有限域是一个包含有限元素的域。通过GF(2^M)来表示域中含有2^M个元素。每一个域中有多个本原多项式,当M=8时,常见的本原多项式为P(x)=x^8+x^4+x^3+x^2+1,AES中的本原多项式为不可约多项式(irreducible polynomial):P(x)=x^8+x^4+x^3+x^1+1。

3.有限域的加法与乘法运算

有限域中的运算方式需要先把数值转化成多项式的形式,然后再进行相关运算。其中加法操作可以直接进行运算。

加法:计算机异或运算

加法例子:4+3

展开多项式为: x^2 + (x^1 + x^0) => 2^2 + 2^1 + 1 => 4 + 2 + 1 => 4 ^ 2 ^ 1 = 7

直接计算:4^3 = 7

乘法:通过乘法结合律展开多项式,如果x的最高指数大于7,那么需要对本原多项式取余数(初二多项式除法运算),否则就是展开后的多项式做加法操作。

取余操作有一个算法,参考《密码编码学与网络安全学原理》一书中提到的公式:

已知GF(2^8)最长的多项式f(x)=b7*x^7+b6*x^6+b5*x^5+b4*x^4+b3*x^3+b2*x^2+b1*x^1+b0*x^0

x*f(x)= b7*x^8+b6*x^7+b5*x^6+b4*x^5+b3*x^4+b2*x^3+b1*x^2+b0*x^1

x*f(x)的情况如下:

当b7=0时,最高指数为7不需要取余,直接做异或加法运算。

当b7=1时,最高指数为8,大于7,则需要取m(x)的余数,推导如下:

f(x) = ( b7*x^8+b6*x^7+b5*x^6+b4*x^5+b3*x^4+b2*x^3+b1*x^2+b0*x^1 )mod m(x);

这里有另外一个等式:x^8 mod m(x) = [m(x) – x^8] = (x^4 + x^3 + x + 1)

所以根据上面的等式可以化简f(x) = b6*x^7+b5*x^6+b4*x^5+b3*x^4+b2*x^3+b1*x^2+b0*x^1 + x^4 + x^3 + x +1

而x^4 + x^3 + x + 1 就是十六进程的0x1B(因为2^4+2^3+2+1=27),因此本原多项式取余的操作就等价于 异或本原多项式。公式如下:

图片来源: 《密码编码学与网络安全学原理》 第88页

高阶的x可以重复使用这个公式,在程序实现部分会详细介绍下。

乘法例子:7*4

展开多项式为:(x^2+x^1+x^0)*(x^2) => x^4 + x^2 + x^2 => 2^4 + 2^2 + 2^2 = 16 ^ 4 ^ 4 = 16

乘法例子:130*3

展开多项式为:(x^7+x^1)*(x^1+x^0) => x^8 + x^7 + x^1 + x^1 => x^8 + x^7 +( x^8+x^4+x^3+x^1+x^0 ) ( 不可约多项式 ) => x^7 + x^4+x^3+x^1+x^0 => 2^7 + 2^4 + 2^3 + 2^1 + 1 = 128 ^ 16 ^ 8 ^ 2 ^ 1 = 155

4.程序的实现

对于任意两个数a和b做乘法运算,基于 GF(2^8) 的条件下,我们知道最后展开的多项式都是2^N之和,N=[0,8]。因此,多项式可能值为2^0=1,2^1=2,2^2=4,2^3=8,2^4=16,2^5=32,2^6=64,2^7=128,2^8=256。换算成二进制就是:

00000001 => 0x01

00000010 => 0x02

00000100 => 0x04

00001000 => 0x08

00010000 => 0x10

00100000 => 0x20

01000000 => 0x40

10000000 => 0x80

所以对于任意字节数a,和它相乘的所有可能为:a*x = a*(0x80+0x40+0x20+0x10+0x08+0x04+0x02+0x01)

比如:0x57 * 0x13

0x57 * 0x13 = 0x57*(0x01+0x02+0x10)

因为0x13 = 2^4+2^1+2^0 = 0x10 + 0x02 + 0x01 所以我们只要分别对a进行0x10、0x02、0x01的乘积再进行累加操作。(如果遇到高阶,还是把0x01-0x80所有乘积都算出来,因为高阶的乘法依赖低阶乘积的结果)

0x57 * 0x01 = (x^6 + x^4 + x^2 + x^1 + x^0 )*x^0 = x^6 + x^4 +x^2 + x^1 + x^0 = 64 ^ 16 ^ 4 ^ 2 ^ 1 = 0x57

0x57*0x02 = (x^6 + x^4 + x^2 + x^1 + x^0 ) *x^1 = x^7 + x^5 + x^3 +x^2 + x^1 = 128 ^ 32 ^ 8 ^ 4 ^ 2 = 0xAE

0x57*0x10 = (x^6 + x^4 + x^2 + x^1 + x^0 ) *x^4 = x^10 + x^8 + x^6 + x^5 + x^4 = (这里我们遇到了x的高阶情况,高阶的计算方式参考第二部分图片中的x*f(x)的那个公式)

所以将0x57*0x10 转成多项式为:(x^4)*0x57 = ((x^3)*0x57)*(x^1) = (((x^2)*0x57)*x^1)*(x^1)=( (((x^1)*0x57)*x^1)*(x^1) )*x^1即((0x57*0x02)*x^1)*(x^1)*(x^1)

因为上面的0x57*0x02=0xAE,即多项式:x^7+x^5+x^3+x^2+x^1,所以我们接着计算(x*( x^7+x^5+x^3+x^2+x^1 ))*x*x 就可以了,继续往下推算:

(x^8+x^6+x^4+x^3+x^2)*x*x

因为最高指数8大于7,所以进行取余操作,取本原多项式的模为:(x^8+x^6+x^4+x^3+x^2+x^8+x^4+x^3+x^1+1)*x*x

(x^6+x^2+x+1)*x*x

(x^7+x^3+x^2+x)*x

x^8+x^4+x^3+x^2

因为最高指数8大于7,所以进行取余操作,取本原多项式的模为:

(x^8+x^4+x^3+x^2+ x^8+x^4+x^3+x^1+1 )

x^2+x+1

4 ^ 2 ^ 1 = 0x07

所以 0x57 * 0x13 = 0x57*(0x01+0x02+0x10) = 0x57*0x01 + 0x57*0x02 + 0x57*0x10 = 0x57 + 0xAE + 0x07 = 0xFE

根据上面的推算我们就可以设计出算法了,对于x*f(x)实质上,x=2的时候,乘以2在计算机里就是左移的操作,我们将上面的计算用二进制表示为:

0x57 * 0x01 = ‭01010111‬ * ‭00000001 = 01010111 = 0x57

0x57 * 0x02 = (0x57*0x01)*0x02 = (0x57*0x01) << 1 = 10101110 = 0xAE

0x57 * 0x04 = (0x57*0x02) << 1 =‭ 101011100‬‬ (这里b7=1,所以进行异或操作,先去掉第9位的1) = (101011100 & 0xFF) ^ 0x1B = 0x47

0x57 * 0x08 = (0x57*0x04) << 1 = ‭10001110‬ = 0x8E

0x57*0x10 = (0x57*0x08) << 1 = ‭100011100‬ (b7=1,同上进行异或操作) = ‭(100011100 &0xFF) ^ 0x1B = 7

算法描述:

第一步:计算0x01-0x10的所有结果集

if (($a << 1) & 0x100) $res[i] = (($a << 1) & 0xFF) ^ 0x1B

else $res[i] = $a << 1

第二步:计算$b由哪几个结果集组成

第三步:异或求和

<?php
function aes_multi($a, $b=0)
{
    if ($a >= 2**8 || 2**8 <= $b) {
        exit('只支持GF(2^8)域的计算');
    }
    $binMulti = [];
    $result = 0;
    for($i = 0; $i < 8; $i++)
    {
        $a = ($a & 0x100) ? (($a & 0xFF) ^ 0x1B) : $a;
        $binMulti[] = $a;
        $a = $a << 1;
    }

    $binString = str_pad(base_convert($b, 10, 2), 8, 0, STR_PAD_LEFT);

    for($i = 0; $i < 8; $i++) {
        if ($binString{$i} === '1') {
            $pos = strlen(substr($binString, $i)) - 1;
            $result ^= $binMulti[$pos];
        }
    }
    return $result;
}

var_dump(aes_multi(0x57, 0x13));

5.参考

官方文档

https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.197.pdf

《密码编码学与网络安全学原理》 验证码: fbhn

https://pan.baidu.com/s/1ZU_HLG3TYQVa1dvS41q3qw
如无特殊说明,文章均为本站原创,转载请注明出处。如发现有什么不对的地方,希望得到您的指点。

发表评论

电子邮件地址不会被公开。 必填项已用*标注