AES算法底层实现原理
1. 基础数学知识
1.1 有限域运算
javascript
/**
* GF(2^8)上的乘法实现
* @param {number} a - 第一个操作数(0-255)
* @param {number} b - 第二个操作数(0-255)
* @returns {number} - 乘法结果
*
* 原理:在有限域GF(2^8)上实现多项式乘法,使用AES标准的不可约多项式x^8 + x^4 + x^3 + x + 1 (0x11B)
*/
function gmul(a, b) {
let p = 0; // 存储结果
for(let i = 0; i < 8; i++) {
if(b & 1) { // 如果b的最低位为1
p ^= a; // 将a与p进行异或运算
}
const hiBit = a & 0x80; // 获取a的最高位
a <<= 1; // 将a左移一位
if(hiBit) {
a ^= 0x1b; // 如果最高位为1,则将a与0x1b进行异或运算
}
b >>= 1; // 将b右移一位
}
return p;
}
/**
* 预计算GF(2^8)乘法表以优化性能
* 生成256x256的查找表,避免运行时计算
*/
const GF_MUL_TABLE = new Array(256); // 创建256x256的数组
for(let x = 0; x < 256; x++) {
const row = new Array(256);
for(let y = 0; y < 256; y++) { // 遍历所有可能的y值
row[y] = gmul(x, y); // 计算x与y的乘积
}
GF_MUL_TABLE[x] = row; // 将结果存储在GF_MUL_TABLE中
}
1.2 S盒生成
javascript
/**
* 生成S盒的实现
* S盒用于 subBytes 变换,提供非线性变换
* 用于AES加密算法的非线性变换
*/
function generateSBox() {
const sbox = new Array(256);
const inv_sbox = new Array(256);
/**
* 1. 求GF(2^8)上的乘法逆元
* 通过遍历所有可能的值,找到每个元素的逆元
*/
for(let i = 0; i < 256; i++) {
if(i === 0) {
sbox[i] = 0; // 0的逆元是0
continue;
}
for(let j = 0; j < 256; j++) {
if(gmul(i, j) === 1) {
sbox[i] = j; // 找到逆元后,存储在sbox中
break;
}
}
}
/**
* 2. 仿射变换
* 将乘法逆元映射到新的位置,并添加固定向量
*/
for(let i = 0; i < 256; i++) {
let x = sbox[i];
// 矩阵乘法和向量加
let y = 0;
for(let j = 0; j < 8; j++) {
y ^= ((x >> j) & 1) << ((j + 4) % 8); // 矩阵乘法和向量加,循环左移4位和异或
}
sbox[i] = y ^ 0x63; // 0x63是固定向量
inv_sbox[sbox[i]] = i; // 同时构建逆S盒
}
return { sbox, inv_sbox }; // 返回S盒和逆S盒
}
2. 核心变换实现
2.1 SubBytes变换
javascript
/**
* SubBytes变换的基本实现
* 使用S盒替换状态矩阵中的每个字节
* @param {Array<Array<number>>} state - 4x4状态矩阵
*/
function subBytes(state) {
for(let i = 0; i < 4; i++) {
for(let j = 0; j < 4; j++) {
state[i][j] = SBOX[state[i][j]]; // 使用S盒替换状态矩阵中的每个字节
}
}
}
/**
* 优化版本 - 使用查表
* 通过DataView直接操作内存,提高性能
* @param {Array<Array<number>>} state - 4x4状态矩阵
* @param {number} offset - 状态矩阵的偏移量
*/
function subBytes_optimized(state, offset) {
const view = new DataView(state.buffer);
for(let i = 0; i < 16; i += 4) {
const word = view.getUint32(offset + i); // 获取32位无符号整数
/**
* 使用预计算表进行变换
* 矩阵乘法和向量加,循环左移4位和异或 处理最高字节
* 次高字节、中间字节、最低字节
*/
view.setUint32(
offset + i,
(T0[word >>> 24] & 0xff000000) ^ // 矩阵乘法和向量加,循环左移4位和异或 处理最高字节
(T1[(word >>> 16) & 0xff] & 0x00ff0000) ^ // 处理次高字节
(T2[(word >>> 8) & 0xff] & 0x0000ff00) ^ // 处理中间字节
(T3[word & 0xff] & 0x000000ff) // 处理最低字节
);
}
}
2.2 ShiftRows变换
javascript
/**
* ShiftRows变换的基本实现
* 对状态矩阵的每一行进行不同程度的循环左移
* @param {Array<Array<number>>} state - 4x4状态矩阵
*
* 变换规则:
* - 第0行: 不移动
* - 第1行: 左移1位
* - 第2行: 左移2位
* - 第3行: 左移3位
*/
function shiftRows(state) {
// 第一行不变
// 第二行循环左移1位
[state[1][0], state[1][1], state[1][2], state[1][3]] =
[state[1][1], state[1][2], state[1][3], state[1][0]];
// 第三行循环左移2位
[state[2][0], state[2][1], state[2][2], state[2][3]] =
[state[2][2], state[2][3], state[2][0], state[2][1]];
// 第四行循环左移3位
[state[3][0], state[3][1], state[3][2], state[3][3]] =
[state[3][3], state[3][0], state[3][1], state[3][2]];
}
/**
* ShiftRows的优化实现
* 使用位运算代替数组操作,提高性能
* @param {Uint32Array} state - 状态数组
*/
function shiftRows_optimized(state) {
// 第二行循环左移1字节
let t = state[1];
state[1] = (t << 8) | (t >>> 24);
// 第三行循环左移2字节
t = state[2];
state[2] = (t << 16) | (t >>> 16);
// 第四行循环左移3字节
t = state[3];
state[3] = (t << 24) | (t >>> 8);
}
2.3 MixColumns变换
javascript
/**
* MixColumns变换的基本实现
* 将状态矩阵的每一列与固定矩阵相乘
* @param {Array<Array<number>>} state - 4x4状态矩阵
*
* 固定矩阵:
* [02 03 01 01]
* [01 02 03 01]
* [01 01 02 03]
* [03 01 01 02]
*/
// MixColumns实现
function mixColumns(state) {
for(let i = 0; i < 4; i++) {
const s0 = state[0][i];
const s1 = state[1][i];
const s2 = state[2][i];
const s3 = state[3][i];
// 矩阵乘法和向量加,循环左移4位和异或 处理最高字节
state[0][i] = gmul(0x02, s0) ^ gmul(0x03, s1) ^ s2 ^ s3;
state[1][i] = s0 ^ gmul(0x02, s1) ^ gmul(0x03, s2) ^ s3; // 处理次高字节
state[2][i] = s0 ^ s1 ^ gmul(0x02, s2) ^ gmul(0x03, s3); // 处理中间字节
state[3][i] = gmul(0x03, s0) ^ s1 ^ s2 ^ gmul(0x02, s3); // 处理最低字节
}
}
/**
* MixColumns的优化实现
* 使用预计算表代替运行时计算
* @param {Array<Array<number>>} state - 状态矩阵
*/
function mixColumns_optimized(state) {
for(let i = 0; i < 4; i++) {
const s0 = state[0][i];
const s1 = state[1][i];
const s2 = state[2][i];
const s3 = state[3][i];
// 使用T表合并subBytes、shiftRows和mixColumns
state[0][i] = T0[s0] ^ T1[s1] ^ T2[s2] ^ T3[s3];
state[1][i] = T0[s1] ^ T1[s2] ^ T2[s3] ^ T3[s0];
state[2][i] = T0[s2] ^ T1[s3] ^ T2[s0] ^ T3[s1];
state[3][i] = T0[s3] ^ T1[s0] ^ T2[s1] ^ T3[s2];
}
}
2.4 密钥扩展
javascript
// 密钥扩展实现
function keyExpansion(key, w, Nk, Nr) {
const Nb = 4; // AES固定块大小为4
// 复制初始密钥
for(let i = 0; i < Nk; i++) {
w[i] = (key[4*i] << 24) |
(key[4*i+1] << 16) |
(key[4*i+2] << 8) |
key[4*i+3];
}
// 扩展密钥
for(let i = Nk; i < Nb * (Nr + 1); i++) {
let temp = w[i-1];
if(i % Nk === 0) {
// RotWord
temp = ((temp << 8) | (temp >>> 24)) & 0xffffffff;
// SubWord
temp = (SBOX[temp >>> 24] << 24) |
(SBOX[(temp >>> 16) & 0xff] << 16) |
(SBOX[(temp >>> 8) & 0xff] << 8) |
SBOX[temp & 0xff];
// Rcon
temp ^= RCON[i/Nk - 1] << 24;
}
else if(Nk > 6 && i % Nk === 4) {
// 仅AES-256需要额外的SubWord
temp = (SBOX[temp >>> 24] << 24) |
(SBOX[(temp >>> 16) & 0xff] << 16) |
(SBOX[(temp >>> 8) & 0xff] << 8) |
SBOX[temp & 0xff];
}
w[i] = w[i-Nk] ^ temp;
}
}
3. 完整加密过程
3.1 基础实现
javascript
/**
* AES类的基础实现
* 包含密钥扩展和加密过程
* @param {Array<number>} key - 16字节密钥
*/
class AES {
constructor(key) {
this.Nk = key.length / 4; // 密钥长度(32位字)
this.Nr = this.Nk + 6; // 轮数(128位密钥10轮,192位密钥12轮,256位密钥14轮)
this.w = new Array(4 * (this.Nr + 1)); // 轮密钥
// 密钥扩展
keyExpansion(key, this.w, this.Nk, this.Nr);
}
/**
* 加密一个数据块(16字节)
* @param {Uint8Array} input - 明文数据块
* @returns {Uint8Array} - 密文数据块
*/
encrypt(input) {
const state = this._createState(input);
// 初始轮密钥加
this._addRoundKey(state, 0);
// Nr-1轮变换
for(let round = 1; round < this.Nr; round++) {
this._subBytes(state);
this._shiftRows(state);
this._mixColumns(state);
this._addRoundKey(state, round);
}
// 最后一轮(没有MixColumns)
this._subBytes(state);
this._shiftRows(state);
this._addRoundKey(state, this.Nr);
return this._stateToOutput(state);
}
// 辅助方法
_createState(input) {/*...*/}
_stateToOutput(state) {/*...*/}
_addRoundKey(state, round) {/*...*/}
}
3.2 优化实现
javascript
/**
* AES加密算法的优化实现类
* 主要优化点:
* 1. 使用查表法代替运算
* 2. 合并SubBytes、ShiftRows和MixColumns操作
* 3. 使用TypedArray提升性能
*/
class AES_Optimized {
// 构造函数 加密密钥
constructor(key) {
// 初始化同基础实现
this.Nk = key.length / 4;
this.Nr = this.Nk + 6;
this.w = new Array(4 * (this.Nr + 1));
// 初始化同上
this._generateTables(); // 生成优化用的查找表
}
_generateTables() {
// 生成T0-T3表
this.T0 = new Array(256);
this.T1 = new Array(256);
this.T2 = new Array(256);
this.T3 = new Array(256);
for(let x = 0; x < 256; x++) {
const s = SBOX[x]; // S盒替换
const t = GF_MUL_TABLE[s]; // GF乘法表查找
// T0表:[2s,s,s,3s]
this.T0[x] = (t[0x02] << 24) | (s << 16) | (s << 8) | t[0x03];
// T1表:[3s,2s,s,s]
this.T1[x] = (t[0x03] << 24) | (t[0x02] << 16) | (s << 8) | s;
// T2表:[s,3s,2s,s]
this.T2[x] = (s << 24) | (t[0x03] << 16) | (t[0x02] << 8) | s;
// T3表:[s,s,3s,2s]
this.T3[x] = (s << 24) | (s << 16) | (t[0x03] << 8) | t[0x02];
}
}
/**
* 优化版本的加密实现
* @param {Uint8Array} input - 16字节明文输入
* @returns {Uint8Array} - 16字节密文输出
*/
encrypt(input) {
// 使用Uint32Array提高性能,TypedArray优化内存访问
let state = new Uint32Array(4);
// 转换输入
for(let i = 0; i < 4; i++) {
state[i] = (input[4*i] << 24) | // 处理最高字节
(input[4*i+1] << 16) | // 处理次高字节
(input[4*i+2] << 8) | // 处理中间字节
input[4*i+3]; // 处理最低字节
}
// 初始轮密钥加
for(let i = 0; i < 4; i++) {
state[i] ^= this.w[i];
}
// 主要轮函数
for(let round = 1; round < this.Nr; round++) {
const s0 = state[0];
const s1 = state[1];
const s2 = state[2];
const s3 = state[3];
// 合并SubBytes、ShiftRows和MixColumns
state[0] = this.T0[s0 >>> 24] ^ // 第0字节通过T0表处理
this.T1[(s1 >>> 16) & 0xff] ^ // 第1字节通过T1表处理
this.T2[(s2 >>> 8) & 0xff] ^ // 第2字节通过T2表处理
this.T3[s3 & 0xff] ^ // 第3字节通过T3表处理
this.w[4*round]; // 轮密钥加
state[1] = this.T0[s1 >>> 24] ^
this.T1[(s2 >>> 16) & 0xff] ^
this.T2[(s3 >>> 8) & 0xff] ^
this.T3[s0 & 0xff] ^
this.w[4*round + 1];
state[2] = this.T0[s2 >>> 24] ^
this.T1[(s3 >>> 16) & 0xff] ^
this.T2[(s0 >>> 8) & 0xff] ^
this.T3[s1 & 0xff] ^
this.w[4*round + 2];
state[3] = this.T0[s3 >>> 24] ^
this.T1[(s0 >>> 16) & 0xff] ^
this.T2[(s1 >>> 8) & 0xff] ^
this.T3[s2 & 0xff] ^
this.w[4*round + 3];
}
// 最后一轮(不使用MixColumns)
const result = new Uint8Array(16);
for(let i = 0; i < 4; i++) {
const t = state[i] ^ this.w[4*this.Nr + i];
result[4*i] = SBOX[t >>> 24]; // 处理最高字节
result[4*i+1] = SBOX[(t >>> 16) & 0xff]; // 处理次高字节
result[4*i+2] = SBOX[(t >>> 8) & 0xff]; // 处理中间字节
result[4*i+3] = SBOX[t & 0xff]; // 处理最低字节
}
return result;
}
}
4. 性能优化要点
- 查表优化
- 预计算S盒和GF乘法表
- 合并SubBytes、ShiftRows和MixColumns的查找表
- 使用TypedArray提高内存访问效率
- 位运算优化
- 使用位运算代替模运算和除法
- 利用位移操作实现字节提取和组合
- 避免不必要的类型转换
- 内存优化
- 重用状态数组
- 使用TypedArray减少内存分配
- 避免中间结果的复制
5. 面试重点
- AES数学基础
- 有限域GF(2^8)的运算原理
- 不可约多项式的选择
- S盒的生成过程
- 核心变换
- 四个变换的数学原理
- 为什么选择这些特定操作
- 各个步骤的密码学意义
- 优化技术
- 查表优化的原理和实现
- 位运算优化的具体应用
- 内存管理的优化策略
- 安全考虑
- 时序攻击的防范
- 缓存攻击的防范
- 密钥管理的最佳实践