关于AES算法的实现与流程

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

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

算法流程

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

加密流程

解密流程

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

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

下面分别介绍

SubBytes

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

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

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

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

ShiftRows

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

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

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

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

MixColumns

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

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

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

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

•则为伽罗华域乘法，表示为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})\)

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

由于

\(\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\)

Key Expansion

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

下面是伪代码的实现

一些脚本

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”

备个份