当前位置：首页 > news >正文

从零实现AES-128加密算法：深入理解对称加密核心原理与Python实战

news 2026/7/4 0:36:38

1. 从零到一：手搓AES加密算法的实战心路

如果你是一名开发者，或者对信息安全感兴趣，那么“AES加密”这个词你肯定不陌生。它几乎是现代互联网数据安全的基石，从你手机里的聊天记录加密，到网上银行的交易保护，背后都有它的身影。但很多时候，我们只是调用一个库函数，比如Python的cryptography库或者Java的Cipher类，输入密钥和明文，就得到了密文。这就像开车，你会踩油门和刹车，但未必清楚发动机是怎么工作的。

最近，我为了彻底搞懂AES，决定抛开所有现成的库，从零开始，用纯Python实现一遍AES-128-ECB算法。这个过程远比我想象的复杂，但也收获巨大。今天，我就把这次“手搓”AES的完整过程、踩过的坑、以及最终那份可以运行的代码，毫无保留地分享给你。这不是一篇枯燥的算法论文，而是一个工程师的实战笔记。你会发现，理解了AES的内部构造，不仅能让你在面试中侃侃而谈，更能让你在遇到加密相关问题时，拥有从原理层面排查和解决的能力。

2. AES加密功能的核心架构与设计抉择

在动手写代码之前，我们必须先搞清楚我们要实现什么，以及为什么这么设计。AES，全称高级加密标准，是一种对称分组密码。对称意味着加密和解密用同一把钥匙；分组则意味着它把数据切成固定大小的块来处理。我们选择实现的是AES-128-ECB，这是最基础的一种形态。

2.1 为什么选择AES-128-ECB作为起点？

AES有几种不同的密钥长度（128位、192位、256位）和几种工作模式（ECB、CBC、CTR等）。我选择AES-128-ECB作为起点，主要基于几个考量：

首先，128位密钥是AES的基准配置。它的轮数固定为10轮，算法结构相对规整，是实现和理解整个AES框架最合适的切入点。192位和256位密钥的轮数更多（12轮和14轮），但核心的变换步骤（SubBytes, ShiftRows, MixColumns, AddRoundKey）是完全一样的，只是密钥扩展和轮数不同。掌握了128位，向上扩展就容易得多。

其次，ECB模式是最简单、最直接的分组密码模式。它直接将明文分成独立的块，每个块用相同的密钥加密。这种模式的缺点非常明显——相同的明文块会产生相同的密文块，这会在某些情况下泄露数据模式，安全性不足。但正因为其简单，它剥离了模式本身的复杂性，让我们可以专注于AES核心的块加密算法本身。我们的目标是理解引擎如何工作，而不是一开始就研究整辆车的传动系统。理解了ECB模式下的AES，再去学习更安全的CBC（密码分组链接）或CTR（计数器）模式，就会水到渠成。

最后，从教学和演示目的出发，ECB模式代码最清晰，没有初始化向量、没有链式操作，加密和解密流程可以最直观地对应起来，非常适合用来剖析算法每一步的输入和输出。

2.2 AES加密的宏观流程：十轮锤炼

AES-128的加密过程，可以想象成一个精密的、重复十次的锻造过程。每一次锻造，都对数据块施加四种不同的“锤打”。一个128位的数据块，在内存中被组织成一个4x4的字节矩阵（称为State）。

初始轮：出人意料地简单，只有一步——AddRoundKey。直接将原始数据块与第一轮扩展密钥进行异或操作。你可以把它理解为给原材料先盖上一个独特的印章。

第1到第9轮（中间轮）：每一轮都包含四个标准步骤，顺序固定：

SubBytes（字节替换）：通过一个预设的S盒（Substitution-box）进行非线性替换。这是AES安全性的核心之一，提供了算法的混淆特性，让输出和输入之间的关系变得极其复杂。
ShiftRows（行移位）：将State矩阵的每一行进行循环左移。第0行不移位，第1行左移1字节，第2行左移2字节，第3行左移3字节。这一步提供了算法的扩散特性，让一个字节的变化能影响到更多位置。
MixColumns（列混淆）：对State矩阵的每一列，与一个固定的多项式矩阵在伽罗瓦域上进行乘法运算。这是扩散特性的主要来源，能将一列中单个字节的变化迅速扩散到整列。
AddRoundKey（轮密钥加）：将当前State与对应轮的扩展密钥进行异或。每一轮的密钥都不同，由最初的密钥通过密钥扩展算法派生而来。

最终轮（第10轮）：与中间轮类似，但省略了MixColumns步骤。只进行SubBytes、ShiftRows和AddRoundKey。这样设计是为了让加密和解密过程在结构上能够对称，简化解密操作。

整个流程就像一条精密的流水线，数据块依次经过这些工序，最终被锻造成面目全非的密文。而解密过程，就是将这些步骤以相反的顺序和逆操作执行一遍。

3. 核心算法模块的逐行拆解与实现

理解了宏观流程，我们进入最核心的部分：用代码实现每一个变换步骤。这里我会用Python来演示，因为Python语法清晰，能让我们聚焦于算法逻辑本身。

3.1 基石：S盒与逆S盒的构建与原理

S盒是AES算法中唯一的非线性部件，也是其能够抵抗各种密码分析攻击的关键。它本质上是一个16x16的查找表，接受一个8位输入，输出一个8位值。

在代码里，我们直接定义这两个庞大的二维数组。加密用s_box，解密用s_box_inv。它们的值不是随便来的，而是通过一个可逆的数学变换生成的，确保了每一个输入都有唯一且看似随机的输出。

s_box = [ [0x63, 0x7c, 0x77, 0x7b, 0xf2, 0x6b, 0x6f, 0xc5, 0x30, 0x01, 0x67, 0x2b, 0xfe, 0xd7, 0xab, 0x76], # ... 其余行省略，实际代码中需完整列出 ] s_box_inv = [ [0x52, 0x09, 0x6a, 0xd5, 0x30, 0x36, 0xa5, 0x38, 0xbf, 0x40, 0xa3, 0x9e, 0x81, 0xf3, 0xd7, 0xfb], # ... 其余行省略 ]

字节替换函数sub_bytes的实现：这个函数遍历State矩阵（在代码中我们用一个长度为16的列表grid表示，按列优先存储），对每个字节进行替换。

def sub_bytes(grid, inv=False): for i, v in enumerate(grid): if inv: # 如果是解密过程 grid[i] = s_box_inv[v >> 4][v & 0xf] else: # 如果是加密过程 grid[i] = s_box[v >> 4][v & 0xf]

这里有个小技巧：v >> 4取字节的高4位作为S盒的行索引，v & 0xf取字节的低4位作为列索引。这样就完成了查表替换。

实操心得：在实现时，务必确保s_box和s_box_inv的数据完全正确，一个字节的错误都会导致加解密失败。建议直接从可靠来源（如NIST官方文档或权威算法书）复制完整的S盒数据。自己计算虽然可行，但极易出错。

3.2 行移位与列混淆：实现数据的扩散

行移位shift_rows：这一步操作的是State矩阵的行。在4x4的矩阵视图中，第0行不变，第1行循环左移1个位置，第2行左移2位，第3行左移3位。解密时则进行反向的循环右移。

在代码实现上，我们用一个一维列表grid来模拟矩阵，索引[0, 1, 2, 3]是第一列，[4,5,6,7]是第二列，以此类推。那么第i行（i从0开始）的所有元素就是grid[i::4]。

def shift_rows(grid, inv=False): for i in range(4): # 遍历4行 row = grid[i::4] # 取出第i行 if inv: # 解密：右移 # 例如i=1，右移1位：取最后1个元素放前面，其余元素放后面 grid[i::4] = row[-i:] + row[:-i] else: # 加密：左移 # 例如i=1，左移1位：从第1个元素开始取到最后，再接上第0个元素 grid[i::4] = row[i:] + row[:i]

列混淆mix_columns：这是AES算法中最复杂的一步，涉及伽罗瓦域上的矩阵乘法。它对State的每一列独立操作。用于加密的固定矩阵是：

[2, 3, 1, 1] [1, 2, 3, 1] [1, 1, 2, 3] [3, 1, 1, 2]

这个矩阵与列向量相乘，结果是一个新的列向量。在伽罗瓦域GF(2^8)上，加法是异或，乘法是模一个不可约多项式的特殊乘法。

为了高效计算，我们通常实现一个xtime函数（或叫gmul）来处理与2的乘法，因为与3的乘法可以表示为x ^ xtime(x)。

def mix_columns(grid): def mul_by_2(n): s = (n << 1) & 0xff # 左移一位相当于乘以2 if n & 0x80: # 如果最高位是1（即值>=128） s ^= 0x1b # 需要模掉不可约多项式 x^8 + x^4 + x^3 + x + 1 (0x11b)，这里异或0x1b return s def mul_by_3(n): return n ^ mul_by_2(n) # 在GF(2^8)上，乘以3等于乘以2的结果再与原值异或 def mix_column(col): # 根据固定矩阵计算新的一列 return [ mul_by_2(col[0]) ^ mul_by_3(col[1]) ^ col[2] ^ col[3], col[0] ^ mul_by_2(col[1]) ^ mul_by_3(col[2]) ^ col[3], col[0] ^ col[1] ^ mul_by_2(col[2]) ^ mul_by_3(col[3]), mul_by_3(col[0]) ^ col[1] ^ col[2] ^ mul_by_2(col[3]), ] # 对State的每一列（每4个字节）应用mix_column函数 for i in range(0, 16, 4): grid[i:i+4] = mix_column(grid[i:i+4])

注意事项：列混淆的逆操作矩阵不同，但这里有一个非常巧妙的性质：在GF(2^8)上，加密矩阵的逆矩阵，其效果等同于对同一列连续进行三次加密操作。因此，在下面的解密函数中，我们通过调用三次mix_columns来实现逆列混淆。这比直接实现一个逆矩阵乘法要简单，但效率略低。生产环境中通常会使用预先计算好的查表法来优化。

3.3 密钥扩展：从一把钥匙到十把钥匙

AES-128的原始密钥是16个字节。但我们需要11轮密钥（1个初始轮密钥+10个轮密钥）。密钥扩展算法就是根据这16字节的原始密钥，生成后续10轮所需的额外40个字节（共16*11=176字节）的算法。

密钥扩展的核心是g函数，它处理每轮密钥的第一个字（4字节）：

字循环：将4字节循环左移一位。
字节替换：对每个字节进行S盒替换。
轮常量异或：将结果与一个轮常量Rcon[i]进行异或。轮常量是一个固定的数组，用于消除对称性。

rc = [0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x1b, 0x36] # 轮常量，只用到前10个 def key_expansion(key): # key是一个16字节的列表 expanded_key = key[:] # 初始密钥作为第一轮密钥的前16字节 for i in range(4, 44): # 总共需要44个字（176字节），从第4个字开始生成 temp = expanded_key[-4:] # 取上一个字 if i % 4 == 0: # 每4个字（即每轮密钥的第一个字）需要特殊处理 # 1. 字循环 temp = temp[1:] + temp[:1] # 2. 字节替换 temp = [s_box[b >> 4][b & 0xf] for b in temp] # 3. 轮常量异或 temp[0] ^= rc[i//4 - 1] # 生成新字：新字 = 上一个字 ^ 4个字之前的字 new_word = [expanded_key[-16 + j] ^ temp[j] for j in range(4)] expanded_key.extend(new_word) return expanded_key

轮密钥加add_round_key：这是最简单的步骤，就是将State矩阵的每一个字节与对应轮的扩展密钥的对应字节进行异或操作。

def add_round_key(grid, round_key): for i in range(16): grid[i] ^= round_key[i]

4. 完整加解密流程的组装与调试

现在，我们已经有了所有的基础零件：sub_bytes,shift_rows,mix_columns,key_expansion,add_round_key。接下来就是按照AES的标准流程把它们组装起来。

4.1 加密函数`encrypt`的组装

加密函数接收一个16字节的明文块b和扩展后的密钥expanded_key，然后严格遵循我们之前描述的轮结构。

def encrypt(b, expanded_key): # 第0轮：初始轮密钥加 add_round_key(b, expanded_key[0:16]) # 第1轮到第9轮：标准四步操作 for round_num in range(1, 10): sub_bytes(b) shift_rows(b) mix_columns(b) # 注意：每轮使用的密钥是 expanded_key[round_num*16 : (round_num+1)*16] add_round_key(b, expanded_key[round_num*16 : (round_num+1)*16]) # 第10轮：最终轮（省略MixColumns） sub_bytes(b) shift_rows(b) add_round_key(b, expanded_key[10*16:]) # 使用最后一轮密钥 return b

4.2 解密函数`decrypt`的逆向思维

解密是加密的逆过程，但顺序和部分操作需要取反。关键点在于，由于列混淆的逆操作我们通过三次正向操作实现，所以解密流程的步骤顺序需要仔细安排。

def decrypt(b, expanded_key): # 初始轮：使用最后一轮密钥 add_round_key(b, expanded_key[10*16:]) # 第9轮到第1轮：逆操作 for round_num in range(9, 0, -1): # 从9倒数到1 shift_rows(b, inv=True) # 逆行移位 sub_bytes(b, inv=True) # 逆字节替换（使用逆S盒） add_round_key(b, expanded_key[round_num*16 : (round_num+1)*16]) # 逆列混淆：执行三次正向列混淆 mix_columns(b) mix_columns(b) mix_columns(b) # 最终轮 shift_rows(b, inv=True) sub_bytes(b, inv=True) add_round_key(b, expanded_key[0:16]) # 使用最初的密钥 return b

注意解密循环的顺序是从后往前的，并且shift_rows和sub_bytes需要在add_round_key之前执行，这与加密的顺序相反。这是因为在代数结构上，解密需要先抵消掉轮密钥的影响，再进行行和字节的逆变换。

4.3 外围包装与数据填充

AES是分组密码，一次处理16字节。对于任意长度的数据，我们需要进行分块处理。此外，如果数据长度不是16的整数倍，还需要进行填充。这里我们采用最简单的零填充。

def aes_encrypt(key, plaintext): # 1. 密钥扩展 expanded_key = key_expansion(key) # 2. 数据填充 pad_len = 16 - (len(plaintext) % 16) padded_data = plaintext + bytes([0] * pad_len) # 零填充 # 3. 分块加密 ciphertext = bytearray() for i in range(0, len(padded_data), 16): block = bytearray(padded_data[i:i+16]) encrypted_block = encrypt(block, expanded_key) ciphertext.extend(encrypted_block) return bytes(ciphertext) def aes_decrypt(key, ciphertext): # 1. 密钥扩展 expanded_key = key_expansion(key) # 2. 分块解密 plaintext = bytearray() for i in range(0, len(ciphertext), 16): block = bytearray(ciphertext[i:i+16]) decrypted_block = decrypt(block, expanded_key) plaintext.extend(decrypted_block) # 3. 去除填充（零填充的简单处理：去除末尾的零字节） # 注意：这种简单的零填充在实际中不安全，仅用于演示。 return bytes(plaintext).rstrip(b'\x00')

4.4 测试与验证

写完了所有代码，最激动人心的就是跑一个测试看看。我们用一个简单的字符串和密钥来测试。

if __name__ == '__main__': # 密钥必须是16字节 key = b'ThisIsASecretKey' plaintext = b'Hello, AES World!This is a test message that is longer than 16 bytes.' print(f"原始明文: {plaintext}") print(f"明文长度: {len(plaintext)}") # 加密 ciphertext = aes_encrypt(key, plaintext) print(f"\n加密后密文 (Hex): {ciphertext.hex()}") # 解密 decrypted = aes_decrypt(key, ciphertext) print(f"解密后明文: {decrypted}") print(f"解密是否成功: {decrypted == plaintext}")

如果一切正确，你会看到解密后的明文与原始明文完全一致。这个过程可能不会一次成功，下面我们就来聊聊调试中会遇到的那些坑。

5. 手搓AES时必踩的坑与排查指南

自己实现加密算法，就像组装一台精密钟表，任何一个齿轮没对准，整个表就不走。下面是我在实现过程中遇到的一些典型问题及解决方法。

5.1 字节序与数据表示问题

问题描述：加解密结果不对，或者中间某一步的状态值与标准测试向量对不上。根因分析：AES算法操作的是字节，但字节在内存或传输中的顺序（大端序、小端序）以及我们如何将字符串或整数转换成字节数组，会直接影响结果。此外，State矩阵在代码中的存储方式（行优先还是列优先）必须保持一致。排查步骤：

统一数据格式：在算法内部，始终使用bytearray或list of integers (0-255)来表示数据。避免混用字符串、十六进制字符串和整数。
验证S盒和轮常量：这是最容易出错的地方。务必使用官方或广泛验证过的数据源。一个字节的错误会导致整个加密链失效。可以单独写一个测试函数，验证几个已知的输入输出对。
使用标准测试向量：NIST提供了完整的AES测试向量。找一组AES-128-ECB的测试用例（包括密钥、明文、密文），用你的代码加密明文，看结果是否与标准密文匹配。这是最权威的验证方法。
逐步调试：不要试图一次性写完所有代码。先实现sub_bytes，用几个已知字节测试。再实现shift_rows，用一个简单的矩阵（如[0,1,2,...,15]）测试移位是否正确。mix_columns是最复杂的，可以找一些在线计算器或者其他库的计算结果进行对比。

5.2 密钥扩展的错误

问题描述：加密似乎正常，但解密失败，或者中间几轮之后数据就乱了。根因分析：密钥扩展算法逻辑错误，导致生成的轮密钥不正确。特别是g函数中的字循环、字节替换和轮常量异或的顺序和细节。解决方案：

将key_expansion函数生成的扩展密钥打印出来，与已知正确的扩展密钥进行逐字节对比。网上有很多AES密钥扩展计算器。
特别注意轮常量Rcon的索引。第一轮（i=4时）使用的是Rcon[1]（即0x01），而不是Rcon[0]。这是一个常见的差一错误。

5.3 伽罗瓦域乘法的实现错误

问题描述：mix_columns步骤后，数据完全不对，解密无法恢复。根因分析：mul_by_2（即xtime）函数实现有误。伽罗瓦域GF(2^8)上的乘法不是普通的整数乘法。核心检查点：

def mul_by_2(x): # 正确实现 if x & 0x80: # 判断最高位是否为1 return ((x << 1) & 0xFF) ^ 0x1B else: return (x << 1) & 0xFF

& 0xFF确保结果保持在8位内。
^ 0x1B是模不可约多项式x^8 + x^4 + x^3 + x + 1（十六进制0x11B）的操作。当左移后最高位溢出时，需要异或0x1B（即0x11B去掉最高位）。
mul_by_3必须定义为x ^ mul_by_2(x)，这是GF(2^8)上的性质。

5.4 工作模式与填充的陷阱

问题描述：短文本加解密正常，长文本解密后末尾出现乱码。根因分析：填充方案和解密后去除填充的逻辑不匹配。我们演示中使用了最简单的零填充，但在实际中这是不安全的，因为无法区分真正的数据末尾的零和填充的零。更安全的做法：使用PKCS#7填充。加密时，如果需要填充n个字节，则每个填充字节的值都是n。解密后，读取最后一个字节的值n，然后去掉末尾的n个字节。

# PKCS#7 填充示例 pad_len = 16 - (len(data) % 16) padding = bytes([pad_len] * pad_len) padded_data = data + padding # 解密后去除填充 pad_len = decrypted_data[-1] if pad_len < 1 or pad_len > 16: raise ValueError("Invalid padding") decrypted_data = decrypted_data[:-pad_len]

5.5 性能与安全警告

重要提醒：我们这里实现的代码是教育目的的。它清晰地展示了AES的原理，但绝不应该用于生产环境，原因有二：

性能：纯Python实现，且没有使用任何优化（如查表法），速度非常慢。生产级库（如OpenSSL,cryptography）使用高度优化的汇编代码或CPU指令（如AES-NI）来实现，速度是天壤之别。
安全性：我们的实现可能容易受到侧信道攻击。例如，执行时间可能依赖于密钥或数据，这会被攻击者利用。专业的加密库经过了严格的安全审计和设计，以抵御此类攻击。

6. 从ECB到更安全的工作模式

理解了AES的核心块加密后，我们再来看看为什么ECB模式不安全，以及更安全的工作模式是如何工作的。

6.1 ECB模式的缺陷可视化

ECB最大的问题是，相同的明文块会产生相同的密文块。如果明文有重复的模式，密文也会泄露这个模式。一个经典的例子是加密一张有大面积纯色块的图片，ECB加密后的图片，其轮廓依然可见。

6.2 更安全的模式：CBC与CTR

为了弥补ECB的缺陷，人们发明了其他工作模式。

CBC模式：密码分组链接模式。每个明文块在加密前，先与前一个密文块进行异或。第一个块则与一个随机生成的初始化向量异或。这样，即使明文相同，由于IV不同或前一块密文不同，加密结果也完全不同。解密时，需要先解密，再与前一密文块异或。CBC模式提供了更好的安全性，但它是串行的，无法并行加密。
CTR模式：计数器模式。它实际上将分组密码转换成了流密码。生成一个随机的计数器初始值，然后对“计数器值+1”进行加密，将得到的密钥流与明文进行异或。解密过程完全相同。CTR模式的优势在于可以并行加密/解密，并且不需要填充（因为是流模式）。

实现CBC模式并不复杂，核心就是在我们的aes_encrypt/decrypt函数基础上，增加一个IV，并在处理每个块时进行异或操作。这留给你作为扩展练习。