从理论到代码：手把手实现AES-128加密算法，打通密码学实践之路

1. 项目概述从“课后习题”到实战复现的跨越最近在整理资料时翻到了以前学习密码学时做的AES加密算法课后习题。当时为了搞懂那些矩阵变换和轮函数没少掉头发。但说实话光会做题和真正理解一个算法在计算机里是怎么“跑”起来的完全是两码事。很多朋友可能和我当初一样学完了AES的理论知道它有几轮、每轮做什么但一提到“复现”脑子里还是空白的不知道从哪里下手。这个项目就是把我当年从“纸上谈兵”到“动手实现”的过程重新梳理一遍并分享一些在实现过程中必然会遇到的坑和解决技巧。AESAdvanced Encryption Standard高级加密标准如今无处不在从你手机里的聊天软件到网上银行的交易背后很可能都有它的身影。理解它不仅仅是完成一道课后题更是理解现代信息安全基石之一的关键。这次复现我们不依赖任何现成的加密库比如Python的cryptography或者Java的javax.crypto而是从最底层的字节操作开始一步步构建起完整的AES-128加密和解密流程。我会重点解释那些在理论课本上一笔带过但在代码里却至关重要的细节比如状态矩阵在内存中到底怎么排列、轮密钥加的具体实现、以及如何高效地进行伽罗瓦域上的乘法运算。2. 核心思路与设计为什么选择“裸写”AES2.1 复现目标与价值澄清首先明确我们复现AES不是为了造一个比现有库更安全、更快的轮子。现有库经过千锤百炼在安全和性能上都是最优选择。我们复现的核心目标有三个深化理解将抽象的数论和代数概念如有限域GF(2^8)转化为具体的代码逻辑彻底打通理论与实践的任督二脉。你会发现书本上的“S盒替换”在代码里就是一个256字节的查找表。掌握细节了解算法每一步的具体输入输出特别是数据在内存中的表示形式。这有助于你在未来进行调试比如遇到“php aes数据不完整”这类错误或进行底层安全分析时能快速定位问题根源。构建信心亲手实现一个世界级的标准算法能极大地提升你对复杂系统的掌控感和学习其他密码学原语的信心。因此我们的设计原则是清晰第一性能第二。代码要尽可能直白地反映算法步骤方便阅读和调试。我们会先实现最基础的AES-128密钥长度128位因为它是所有变体的基础理解了它AES-192和AES-256只是轮数和密钥扩展上的自然延伸。2.2 整体架构与数据流设计AES是一种分组密码每次处理一个16字节128位的明文块。我们的程序将围绕以下几个核心模块构建字节处理层所有操作的基础。AES内部将16字节的块视为一个4x4的“状态”矩阵。但在内存中它是按列优先顺序存储的。这是一个关键细节。假设明文字节为p0, p1, ..., p15那么状态矩阵s[r][c]r行c列0起始的对应关系是s[r][c] p[r 4*c]。很多初学者实现的加解密结果不对第一步就在这里出了错。密钥扩展模块根据初始的16字节密钥生成每一轮所需的轮密钥。这是AES的精华之一涉及了S盒替换、轮常量Rcon等操作。我们将详细实现它并解释轮常量的生成原理。轮函数模块这是加密的核心循环体每轮依次执行四个步骤SubBytes字节替换、ShiftRows行移位、MixColumns列混淆、AddRoundKey轮密钥加。解密则是逆过程。我们会为每个步骤编写独立的函数。伽罗瓦域运算模块MixColumns及其逆运算的核心是GF(2^8)上的乘法和加法。我们需要实现一个高效的有限域乘法函数。这里不会深入抽象代数而是用查表法和xtime乘以2操作来优雅地解决。整个加密的数据流可以概括为明文 - 初始轮密钥加 - 执行9轮标准轮函数 - 执行最后一轮不含MixColumns- 密文。解密过程正好相反。我们将用清晰的函数调用链来体现这一过程。注意在真正开始写代码前务必准备好AES的标准文档如FIPS PUB 197作为参考。我们的实现将严格遵循该标准确保结果的正确性这样才能和课后习题的答案以及官方测试向量进行比对。3. 核心模块的代码级拆解3.1 状态矩阵与内存布局这是所有操作的舞台。我们用一个二维列表Python或二维数组C/Java来表示4x4的状态矩阵。class AES: def __init__(self, key): self.key key self.state [[0] * 4 for _ in range(4)] # 4行4列的状态矩阵 def _bytes_to_state(self, data_bytes): 将16字节的数组加载到状态矩阵中列优先 for col in range(4): for row in range(4): self.state[row][col] data_bytes[row 4 * col] def _state_to_bytes(self): 将状态矩阵转回16字节的数组列优先 output [0] * 16 for col in range(4): for row in range(4): output[row 4 * col] self.state[row][col] return output关键点row 4 * col这个索引计算是列优先的精髓。务必在_bytes_to_state和_state_to_bytes中保持完全一致否则数据就乱套了。在调试时可以打印出状态矩阵来直观验证。3.2 S盒与逆S盒的实现SubBytes和InvSubBytes操作通过查表完成。S盒是一个256字节的预计算表它是一个非线性变换提供了算法的混淆特性。# AES S盒 (Substitution Box) S_BOX [ 0x63, 0x7c, 0x77, 0x7b, 0xf2, 0x6b, 0x6f, 0xc5, 0x30, 0x01, 0x67, 0x2b, 0xfe, 0xd7, 0xab, 0x76, # ... 此处省略中间240个值实际代码需补全完整的256个值 0x8c, 0xa1, 0x89, 0x0d, 0xbf, 0xe6, 0x42, 0x68, 0x41, 0x99, 0x2d, 0x0f, 0xb0, 0x54, 0xbb, 0x16 ] # 逆S盒用于解密 INV_S_BOX [ 0x52, 0x09, 0x6a, 0xd5, 0x30, 0x36, 0xa5, 0x38, 0xbf, 0x40, 0xa3, 0x9e, 0x81, 0xf3, 0xd7, 0xfb, # ... 同样需要补全完整的256个值 0x17, 0x2b, 0x04, 0x7e, 0xba, 0x77, 0xd6, 0x26, 0xe1, 0x69, 0x14, 0x63, 0x55, 0x21, 0x0c, 0x7d ] def sub_bytes(self): 字节替换将状态矩阵中的每个字节替换为S盒中对应位置的值 for i in range(4): for j in range(4): self.state[i][j] S_BOX[self.state[i][j]]实操心得千万不要手打这512个十六进制数极容易出错。正确做法是从可靠来源如官方文档、权威开源代码直接复制粘贴整个数组定义。一个错误的字节就可能导致整个加解密失败且极难排查。3.3 行移位与逆行移位ShiftRows很简单就是状态矩阵的每一行进行循环左移第0行不移第1行移1位第2行移2位第3行移3位。逆操作就是循环右移。def shift_rows(self): 行移位 # 第0行不移 # 第1行循环左移1位 self.state[1][0], self.state[1][1], self.state[1][2], self.state[1][3] \ self.state[1][1], self.state[1][2], self.state[1][3], self.state[1][0] # 第2行循环左移2位 (等于交换两对) self.state[2][0], self.state[2][1], self.state[2][2], self.state[2][3] \ self.state[2][2], self.state[2][3], self.state[2][0], self.state[2][1] # 第3行循环左移3位 (等于循环右移1位) self.state[3][0], self.state[3][1], self.state[3][2], self.state[3][3] \ self.state[3][3], self.state[3][0], self.state[3][1], self.state[3][2]逆移位inv_shift_rows的逻辑正好相反。这个操作在概念上简单但在实现时要注意索引避免移错了方向。3.4 列混淆与逆列混淆的核心伽罗瓦域乘法这是AES中最“数学”的部分。MixColumns将状态矩阵的每一列视为GF(2^8)上的一个多项式并与一个固定多项式c(x)进行模乘。逆操作则与d(x)相乘。固定矩阵如下 加密MixColumns[02 03 01 01] [01 02 03 01] [01 01 02 03] [03 01 01 02]解密InvMixColumns[0e 0b 0d 09] [09 0e 0b 0d] [0d 09 0e 0b] [0b 0d 09 0e]我们需要实现GF(2^8)上的乘法其不可约多项式为x^8 x^4 x^3 x 1十六进制表示为0x11b。def _gf_multiply(self, a, b): 在GF(2^8)上乘法使用xtime方法效率较高且易于理解 p 0 for _ in range(8): if b 1: # 如果b的最低位是1 p ^ a # 则将a加到p上在GF(2)上加就是异或 high_bit_set a 0x80 # 判断a的最高位是否为1 a 1 # a左移一位 if high_bit_set: a ^ 0x11b # 如果溢出则模不可约多项式 b 1 # b右移一位 return p基于这个乘法函数我们就可以实现列混淆。以加密的MixColumns为例它对每一列进行计算新列的每个元素都是旧列四个元素的线性组合。def mix_columns(self): 列混淆 new_state [[0] * 4 for _ in range(4)] for col in range(4): s0, s1, s2, s3 self.state[0][col], self.state[1][col], self.state[2][col], self.state[3][col] new_state[0][col] self._gf_multiply(0x02, s0) ^ self._gf_multiply(0x03, s1) ^ s2 ^ s3 new_state[1][col] s0 ^ self._gf_multiply(0x02, s1) ^ self._gf_multiply(0x03, s2) ^ s3 new_state[2][col] s0 ^ s1 ^ self._gf_multiply(0x02, s2) ^ self._gf_multiply(0x03, s3) new_state[3][col] self._gf_multiply(0x03, s0) ^ s1 ^ s2 ^ self._gf_multiply(0x02, s3) self.state new_state性能优化提示上述_gf_multiply在循环中调用次数很多加密一轮要调用4列4个元素4次乘法64次是性能热点。一个常见的优化是预先计算好与固定值2, 3, 9, 11, 13, 14的乘法结果做成查找表这就是所谓的“T表”优化。但在我们以清晰为目标的初版实现中可以先用这个清晰但稍慢的版本。3.5 密钥扩展生成每一轮的“钥匙”密钥扩展算法将初始的16字节密钥扩展成11个轮密钥AES-128需要10轮加密加上一个初始轮密钥加共11个。它的设计巧妙既保证了密钥的随机性又避免了产生弱密钥。def _key_expansion(self, key): 密钥扩展生成所有轮密钥 w [0] * 44 # AES-128共有44个32位的字4字节 # 初始的4个字就是原始密钥 for i in range(4): w[i] (key[4*i] 24) | (key[4*i1] 16) | (key[4*i2] 8) | key[4*i3] # 生成后续的字 for i in range(4, 44): temp w[i-1] if i % 4 0: # 1. 字循环左移一个字节 temp ((temp 8) 0xffffffff) | (temp 24) # 2. 字节替换使用S盒 byte0 (temp 24) 0xff byte1 (temp 16) 0xff byte2 (temp 8) 0xff byte3 temp 0xff temp (S_BOX[byte0] 24) | (S_BOX[byte1] 16) | (S_BOX[byte2] 8) | S_BOX[byte3] # 3. 与轮常量异或 rcon self._rcon(i // 4) temp ^ rcon # 4. 与前一个字异或 w[i] w[i-4] ^ temp return w def _rcon(self, i): 生成轮常量Rcon[i] [rc(i), 0x00, 0x00, 0x00] rc 1 for _ in range(1, i): rc self._gf_multiply(rc, 0x02) # 在GF(2^8)上rc(i) rc(i-1) * 2 return rc 24关键点解析密钥扩展中每4个字即每生成一个新的轮密钥后会有一个复杂的变换RotWord SubWord Rcon这引入了非线性并打破了对称性。_rcon函数中的乘法同样是在GF(2^8)上进行的。确保你的_gf_multiply函数在这里也能正确工作。4. 完整加解密流程的串联与实现4.1 加密流程的代码组装有了所有的基础组件现在我们可以把它们组装成一个完整的加密函数。def encrypt(self, plaintext): 加密一个16字节的明文块 # 1. 将明文字节加载到状态矩阵 self._bytes_to_state(plaintext) # 2. 初始轮密钥加 (使用第0个轮密钥) round_key self._get_round_key(0) self._add_round_key(round_key) # 3. 执行9轮标准轮函数 for round_num in range(1, 10): self.sub_bytes() self.shift_rows() self.mix_columns() round_key self._get_round_key(round_num) self._add_round_key(round_key) # 4. 最后一轮不含MixColumns self.sub_bytes() self.shift_rows() round_key self._get_round_key(10) self._add_round_key(round_key) # 5. 将状态矩阵输出为密文字节 ciphertext self._state_to_bytes() return ciphertext def _add_round_key(self, round_key): 轮密钥加状态矩阵与轮密钥逐字节异或 for col in range(4): word round_key[col] s0 (word 24) 0xff s1 (word 16) 0xff s2 (word 8) 0xff s3 word 0xff self.state[0][col] ^ s0 self.state[1][col] ^ s1 self.state[2][col] ^ s2 self.state[3][col] ^ s34.2 解密流程的实现要点解密是加密的逆过程但顺序并非简单倒置。因为除了InvSubBytes和InvShiftRows是直接逆操作外InvMixColumns需要在AddRoundKey之前进行并且需要用到特殊的密钥调度。正确的AES-128解密轮函数顺序为初始轮密钥加使用最后一轮密钥执行9轮InvShiftRows - InvSubBytes - AddRoundKey使用逆序的轮密钥- InvMixColumns最后一轮InvShiftRows - InvSubBytes - AddRoundKey使用初始密钥注意这里的AddRoundKey使用的密钥顺序是倒序的K10, K9, ..., K0。更高效的一种实现方式是在解密前先对轮密钥进行一个变换即对K0到K9应用InvMixColumns这样解密的流程就可以变得和加密流程完全对称InvSubBytes - InvShiftRows - InvMixColumns - AddRoundKey只是使用的组件都是逆的。为了清晰我们先实现最直观的版本。def decrypt(self, ciphertext): 解密一个16字节的密文块 self._bytes_to_state(ciphertext) # 使用第10轮密钥进行初始轮密钥加 round_key self._get_round_key(10) self._add_round_key(round_key) # 执行9轮 for round_num in range(9, 0, -1): # round_num从9递减到1 self.inv_shift_rows() self.inv_sub_bytes() round_key self._get_round_key(round_num) self._add_round_key(round_key) self.inv_mix_columns() # 注意InvMixColumns在AddRoundKey之后 # 最后一轮 self.inv_shift_rows() self.inv_sub_bytes() round_key self._get_round_key(0) # 使用初始密钥 self._add_round_key(round_key) plaintext self._state_to_bytes() return plaintext重要区别观察decrypt函数中inv_mix_columns()的位置它是在_add_round_key()之后调用的。这是解密算法标准定义所要求的与加密流程mix_columns()在_add_round_key()之前不同。如果顺序搞反解密必然失败。5. 验证、调试与常见问题实录5.1 使用标准测试向量进行验证实现完成后绝不能想当然认为它是对的。必须使用官方或广泛认可的测试向量进行验证。这里给出一个AES-128的经典测试向量密钥2b 7e 15 16 28 ae d2 a6 ab f7 15 88 09 cf 4f 3c明文32 43 f6 a8 88 5a 30 8d 31 31 98 a2 e0 37 07 34密文39 25 84 1d 02 dc 09 fb dc 11 85 97 19 6a 0b 32编写一个简单的测试函数def test_aes(): key bytes.fromhex(2b7e151628aed2a6abf7158809cf4f3c) plaintext bytes.fromhex(3243f6a8885a308d313198a2e0370734) expected_ciphertext bytes.fromhex(3925841d02dc09fbdc118597196a0b32) aes AES(key) ciphertext aes.encrypt(plaintext) print(f计算密文: {ciphertext.hex()}) print(f期望密文: {expected_ciphertext.hex()}) assert ciphertext expected_ciphertext, 加密测试失败 decrypted aes.decrypt(ciphertext) print(f解密明文: {decrypted.hex()}) print(f原始明文: {plaintext.hex()}) assert decrypted plaintext, 解密测试失败 print(所有测试通过)5.2 典型问题排查清单在复现过程中几乎一定会遇到加解密结果不对的情况。下面是一个排查清单按照从大概率到小概率的顺序进行问题现象可能原因排查方法加密结果完全不对与测试向量一个字节都对不上1.状态矩阵内存布局错误列优先/行优先搞反。2.密钥扩展错误导致所有轮密钥都是错的。3.S盒数据错误错了一个字节整个结果就面目全非。1. 单步调试在_bytes_to_state后立刻打印状态矩阵与明文字节手动核对位置。2. 打印出前两轮扩展后的轮密钥与标准文档或可靠代码的中间结果对比。3. 检查S_BOX和INV_S_BOX数组是否完整、准确复制。加密结果部分正确但中间某些字节错误1.ShiftRows移位方向或位数错误加密左移解密右移。2.MixColumns矩阵系数用错加密用{02,03,01,01}解密用{0e,0b,0d,09}。3.GF(2^8)乘法实现有误。1. 针对一个简单的输入如全零状态手动计算一轮ShiftRows后结果与程序输出对比。2. 同样用简单输入手动计算MixColumns对比结果。可以搜索在线的AES计算器辅助。3. 单独测试_gf_multiply函数验证几个关键值_gf_multiply(0x57, 0x83)应该等于0xc1。加密正确但解密失败1.解密流程顺序错误特别是InvMixColumns的位置。2.逆S盒INV_S_BOX错误或与S盒不匹配。3.解密时使用的轮密钥顺序错误。1. 严格对照标准解密流程图检查函数调用顺序。2. 验证S盒和逆S盒是否互逆INV_S_BOX[S_BOX[i]] i应对所有i成立。3. 确认decrypt函数中_get_round_key的参数是递减的。处理多块数据或填充时出错1.未处理数据填充如PKCS#7。AES是分组密码明文长度必须是16字节的倍数。2.工作模式如CBC实现有误导致块与块之间关联错误。1. 本项目聚焦于单块加解密核心算法。多块和填充属于“应用层”需额外实现。确保你的测试是针对单一块16字节。2. 如果实现了CBC等模式请先确保ECB模式即单块直接加解密完全正确。一个实用的调试技巧实现一个print_state(round)函数在每一轮加密/解密后打印出状态矩阵的十六进制值。将这些中间结果与标准文档如FIPS 197附录C中提供的中间状态进行逐轮比对。这是定位问题轮次最快的方法。5.3 从“课后习题”到实际应用的思考完成这个复现项目后再回头看那些课后习题比如“计算某一轮变换后的状态矩阵”、“给出轮密钥的第i个字”你会发现它们变得异常简单因为你已经知道了每一步在代码中对应的具体操作。更重要的是你获得了分析和解决实际中AES相关问题的能力。例如当你遇到“php aes数据不完整”的错误时你立刻会想到这可能是填充Padding问题或者CBC模式下的初始化向量IV未正确传递。当你看到“检测到目标服务支持ssl弱加密算法”的扫描报告时你会明白这可能是因为服务端配置支持了已被认为不安全的加密套件例如使用了CBC模式且没有安全的初始化向量或者甚至支持了ECB模式而不仅仅是AES算法本身的问题。如果你想在Qt或Android中集成加密功能你会知道直接使用平台提供的QAESEncryption或javax.crypto.Cipher库才是正确、安全的选择而不是嵌入自己实现的这个“教学版”AES。自己实现的版本用于学习和验证而生产环境必须使用经过严格审计和性能优化的标准库。这个亲手搭建的过程赋予你的不是一段可以投产的加密代码而是一张清晰的算法心智地图和一份排错指南。下次当加密解密出现意料之外的结果时你不再是盲目地搜索和尝试而是能够有条理地沿着数据流和算法步骤一步步定位问题的根源。这才是复现经典算法的最大价值。