每日算法 — 使用java实现AES加密：分组密码与轮函数变换

概述

AES（Advanced Encryption Standard）是目前最广泛使用的对称加密算法之一，由美国国家标准与技术研究院（NIST）于2001年确立。本文将用Java从零实现AES-128的核心逻辑，深入讲解密钥扩展、字节替换、行移位、列混淆和轮密钥加五大变换，帮助读者理解现代密码学的数学基础。

算法原理

AES属于分组密码，固定分组长度为128位（16字节），密钥长度支持128、192、256位。AES-128使用10轮迭代，每轮包含四个基本变换：

1. SubBytes（字节替换）：通过S盒进行非线性替换
2. ShiftRows（行移位）：对状态矩阵的每一行进行循环移位
3. MixColumns（列混淆）：在GF(2⁸)域上进行矩阵乘法
4. AddRoundKey（轮密钥加）：将状态与轮密钥进行异或

Java实现

核心常量定义

public class AES128 {
    // AES S盒（256字节）
    private static final int[] SBOX = {
        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
    };

    // 逆S盒
    private static final int[] INV_SBOX = new int[256];
    static {
        for (int i = 0; i < 256; i++) {
            INV_SBOX[SBOX[i]] = i;
        }
    }

    // 轮常数
    private static final int[] RCON = {
        0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x1b, 0x36
    };

    private static final int NB = 4;  // 列数（32位字）
    private static final int NR = 10; // 轮数（AES-128）
    private static final int NK = 4;  // 密钥字数

    // 状态矩阵：4x4字节数组
    private int[][] state;

密钥扩展算法

    /**
     * 密钥扩展：将128位主密钥扩展为11组轮密钥（每组128位）
     */
    public int[][] keyExpansion(byte[] key) {
        int[][] w = new int[NB * (NR + 1)][4];

        // 前NK个字直接复制密钥
        for (int i = 0; i < NK; i++) {
            w[i][0] = key[4 * i] & 0xFF;
            w[i][1] = key[4 * i + 1] & 0xFF;
            w[i][2] = key[4 * i + 2] & 0xFF;
            w[i][3] = key[4 * i + 3] & 0xFF;
        }

        // 扩展剩余字
        for (int i = NK; i < NB * (NR + 1); i++) {
            int[] temp = new int[]{w[i-1][0], w[i-1][1], w[i-1][2], w[i-1][3]};

            if (i % NK == 0) {
                // RotWord + SubWord + Rcon
                temp = rotWord(temp);
                temp = subWord(temp);
                temp[0] ^= RCON[i / NK - 1];
            }

            w[i][0] = w[i - NK][0] ^ temp[0];
            w[i][1] = w[i - NK][1] ^ temp[1];
            w[i][2] = w[i - NK][2] ^ temp[2];
            w[i][3] = w[i - NK][3] ^ temp[3];
        }

        return w;
    }

    private int[] rotWord(int[] word) {
        return new int[]{word[1], word[2], word[3], word[0]};
    }

    private int[] subWord(int[] word) {
        return new int[]{
            SBOX[word[0]], SBOX[word[1]],
            SBOX[word[2]], SBOX[word[3]]
        };
    }

核心轮变换

    /**
     * 字节替换：使用S盒对每个字节进行非线性替换
     */
    private void subBytes() {
        for (int r = 0; r < 4; r++) {
            for (int c = 0; c < 4; c++) {
                state[r][c] = SBOX[state[r][c]];
            }
        }
    }

    /**
     * 逆字节替换
     */
    private void invSubBytes() {
        for (int r = 0; r < 4; r++) {
            for (int c = 0; c < 4; c++) {
                state[r][c] = INV_SBOX[state[r][c]];
            }
        }
    }

    /**
     * 行移位：第i行循环左移i个字节
     */
    private void shiftRows() {
        for (int r = 1; r < 4; r++) {
            int[] temp = new int[4];
            for (int c = 0; c < 4; c++) {
                temp[c] = state[r][(c + r) % 4];
            }
            System.arraycopy(temp, 0, state[r], 0, 4);
        }
    }

    /**
     * 逆行移位
     */
    private void invShiftRows() {
        for (int r = 1; r < 4; r++) {
            int[] temp = new int[4];
            for (int c = 0; c < 4; c++) {
                temp[c] = state[r][(c - r + 4) % 4];
            }
            System.arraycopy(temp, 0, state[r], 0, 4);
        }
    }

    /**
     * GF(2^8)上的乘法
     */
    private int gmul(int a, int b) {
        int p = 0;
        for (int i = 0; i < 8; i++) {
            if ((b & 1) != 0) p ^= a;
            boolean hiBitSet = (a & 0x80) != 0;
            a <<= 1;
            if (hiBitSet) a ^= 0x1b; // 模x^8 + x^4 + x^3 + x + 1
            b >>= 1;
        }
        return p & 0xFF;
    }

    /**
     * 列混淆：在GF(2^8)上与固定矩阵相乘
     */
    private void mixColumns() {
        for (int c = 0; c < 4; c++) {
            int a0 = state[0][c], a1 = state[1][c];
            int a2 = state[2][c], a3 = state[3][c];
            state[0][c] = gmul(a0, 2) ^ gmul(a1, 3) ^ a2 ^ a3;
            state[1][c] = a0 ^ gmul(a1, 2) ^ gmul(a2, 3) ^ a3;
            state[2][c] = a0 ^ a1 ^ gmul(a2, 2) ^ gmul(a3, 3);
            state[3][c] = gmul(a0, 3) ^ a1 ^ a2 ^ gmul(a3, 2);
        }
    }

    /**
     * 轮密钥加：状态与轮密钥逐字节异或
     */
    private void addRoundKey(int[][] roundKey, int round) {
        for (int c = 0; c < 4; c++) {
            for (int r = 0; r < 4; r++) {
                state[r][c] ^= roundKey[round * 4 + c][r];
            }
        }
    }

加密与解密主流程

    /**
     * AES-128加密单分组（16字节）
     */
    public byte[] encrypt(byte[] input, byte[] key) {
        int[][] w = keyExpansion(key);
        state = new int[4][4];

        // 输入转为状态矩阵（列优先）
        for (int c = 0; c < 4; c++) {
            for (int r = 0; r < 4; r++) {
                state[r][c] = input[r + 4 * c] & 0xFF;
            }
        }

        addRoundKey(w, 0);

        for (int round = 1; round < NR; round++) {
            subBytes();
            shiftRows();
            mixColumns();
            addRoundKey(w, round);
        }

        subBytes();
        shiftRows();
        addRoundKey(w, NR);

        // 状态矩阵转输出
        byte[] output = new byte[16];
        for (int c = 0; c < 4; c++) {
            for (int r = 0; r < 4; r++) {
                output[r + 4 * c] = (byte) state[r][c];
            }
        }
        return output;
    }

    /**
     * PKCS7填充
     */
    public byte[] pkcs7Padding(byte[] data) {
        int blockSize = 16;
        int padLen = blockSize - (data.length % blockSize);
        byte[] padded = new byte[data.length + padLen];
        System.arraycopy(data, 0, padded, 0, data.length);
        for (int i = data.length; i < padded.length; i++) {
            padded[i] = (byte) padLen;
        }
        return padded;
    }

    public static void main(String[] args) {
        AES128 aes = new AES128();
        byte[] key = "Thats my Kung Fu".getBytes(); // 16字节密钥
        byte[] plaintext = "Two One Nine Two".getBytes();

        byte[] ciphertext = aes.encrypt(plaintext, key);
        System.out.println("密文: " + bytesToHex(ciphertext));
    }

    private static String bytesToHex(byte[] bytes) {
        StringBuilder sb = new StringBuilder();
        for (byte b : bytes) {
            sb.append(String.format("%02x", b));
        }
        return sb.toString();
    }
}

安全性分析

AES的安全性建立在以下数学基础之上：

• 非线性层（S盒）：提供混淆，抵抗差分攻击和线性攻击
• 线性层（行移位+列混淆）：提供扩散，确保单个输入位影响多个输出位
• 密钥扩展：确保轮密钥之间的统计独立性

目前AES-128尚无实用的密码分析攻击，穷举2^128次密钥在计算上不可行。

复杂度分析

总结

本文完整实现了AES-128的核心算法，包括密钥扩展、四轮变换和PKCS7填充。通过手写代码，读者可以深入理解分组密码的设计思想：混淆与扩散的完美结合。在实际工程中，建议使用Java标准库的javax.crypto.Cipher，但理解底层原理对于密码学安全至关重要。