CC的博客

没事就爱瞎折腾

0%

Python实现AES加解密

发表于 更新于 分类于

简介

  • 最近实际逆向过程中，经常会遇到AES算法，而且有时也会遇到一些非标准AES或者魔改的AES

  • 本着进一步了解AES算法的态度，决定结合网上各种资料，自己动手实现一次AES加解密，加深自己对AES的了解

  • 当然网上有很多优秀的AES实现了，其中最著名的当属：openssl，openssl包含非常多的密码学算法的实现，而且很多都是性能优化后的实现。一个比较小巧的c语言实现是：https://github.com/kokke/tiny-AES-c

  • python的一些AES实现:

  • 这里再介绍一下python的：pycryptodome库，这个虽然是python库，但底层算法是c写的，所以性能上是非常不错的，可以安装这个库替换python的Crypto库，也可以与Crypto共存。这个库可以作为python中各种加密算法的标准库来使用。

  • 因为这里是以学习为目的，所以本文不考虑任何性能上的问题

开始

  • AES算法总体上可以分为两部分去实现，一部分是：密钥扩展，另一部分是：加解密逻辑

  • 下面首先来实现密钥扩展，这个连接有AES密钥扩展的详细介绍https://www.brainkart.com/article/AES-Key-Expansion_8410/

  • 下面盗用上面提到链接中的两张图，第一张图是AES密钥扩展的实现伪代码实现，第二张图为AES密钥扩展的流程图

    image-20220917152134364

    image-20220917152200906

  • 下面来解析这两张图，首先看图中的这一部分，这张图什么意思呢？这张图表示，将密钥划分为4x4的矩阵，需要注意的点是这个密钥是以列为主顺序(Column-major order)的矩阵，而不是以行为主顺序(Row-major order)的矩阵，这两种矩阵相互转化的实际上就是矩阵转置。密钥的每一列记为w0，w1， w2， w3（w代表word，32位即4字节整数，w0 ... w3视为一个word类型数组）

    • 题外话：像c语言中的二维数组就是以行为主顺序的，不注意这个的话，可能最后实现的"AES"是非标准的AES。实际逆向工作中就有遇到过，密钥和数据输入输出都没转置的情况，如果遇到这种"AES"，如何使用标准AES去实现呢？很简单，只需将密钥、输入、输出都进行矩阵转置即可

    image-20220917152503403

  • 接着来看这部分，这张图又代表什么含义呢？先不看w4，只看w5，w6，w7，可以看到w5 = w1 xor w4，w6 = w2 xor w5， w7 = w3 xor w6 即（wi = wi-4 xor wi-1）。再来看w4部分，下图w3指出的g代表使用g函数处理w3，所以w4 = w0 xor g(w3)。就这样依次类推，以后的w8，w9 ... wi都是这么生成的（其中如果i为4的倍数，则wi-1需要先经过g函数处理后再与wi-4进行异或）

    image-20220917154217910

  • 接着看下面这部分，下图即为上面提到的g函数，这个g函数可以拆分成3部分来看

    image-20220917155050764

  • 首先是下图这个，下图这个代表将word类型循环左移1位如：第0个字节移到最后一位，其余3字节往左移动1位

    image-20220917155512887

  • 接着来看这个，下图B1，B2，B3，B0经过S后得到B1'，B2'，B3'，B0'，S代表S-Box，也就是说这一步操作是将word的每个字节分别经过S-Box替换得到新的word

    image-20220917155804412

  • 最后是这个B1'，B2'，B3'，B0'与RCj，0，0，0异或得到g函数最终输出w'，这个RCj代表什么呢？这个代表着AES的密钥扩展的轮常量Rcon（这些值好像与有限域GF(2^8）上的乘法有关），这个AES轮常量也是word类型数据，而且每个Rcon的右边3个字节总为0，只有第一个字节会随着循环发生改变。Rcon的值为"01 02 04 08 10 20 40 80 1B 36"（有些AES实现中Rcon常量很多，但实际上AES密钥扩展用到的就只有这些）

    image-20220917160008208

    image-20220917160335145

  • 回过头来再看密钥扩展函数的为代码就很容易理解了，第一个循环作用实际上就是按列取密钥数据得到wi，第二个循环就是密钥扩展的主逻辑了，RotWord代表将word的4个字节循环左移1位，SubWord代表将word的每个字节进行S-Box替换，Rcon代表着轮常量数组

    image-20220917152134364

  • 接下来使用python实现AES密钥扩展了，首先定义sbox和i_sbox。sbox和i_sbox相当于互为逆运算，一个字节使用sbox进行字节替换后再用i_sbox进行字节替换得到的还是它本身，反过来也一样。密钥扩展算法里面只用到sbox，加密算法也用到了sbox，解密则用的为i_sbox

    image-20220917190656328

    image-20220917190808814

  • 接着定义轮常量Rcon，注意第0个0x8d实际上并没有用到，这里加上这个主要是后面取值方便，参考：https://github.com/kokke/tiny-AES-c的密钥扩展实现，对于AES 128用到了10个Rcon值，192只用到了其中的8个，256则只用到了7个，Rcon[0]在AES中没有被使用

    image-20220917191346001

    image-20220917191553869

  • 接下来编写sub_word函数，这里为了方便将word直接视为4字节的数组，而不是视为一个32位的整数，代码很简单，就是将word的每个字节通过sbox查表方式替换得到新的字节，最后返回替换后的结果

    image-20220917191830108

  • 类似地可以按以下方式实现rot_word，循环左移1个字节，可以通过取余数的方式来实现

    image-20220917192242734

  • 最后是异或函数xor，将a，b中的每个字节异或得到输出

    image-20220917192445315

  • 定义了上面的运算函数后，就可以编写密钥扩展函数了，总体函数如下

    image-20220917192603229

  • 首先解释下前面部分的作用，因为AES有128、192、256位数之分，所以先根据输入参数判断选用的是哪种，如果为128则定义密钥长度为klen=16字节，nk=4（nk代表原始密钥有多少个4字节的word，nk与轮常量Rcon取值有关），扩展后的密钥长度为176（16+10*16）。因为标准AES的密钥扩展后的密钥前klen字节为原AES密钥，所以轮密钥前klen字节只需复制原来的密钥即可

    image-20220917192723809

  • 接下来看下面部分，"//"代表只保留整数的除法（python中单"/"除法，如果有小数会保留小数），temp按照前面的先取wi-1，如果i为nk的倍数，那么就进行先rot_word，再sub_word，最后再与轮常量rcon_t异或，从前面可知rcon_t数组后3个元素固定为0，第0个元素通过i//nk来确定。最后wi-nk与wi-1异或（因为要扩展到192和256，所以不是wi-4而是wi-nk）

    • 这里需要注意的是如果是AES 256，那么当i%nk == 4时，temp还要再进行一次sub_word运算，这个也是从tiny-AES-c中的实现得知，实际上最前面的密钥扩展描述的是AES 128的密钥扩展，所以这里需要补充一下AES 256密钥扩展

    image-20220917193444822

  • 接下来测试AES 128密钥扩展，以16个00字节为例，密钥扩展后结果如下，这个00得到的密钥扩展结果还是挺有意义的，有时判断一个算法是否为标准AES实现，可以首先通过对比同样为16个00字节密钥时，密钥扩展输出是否与标准AES一致。在实现AES时，也可以通过这种方式，来对比标准AES的结果，看自己实现的是否正确。

    image-20220917195219892

  • 接着来看AES加密部分，同样先来看张图，图来自https://www.brainkart.com/article/The-AES-Encryption-Algorithm_9558/

    image-20220917210513080

  • AES加密每轮循环可以分为SubBytes、ShiftRows、MixColumns、AddRoundKey四个部分（除最后一轮外，最后一轮没有MixColumns）

  • 先来看前两个SubBytes和ShiftRows，这两个顺序其实可以对调（结果一样），SubBytes就是将输入的16个字节每个字节经过sbox替换得到新的16字节

    image-20220917210840858

  • ShifRows有个形象的图，如下图所示，ShifRows就是第0行不变，第1行循环左移1字节，第2行循环左移2字节，第3行循环左移3字节，参考：http://www.moserware.com/2009/09/stick-figure-guide-to-advanced.html

    image-20220917212201020

  • 接着是MixColumns，列混淆有点复杂，右乘一个固定矩阵，其中的运算与有限域GF(2^8)的四则运算有关，参考：https://www.brainkart.com/article/Advanced-Encryption-Standard(AES)-Transformation-Functions_8409/

    image-20220917232817574

    image-20220917232910940

  • 最后是AddRoundKey，AddRoundKey比较容易理解，就是将当前状态state每个字节与下一轮密钥的每个字节异或

  • AES解密的话则是所有操作反过来，每轮循环先AddRoundKey（因为是异或，所以可以用同一个函数），再InvMixColumns，再InvShifRows，最后InvSubBytes，这三个都是与加密的3个变换是相反的

  • 接着可以编写Python代码了，首先是最容易实现的SubBytes和InvSubBytes，只需将每个字节通过查表替换即可

    image-20220917233759724

  • 这里再定义一个矩阵转置函数transpose，之所以要这个函数，就是前面所提到的AES的矩阵是Column-major order，而C语言、Python这些编程语言的数组其实是Row-major order的，所以需要对密钥、输入输出都进行矩阵转置才能与标准AES一致，这个transpose函数用了个最简单粗暴的方法实现

    image-20220917234022205

  • 接着是AddRoundKey，这里接收3个参数，分别为当前循环数cur_round，加解密状态state，轮密钥数组round_key，每次AddRoundKey只需将state与相对应的轮密钥异或即可

    image-20220917233901866

  • 接着是ShiftRows和InvShiftRows，这里同样选择最简单粗暴的方式来实现

    image-20220917234537749

  • 接着是最个人认为AES最难以理解的就是MixColumns和InvMixColumns，这里有限域GF(2^8)乘法直接抄https://gist.github.com/raullenchai/2920069的实现

    image-20220917234654838

  • MixColumns，按照下图的右乘固定矩阵方式，实现如下

    image-20220917234947434

    image-20220917234916382

  • InvMixColumns，按照下图的右乘另一个固定矩阵方式，实现如下

    image-20220917235133997

    image-20220917235225560

  • 从下图可以看出，所用到的两个固定矩阵是互为逆矩阵，所以可以用来加解密

    image-20220917235258295

  • 有了上面这些就可以实现AES加密函数了，如下图所示

    image-20220918110420942

  • 首先来解释前面部分，首先判断key是否为字符串，如果是那么将之转化为bytes类型。然后是判断是否有bits参数，如果没有则根据密钥key长度自动判断bits的值，然后就是调用前面实现的密钥扩展函数key_expansion来生成轮密钥数组，并计算加密循环次数

    image-20220918110440201

  • 接着同样先判断输入是否为字符串，如果是那么先将之转化为bytes类型。然后是将输入进行矩阵每16个字节进行转置，输出也是进行转置，然后就是按每轮循环SubBytes、ShiftRows、MixColumns、AddRoundKey进行（最后一轮循环没有MixColumns）

    image-20220918110457960

  • AES解密跟加密的过程刚好反过来，AddRoundKey的初始轮数是最后一轮，每轮循环的顺序是AddRoundKey、InvMixColumns、InvShiftRows、InvSubBytes

    image-20220918111212449

  • 测试加解密，并与pycryptodome库的结果相对比来判断是否正确实现

    image-20220918111630976

  • 至此，成功用Python实现了AES，本文完整代码：AES.ipynb