SHA1算法詳解

SHA1算法作為摘要算法的一種，被使用于各種簽名、摘要等場(chǎng)景，本章我們?cè)敿?xì)分析下SHA1算法細(xì)節(jié)；

術(shù)語(yǔ)定義

word：32bit的String，可以表示為8個(gè)16進(jìn)制的序列，例如A103FE23；
integer：表示?0-2^32-1?之間的數(shù)字；
block：表示512bit的String，一個(gè)block可以表示為16個(gè)word的序列（數(shù)組）；

消息填充規(guī)則

對(duì)于待摘要的消息M，先填充一個(gè)?bit 1，然后填充N個(gè)?bit 0，最后填充?64bit?的消息M的長(zhǎng)度信息（單位bit），最終需要滿足以下條件：

(消息M的長(zhǎng)度 + 1 + N + 64) % 512 = 0; PS：消息M的長(zhǎng)度單位是bit；

函數(shù)定義：

f(t;B,C,D) = (B AND C) OR ((NOT B) AND D) ( 0 <= t <= 19)
f(t;B,C,D) = B XOR C XOR D (20 <= t <= 39)
f(t;B,C,D) = (B AND C) OR (B AND D) OR (C AND D) (40 <= t <= 59)
f(t;B,C,D) = B XOR C XOR D (60 <= t <= 79).
K(t) = 5A827999 ( 0 <= t <= 19)
K(t) = 6ED9EBA1 (20 <= t <= 39)
K(t) = 8F1BBCDC (40 <= t <= 59)
K(t) = CA62C1D6 (60 <= t <= 79).
S^n(X) = (X << n) OR (X >> 32-n)

摘要算法

PS：摘要算法有兩種，一種使用內(nèi)存多一點(diǎn)兒，算法比較簡(jiǎn)單（相當(dāng)于以空間換時(shí)間），一種使用內(nèi)存少一點(diǎn)，算法比較復(fù)雜（相當(dāng)于以時(shí)間換空間），這里我們使用第一種算法，也就是使用內(nèi)存多一點(diǎn)兒，但是算法簡(jiǎn)單的；

1、聲明四個(gè)buffer：

兩個(gè)長(zhǎng)度為5的buffer，單位為word，其中一個(gè)buffer中的數(shù)據(jù)打標(biāo)為?A、B、C、D、E，另外一個(gè)buffer中的數(shù)據(jù)打標(biāo)為H0、H1、H2、H3、H4；
一個(gè)長(zhǎng)度為80的buffer，單位word，其中數(shù)據(jù)打標(biāo)為W(0)、W(1)、W(2)...W(79)；
一個(gè)長(zhǎng)度為1的buffer，單位word，打標(biāo)為TEMP；

2、將打標(biāo)為H的buffer填充為以下值：

H0: 0x67452301
H1: 0xEFCDAB89
H2: 0x98BADCFE
H3: 0x10325476
H4: 0xC3D2E1F0

3、將帶摘要的消息按照上文提到的填充規(guī)則填充；

4、將填充好后的數(shù)據(jù)按照512bit分組為M0、M1、M2...Mn來(lái)循環(huán)處理，直至所有分組處理完成，其中Mi的處理規(guī)則如下：

將Mi中的數(shù)據(jù)從左到右拆分放入W(0)、W(1)...W(15)中；PS：注意，Mi中的數(shù)據(jù)總共512bit，正好拆分為16個(gè)word放入W(0)-W(15)中；
循環(huán)處理（t從16循環(huán)到79）：W(t) = S^1(W(t-3) XOR W(t-8) XOR W(t-14) XOR W(t-16))；
使A = H0, B = H1, C = H2, D = H3, E = H4；
循環(huán)處理（t從0循環(huán)到79）：TEMP = S^5(A) + f(t;B,C,D) + E + W(t) + K(t);E = D; D = C; C = S^30(B); B = A; A = TEMP;
最后更新Hbuffer中的值：H0 = H0 + A, H1 = H1 + B, H2 = H2 + C, H3 = H3 + D, H4 = H4 + E；

當(dāng)Mn處理完成后H0 H1 H2 H3 H4就是我們需要的消息摘要；

參考文檔：

SHA1規(guī)范：RFC3174

參考Java實(shí)現(xiàn)：

import java.util.Arrays;

/**
 * RFC3174規(guī)范的參考實(shí)現(xiàn)
 * 
 * @author JoeKerouac
 * @since 1.0.0
 */
public class SHA1 {

    /**
     * block大小，單位byte
     */
    private static final int BLOCK_SIZE = 64;

    private final int[] H = new int[5];
    private final int[] W = new int[80];

    /**
     * 計(jì)算摘要信息
     *
     * @param data
     *            要計(jì)算摘要信息的數(shù)據(jù)
     * @return 計(jì)算結(jié)果
     */
    public byte[] digest(byte[] data) {
        reset();

        byte[] padding = padding(data);
        int blockCount = padding.length / BLOCK_SIZE;
        for (int i = 0; i < blockCount; i++) {
            process(padding, i * BLOCK_SIZE);
        }

        byte[] result = new byte[20];
        for (int i = 0; i < 5; i++) {
            writeInt(H[i], result, i * 4);
        }

        return result;
    }

    /**
     * 重置H狀態(tài)值
     */
    private void reset() {
        H[0] = 0x67452301;
        H[1] = 0xEFCDAB89;
        H[2] = 0x98BADCFE;
        H[3] = 0x10325476;
        H[4] = 0xC3D2E1F0;

    }

    /**
     * 填充
     * 
     * @param data
     *            要填充的數(shù)據(jù)
     * @return 填充結(jié)果
     */
    private byte[] padding(byte[] data) {
        // 計(jì)算總共需要填充的長(zhǎng)度
        int paddingSize = BLOCK_SIZE - (data.length % BLOCK_SIZE);
        paddingSize = paddingSize < 9 ? paddingSize + BLOCK_SIZE : paddingSize;

        // 開(kāi)始生成填充后的數(shù)據(jù)
        byte[] padding = new byte[data.length + paddingSize];
        System.arraycopy(data, 0, padding, 0, data.length);
        // 先填充一個(gè)bit1和7個(gè)bit0，正好對(duì)應(yīng)有符號(hào)byte值的-128
        padding[data.length] = -128;

        // 填充0
        for (int i = data.length + 1; i < padding.length - 8; i++) {
            padding[i] = 0;
        }

        // 填充原消息的長(zhǎng)度
        writeLong(data.length * 8L, padding, padding.length - 8);
        return padding;
    }

    /**
     * 將long值寫(xiě)入byte數(shù)組
     * 
     * @param value
     *            long值
     * @param data
     *            數(shù)組
     * @param offset
     *            寫(xiě)入起始位置
     */
    private void writeLong(long value, byte[] data, int offset) {
        for (int i = 0; i < 8; i++) {
            data[offset + i] = (byte)(value >>> ((7 - i) * 8) & 0xff);
        }
    }

    /**
     * 將int值寫(xiě)入byte數(shù)組
     * 
     * @param value
     *            int值
     * @param data
     *            要寫(xiě)入的數(shù)組
     * @param offset
     *            寫(xiě)入起始位置
     */
    private void writeInt(int value, byte[] data, int offset) {
        for (int i = 0; i < 4; i++) {
            data[offset + i] = (byte)(value >>> ((3 - i) * 8) & 0xff);
        }
    }

    /**
     * 從起始位置開(kāi)始往后將原始數(shù)據(jù)中的4個(gè)byte合并為一個(gè)int
     * 
     * @param data
     *            原始數(shù)據(jù)
     * @param offset
     *            起始位置
     * @return int
     */
    private int mergeToInt(byte[] data, int offset) {
        return Byte.toUnsignedInt(data[offset]) << 24 | Byte.toUnsignedInt(data[1 + offset]) << 16
            | Byte.toUnsignedInt(data[2 + offset]) << 8 | Byte.toUnsignedInt(data[3 + offset]);
    }

    /**
     * 處理數(shù)據(jù)指定起始位置開(kāi)始的一個(gè)block
     * 
     * @param data
     *            待處理的數(shù)據(jù)
     * @param offset
     *            起始位置
     */
    private void process(byte[] data, int offset) {
        for (int j = 0; j < 16; j++) {
            W[j] = mergeToInt(data, offset + j * 4);
        }

        for (int t = 16; t < 80; t++) {
            // W(t-3) XOR W(t-8) XOR W(t-14) XOR W(t-16)
            int value = W[t - 3] ^ W[t - 8] ^ W[t - 14] ^ W[t - 16];
            W[t] = value << 1 | value >>> 31;
        }

        int temp;
        int A = H[0];
        int B = H[1];
        int C = H[2];
        int D = H[3];
        int E = H[4];

        for (int t = 0; t < 80; t++) {
            // TEMP = S^5(A) + f(t;B,C,D) + E + W(t) + K(t);
            temp = (A << 5 | A >>> 27) + f(t, B, C, D) + E + W[t] + k(t);
            E = D;
            D = C;
            C = B << 30 | B >>> 2;
            B = A;
            A = temp;
        }

        H[0] += A;
        H[1] += B;
        H[2] += C;
        H[3] += D;
        H[4] += E;
    }

    /**
     * 對(duì)應(yīng)RFC3174規(guī)范中的函數(shù)K
     * 
     * @param t
     *            t
     * @return 結(jié)果
     */
    private int k(int t) {
        // K(t) = 5A827999 ( 0 <= t <= 19)
        // K(t) = 6ED9EBA1 (20 <= t <= 39)
        // K(t) = 8F1BBCDC (40 <= t <= 59)
        // K(t) = CA62C1D6 (60 <= t <= 79).
        if (t >= 0 && t <= 19) {
            return 0x5A827999;
        } else if (t <= 39) {
            return 0x6ED9EBA1;
        } else if (t <= 59) {
            return 0x8F1BBCDC;
        } else {
            return 0xCA62C1D6;
        }
    }

    /**
     * 對(duì)應(yīng)RFC3174規(guī)范中的函數(shù)f
     * 
     * @param t
     *            t
     * @param B
     *            B
     * @param C
     *            C
     * @param D
     *            D
     * @return 結(jié)果
     */
    private int f(int t, int B, int C, int D) {
        // f(t;B,C,D) = (B AND C) OR ((NOT B) AND D) ( 0 <= t <= 19)
        // f(t;B,C,D) = B XOR C XOR D (20 <= t <= 39)
        // f(t;B,C,D) = (B AND C) OR (B AND D) OR (C AND D) (40 <= t <= 59)
        // f(t;B,C,D) = B XOR C XOR D (60 <= t <= 79).
        if (t >= 0 && t <= 19) {
            return (B & C) | (~B & D);
        } else if (t <= 39) {
            return B ^ C ^ D;
        } else if (t <= 59) {
            return B & C | B & D | C & D;
        } else {
            return B ^ C ^ D;
        }
    }

    public static void main(String[] args) {
        // 假設(shè)這就是我們的數(shù)據(jù)，實(shí)際使用中將data替換為實(shí)際的數(shù)據(jù)即可
        byte[] data = new byte[63];
        SHA1 sha1 = new SHA1();
        // 計(jì)算消息摘要
        byte[] digest = sha1.digest(data);
        System.out.println(Arrays.toString(digest));
    }

聯(lián)系我

作者微信：JoeKerouac
微信公眾號(hào)（文章會(huì)第一時(shí)間更新到公眾號(hào)）：代碼深度研究院
GitHub：https://github.com/JoeKerouac