介绍就不介绍了……直接上干货了
了解一下AES算法的流程实现与细节(

算法流程

img

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

加密流程

image-20210902200508503

解密流程

image-20210902212858194

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

  • SubBytes(字节代替)

  • ShiftRows(行移位)

  • MixColumns(列混淆)

  • AddRoundKey(轮密钥加)

下面分别介绍

SubBytes

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

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

image-20210902201027002

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

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

image-20210902201241543

ShiftRows

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

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

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

image-20210902201714638

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

image-20210902201919468

MixColumns

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

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

image-20210902204407041

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

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

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

s0,c=GMul(2,s0,c)GMul(3,s1,c)s3,cs'_{0,c} = GMul(2, s_{0,c}) \bigoplus GMul(3,s_{1,c}) \bigoplus s_{3,c}

s1,c=s0,cGMul(2,s1,c)GMul(3,s2,c)s3,cs'_{1,c} = s_{0,c} \bigoplus GMul(2,s_{1,c}) \bigoplus GMul(3,s_{2,c}) \bigoplus s_{3,c}

s2,c=s0,cs1,cGMul(2,s2,c)GMul(3,s3,c)s'_{2,c} = s_{0,c} \bigoplus s_{1,c} \bigoplus GMul(2,s_{2,c}) \bigoplus GMul(3,s_{3,c})

s3,c=GMul(3,s0,c)s1,cs2,cGMul(2,s3,c)s'_{3,c} = GMul(3,s_{0,c}) \bigoplus s_{1,c} \bigoplus s_{2,c} \bigoplus GMul(2,s_{3,c})

image-20210902210724656

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

image-20210902210936854

由于

[0e0b0d09090e0b0d0d090e0b0b0d090e][02030101010203010101020303010102]=[01000000000100000000010000000001]\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”。加密过程中,每轮的输入与轮子密钥异或一次;因此,解密时再异或上该轮的轮子密钥即可恢复。

[s0,c,s1,c,s2,c,s3,c]=[s0,c,s1,c,s2,c,s3,c][ωroundNb+c]for 0c<Nb[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

image-20210902212637505

Key Expansion

密钥扩展算法的原理图如下:

img

下面是伪代码的实现

image-20210902212014457

常规态操作

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"