AES算法底层实现原理

1. 基础数学知识

1.1 有限域运算

/**
 * 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盒生成

/**
 * 生成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变换

/**
 * 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变换

/**
 * 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变换

/**
 * 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 密钥扩展

// 密钥扩展实现
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 基础实现

/**
 * 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 优化实现

/**
 *  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. 性能优化要点

1. 查表优化

• 预计算S盒和GF乘法表
• 合并SubBytes、ShiftRows和MixColumns的查找表
• 使用TypedArray提高内存访问效率

2. 位运算优化

• 使用位运算代替模运算和除法
• 利用位移操作实现字节提取和组合
• 避免不必要的类型转换

3. 内存优化

• 重用状态数组
• 使用TypedArray减少内存分配
• 避免中间结果的复制

5. 面试重点

1. AES数学基础

• 有限域GF(2^8)的运算原理
• 不可约多项式的选择
• S盒的生成过程

2. 核心变换

• 四个变换的数学原理
• 为什么选择这些特定操作
• 各个步骤的密码学意义

3. 优化技术

• 查表优化的原理和实现
• 位运算优化的具体应用
• 内存管理的优化策略

4. 安全考虑

• 时序攻击的防范
• 缓存攻击的防范
• 密钥管理的最佳实践

参考资源

• FIPS 197 - AES标准
• Understanding Cryptography - AES章节
• Fast Software Encryption