AES-Analyse

预处理：

AES是一种分组对称加密算法，原文进入处理之前，将按照16bytes(128bits)的块大小进行切割分组，逐块进行处理(明文字符总长度不满16倍数就填充。）

AES的大致工作流程:

我按照几个模块的方式去记忆：

将字节替换(BS)，行位移(SR)，列混淆(MC)，轮密钥加(KA)记作一个模块。
将字节替换(BS)，行位移(SR)，轮密钥加(KA)记作特殊模块。
首先进行一次轮密钥加(KA)。
中间用正常模块处理。
最后一轮用特殊模块处理。

详细的单轮流程图：

字节替换：直接查表(表的设计原理见文章[2])。
行位移，列混淆：按照图中的顺序打乱就完了，用来扰乱结构的。
轮密钥加：将轮输入与轮密钥在有限域(GF)上与轮密钥相加

其中轮密钥由拓展密钥算法求出，根据输入Key进行定义，根据密钥编排摁加就行，这个不重要，确保够乱够数就行。

Q：为什么会有一个特殊模块？

A：设计上方便正逆向处理，可以在流程图中看得出加解密流程是对称进行的，解密的时候按照加密的逆过程来就行，这种设计有利于硬件设计、处理吧。

大致算法实现：

在有限域GF(3^2)上的实现(抄TCTF题目抄来的)：

GF(有限域的实现算法):

class GF:
    def __init__(self, value):
        if type(value) == int:
            self.value = [(value // (3 ** i)) % 3 for i in range(5)]
            print(self.value)
        elif type(value) == list and len(value) == 5:
            self.value = value
        else:
            assert False, "Wrong input to the constructor"

    def __str__(self):
        return f"GF({self.to_int()})"

    def __repr__(self):
        return str(self)

    def __hash__(self):
        return hash(tuple(self.value))

    def __eq__(self, other):
        assert type(other) == GF
        return self.value == other.value
    
    def __add__(self, other):
        assert type(other) == GF
        return GF([(x + y) % 3 for x, y in zip(self.value, other.value)])
    
    def __sub__(self, other):
        assert type(other) == GF
        return GF([(x - y) % 3 for x, y in zip(self.value, other.value)])
    
    def __mul__(self, other):
        assert type(other) == GF

        arr = [0 for _ in range(9)]
        for i in range(5):
            for j in range(5):
                arr[i + j] = (arr[i + j] + self.value[i] * other.value[j]) % 3
        
        # Modulus: x^5 + 2*x + 1
        for i in range(8, 4, -1):
            arr[i - 4] = (arr[i - 4] - 2 * arr[i]) % 3
            arr[i - 5] = (arr[i - 5] - arr[i]) % 3
        
        return GF(arr[:5])
    
    def __pow__(self, other):
        assert type(other) == int
        base, ret = self, GF(1)
        while other > 0:
            if other & 1:
                ret = ret * base
            other >>= 1
            base = base * base
        return ret

    def inverse(self):
        return self ** 241

    def __div__(self, other):
        assert type(other) == GF
        return self * other.inverse()
    
    def to_int(self):
        return sum([self.value[i] * (3 ** i) for i in range(5)])

if __name__ == "__main__":
    '''
	#测试代码可行性，测试与理论是否相符，，
    print(GF(2)*GF(2))
    assert GF(3) * GF(3) == GF(9)
    assert GF(9) * GF(27) == GF(5)
    assert GF(5).inverse() == GF(240)
    '''

Cipher(加解密实现算法):

from GF import GF

SBOX, INV_SBOX = dict(), dict()
for i in range(3 ** 5):
    v = GF(23) + (GF(0) if i == 0 else GF(i).inverse())
    SBOX[GF(i)] = v
    INV_SBOX[v] = GF(i)

class BlockCipher:
    def __init__(self, key: bytes, rnd: int):
        assert len(key) == 9
        sks = [GF(b) for b in key]
        for i in range(rnd * 9):
            sks.append(sks[-1] + SBOX[sks[-9]])
        self.subkeys = [sks[i:i+9] for i in range(0, (rnd + 1) * 9, 9)]
        self.rnd = rnd

    def _add_key(self, l1, l2):
        return [x + y for x, y in zip(l1, l2)]

    def _sub_key(self, l1, l2):
        return [x - y for x, y in zip(l1, l2)]
    
    def _sub(self, l):
        return [SBOX[x] for x in l]

    def _sub_inv(self, l):
        return [INV_SBOX[x] for x in l]
    
    def _shift(self, b):
        return [
            b[0], b[1], b[2],
            b[4], b[5], b[3],
            b[8], b[6], b[7]
        ]
    
    def _shift_inv(self, b):
        return [
            b[0], b[1], b[2],
            b[5], b[3], b[4],
            b[7], b[8], b[6]
        ]
    
    def _mix(self, b):
        b = b[:] # Copy
        for i in range(3):
            x = GF(7) * b[i] + GF(2) * b[3 + i] + b[6 + i]
            y = GF(2) * b[i] + b[3 + i] + GF(7) * b[6 + i]
            z = b[i] + GF(7) * b[3 + i] + GF(2) * b[6 + i]
            b[i], b[3 + i], b[6 + i] = x, y, z
        return b
    
    def _mix_inv(self, b):
        b = b[:] # Copy
        for i in range(3):
            x = GF(86) * b[i] + GF(222) * b[3 + i] + GF(148) * b[6 + i]
            y = GF(222) * b[i] + GF(148) * b[3 + i] + GF(86) * b[6 + i]
            z = GF(148) * b[i] + GF(86) * b[3 + i] + GF(222) * b[6 + i]
            b[i], b[3 + i], b[6 + i] = x, y, z
        return b
    
    def encrypt(self, inp: bytes):
        assert len(inp) == 9
        b = [GF(x) for x in inp]
        
        b = self._add_key(b, self.subkeys[0])
        for i in range(self.rnd):
            b = self._sub(b)
            b = self._shift(b)
            if i < self.rnd - 2:
                b = self._mix(b)
            b = self._add_key(b, self.subkeys[i + 1])
        
        return bytes([x.to_int() for x in b])
    
    def decrypt(self, inp: bytes):
        assert len(inp) == 9
        b = [GF(x) for x in inp]

        for i in reversed(range(self.rnd)):
            b = self._sub_key(b, self.subkeys[i + 1])
            if i < self.rnd - 2:
                b = self._mix_inv(b)
            b = self._shift_inv(b)
            b = self._sub_inv(b)
        b = self._sub_key(b, self.subkeys[0])
        
        return bytes([x.to_int() for x in b])

if __name__ == "__main__":
    import random
    key = bytes(random.randint(0, 242) for i in range(9))
    cipher = BlockCipher(key, 5) #定义密钥与加密轮数
    ct = cipher.encrypt(pt)
    pt_ = cipher.decrypt(ct)
    assert pt == pt_

攻击分析：

目前针对AES算法本身比较有效的攻击办法就是文章[3]所用的Square Attack。（也就是不考虑分组模式影响的前提下）

当然再考虑侧信道攻击，注入故障的前提下，利用差分去打相邻两轮的处理结果推出密钥也不是不行。

目前出过的相关赛题有：

2016 TCTF
2018 强网杯决赛 revolver
2020 [Google CTF](https://github.com/nguyenduyhieukma/CTF-Writeups/blob/master/Google CTF Quals/2020/oracle/oracle-solution.ipynb)
2023 强网拟态
2023 TCTF

做一道吐一道。

三顺七的笔记