Mas0n
mailto:MasonShi@88.com
翻车鱼

关于AES算法的实现与流程

关于AES算法的实现与流程

这篇本来是放在另一个笔记网站里的,但是因为gridea不支持mathJax,强迫症犯了,移到了这里。

随便记了些要点,算是简单了解一下AES算法的流程实现与细节吧

算法流程

https://cdn.shi1011.cn/2021/09/9a240448c3d64d81b8d02f8d9f4ba59e.png?imageMogr2/format/webp/interlace/0/quality/90|watermark/2/text/wqlNYXMwbg/font/bXN5aGJkLnR0Zg/fontsize/14/fill/IzMzMzMzMw/dissolve/80/gravity/southeast/dx/5/dy/5

用图说话就是这样一个流程,但是我不喜欢看图,所以我们来看伪代码实现

加密流程

https://cdn.shi1011.cn/2021/09/82a4c419da0a3996a17691747ce650ca.png?imageMogr2/format/webp/interlace/0/quality/90|watermark/2/text/wqlNYXMwbg/font/bXN5aGJkLnR0Zg/fontsize/14/fill/IzMzMzMzMw/dissolve/80/gravity/southeast/dx/5/dy/5

解密流程

https://cdn.shi1011.cn/2021/09/5c26a7da540a32f7d12e8b432ce495c4.png?imageMogr2/format/webp/interlace/0/quality/90|watermark/2/text/wqlNYXMwbg/font/bXN5aGJkLnR0Zg/fontsize/14/fill/IzMzMzMzMw/dissolve/80/gravity/southeast/dx/5/dy/5

这是AES加密的核心算法,分为四部分

  • SubBytes(字节代替)
  • ShiftRows(行移位)
  • MixColumns(列混淆)
  • AddRoundKey(轮密钥加)

下面分别介绍

SubBytes

字节代替很简单,仅是一个简单的查表动作。

下图就是一张标准的S-box表

https://cdn.shi1011.cn/2021/09/47785d3f1137b6459c1b82d63edb4be4.png?imageMogr2/format/webp/interlace/0/quality/90|watermark/2/text/wqlNYXMwbg/font/bXN5aGJkLnR0Zg/fontsize/14/fill/IzMzMzMzMw/dissolve/80/gravity/southeast/dx/5/dy/5

映射方式:把该字节的高4位作为行值,低4位作为列值,以这些行列值作为索引从S盒中对应位置取出元素作为输出。例如,十六进制数95所对应的S盒的行值是9,列值是5,S盒中在此位置的值是2A,相应的95被映射为2A

下图为标准的逆S-box表,它与S-box相互对应,例如:十六进制数12在S-box中对应c9,将c9映射到InvS-Box对应12,即两者互逆。

https://cdn.shi1011.cn/2021/09/e557053d456c680b37aca9ba7a5e1a7c.png?imageMogr2/format/webp/interlace/0/quality/90|watermark/2/text/wqlNYXMwbg/font/bXN5aGJkLnR0Zg/fontsize/14/fill/IzMzMzMzMw/dissolve/80/gravity/southeast/dx/5/dy/5

ShiftRows

顾名思义,行移位,就是左移右移,用于提供算法的扩散性

在加密时,使用正向行移位

其原理图如下。其中:第一行保持不变,第二行循环左移8比特,第三行循环左移16比特,第四行循环左移24比特。

https://cdn.shi1011.cn/2021/09/d7421a839f165c705bbd2a920392cf9a.png?imageMogr2/format/webp/interlace/0/quality/90|watermark/2/text/wqlNYXMwbg/font/bXN5aGJkLnR0Zg/fontsize/14/fill/IzMzMzMzMw/dissolve/80/gravity/southeast/dx/5/dy/5

而逆向行移位即是相反的操作。即:第一行保持不变,第二行循环右移8比特,第三行循环右移16比特,第四行循环右移24比特。

https://cdn.shi1011.cn/2021/09/0ef164604d9d6188f2fb1e0cccc80fbf.png?imageMogr2/format/webp/interlace/0/quality/90|watermark/2/text/wqlNYXMwbg/font/bXN5aGJkLnR0Zg/fontsize/14/fill/IzMzMzMzMw/dissolve/80/gravity/southeast/dx/5/dy/5

MixColumns

列混淆在AES算法中是最复杂的一部分。其利用GF(\({2^8}\))域上算术特性的一个代替,同样用于提供算法的扩散性

其正向列混淆的原理图如下

https://cdn.shi1011.cn/2021/09/78c2a5abf71f3f47dac7fedaec57ba57.png?imageMogr2/format/webp/interlace/0/quality/90|watermark/2/text/wqlNYXMwbg/font/bXN5aGJkLnR0Zg/fontsize/14/fill/IzMzMzMzMw/dissolve/80/gravity/southeast/dx/5/dy/5

要注意的是这里的并不是通常意义上的乘法与加法,而是定义在伽罗华域上的二元运算

代表模二加法,相当于异或运算。

则为伽罗华域乘法,表示为GMul,则上式运算可以表示为:

\(s’_{0,c} = GMul(2, s_{0,c}) \bigoplus GMul(3,s_{1,c}) \bigoplus s_{3,c}\)

\(s’_{1,c} = s_{0,c} \bigoplus GMul(2,s_{1,c}) \bigoplus GMul(3,s_{2,c}) \bigoplus s_{3,c}\)

\(s’_{2,c} = s_{0,c} \bigoplus s_{1,c} \bigoplus GMul(2,s_{2,c}) \bigoplus GMul(3,s_{3,c})\)

\(s’_{3,c} = GMul(3,s_{0,c}) \bigoplus s_{1,c} \bigoplus s_{2,c} \bigoplus GMul(2,s_{3,c})\)

https://cdn.shi1011.cn/2021/09/c46ba3ca78044ab7815b8c3cca9e2665.png?imageMogr2/format/webp/interlace/0/quality/90|watermark/2/text/wqlNYXMwbg/font/bXN5aGJkLnR0Zg/fontsize/14/fill/IzMzMzMzMw/dissolve/80/gravity/southeast/dx/5/dy/5

同样的,逆向列混淆原理如下图所示

https://cdn.shi1011.cn/2021/09/60fc26371de09f268f967ba71c14534a.png?imageMogr2/format/webp/interlace/0/quality/90|watermark/2/text/wqlNYXMwbg/font/bXN5aGJkLnR0Zg/fontsize/14/fill/IzMzMzMzMw/dissolve/80/gravity/southeast/dx/5/dy/5

由于

\(\begin{bmatrix} 0e & 0b & 0d & 09 \\ 09 & 0e & 0b & 0d \\ 0d & 09 & 0e & 0b \\ 0b & 0d & 09 & 0e \\\end{bmatrix} \begin{bmatrix} 02 & 03 & 01 & 01 \\ 01 & 02 & 03 & 01 \\ 01 & 01 & 02 & 03 \\ 03 & 01 & 01 & 02 \\\end{bmatrix}=\begin{bmatrix} 01 & 00 & 00 & 00 \\ 00 & 01 & 00 & 00 \\ 00 & 00 & 01 & 00 \\ 00 & 00 & 00 & 01 \\\end{bmatrix}\)

说明两个矩阵互逆,经过一次逆向列混淆后即可恢复原文。

AddRoundKey

轮密钥加较简单,其依据的原理是“任何数和自身的异或结果为0”。加密过程中,每轮的输入与轮子密钥异或一次;因此,解密时再异或上该轮的轮子密钥即可恢复。

\([s’_{0,c}, s’_{1,c}, s’_{2,c}, s’_{3,c}] = [s_{0,c}, s_{1,c}, s_{2,c}, s_{3,c}] \bigoplus [\omega_{round*Nb+c}] \quad for \ 0 \le c < Nb\)

https://cdn.shi1011.cn/2021/09/69e4a960b5da1290024393c1f44bddbc.png?imageMogr2/format/webp/interlace/0/quality/90|watermark/2/text/wqlNYXMwbg/font/bXN5aGJkLnR0Zg/fontsize/14/fill/IzMzMzMzMw/dissolve/80/gravity/southeast/dx/5/dy/5

Key Expansion

密钥扩展算法的原理图如下,相对简单,这里就不再赘述了

https://cdn.shi1011.cn/2021/09/2f9cbca67e6abe04c1b0da8d3e0f5aba.png?imageMogr2/format/webp/interlace/0/quality/90|watermark/2/text/wqlNYXMwbg/font/bXN5aGJkLnR0Zg/fontsize/14/fill/IzMzMzMzMw/dissolve/80/gravity/southeast/dx/5/dy/5

下面是伪代码的实现

https://cdn.shi1011.cn/2021/09/04de00e7db9a9d90ef6761c37aa55c87.png?imageMogr2/format/webp/interlace/0/quality/90|watermark/2/text/wqlNYXMwbg/font/bXN5aGJkLnR0Zg/fontsize/14/fill/IzMzMzMzMw/dissolve/80/gravity/southeast/dx/5/dy/5

一些脚本

Sbox2InvSbox

正常情况下AES拥有对应不变的Sbox和InvSbox,对于CTF而言,出题者会对算法进行自定义,以达到混淆,加大破解难度。改变Sbox就是较为常见的修改方式,但同时要清楚,在实际应用过程中,修改Sbox可能会导致算法变得不安全。

下面是一份通过Sbox得到InvSbox的脚本

# -*- coding:utf-8 -*-
"""
@Author: Mas0n
@File: aesInvsBox.py
@Time: 2021-09-02 13:21
@Desc: It's all about getting better.
"""


def AES_INVSbox(box):
    aSbox = [[0 for j in range(16)] for i in range(16)]
    for i in range(16):
        aSbox[i] = box[i * 16:i * 16 + 16]

    invSbox = [[0 for j in range(16)] for i in range(16)]
    for i in range(16):
        for j in range(16):
            h = (aSbox[i][j] & 0xf0) >> 4
            l = aSbox[i][j] & 0xf
            invSbox[h][l] = (i << 4) + j
            # print(hex(aSbox[i][j]), hex(h), hex(l), hex(invSbox[h][l]))

    # print(invSbox)
    print("| 0  |  1  |  2  |  3  |  4  |  5  |  6  |  7  |  8  |  9  |  a  |  b  |  c  |  d  |  e  |  f  |")
    # print("---------------------------------------------------------------------------------------------")
    for i in invSbox:
        for j in i:
            print("0x" + hex(j)[2:].zfill(2), end=", ")
        print()


sbox = [0x7C, 0xF2, 0x63, 0x7B, 0x77, 0x6B, 0x6F, 0xC5, 0x30, 0x01, 0x67, 0x2B, 0xFE, 0xD7, 0xAB, 0x76,
        0xCA, 0x82, 0xC9, 0x7D, 0xFA, 0x59, 0x47, 0xF0, 0xAD, 0xD4, 0xA2, 0xAF, 0x9C, 0xA4, 0x72, 0xC0,
        0xB7, 0xFD, 0x93, 0x26, 0x36, 0x3F, 0xF7, 0xCC, 0x34, 0xA5, 0xE5, 0xF1, 0x71, 0xD8, 0x31, 0x15,
        0x04, 0xC7, 0x23, 0xC3, 0x18, 0x96, 0x05, 0x9A, 0x07, 0x12, 0x80, 0xE2, 0xEB, 0x27, 0xB2, 0x75,
        0x09, 0x83, 0x2C, 0x1A, 0x1B, 0x6E, 0x5A, 0xA0, 0x52, 0x3B, 0xD6, 0xB3, 0x29, 0xE3, 0x2F, 0x84,
        0x53, 0xD1, 0x00, 0xED, 0x20, 0xFC, 0xB1, 0x5B, 0x6A, 0xCB, 0xBE, 0x39, 0x4A, 0x4C, 0x58, 0xCF,
        0xD0, 0xEF, 0xAA, 0xFB, 0x43, 0x4D, 0x33, 0x85, 0x45, 0xF9, 0x02, 0x7F, 0x50, 0x3C, 0x9F, 0xA8,
        0x51, 0xA3, 0x40, 0x8F, 0x92, 0x9D, 0x38, 0xF5, 0xBC, 0xB6, 0xDA, 0x21, 0x10, 0xFF, 0xF3, 0xD2,
        0x0C, 0xCD, 0x13, 0xEC, 0x5F, 0x97, 0x44, 0x17, 0xC4, 0xA7, 0x7E, 0x3D, 0x64, 0x5D, 0x19, 0x73,
        0x60, 0x81, 0x4F, 0xDC, 0x22, 0x2A, 0x90, 0x88, 0x46, 0xEE, 0xB8, 0x14, 0xDE, 0x5E, 0x0B, 0xDB,
        0xE0, 0x32, 0x3A, 0x0A, 0x49, 0x06, 0x24, 0x5C, 0xC2, 0xD3, 0xAC, 0x62, 0x91, 0x95, 0xE4, 0x79,
        0xE7, 0xC8, 0x37, 0x6D, 0x8D, 0xD5, 0x4E, 0xA9, 0x6C, 0x56, 0xF4, 0xEA, 0x65, 0x7A, 0x08, 0xAE,
        0xBA, 0x78, 0x25, 0x2E, 0x1C, 0xA6, 0xB4, 0xC6, 0xE8, 0xDD, 0x74, 0x1F, 0x4B, 0xBD, 0x8B, 0x8A,
        0x70, 0x3E, 0xB5, 0x66, 0x48, 0x03, 0xF6, 0x0E, 0x61, 0x35, 0x57, 0xB9, 0x86, 0xC1, 0x1D, 0x9E,
        0xE1, 0xF8, 0x98, 0x11, 0x69, 0xD9, 0x8E, 0x94, 0x9B, 0x1E, 0x87, 0xE9, 0xCE, 0x55, 0x28, 0xDF,
        0x8C, 0xA1, 0x89, 0x0D, 0xBF, 0xE6, 0x42, 0x68, 0x41, 0x99, 0x2D, 0x0F, 0xB0, 0x54, 0xBB, 0x16]


AES_INVSbox(sbox)

一些参考实例

openluopworld/aes_128 – GitHub
matt-wu/AES – GitHub

参考资料

FIPS PUB 197: the official AES standard
“Intel® Advanced Encryption Standard (AES) New Instructions Set”

备个份

本文链接:https://blog.shi1011.cn/learn/1567
本文采用 CC BY-NC-SA 3.0 Unported 协议进行许可

Mas0n

文章作者

发表评论

textsms
account_circle
email

翻车鱼

关于AES算法的实现与流程
这篇本来是放在另一个笔记网站里的,但是因为gridea不支持mathJax,强迫症犯了,移到了这里。 随便记了些要点,算是简单了解一下AES算法的流程实现与细节吧 算法流程 用图说…
扫描二维码继续阅读
2021-09-10