对称密码-AES

参考：

https://dexterjie.github.io/2023/07/23/%E5%9D%97%E5%AF%86%E7%A0%81/AES/?highlight=aes

一、简介

高级加密标准（Advanced Encryption Standard，AES）是美国联邦政府采用的分组密码标准，由比利时密码学家Joan Daemen和Vincent Rijmen设计，又称Rijndael加密法。该标准于2001年11月26日由美国国家标准与技术研究院（NIST）发布于FIPS PUB 197文件，2002年5月26日生效，旨在替代数据加密标准（DES）。其区块长度固定为128位，密钥长度可选128、192或256位，加密过程包含AddRoundKey、SubBytes、ShiftRows和MixColumns四个步骤。

1997年NIST启动替代DES的算法征集，要求候选算法分组长度至少128位，密钥可选128/192/256位。1999年4月从15个候选算法中筛选出5个入围方案，2000年10月选定Rijndael算法，2001年正式确立为AES。该标准在实现时对原Rijndael算法进行了标准化约束，现已成为商业数据加密的国际标准，支持ECB、CBC、CFB和OFB等多种加密模式，应用于短分组加密等技术领域

二、Rijndeal的数学基础和设计思想

（1）有限域GF(2^8)

Ⅰ.性质

• 域同构

$$ 两个域F和G同构，如果存在双射\phi: F → G，使得：$$

$$\phi(a+b)=\phi(a)+\phi(b)$$

$$\phi(a×b)=\phi(a)×\phi(b)$$

• $$对于任意素数p和正整数n，在同构意义下存在唯一的一个有限域，包含p^n个元$$

$$GF(2^8) 有256个元素的有限域，这是唯一确定的代数结$$

• 有限域中的元素可以用多种不同的方式表示

主要表示方法有：

1. 多项式表示
2. 整数表示
3. 向量表示

Ⅱ.计算

1. 加法（减法）

多项式表达中，GF(2^8)上的两个元素之和仍为一个次数不超过7的多项式，其系数等于两个元素对应系数的模2加（比特异或）

由于每个元素的加法逆元就是本身，所以加法和减法相同

1. 乘法

GF（2^8）上的两个元素的乘积就是这两个多项式的模乘，在Rujndeal算法中，这个8次不可约多项式为：

$$m(x)=x^8+x^4+x^3+x+1$$

十六进制表示为11B

• 乘法运算满足交换律，且有单位元01
• 乘法运算满足分配律

1. x乘法运算

$$x \cdot b(x)=b_7x^8+b_6x^7+b_5x^6+…+b_1x^2+b_0x \pmod {m(x)}$$

• $$若b_7=0,则求模结果不变 $$
• $$若b_7\neq0，则为乘积结果减去m(x)，即求乘积结果与m(x)的异或$$

x乘b(x)可以先对b(x)在字节内左移一位，若b_7=1则再与1B（二进制为00011011）做逐比特异或

记该运算为b=xtime(a)

（2）系数在GF(2^8)上的多项式

• $$4个字节构成的向量可以表示为系数在GF(2^8)上的次数小于2的多项式$$

$$规定多项式的乘法必须要取模M(x)=x^4+$$，M(x)不是GF(2^8)上的不可约多项式，故这种乘法不是群运算

$$在Rijndeal算法中，这种乘法运算只限于乘一个固定的有逆元的多项式a(x)=a_3x^3+a_2x^2+a_1x+a_$$

• $$定理：系数在GF(2^8)上的多项式a_3x^3+a_2x^2+a_1x+a_0是模x^4+1可逆的，当且仅当矩阵$$

$$\begin{pmatrix} a_0&a_3&a_2&a_1\ a_1&a_0&a_3&a_2\ a_2&a_1&a_0&a_3\ a_3&a_2&a_1&a_0\ \end{pmatrix}$$

$$在GF(2^8)上可$$

$$c(x) = x \otimes b(x) 定义为x与b(x) 的模x^4+1乘法，即c(x) = x \otimes b(x) = b_2 x^3 + b_1 x^2 + b_0 x + b_3$$

$$其矩阵表示中，除了a_1=01w外，其他所有的a_i=00,即：$$

$$\begin{pmatrix} c_0 \ c_1 \ c_2 \ c_3 \end{pmatrix} = \begin{pmatrix} 00 & 00 & 00 & 01 \ 01 & 00 & 00 & 00 \ 00 & 01 & 00 & 00 \ 00 & 00 & 01 & 00 \end{pmatrix} \begin{pmatrix} b_0 \ b_1 \ b_2 \ b_3 \end{pmatrix}$$

$$因此，x（或 x 的幂）模乘多项式相当于对字节构成的向量进行字节循环移位。$$

（3）设计思想

Feistel结构：将中间状态的部分比特不加改变地简单放置到其他位置。

当前大多数分组密码，其轮函数是Feistel结构

Rijndeal没有这种结构，其轮函数是由3个不同的可逆均匀变换组成的，称它们为3个层。

（宽轨迹策略：提供抗线性密码分析和差分密码分析能力的一种设计）

1. 线性混合层：确保多轮之上的高度扩散
2. 非线性层：将具有最优的“最坏情况非线性特性”的S盒并行使用
3. 密钥加层：单轮子密钥简单地异或到中间状态，实现一次掩盖

为使加解密算法在结构上接近，最后一轮的线性混合层与前面各轮的线性混合层不同。

四、工作模式

（1）ECB 电码本模式

Ⅰ.原理

先将明文进行分块，然后用相同的加密方式和密钥进行加密。

• 相同的明文块产生相同的密文块。

明文m和密钥key的长度必须是16的倍数

from Crypto.Cipher import AES
import random
from Crypto.Util.number import *

key = random.getrandbits(128)
key = long_to_bytes(key)

aes = AES.new(key,AES.MODE_ECB)
m = b'abcdefghijklmnop'

c = aes.encrypt(m)
print(c)

plaintext = aes.decrypt(c)
print(plaintext)

Ⅱ.例题

1.逐字节爆破

题目

您将在ECB(电子本)模式下获得由AES算法生成的密文。加密密钥未知。

密文包含你应该找到的标志。所以你的任务是在ECB模式下破解AES算法

您可以访问加密设备，并且可以每次重复使用相同的密钥对任意数据进行加密。

您输入的数据将被添加到标志的前面，您将收到一个新的密文。
注意! ! !您输入的数据必须是base64编码!!

思路

$$这道题的flag长度为48，分组为$$

$$m_1m_2…m_{16} \qquad m_{17}m_{18}…m_{32} \qquad m_{33}m_{34}…m_{48}$$

$$先输入15个0，于是分组为：$$

$$00…0m_1 \qquad m_2m_3…m_{17} \qquad m_{18}m_{19}…m_{33} \qquad m_{34}m_{35}…m_{48}$$

$$记此时对应的密文为enc_{flag}$$

$$爆破第一段，只需要输入00…0+X$$

$$此时的分组为$$

$$00…0X \qquad m_2…m_{17} \qquad m_{18}…m_{33} \qquad m_{34}…m_{48}$$

$$记此时对应的密文为c$$

$$对比c[:16]和enc_{flag}[:16]即可$$

$$爆破第二段输入flag[:-15]+X+00…0$$

$$m_2…m_{16}X \qquad 0…0m_1 \qquad m_2…m_{17} \qquad m_{18}…m{33} \qquad m_{34}…m_{48}$$

$$记此时密文为c$$

$$对比c[:16]与enc_{flag}[16:32]即可$$

$$爆破第三段输入$$

$$m_{18}…m_{32}X \qquad 0…0m_1 \qquad m_2…m_{17} \qquad m_{18}…m_{33} \qquad m_{34}…m_{48}$$

$$记此时密文为c$$

$$对比c[:16]和enc_{flag}[32:48]即可$$

解答

from pwn import *  # 导入pwn工具库，用于网络通信和二进制攻击
from tqdm import *  # 导入tqdm库，用于显示进度条
import base64  # 导入base64编码库

# 连接到远程服务器
sh = remote("ctf.mf.grsu.by",9016)

# 接收直到看到指定字符串
sh.recvuntil(b"secret ciphertext (b64):")
# 读取一行（包含base64编码的密文）
ciphertext = sh.recvline()
# 读取下一行（可能是空行或提示）
sh.recvline()

# 初始化flag字符串
flag = ""

# 第一部分：爆破flag的前16字节
for i in trange(16):  # 使用tqdm显示进度，i从0到15
    # 发送"0"*(15-i)的base64编码
    sh.sendline(base64.b64encode((b"0"*(15-i))))
    # 接收服务器的响应并解析出密文
    c = sh.recvline().strip().decode().split(":")[-1].strip()
    # 解码base64密文
    enc_flag = base64.b64decode(c.encode())
    
    # 遍历可打印字符（ASCII 33-127）
    for j in range(33,128):
        # 构造消息：前导0 + 已知flag部分 + 猜测字符
        msg = (("0"*(15-i)) + flag +  chr(j)).encode()
        # 发送消息
        sh.sendline(base64.b64encode(msg))
        # 接收响应并解析密文
        cc = sh.recvline().strip().decode().split(":")[-1].strip()
        cipher = base64.b64decode(cc)
        
        # 如果密文前16字节匹配，说明猜对了
        if cipher[:16] == enc_flag[:16]:
            flag += chr(j)  # 添加到flag
            print(f"flag:{flag}")
            break

# 第二部分：爆破flag的第17-32字节
for i in trange(16):
    sh.sendline(base64.b64encode((b"0"*(15-i))))
    c = sh.recvline().strip().decode().split(":")[-1].strip()
    enc_flag = base64.b64decode(c.encode())
    for j in range(33,128):
        # 注意：这里使用flag的后15个字符 + 猜测字符 + 前导0
        msg = (flag[-15:] + chr(j) + "0"*(15-i)).encode()
        sh.sendline(base64.b64encode(msg))
        cc = sh.recvline().strip().decode().split(":")[-1].strip()
        cipher = base64.b64decode(cc)
        # 比较密文的第二个16字节块
        if cipher[:16] == enc_flag[16:32]:
            flag += chr(j)
            print(f"flag:{flag}")
            break

# 第三部分：爆破flag的第33-48字节
for i in trange(16):
    sh.sendline(base64.b64encode((b"0"*(15-i))))
    c = sh.recvline().strip().decode().split(":")[-1].strip()
    enc_flag = base64.b64decode(c.encode())
    for j in range(33,128):
        msg = (flag[-15:] + chr(j) + "0"*(15-i)).encode()
        sh.sendline(base64.b64encode(msg))
        cc = sh.recvline().strip().decode().split(":")[-1].strip()
        cipher = base64.b64decode(cc)
        # 比较密文的第三个16字节块
        if cipher[:16] == enc_flag[32:48]:
            flag += chr(j)
            print(f"flag:{flag}")
            break

grodno[910f50AES_1n_ECB_m0de_1s_hackable9la0le]

（2）CBC

Ⅰ.原理

通过引入初始化向量(IV)和前一个密文块的链接，使得每个密文块都依赖于之前所有的明文块

from Crypto.Cipher import AES
import random
from Crypto.Util.number import *

# 加密
iv = random.getrandbits(128)
iv = long_to_bytes(iv)
key = random.getrandbits(128)
key = long_to_bytes(key)
print(key,iv,sep='\n')

aes = AES.new(key,AES.MODE_CBC,iv)
m = b'abcdefghijklmnop'
c = aes.encrypt(m)
print(c)

# 解密
key = b'\xd4\xc5\x0f\xf3\x89\xd3[\x94\xbc\xde\xacds\xae\xf3\x1b'
iv = b'\xf0\x90\xd1\x99\r\xb1\xa7\x81\xa8\xae\xbbQ\xec\xaa\xef\x10'
c = b'\x95{\x80\xffS\x14L^\x9e?\x08~y\nH1'

decryption = AES.new(key,AES.MODE_CBC,iv)
plaintext = decryption.decrypt(c)
print(plaintext)

（3）CTR

Ⅰ.原理

将分组密码转换为流密码。使用一个计数器，对计数器值加密得到密钥流，然后与明文异或得到密文

Nonce:随机数

Counter:它是由IV经过一定的规则之后生成的一段数据，长度与数据块的长度相等

Counter通过ECB加密后得到一个Counter的密文，再和明文1进行异或得到密文1。在加密结束后Counter的值加1，然后再次用ECB加密，依次加密

• 将分组密码变成流密码
• 不需要填充
• 并行加解密

import json
from base64 import b64encode
from Crypto.Cipher import AES
from Crypto.Random import get_random_bytes

data = b"secret"
key = get_random_bytes(16)
cipher = AES.new(key, AES.MODE_CTR)
ct_bytes = cipher.encrypt(data)
nonce = b64encode(cipher.nonce).decode('utf-8')
ct = b64encode(ct_bytes).decode('utf-8')
result = json.dumps({'nonce':nonce, 'ciphertext':ct})
print(result)
{"nonce": "XqP8WbylRt0=", "ciphertext": "Mie5lqje"}
import json
from base64 import b64decode
from Crypto.Cipher import AES

# We assume that the key was securely shared beforehand
try:
    b64 = json.loads(json_input)
    nonce = b64decode(b64['nonce'])
    ct = b64decode(b64['ciphertext'])
    cipher = AES.new(key, AES.MODE_CTR, nonce=nonce)
    pt = cipher.decrypt(ct)
    print("The message was: ", pt)
except (ValueError, KeyError):
    print("Incorrect decryption")