Redis 源碼深度解析：SHA-1 演算法原理、填充機制與 C 語言實現細節

Redis 源碼深度解析：SHA-1 演算法原理、填充機制與 C 語言實現細節

Redis 使用 SHA-1 (Secure Hash Algorithm 1) 生成 160 位訊息摘要，其實現源碼 (sha1.c) 移植自 Valgrind 專案。本文深入剖析 SHA-1 流程、填充規則、大小端處理、核心變換函數 SHA1Transform 及四輪非線性函數 R0-R4 的位運算邏輯。

SHA-1 演算法五大步驟

1. 附加填充位：訊息長度模 512 ≡ 448 (bit)。先補 1，再補 0，至少 1 bit，最多 512 bits (64 bytes)。
2. 附加長度：補 64 bits (8 bytes) 原始訊息長度 (big-endian)，使總長度為 512 的倍數。
3. 初始化雜湊緩衝區：五個 32-bit 字 (H0-H4) 設定魔數常數。
4. 處理訊息分塊：每 512-bit 分塊執行 80 輪運算，更新雜湊值。
5. 輸出摘要：最終 H0-H4 拼接為 160-bit (20 bytes) 摘要。

核心結構體 SHA1_CTX

typedef struct {
    u_int32_t state[5];   // H0-H4，160-bit 雜湊值
    u_int32_t count[2];   // 訊息總長度 (bit)，count[0] 低 32 位，count[1] 高 32 位
    unsigned char buffer[64]; // 512-bit 訊息分塊緩衝區
} SHA1_CTX;

關鍵函數流程解析

SHA1Init — 初始化魔數

context->state[0] = 0x67452301;
context->state[1] = 0xEFCDAB89;
context->state[2] = 0x98BADCFE;
context->state[3] = 0x10325476;
context->state[4] = 0xC3D2E1F0;
context->count[0] = context->count[1] = 0;

SHA1Update — 串流式填充分塊

• 更新 count (bit 長度)，處理溢位進位。
• 計算 buffer 當前偏移 j = (count[0]>>3) & 63 (byte 偏移)。
• 若新資料湊滿 64 bytes：複製湊滿 → SHA1Transform → 後續每 64 bytes 直接 Transform → 剩餘資料複製到 buffer 開頭。
• 否則直接追加到 buffer 末尾。

SHA1Final — 完成填充、輸出摘要

1. 將 count 拆解為 8 bytes big-endian 存入 finalcount (端序無關寫法)。
2. 先填充單一 byte 0x80 (binary 10000000) — 對應「補 1 後接 0」。
3. 循環填充 0x00 直到 (count[0] & 504) == 448 (即 bit 長度模 512 ≡ 448)。
   註：& 504 (0b111111000) 與 & 511 效果相同，因 count 為 8 的倍數，低 3 bits 恆為 0。
4. 填充 8 bytes finalcount (原始長度)，觸發最後一次 SHA1Transform。
5. 將 state[5] 拆解為 20 bytes big-endian 輸出至 digest。

SHA1Transform — 核心 80 輪運算

輸入：state[5] (H0-H4)、buffer[64] (16 個 32-bit 字)。

擴展：16 字 → 80 字 W[0..79]：

• W[t] = M[t] (t=0..15)
• W[t] = ROTL1(W[t-3] ^ W[t-8] ^ W[t-14] ^ W[t-16]) (t=16..79)

四輪非線性函數 f(t) 與常數 K(t)：

每輪更新 (A,B,C,D,E 對應 v,w,x,y,z)：

TEMP = ROTL5(A) + f(t;B,C,D) + E + W[t] + K(t)
E = D; D = C; C = ROTL30(B); B = A; A = TEMP

輪後更新 H：H0+=A, H1+=B, H2+=C, H3+=D, H4+=E。

關鍵巨集實現細節

#define rol(v,b) (((v)<<(b)) | ((v)>>(32-(b))))  // 32-bit 循環左移

// 共用體：buffer 同時視為 64 bytes 或 16 個 32-bit 字
typedef union { unsigned char c[64]; u_int32_t l[16]; } CHAR64LONG16;

// blk0: 小端機器將 buffer[0..15] 轉大端 (網路序)；大端機器不動作
#define blk0(i) (block->l[i] = (rol(block->l[i],24)&0xFF00FF00) | (rol(block->l[i],8)&0x00FF00FF))

// blk: 實現 W[t] = ROTL1(W[t-3]^W[t-8]^W[t-14]^W[t-16])，利用模 16 循環覆寫 l[i&15]
#define blk(i) (block->l[i&15] = rol(block->l[(i+13)&15]^block->l[(i+8)&15]^block->l[(i+2)&15]^block->l[i&15], 1))

// 四輪運算巨集 (v,w,x,y,z 對應 A,B,C,D,E)
#define R0(v,w,x,y,z,i) z+=((w&(x^y))^y)+blk0(i)+0x5A827999+rol(v,5); w=rol(w,30);
#define R1(v,w,x,y,z,i) z+=((w&(x^y))^y)+blk(i)+0x5A827999+rol(v,5); w=rol(w,30);
#define R2(v,w,x,y,z,i) z+=(w^x^y)+blk(i)+0x6ED9EBA1+rol(v,5); w=rol(w,30);
#define R3(v,w,x,y,z,i) z+=(((w|x)&y)|(w&x))+blk(i)+0x8F1BBCDC+rol(v,5); w=rol(w,30);
#define R4(v,w,x,y,z,i) z+=(w^x^y)+blk(i)+0xCA62C1D6+rol(v,5); w=rol(w,30);

R0/R1 差異解析

• 第 0-15 輪使用 blk0 (直接取原始分塊字，含端序轉換)。
• 第 16-19 輪使用 blk (開始擴展生成 W[t])，故分離為 R1。
• 第 20-79 輪統一使用 blk 擴展，對應 R2/R3/R4。

大小端無關寫法原理

(context->count[0] >> 24) & 255 等位移操作語義為「除以 2^24 取低 8 位」，與機器儲存順序無關，確保輸出位元組序固定為 Big-Endian (網路序)。

總結

Redis 的 SHA-1 實現展示了經典雜湊演算法的高效 C 語言移植技巧：串流式填充 (Update)、端序無關序列化、共用體零拷貝視圖、巨集展開 80 輪避免函數呼叫開銷、魔數常數優化。雖 SHA-1 已不建議用於密碼學簽名，但理解其結構對學習 SHA-256、BLAKE2 等現代雜湊函數極有幫助。