Cơ chế hoạt động của Secure Hash Algorithm (SHA)

SHA (Secure Hash Algorithm) là họ hàm băm mật mã do NIST/NSA thiết kế. Bài viết tập trung vào SHA-1 (lịch sử) và SHA-256 (tiêu chuẩn hiện tại) — cấu trúc Merkle-Damgård.

SHA-256: Quy trình chi tiết (FIPS 180-4)

Bước 1: Padding (Đệm thông điệp)

• Thông điệp M độ dài L bit.
• Thêm bit 1.
• Thêm k bit 0 sao cho: L + 1 + k ≡ 448 (mod 512).
• Thêm 64-bit big-endian encoding của L (độ dài bản gốc).
• Kết quả: độ dài ≡ 0 (mod 512). Padding luôn được thêm (ngay cả khi đã đúng độ dài).

Bước 2: Phân chia khối (Parsing)

• Chia padded message thành N khối 512-bit (M⁽¹⁾, M⁽²⁾, ..., M⁽ᴺ⁾).
• Mỗi khối 512-bit = 16 word 32-bit (big-endian).

Bước 3: Khởi tạo trạng thái (Initial Hash Value - IV)

8 thanh ghi 32-bit (A..H) khởi tạo từ phần thập phân của căn bậc 2 của 8 số nguyên tố đầu tiên:

H₀ = 6a09e667  bb67ae85  3c6ef372  a54ff53a
     510e527f  9b05688c  1f83d9ab  5be0cd19
# Big-endian: most significant byte first

Bước 4: Mở rộng Message Schedule (W[0..63])

Từ 16 word Mᵢ (32-bit) → sinh 64 word W[t]:

W[t] = M[t]                              for t = 0..15
W[t] = σ₁(W[t-2]) + W[t-7] + σ₀(W[t-15]) + W[t-16]   for t = 16..63

σ₀(x) = ROTR⁷(x) ⊕ ROTR¹⁸(x) ⊕ SHR³(x)
σ₁(x) = ROTR¹⁷(x) ⊕ ROTR¹⁹(x) ⊕ SHR¹⁰(x)
# + là cộng modulo 2³²

Bước 5: Vòng nén (Compression Function) — 64 vòng

Khởi tạo working variables: a..h = H₀..H₇.

Mỗi vòng t = 0..63:

T₁ = h + Σ₁(e) + Ch(e,f,g) + K[t] + W[t]
T₂ = Σ₀(a) + Maj(a,b,c)
h = g; g = f; f = e; e = d + T₁
d = c; c = b; b = a; a = T₁ + T₂

Ch(x,y,z) = (x ∧ y) ⊕ (¬x ∧ z)        # Choose
Maj(x,y,z) = (x ∧ y) ⊕ (x ∧ z) ⊕ (y ∧ z)  # Majority
Σ₀(x) = ROTR²(x) ⊕ ROTR¹³(x) ⊕ ROTR²²(x)
Σ₁(x) = ROTR⁶(x) ⊕ ROTR¹¹(x) ⊕ ROTR²⁵(x)
K[t] = 64 hằng số (căn bậc 3 của 64 số nguyên tố đầu tiên, phần thập phân)

Bước 6: Cập nhật trạng thái & Output

Hᵢ = Hᵢ₋₁ + (a,b,c,d,e,f,g,h)  # Cộng modulo 2³² từng word
# Sau khối cuối N: Hash = Hᴺ (256-bit = 8 word 32-bit)

SHA-512 (Tương tự, 64-bit word)

• Block 1024-bit, 16 word 64-bit → mở rộng 80 word.
• 80 vòng. IV từ căn bậc 2 của 8 số nguyên tố đầu tiên (64-bit).
• Hằng số K[t] từ căn bậc 3 của 80 số nguyên tố đầu tiên.
• Output 512-bit (8 word 64-bit). Nhanh hơn trên CPU 64-bit.

SHA-3 (Keccak) — Kiến trúc khác hoàn toàn (Sponge)

• State 1600-bit = rate (r) + capacity (c). SHA3-256: r=1088, c=512.
• Absorb: XOR block r-bit vào state → Keccak-f[1600] (24 vòng permutation).
• Squeeze: Output r-bit → Keccak-f nếu cần thêm.
• Không length extension. XOF (SHAKE128/256) output tùy ý.

Tóm tắt so sánh

Khuyến nghị 2024: Mặc định SHA-256 (phổ biến, hardware accel, an toàn). Cần XOF/domain separation → SHAKE256. Hiệu năng cao đa luồng → BLAKE3. Dự phòng/đa dạng → SHA3-256.