![~AET3NUS]A7{[237X9)_IX2.jpg](https://ucc.alicdn.com/pic/developer-ecology/b94f627afb994c01af900fdd8929f4ac.jpg?x-oss-process=image/resize,w_1400/format,webp "~AET3NUS]A7{[237X9)_IX2.jpg")
AES加密算法
本文将不会讲述过多有关AES的数学知识, 如果有兴趣的可以自行了解。
发展历史
❝高级加密标准（英语：Advanced Encryption Standard，缩写：AES），又称Rijndael加密法（荷兰语发音：[ˈrɛindaːl]，音似英文的“Rhine doll”），是美国联邦政府采用的一种区块加密标准。这个标准用来替代原先的DES，已经被多方分析且广为全世界所使用。经过五年的甄选流程，高级加密标准由美国国家标准与技术研究院（NIST）于2001年11月26日发布于FIPS PUB 197，并在2002年5月26日成为有效的标准。现在，高级加密标准已然成为对称密钥加密中最流行的算法之一。该算法为比利时密码学家Joan Daemen和Vincent Rijmen所设计，结合两位作者的名字，以Rijndael为名投稿高级加密标准的甄选流程。
❞
S-AES
首先来看一个简化版的AES, 简化AES(S-AES)是Santa Clara大学的Edward Schaefer教授和他的学生提出来的，S-AES和AES在结构上非常相似，因为其参数规模更小，更加便于直观的显示和研究，理解了S-AES对于后面将要介绍的AES算法非常有帮助，在下文介绍AES的过程当中，我也会对比一下S-AES来进行说明，下面就先来看一下S-AES吧。
输入输出
S-AES的加密和解密均采用16位分组的消息，然后添加16位的秘钥，最终输出16位分组的结果，并且S-AES仅仅执行两轮的迭代操作。
S-AES流程
上图展示了S-AES的解密过程，主要操作即为两轮的迭代，最终由16bit的明文转换成为16bit的密文。
轮密钥加
这一步比较简单，就是分别将各个状态和密钥进行异或操作，由于异或操作的可逆性，因此加密和解密过程当中的轮密钥加步骤是完全相同的。
S-AES轮密钥加样例
半字节替代
这一步用到了一个的一个S盒，如下图所示:
S-AES-S盒
这一步操作是半个字的前半部分(二进制)作为行号，后半部分作为列号, 以1(0001)为例，可以找到(00, 01), 查表即可得到对应的结果4。
![2H$VE5{Q($74ZNHX0VK]C10.png](https://ucc.alicdn.com/pic/developer-ecology/41aaa8d44fd842719ffa52d14c2a6076.png?x-oss-process=image/resize,w_1400/format,webp "2H$VE5{Q($74ZNHX0VK]C10.png")
S-AES-半字节替代
行移位
这一步对于S-AES来说，实际上也就是将第二行的两个元素换一下位置，原始操作应该是将第二行循环移动半个字。
![A[U)O2L0LPZM%CE@U8E1$]P.png](https://ucc.alicdn.com/pic/developer-ecology/4aeff66ffc3648158ee3e9b046cdbd40.png?x-oss-process=image/resize,w_1400/format,webp "A[U)O2L0LPZM%CE@U8E1$]P.png")
S-AES-行移位
列混淆
列混淆函数对每一列进行单独操作，一列当中的每半个字节都被该函数映射成为一个新的状态，这个变换可以用矩阵乘法来表示, 注意这里的乘法运算实际上是在上的运算，具体有限域的运算我不在本文做详细的展开了，有兴趣的读者可以自行查阅相关的资料(给自己挖一个坑，后面单独写一篇文章讲一下有限域的相关知识, 这个至于什么时候填，先挖上再说吧， 哈哈)。当前可以先看做是一个特殊的乘法运算就好了。
对与逆列混淆来说，其实就是找到一个矩阵使得这个矩阵乘以上面的矩阵等于一个二街单位阵，因此列混淆的求逆操作如下:
可以发现，
再次注意，上面的运算都是基于上的运算。
密钥扩展
和其他的分组加密算法类似，对于S-AES输入的密钥是16bit, 因此需要做一个密钥扩展，将其扩展为4个新的字，总共6个字, 具体算法如下:
w_0 = k_0 \\ w_1 = k_1 \\ w_2 = w_0 \oplus g(w_1) \\ w_3 = w_2 \oplus w_1 \\ w_4 = w_2 \oplus g(w_3) \\ w_5 = w_4 \oplus w_3
![2Y2ZI7_Z78~VF%A]MYD){1R.png](https://ucc.alicdn.com/pic/developer-ecology/e9278f0c0c0447dc8b4d2d39faae9289.png?x-oss-process=image/resize,w_1400/format,webp "2Y2ZI7_Z78~VF%A]MYD){1R.png")
S-AES密钥扩展
上图给出了一个当输入密钥为2D55(0010 1101 0101 0101)的一个密钥扩展的例子。
对于S-AES，因为操作比较简单，基本可以采取手算的方式，我也推荐大家可以用笔去计算一下，加深一下理解，因此代码我就不写了, 这绝对不是因为我懒(才怪)。
到这里，S-AES基本的流程就算介绍完了，这个相对于原本的AES算法来说，简化了非常多的部分，但是对于整个细节和流程来说，还是十分相似的，因此，如果能搞懂了上面的，相信理解原始的AES将没有问题，下面来具体看一下真实的AES。
算法描述
AES没有采用经典的Feistel结构，而是每一轮都是用完整的分组内容进行处理，整体结构如下图所示:
整体结构
对于AES来说，明文分组位128位, 密钥长度可以为128位，192位，256位，在本文当中，如果不做特殊说明，均按照AES-128来进行讲解。
这里相比于S-AES来说，轮数增加了，但是整个结构还是比较相似的，最后一轮同样少一个变换。
密钥扩展算法
对于AES来说，密钥扩展算法输入值位16个字节，输出值位176个字节。按照如下的方式进行处理。
- 将原始的密钥转换成4个一组，分别存到
w当中。 - 对于剩下的40个, 按照一定的规则运算之后依次迭代填入。
整体流程如下图所示，注意这里画图顺序是竖着看的。
AES-密钥扩展算法
字节替代变换
对于AES而言，字节替代变换实际上是一个简单的查表操作，AES定义了一个SBox, 通过对应表即可得到对应的值, 如下图所示。
AES-字节替代
具体这个SBox涉及到了GF()上的运算，具体SBox是基于查表实现的取逆，因此这块原理不详细说问题也不大。相比于S-AES只是计算的有限域不同，其他基本相似。
行移位
这一步比较简单，第一行不变，第二行按照字左移一个，第三行左移两个，第四行左移三个，如下图所示:
![6O)`QB`$WMVOH]PIGRI9U_C.png](https://ucc.alicdn.com/pic/developer-ecology/d3c9560c09144c728deafe3a194382cb.png?x-oss-process=image/resize,w_1400/format,webp "6O)`QB`$WMVOH]PIGRI9U_C.png")
行移位
因为这个是一个4乘以4的矩阵，因此对行移位的时候，比起S-AES来说，要稍稍复杂一点，对于第二行开始进行循环左移一个字。
列混淆
列混淆变换的正向变换对应每一列进行独立操作，每一列的每个字节被映射成为一个新的值，如下图所示:
列混淆
这其中也是针对有限域GF(256)上面的运算，详细的数学知识也不再本文讲解了，有兴趣可以参考一下文章底部的参考链接。
给出一个乘法的实现，对着c改的rust, 哈哈, 读者在阅读代码的时候可以理解为他是一种特别的乘法就好了。
fn gmul(ap: u8, bp: u8) -> u8 { let mut p = 0u8; let mut a = ap; let mut b = bp; while a != 0 && b != 0 { if b & 1 != 0 { p ^= a; } if a & 0x80 != 0 { // XOR with the primitive polynomial x^8 + x^4 + x^3 + x + 1 (0b1_0001_1011) – you can change it but it must be irreducible a = (((a << 1) as u16) ^ 0x11b) as u8; } else { a = a << 1; } b >>= 1; } return p & 0xFF; }
同样，这个变换也可以通过一个矩阵表示:
轮密钥加
这一步是根据128位状态同128位的轮密钥进行异或运算，这一步应该比较好理解，如下图所示:
轮密钥加
同S-AES一样，这异步的正向操作和逆向操作也是一样的。
上面我只介绍了正向的变换规则，如果是解密，要做一个逆的操作，因为异或运算再做一次又回去了，其他的一次如下, 逆字节替代，逆行移位，逆列混淆。
总结
对于标准的AES本文只是简单的叙述了一下大体的流程，省略了一部分的细节，如果能搞懂S-AES相信理解标准AES并不算太难，本文并没有对有限域的相关运算详细解释，有兴趣的读者可以自行查阅相关资料。
代码实现
依然用老演员，rust了，代码仅供参考和研究学习使用，生产环境请直接使用标准库的实现。
use std::convert::TryInto; static SBOX: [[u8; 16]; 16] = [ [0x63, 0x7c, 0x77, 0x7b, 0xf2, 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], [0xcd, 0x0c, 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, 0xae, 0x08], [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], ]; static INV_SBOX: [[u8; 16]; 16] = [ [0x52, 0x09, 0x6a, 0xd5, 0x30, 0x36, 0xa5, 0x38, 0xbf, 0x40, 0xa3, 0x9e, 0x81, 0xf3, 0xd7, 0xfb], [0x7c, 0xe3, 0x39, 0x82, 0x9b, 0x2f, 0xff, 0x87, 0x34, 0x8e, 0x43, 0x44, 0xc4, 0xde, 0xe9, 0xcb], [0x54, 0x7b, 0x94, 0x32, 0xa6, 0xc2, 0x23, 0x3d, 0xee, 0x4c, 0x95, 0x0b, 0x42, 0xfa, 0xc3, 0x4e], [0x08, 0x2e, 0xa1, 0x66, 0x28, 0xd9, 0x24, 0xb2, 0x76, 0x5b, 0xa2, 0x49, 0x6d, 0x8b, 0xd1, 0x25], [0x72, 0xf8, 0xf6, 0x64, 0x86, 0x68, 0x98, 0x16, 0xd4, 0xa4, 0x5c, 0xcc, 0x5d, 0x65, 0xb6, 0x92], [0x6c, 0x70, 0x48, 0x50, 0xfd, 0xed, 0xb9, 0xda, 0x5e, 0x15, 0x46, 0x57, 0xa7, 0x8d, 0x9d, 0x84], [0x90, 0xd8, 0xab, 0x00, 0x8c, 0xbc, 0xd3, 0x0a, 0xf7, 0xe4, 0x58, 0x05, 0xb8, 0xb3, 0x45, 0x06], [0xd0, 0x2c, 0x1e, 0x8f, 0xca, 0x3f, 0x0f, 0x02, 0xc1, 0xaf, 0xbd, 0x03, 0x01, 0x13, 0x8a, 0x6b], [0x3a, 0x91, 0x11, 0x41, 0x4f, 0x67, 0xdc, 0xea, 0x97, 0xf2, 0xcf, 0xce, 0xf0, 0xb4, 0xe6, 0x73], [0x96, 0xac, 0x74, 0x22, 0xe7, 0xad, 0x35, 0x85, 0xe2, 0xf9, 0x37, 0xe8, 0x1c, 0x75, 0xdf, 0x6e], [0x47, 0xf1, 0x1a, 0x71, 0x1d, 0x29, 0xc5, 0x89, 0x6f, 0xb7, 0x62, 0x0e, 0xaa, 0x18, 0xbe, 0x1b], [0xfc, 0x56, 0x3e, 0x4b, 0xc6, 0xd2, 0x79, 0x20, 0x9a, 0xdb, 0xc0, 0xfe, 0x78, 0xcd, 0x5a, 0xf4], [0x1f, 0xdd, 0xa8, 0x33, 0x88, 0x07, 0xc7, 0x31, 0xb1, 0x12, 0x10, 0x59, 0x27, 0x80, 0xec, 0x5f], [0x60, 0x51, 0x7f, 0xa9, 0x19, 0xb5, 0x4a, 0x0d, 0x2d, 0xe5, 0x7a, 0x9f, 0x93, 0xc9, 0x9c, 0xef], [0xa0, 0xe0, 0x3b, 0x4d, 0xae, 0x2a, 0xf5, 0xb0, 0xc8, 0xeb, 0xbb, 0x3c, 0x83, 0x53, 0x99, 0x61], [0x17, 0x2b, 0x04, 0x7e, 0xba, 0x77, 0xd6, 0x26, 0xe1, 0x69, 0x14, 0x63, 0x55, 0x21, 0x0c, 0x7d], ]; static RC: [u8; 11] = [0x00, 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x1B, 0x36]; fn rot_word(word: &[u8; 4]) -> [u8; 4] { let mut result = [0u8; 4]; for i in 0..4 { result[i] = word[(i + 1) % 4]; } return result; } fn xor(a: &[u8; 4], b: &[u8; 4]) -> [u8; 4] { let mut result = [0u8; 4]; for i in 0..4 { result[i] = a[i] ^ b[i]; } return result; } fn sub_word(word: &[u8; 4]) -> [u8; 4] { let mut result = [0u8; 4]; for i in 0..4 { result[i] = substitute(word[i], true); } return result; } fn substitute(byte: u8, encryption: bool) -> u8 { let upper_nibble = ((byte >> 4) & 0xF) as usize; let lower_nibble = (byte & 0xF) as usize; match encryption { true => SBOX[upper_nibble][lower_nibble], false => INV_SBOX[upper_nibble][lower_nibble], } } /* 轮密钥加 */ fn add_round_key(state: &mut [[u8; 4]; 4], key: &[[u8; 4]; 4]) { for (i, row) in state.iter_mut().enumerate() { for (j, item) in row.iter_mut().enumerate() { *item ^= key[j][i]; } } } /* 字节替代 */ fn sub_bytes(state: &mut [[u8; 4]; 4]) { for i in 0..4 { for j in 0..4 { state[i][j] = substitute(state[i][j], true); } } } /* 逆字节替代 */ fn inv_sub_bytes(state: &mut [[u8; 4]; 4]) { for i in 0..4 { for j in 0..4 { state[i][j] = substitute(state[i][j], false); } } } /* 行移位 */ fn shift_rows(state: &mut [[u8; 4]; 4]) { for i in 1..4 { let mut tmp = vec![0u8; i]; for j in 0..i { tmp[j] = state[i][j]; } for j in 0..4 - i { state[i][j] = state[i][j + i]; } for j in 0..i { state[i][3 - j] = tmp[i - j - 1]; } } } /* 逆行移位 */ fn inv_shift_rows(state: &mut [[u8; 4]; 4]) { for i in (1..4).rev() { let mut tmp = vec![0u8; i]; for j in 0..i { tmp[j] = state[4 - i][j]; } for j in 0..4 - i { state[4 - i][j] = state[4 - i][j + i]; } for j in 0..i { state[4 - i][3 - j] = tmp[i - j - 1]; } } } fn gmul(ap: u8, bp: u8) -> u8 { let mut p = 0u8; let mut a = ap; let mut b = bp; while a != 0 && b != 0 { if b & 1 != 0 { p ^= a; } if a & 0x80 != 0 { // XOR with the primitive polynomial x^8 + x^4 + x^3 + x + 1 (0b1_0001_1011) – you can change it but it must be irreducible a = (((a << 1) as u16) ^ 0x11b) as u8; } else { a = a << 1; } b >>= 1; } return p & 0xFF; } /* 列混合 */ fn mix_columns(state: &mut [[u8; 4]; 4]) { for i in 0..4 { let mut temp = [0u8; 4]; for j in 0..4 { temp[j] = state[j][i]; } state[0][i] = gmul(temp[0], 2) ^ gmul(temp[3], 1) ^ gmul(temp[2], 1) ^ gmul(temp[1], 3); state[1][i] = gmul(temp[1], 2) ^ gmul(temp[0], 1) ^ gmul(temp[3], 1) ^ gmul(temp[2], 3); state[2][i] = gmul(temp[2], 2) ^ gmul(temp[1], 1) ^ gmul(temp[0], 1) ^ gmul(temp[3], 3); state[3][i] = gmul(temp[3], 2) ^ gmul(temp[2], 1) ^ gmul(temp[1], 1) ^ gmul(temp[0], 3); } } /* 逆列混合 */ fn inv_mix_columns(state: &mut [[u8; 4]; 4]) { for i in 0..4 { let mut temp = [0u8; 4]; for j in 0..4 { temp[j] = state[j][i]; } state[0][i] = gmul(temp[0], 14) ^ gmul(temp[3], 9) ^ gmul(temp[2], 13) ^ gmul(temp[1], 11); state[1][i] = gmul(temp[1], 14) ^ gmul(temp[0], 9) ^ gmul(temp[3], 13) ^ gmul(temp[2], 11); state[2][i] = gmul(temp[2], 14) ^ gmul(temp[1], 9) ^ gmul(temp[0], 13) ^ gmul(temp[3], 11); state[3][i] = gmul(temp[3], 14) ^ gmul(temp[2], 9) ^ gmul(temp[1], 13) ^ gmul(temp[0], 11); } } pub struct AES { key: [[u8; 4]; 44], } impl AES { pub fn new(key: &[u8]) -> AES { AES { key: AES::generate_key(key.try_into().expect("key must be 16 words")), } } fn generate_key(key: &[u8; 16]) -> [[u8; 4]; 44] { let mut original_key = [[0u8; 4]; 4]; let mut expanded_key = [[0u8; 4]; 44]; // 转换key for i in 0..16 { original_key[i / 4][i % 4] = key[i]; } for i in 0..44 { expanded_key[i] = match i { n if n < 4 => original_key[i], n if n >= 4 && n % 4 == 0 => { let mut r_con = [0u8; 4]; r_con[0] = RC[i / 4]; xor(&xor(&expanded_key[i - 4], &sub_word(&rot_word(&expanded_key[i - 1]))), &r_con) } _ => xor(&expanded_key[i - 4], &expanded_key[i - 1]), } } expanded_key } fn encrypt_block(&mut self, bytes: &[u8; 16]) -> [u8; 16] { let mut result = [0u8; 16]; let mut state = [[0u8; 4]; 4]; for i in 0..16 { state[i % 4][i / 4] = bytes[i]; } add_round_key(&mut state, self.key[0..4].try_into().expect("")); for i in 1..10 { sub_bytes(&mut state); shift_rows(&mut state); mix_columns(&mut state); add_round_key(&mut state, &self.key[i * 4..(i + 1) * 4].try_into().expect("")); } sub_bytes(&mut state); shift_rows(&mut state); add_round_key(&mut state, &self.key[40..44].try_into().expect("")); for i in 0..4 { for j in 0..4 { result[4 * j + i] = state[i][j] } } return result; } pub fn encrypt(&mut self, bytes: &[u8]) -> Vec<u8> { let mut result = vec![0u8; bytes.len()]; for i in 0..bytes.len() / 16 { let mut block = [0u8; 16]; for j in 0..16 { block[j] = bytes[i * 16 + j]; } block = self.encrypt_block(&block); for j in 0..16 { result[i * 16 + j] = block[j]; } } result } fn decrypt_block(&mut self, bytes: &[u8; 16]) -> [u8; 16] { let mut result = [0u8; 16]; let mut state = [[0u8; 4]; 4]; for i in 0..16 { state[i % 4][i / 4] = bytes[i]; } add_round_key(&mut state, &self.key[40..44].try_into().expect("")); inv_shift_rows(&mut state); inv_sub_bytes(&mut state); for i in (1..10).rev() { add_round_key(&mut state, &self.key[i * 4..(i + 1) * 4].try_into().expect("")); inv_mix_columns(&mut state); inv_shift_rows(&mut state); inv_sub_bytes(&mut state); } add_round_key(&mut state, &self.key[0..4].try_into().expect("")); for i in 0..4 { for j in 0..4 { result[4 * j + i] = state[i][j] } } return result; } pub fn decrypt(&mut self, bytes: &[u8]) -> Vec<u8> { let mut result = vec![0u8; bytes.len()]; for i in 0..bytes.len() / 16 { let mut block = [0u8; 16]; for j in 0..16 { block[j] = bytes[i * 16 + j]; } block = self.decrypt_block(&block); for j in 0..16 { result[i * 16 + j] = block[j]; } } return result; } } #[cfg(test)] mod test { use crate::aes::{AES}; #[test] fn test() { let mut aes = AES::new("0123456789ABCDEF".as_bytes()); let result = aes.encrypt("AAAAAAAAAAAAAAAA".as_bytes()); println!("{:?}", result); let result = aes.decrypt(&result); println!("{:?}", result); } }
