SHA3(Secure Hash Algorithm 3)

 最近在看 PQC (後量子密碼學) 的 ML SDA 當中有用到 SHA3 , 小有所感趁機紀錄以下的內容根據 FIPS 官方資料 (https://csrc.nist.gov/pubs/fips/202/final)進行閱讀後的整理

前言

在資訊安全領域裡，「雜湊函數（Hash Function）」是一個基礎但極其重要的工具。它能夠將任何長度的輸入訊息，轉換成固定長度的輸出（稱為訊息摘要）。這個摘要具有以下特性：

• 不可逆：幾乎不可能從輸出反推出原始輸入。
• 抗碰撞：不同的輸入幾乎不會產生相同的輸出。
• 固定長度：無論輸入多大，輸出長度固定。

這些特性，讓 Hash 被廣泛應用於：

• 驗證資料完整性（檔案驗證、下載檢查碼）。
• 數位簽章與驗證。
• 密碼學基礎建構（例如 HMAC、隨機數產生器）。

在過去幾十年，SHA（Secure Hash Algorithm, 安全雜湊演算法）系列成為最常用的雜湊家族。從 SHA-0、SHA-1 到 SHA-2，逐步守護著資訊安全。然而，隨著計算能力提升以及演算法分析技術進步，舊有的雜湊標準逐漸顯現弱點。這也引出了今天的主角：SHA-3。

SHA 的歷史

• SHA-0（1993 年）
• 第一版安全雜湊演算法，由美國國家安全局（NSA）設計並發表。
• 由於存在安全弱點，很快就被棄用。
• SHA-1（1995 年）
• 改良後的版本，輸出長度為 160 位元。
• 曾廣泛應用在 SSL、數位簽章、檔案驗證等場景。
• 但隨著 2017 年 Google 公布實際碰撞攻擊實例，SHA-1 正式被視為不再安全。
•     SHA-2（2001 年）
• 包含多個版本：SHA-224、SHA-256、SHA-384、SHA-512。
• 輸出長度更長，設計更安全，目前仍被廣泛使用。
• 但其設計仍是基於 Merkle–Damgård 結構，若未來計算能力大幅提升，潛在風險依舊存在。

•     SHA-3（2015 年，正式標準化）
• 由 Keccak 演算法在 NIST（美國國家標準技術研究院）舉辦的雜湊演算法競賽中勝出。
• 最大的不同是：架構完全不同。SHA-3 基於 Sponge 結構，而不是傳統的 Merkle–Damgård。
• 這使得 SHA-3 在安全性與彈性上具備不同優勢，也能衍生出 SHAKE（可延伸輸出長度的雜湊函數）。

SHA-3 的核心設計 — Sponge 結構

    SHA-3 與過去的 SHA-1、SHA-2 最大的不同在於底層架構。
    傳統 SHA-1、SHA-2 採用 Merkle–Damgård 結構，而 SHA-3 採用 Sponge 結構。

Sponge 結構是什麼？

    "Sponge" 這個詞在英文中是「海綿」的意思。它的運作方式就像海綿一樣：

• 吸收 (Absorb)：把輸入的訊息分段「吸收」進去。
• 擠出 (Squeeze)：再從內部「擠出」固定長度的雜湊值。

    這樣的設計讓 SHA-3 擁有更高的彈性，可以產生不同長度的輸出（例如 SHAKE），同時提升了安全性。

基本名詞及定義

    在 SHA-3 中，Sponge 結構運作的核心是一個 state（狀態），記為 b 位元。

    這個狀態又分成兩個部分：

• Rate (r)：用來與輸入或輸出互動的區域。
• Capacity (c)：保留安全性緩衝的區域，不直接與外部互動。

    公式表示為：𝑏 = 𝑟 + 𝑐 

    在 SHA-3 標準中，b 固定為 1600 bits。

    下表為整理出來在不同的 SHA3 所對應的 d (輸出長度)、b (state size)、b (state size)、r = b – c (rate)

    Sponge 結構運作流程

    1. Padding（填充）將訊息補成可以被 r 整除的長度。

    2. Absorb（吸收）每次取 r 位元輸入，與 state 的前 r 位做 XOR。每次吸收後，都執行一次 permutation（Keccak-f）。
    3. Squeeze（擠出）吸收完成後，從 state 的前 r 位元取出輸出。若輸出不足，再跑 permutation，直到得到所需長度。

    SHA-3 運算流程

SHA-3 的運算可以分成以下幾個主要階段，每一步都對最終的安全性與結果至關重要：

• Padding（訊息填充）：先將輸入訊息補成符合規格的長度。
• Absorb（吸收）：將訊息分段後，依序與狀態的前 r 位 XOR，並搭配 permutation。
• Permutation（排列）：核心計算，包括五個步驟（θ、ρ、π、χ、ι），持續執行 24 輪。
• Squeeze（擠出）：當所有輸入都吸收完，開始從狀態輸出結果。
• Output（輸出結果）：依據需求產生固定長度（SHA3-256 等）或可變長度（SHAKE）的雜湊值。

    1. Padding（訊息填充）

在進入 Sponge 結構之前，訊息需要先經過填充，才能確保長度符合演算法需求。這個步驟稱為 Padding（填充）。

SHA-3 採用的填充方式叫做 pad10*1，規則如下： 

M′=M∥1∥0i∥1

• M：原始訊息
• ∥ parallel：表示「串接」
• 0^i：i 個連續的 0，比數由需求決定

換句話說：填充的步驟是： 

1. 在訊息後面加上一個 1。 
2. 補上一些 0，直到總長度距離 r 的整數倍只差一個位元。 
3. 最後再補上一個 1。 

這樣能確保填充後的訊息長度剛好是 r 的整數倍，能被正確切分為多個區塊進入吸收階段。

Domain 區分

SHA-3 還有一個小設計，就是 Domain 分類碼，用來區分不同的演算法：

SHA3(固定長度雜湊)：在填充時加上 01

SHAKE(可變長度雜湊，XOF)：在填充時加上 1111

這樣，即使處理相同的輸入，SHA3 與 SHAKE 也能得到不同的結果，避免不同演算法之間的混淆。

    2. Absorb（吸收）

在訊息經過 Padding（填充） 之後，就會被分割成一個個長度為 r 的區塊。

這些區塊會依序被「吸收」進 Sponge 結構的狀態（state） 

吸收的過程可以簡單描述為： 

1. 取一個長度為 r 的區塊。 
2. 與 state 的前 r 位做 XOR。 
3. 對整個 state 執行一次 permutation（Keccak-f）。 
4. 重複以上步驟，直到所有區塊都處理完成。 

Absorb 就像是在「一邊倒入訊息，一邊不斷攪拌」；每次加入新的一部分資料，整個 state 就會被重新混合，確保所有輸入都影響到最終輸出。 

 

「完成所有訊息的吸收後，Sponge 結構內部的 state 已經被充分混合。接下來，進入 SHA-3 的核心——Permutation（排列），也就是核心的五大運算：θ、ρ、π、χ、ι。」 

    3. Permutation（排列）

在 SHA-3 的 Sponge 結構中，每吸收一個區塊，state 就會經過一次 Permutation（排列），這是 SHA-3 的核心運算。

這個排列函數稱為 Keccak-f，它的作用就是不斷地重新「打散」state 中的資料，讓任何一點輸入變化都能擴散到整個 1600-bit 的狀態中。

Keccak-f 的運算由 24 輪（Rounds） 組成，每一輪包含五個子步驟：

• θ (Theta) – 行間的奇偶校正，確保每個 bit 都與其他列發生關聯。
• ρ (Rho) – 位元內的旋轉，將數據以不同的位移方式重新排列。
• π (Pi) – 位置置換，把資料在整個矩陣中打散。
• χ (Chi) – 非線性替換，讓結果不可逆，增強雜湊的安全性。
• ι (Iota) – 注入常數（Round Constant），打破排列中的對稱性。

這五大步驟會依序執行，完成一次 round。總共 24 輪運算，讓輸入徹底「混合」，為最終輸出提供強大的安全性基礎。

數學計算的 x,y,z 座標方向

 

    3.1 θ (Theta) 

目的 

    每一個 bit 和矩陣中其他列產生關聯，避免單獨某一列被孤立。

數學定義  

    Input : state array A.

    Output : state array A′.

    Steps : 

    1. For all pairs (x, z) such that 0 ≤ x < 5 and 0 ≤ z < w, let C[x, z] = A[x, 0, z] ⊕ A[x, 1, z] ⊕ A[x, 2, z] ⊕ A[x, 3, z] ⊕ A[x, 4, z].

    2. For all pairs (x, z) such that 0 ≤ x < 5 and 0 ≤ z < w let D[x, z] = C[(x - 1) mod 5, z] ⊕ C[(x+1) mod 5, (z – 1) mod w].

    3. For all triples (x, y, z) such that 0 ≤ x < 5, 0 ≤ y < 5, and 0 ≤ z < w, let A′[x, y, z] = A[x, y, z] ⊕ D[x, z].

    可以把 θ 想像成「幫每一欄加上來自左右兩邊的修正」。這樣一來，state 中的每個 bit 不再只和自己所在的那一列有關，而會受到左右鄰居影響，確保整個矩陣的資料有更強的連結性。

我拆解階段示意圖

文件內的示意圖

    3.2 ρ (rho)

目的 

    將每個「字（lane）」內的位元，依照固定的偏移量進行循環旋轉，讓資料在不同位置重新分布，避免保持原有的排列模式。

數學定義  

    Input : state array A.

    Output : state array A′.

    Steps : 

    1. For all z such that 0 ≤ z < w, let A′ [0, 0, z] = A[0, 0, z].

    2. Let (x, y) = (1, 0).

    3. For t from 0 to 23:

        a. for all z such that 0 ≤ z < w, let A′[x, y, z] = A[x, y, (z – (t + 1)(t + 2)/2) mod w];

        b. let (x, y) = (y, (2x + 3y) mod 5).

   4. Return A′.

此處的數學計算，需要依照定義的表格進行計算  

ρ (rho) 移動示意圖

    3.3 π (pi)

目的

    將每個「字（lane）」的位置重新排列，把資料在整個 5×5 矩陣中打散，避免不同 lane 之間長時間保持原本的相對位置。

數學定義

    Input : state array A.

    Output : state array A′.

    Steps : 

    1. For all triples (x, y, z) such that 0 ≤ x < 5, 0 ≤ y < 5, and 0 ≤ z < w, let A′[x, y, z]= A[(x + 3y) mod 5, x, z].

    2. Return A′.

 

文件內移動示意圖

補充說明：對應到的整個欄位會一起移動示意圖

 

    3.4 χ (chi)

目的

    執行非線性運算。

數學定義

    對每個位置(x,y) 進行邏輯運算

Input : state array A.

Output : state array A′.

Steps : 

1. For all triples (x, y, z) such that 0 ≤ x < 5, 0 ≤ y < 5, and 0 ≤ z < w, let A′ [x, y, z] = A[x, y, z] ⊕ ((A[(x+1) mod 5, y, z] ⊕ 1) ⋅ A[(x+2) mod 5, y, z]).

2. Return A′.

 

以中文來說就是，每個新的 bit 要「自己 XOR (NOT 右1 AND 右2)

    3.5 ι (iota)

目的

    打破對稱性 (symmetry)，因為前面四步驟都是相對「規律化」的運算，如果每一輪完全一樣，可能會讓某些結構性的對稱被保留下來，降低安全性。

為避免這種情況，ι 會在 每一輪 (round) 將一個 Round Constant (RC) 注入狀態矩陣的 

(0,0) 位置：𝐴′[0,0]=𝐴[0,0]⊕𝑅𝐶[𝑖]

RC 的生成方式

    這些 round constant 並不是隨機硬塞的，而是透過 線性反饋移位暫存器 (LFSR, Linear Feedback Shift Register) 生成。

LFSR 的特性是根據一個多項式進行移位與回饋，能產生一組長度固定、分布均勻的 pseudo-random 序列。

在 Keccak 中，RC 的生成公式源自以下規則：

𝑅𝐶[𝑖]𝑗=𝑟𝑐(j+7i)

其中：

𝑅𝐶[𝑖]𝑗：第𝑖 輪 RC 的第𝑗 個位元。

𝑟𝑐(𝑡)：由 LFSR 產生的單一位元函數。

LFSR 的核心多項式為：

x⁸+x⁶+x⁵+x⁴+1 

ι(𝐴, 𝑖𝑟)

在每一輪 permutation 的最後，會呼叫 ι(A, 𝑖𝑟)，將對應的 round constant 
𝑅𝐶[𝑖𝑟] 注入 state。

ι(A,𝑖r​):A[0,0]←A[0,0]⊕RC[𝑖𝑟​]

其中：

• 𝐴：當前的 state。
• 𝑖𝑟：round index（第幾輪，從 0 到 23）。
• 𝑅𝐶[𝑖𝑟]：第𝑖𝑟​ 輪對應的 round constant，由前面介紹的 LFSR 產生。

    4. Squeeze（擠出）

在所有輸入訊息經過 Padding → Absorb → Permutation 之後，state 內部已經被充分混合。

接下來就進入最後一個步驟 Squeeze（擠出）。

運作方式

從 state 的前 r 位取出資料，作為輸出的雜湊值。

如果輸出的長度足夠（例如 SHA3-256 需要 256 bits），就結束。

如果輸出長度不足（例如 SHAKE 需要可變長度輸出），則再次對 state 執行一次 Keccak-f permutation，再取前 r 位，直到輸出達到需求。

Rate (r) 的影響

不同的 SHA-3 變種，因為輸出長度不同，會對應到不同的 rate (r)。

• SHA3-224：r = 1152 bits, c = 448 bits
• SHA3-256：r = 1088 bits, c = 512 bits
• SHA3-384：r = 832 bits, c = 768 bits
• SHA3-512：r = 576 bits, c = 1024 bits
• SHAKE128：r = 1344 bits, c = 256 bits
• SHAKE256：r = 1088 bits, c = 512 bits

這些設定確保雜湊長度與安全強度的需求同時被滿足，在 Squeeze 階段，就是從這個 r 區域 取出輸出。

    5. Output（輸出結果）

經過 Padding → Absorb → Permutation → Squeeze 四個階段後，SHA-3 就會產生最終的雜湊輸出。

不同的演算法對應不同的輸出長度與安全等級：

SHA-3 系列（固定長度輸出）

• SHA3-224 → 224 bits (28 bytes)
• SHA3-256 → 256 bits (32 bytes)
• SHA3-384 → 384 bits (48 bytes)
• SHA3-512 → 512 bits (64 bytes)

這些輸出長度是標準規範好的，對應到不同層級的安全需求。

SHAKE 系列（可延伸輸出，XOF）

• SHAKE128 → 可輸出任意長度，r = 1344, c = 256 
• SHAKE256 → 可輸出任意長度，r = 1088, c = 512

雖然 SHAKE 理論上可以擠出無限長度，但實務上至少需要：
SHAKE128：建議 ≥128 bits（前像安全），或 ≥256 bits（碰撞安全）。
SHAKE256：建議 ≥256 bits（前像安全），或 ≥512 bits（碰撞安全）。