每日算法 — 使用java实现SHA-256：哈希算法与位运算消息摘要

引言

SHA-256（Secure Hash Algorithm 256-bit）是美国国家安全局设计的密码学哈希函数，可将任意长度输入映射为固定256位（32字节）摘要。本文用纯Java实现SHA-256算法，不依赖任何第三方库，深入讲解消息填充、块处理、轮函数与位运算技巧。

一、算法概述

SHA-256属于Merkle-Damgard结构，处理流程为：
1. 消息填充: 使总长度 ≡ 448 (mod 512)
2. 长度附加: 附加原始消息长度（64位大端整数）
3. 分块处理: 每512位为一个消息块
4. 轮压缩: 64轮位运算更新8个工作变量

二、常量与初始化向量

public class SHA256 {
    // 前64个质数的立方根小数部分的前32位
    private static final int[] K = {
        0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5,
        0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
        0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3,
        0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
        0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc,
        0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
        0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7,
        0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
        0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13,
        0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
        0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3,
        0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
        0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5,
        0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
        0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208,
        0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2
    };

    // 前8个质数的平方根小数部分的前32位
    private static final int[] H0 = {
        0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a,
        0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19
    };
}

三、核心位运算工具

public class SHA256 {

    // 循环右移: 将32位整数向右旋转n位
    private static int rotr(int x, int n) {
        return (x >>> n) | (x << (32 - n));
    }

    // 选择函数 Ch(x,y,z) = (x & y) ^ (~x & z)
    private static int ch(int x, int y, int z) {
        return (x & y) ^ (~x & z);
    }

    // 多数函数 Maj(x,y,z) = (x & y) ^ (x & z) ^ (y & z)
    private static int maj(int x, int y, int z) {
        return (x & y) ^ (x & z) ^ (y & z);
    }

    // Sigma0: 对大端轮常量的位混合
    private static int sigma0(int x) {
        return rotr(x, 2) ^ rotr(x, 13) ^ rotr(x, 22);
    }

    // Sigma1
    private static int sigma1(int x) {
        return rotr(x, 6) ^ rotr(x, 11) ^ rotr(x, 25);
    }

    // gamma0: 消息调度的低位扩散
    private static int gamma0(int x) {
        return rotr(x, 7) ^ rotr(x, 18) ^ (x >>> 3);
    }

    // gamma1
    private static int gamma1(int x) {
        return rotr(x, 17) ^ rotr(x, 19) ^ (x >>> 10);
    }
}

四、消息填充与分块

public class SHA256 {

    /**
     * 将输入字节数组填充为512位的整数倍
     * 填充规则: 原始消息 + 1个0x80 + k个0x00 + 8字节原始长度
     */
    public static byte[] padMessage(byte[] message) {
        long originalLengthBits = (long) message.length * 8;

        // 计算需要填充的0的个数
        // 总长度 ≡ 448 (mod 512)，即总字节数 ≡ 56 (mod 64)
        int paddingLength = (64 - (message.length + 9) % 64) % 64;

        byte[] padded = new byte[message.length + 1 + paddingLength + 8];

        // 复制原始消息
        System.arraycopy(message, 0, padded, 0, message.length);

        // 附加 0x80
        padded[message.length] = (byte) 0x80;

        // 附加原始长度（64位大端）
        int lengthPos = message.length + 1 + paddingLength;
        for (int i = 0; i < 8; i++) {
            padded[lengthPos + i] = (byte) (originalLengthBits >>> (56 - i * 8));
        }

        return padded;
    }

    /**
     * 将填充后的字节数组分割为512位（64字节）的块
     */
    public static int[][] splitBlocks(byte[] padded) {
        int blockCount = padded.length / 64;
        int[][] blocks = new int[blockCount][16]; // 每块16个32位字

        for (int b = 0; b < blockCount; b++) {
            for (int w = 0; w < 16; w++) {
                int idx = b * 64 + w * 4;
                // 大端序组合4个字节为一个int
                blocks[b][w] = ((padded[idx] & 0xFF) << 24) |
                               ((padded[idx + 1] & 0xFF) << 16) |
                               ((padded[idx + 2] & 0xFF) << 8) |
                               (padded[idx + 3] & 0xFF);
            }
        }
        return blocks;
    }
}

五、轮压缩函数

public class SHA256 {

    /**
     * 处理单个512位消息块
     * @param block 16个32位字的数组
     * @param H 当前哈希值（8个32位字）
     */
    private static void processBlock(int[] block, int[] H) {
        // 1. 消息调度: 将16个字扩展为64个字
        int[] W = new int[64];
        System.arraycopy(block, 0, W, 0, 16);

        for (int t = 16; t < 64; t++) {
            W[t] = gamma1(W[t - 2]) + W[t - 7] + gamma0(W[t - 15]) + W[t - 16];
        }

        // 2. 初始化工作变量
        int a = H[0], b = H[1], c = H[2], d = H[3];
        int e = H[4], f = H[5], g = H[6], h = H[7];

        // 3. 64轮压缩
        for (int t = 0; t < 64; t++) {
            int T1 = h + sigma1(e) + ch(e, f, g) + K[t] + W[t];
            int T2 = sigma0(a) + maj(a, b, c);
            h = g;
            g = f;
            f = e;
            e = d + T1;
            d = c;
            c = b;
            b = a;
            a = T1 + T2;
        }

        // 4. 累加到哈希值
        H[0] += a; H[1] += b; H[2] += c; H[3] += d;
        H[4] += e; H[5] += f; H[6] += g; H[7] += h;
    }
}

六、完整哈希计算

public class SHA256 {

    /**
     * 计算字节数组的SHA-256摘要
     * @param message 输入消息
     * @return 32字节的哈希值
     */
    public static byte[] hash(byte[] message) {
        // 1. 填充
        byte[] padded = padMessage(message);

        // 2. 分块
        int[][] blocks = splitBlocks(padded);

        // 3. 初始化哈希值
        int[] H = H0.clone();

        // 4. 逐块处理
        for (int[] block : blocks) {
            processBlock(block, H);
        }

        // 5. 输出256位（32字节）
        byte[] digest = new byte[32];
        for (int i = 0; i < 8; i++) {
            digest[i * 4] = (byte) (H[i] >>> 24);
            digest[i * 4 + 1] = (byte) (H[i] >>> 16);
            digest[i * 4 + 2] = (byte) (H[i] >>> 8);
            digest[i * 4 + 3] = (byte) H[i];
        }

        return digest;
    }

    /**
     * 将字节数组转为十六进制字符串
     */
    public static String bytesToHex(byte[] bytes) {
        StringBuilder sb = new StringBuilder(bytes.length * 2);
        for (byte b : bytes) {
            sb.append(String.format("%02x", b & 0xFF));
        }
        return sb.toString();
    }

    /**
     * 计算字符串的SHA-256摘要
     */
    public static String hashString(String input) {
        return bytesToHex(hash(input.getBytes(java.nio.charset.StandardCharsets.UTF_8)));
    }

    public static void main(String[] args) {
        // 标准测试向量
        String[] tests = {
            "",
            "abc",
            "abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq",
            "The quick brown fox jumps over the lazy dog"
        };

        String[] expected = {
            "e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855",
            "ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad",
            "248d6a61d20638b8e5c026930c3e6039a33ce45964ff2167f6ecedd419db06c1",
            "d7a8fbb307d7809469ca9abcb0082e4f8d5651e46d3cdb762d02d0bf37c9e592"
        };

        System.out.println("SHA-256 标准测试向量验证:");
        for (int i = 0; i < tests.length; i++) {
            String result = hashString(tests[i]);
            boolean pass = result.equals(expected[i]);
            System.out.printf("Test %d: %s%n", i + 1, pass ? "PASS" : "FAIL");
            if (!pass) {
                System.out.println("  Expected: " + expected[i]);
                System.out.println("  Got:      " + result);
            }
        }

        // 雪崩效应演示
        System.out.println("\n雪崩效应测试 (输入改变1位，输出变化约50%):");
        String base = "hello world";
        String modified = "hello worle"; // 最后一个字符 d->e
        String hash1 = hashString(base);
        String hash2 = hashString(modified);
        System.out.println("'" + base + "' -> " + hash1);
        System.out.println("'" + modified + "' -> " + hash2);

        int diffBits = 0;
        for (int i = 0; i < hash1.length(); i++) {
            if (hash1.charAt(i) != hash2.charAt(i)) diffBits++;
        }
        System.out.printf("十六进制字符差异: %d/%d (%.1f%%)%n", 
            diffBits, hash1.length(), 100.0 * diffBits / hash1.length());
    }
}

七、HMAC-SHA256扩展

基于SHA-256构造消息认证码（HMAC），用于验证消息完整性与真实性：

public class HMAC_SHA256 {
    private static final int BLOCK_SIZE = 64; // SHA-256的块大小为64字节

    /**
     * 计算HMAC-SHA256
     * @param key 密钥
     * @param message 消息
     * @return HMAC值
     */
    public static byte[] hmac(byte[] key, byte[] message) {
        // 密钥处理: 超过块大小则先哈希
        if (key.length > BLOCK_SIZE) {
            key = SHA256.hash(key);
        }

        // 填充到块大小
        byte[] paddedKey = new byte[BLOCK_SIZE];
        System.arraycopy(key, 0, paddedKey, 0, key.length);

        // ipad = 0x36 重复
        byte[] ipad = new byte[BLOCK_SIZE];
        byte[] opad = new byte[BLOCK_SIZE];
        for (int i = 0; i < BLOCK_SIZE; i++) {
            ipad[i] = (byte) (paddedKey[i] ^ 0x36);
            opad[i] = (byte) (paddedKey[i] ^ 0x5c);
        }

        // H(K XOR opad || H(K XOR ipad || message))
        byte[] innerInput = new byte[BLOCK_SIZE + message.length];
        System.arraycopy(ipad, 0, innerInput, 0, BLOCK_SIZE);
        System.arraycopy(message, 0, innerInput, BLOCK_SIZE, message.length);
        byte[] innerHash = SHA256.hash(innerInput);

        byte[] outerInput = new byte[BLOCK_SIZE + innerHash.length];
        System.arraycopy(opad, 0, outerInput, 0, BLOCK_SIZE);
        System.arraycopy(innerHash, 0, outerInput, BLOCK_SIZE, innerHash.length);

        return SHA256.hash(outerInput);
    }
}

八、复杂度分析

九、安全特性分析

1. 雪崩效应: 输入1位变化导致输出约50%位变化，本文代码已验证
2. 抗碰撞性: 目前无有效方法找到两个不同输入具有相同SHA-256摘要
3. 单向性: 从摘要反推原始消息在计算上不可行
4. 长度扩展攻击防护: 直接使用SHA-256易受此攻击，应使用HMAC-SHA256

总结

本文完整实现了SHA-256哈希算法，涵盖消息填充、块处理、64轮位运算压缩及HMAC扩展。核心技巧包括大端序处理、循环移位与位选择函数的硬件友好设计。读者可以在此基础上理解更高级的密码学原语，如数字签名、PBKDF2密钥派生等。