草庐IT

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

幽幽古道，乾坤相伴。 2023-03-28 原文

1.前言

 最近做微信小程序开发，小程序里面对敏感数据的加密采用了 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由哪几个结果集组成
第三步：异或求和

4.1  PHP实现AES列混合有限域乘积计算 

PHP实现AES列混合有限域乘积计算

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 

AES-RijndaelRijndaeldiv0x本原PHP

有关AES-Rijndael有限域(Galois Field)GF(2^8)运算的介绍与实现（PHP版）的更多相关文章

  1. ruby - 如何根据特征实现 FactoryGirl 的条件行为 - 2

    我有一个用户工厂。我希望默认情况下确认用户。但是鉴于unconfirmed特征，我不希望它们被确认。虽然我有一个基于实现细节而不是抽象的工作实现，但我想知道如何正确地做到这一点。factory:userdoafter(:create)do|user,evaluator|#unwantedimplementationdetailshereunlessFactoryGirl.factories[:user].defined_traits.map(&:name).include?(:unconfirmed)user.confirm!endendtrait:unconfirmeddoenden

  2. 华为OD机试用Python实现 -【明明的随机数】 2023Q1A - 2

    华为OD机试题本篇题目：明明的随机数题目输入描述输出描述：示例1输入输出说明代码编写思路最近更新的博客华为od2023|什么是华为od，od薪资待遇，od机试题清单华为OD机试真题大全，用Python解华为机试题|机试宝典【华为OD机试】全流程解析+经验分享,题型分享,防作弊指南华为o

  3. Unity 热更新技术 | （三） Lua语言基本介绍及下载安装 - 2

    ?博客主页：https://xiaoy.blog.csdn.net?本文由呆呆敲代码的小Y原创，首发于CSDN??学习专栏推荐：Unity系统学习专栏?游戏制作专栏推荐：游戏制作?Unity实战100例专栏推荐：Unity实战100例教程?欢迎点赞?收藏⭐留言?如有错误敬请指正！?未来很长，值得我们全力奔赴更美好的生活✨------------------❤️分割线❤️-------------------------

  4. 基于C#实现简易绘图工具【100010177】 - 2

    C#实现简易绘图工具一.引言实验目的:通过制作窗体应用程序(C#画图软件),熟悉基本的窗体设计过程以及控件设计,事件处理等,熟悉使用C#的winform窗体进行绘图的基本步骤,对于面向对象编程有更加深刻的体会.Tutorial任务设计一个具有基本功能的画图软件**·包括简单的新建文件,保存,重新绘图等功能**·实现一些基本图形的绘制,包括铅笔和基本形状等,学习橡皮工具的创建**·设计一个合理舒适的UI界面**注明:你可能需要先了解一些关于winform窗体应用程序绘图的基本知识,以及关于GDI+类和结构的知识二.实验环境Windows系统下的visualstudio2017C#窗体应用程序三.

  5. ruby - Ruby 中的单 block AES 解密 - 2

    我需要尝试一些AES片段。我有一些密文c和一个keyk。密文已使用AES-CBC加密，并在前面加上IV。不存在填充，纯文本的长度是16的倍数。所以我这样做:aes=OpenSSL::Cipher::Cipher.new("AES-128-CCB")aes.decryptaes.key=kaes.iv=c[0..15]aes.update(c[16..63])+aes.final它工作得很好。现在我需要手动执行CBC模式，所以我需要单个block的“普通”AES解密。我正在尝试这个:aes=OpenSSL::Cipher::Cipher.new("AES-128-ECB")aes.dec

  6. MIMO-OFDM无线通信技术及MATLAB实现（1）无线信道：传播和衰落 - 2

     MIMO技术的优缺点优点通过下面三个增益来总体概括：阵列增益。阵列增益是指由于接收机通过对接收信号的相干合并而活得的平均SNR的提高。在发射机不知道信道信息的情况下，MIMO系统可以获得的阵列增益与接收天线数成正比复用增益。在采用空间复用方案的MIMO系统中，可以获得复用增益，即信道容量成倍增加。信道容量的增加与min(Nt,Nr)成正比分集增益。在采用空间分集方案的MIMO系统中，可以获得分集增益，即可靠性性能的改善。分集增益用独立衰落支路数来描述，即分集指数。在使用了空时编码的MIMO系统中，由于接收天线或发射天线之间的间距较远，可认为它们各自的大尺度衰落是相互独立的，因此分布式MIMO

  7. 【Java入门】使用Java实现文件夹的遍历 - 2

    遍历文件夹我们通常是使用递归进行操作，这种方式比较简单，也比较容易理解。本文为大家介绍另一种不使用递归的方式，由于没有使用递归，只用到了循环和集合，所以效率更高一些！一、使用递归遍历文件夹整体思路1、使用File封装初始目录，2、打印这个目录3、获取这个目录下所有的子文件和子目录的数组。4、遍历这个数组，取出每个File对象4-1、如果File是否是一个文件，打印4-2、否则就是一个目录，递归调用代码实现publicclassSearchFile{publicstaticvoidmain(String[]args){//初始目录Filedir=newFile("d:/Dev");Datebeg

  8. ruby - Arrays Sets 和 SortedSets 在 Ruby 中是如何实现的 - 2

    通常，数组被实现为内存块，集合被实现为HashMap，有序集合被实现为跳跃列表。在Ruby中也是如此吗？我正在尝试从性能和内存占用方面评估Ruby中不同容器的使用情况 最佳答案 数组是Ruby核心库的一部分。每个Ruby实现都有自己的数组实现。Ruby语言规范只规定了Ruby数组的行为，并没有规定任何特定的实现策略。它甚至没有指定任何会强制或至少建议特定实现策略的性能约束。然而，大多数Rubyist对数组的性能特征有一些期望，这会迫使不符合它们的实现变得默默无闻，因为实际上没有人会使用它:插入、前置或追加以及删除元素的最坏情况步骤复

  9. ruby - 使用 AES 的 Rails 加密，过于复杂 - 2

    我在加密来self正在使用的第三方供应商的值时遇到问题。他们的指令如下:1)Converttheencryptionpasswordtoabytearray.2)Convertthevaluetobeencryptedtoabytearray.3)Theentirelengthofthearrayisinsertedasthefirstfourbytesontothefrontofthefirstblockoftheresultantbytearraybeforeencryption.4)EncryptthevalueusingAESwith:1.256-bitkeysize,2.25

  10. ruby - "public/protected/private"方法是如何实现的，我该如何模拟它？ - 2

    在ruby中，你可以这样做:classThingpublicdeff1puts"f1"endprivatedeff2puts"f2"endpublicdeff3puts"f3"endprivatedeff4puts"f4"endend现在f1和f3是公共(public)的，f2和f4是私有(private)的。内部发生了什么，允许您调用一个类方法，然后更改方法定义？我怎样才能实现相同的功能(表面上是创建我自己的java之类的注释)例如...classThingfundeff1puts"hey"endnotfundeff2puts"hey"endendfun和notfun将更改以下函数定

随机推荐