Keccak 密碼學原創分析：海綿結構與以太坊雜湊函數的深度數學推導

搞密碼學的人都知道 Keccak，但說實話，大多數人對它的理解只停留在「這是以太坊用的雜湊函數，比 SHA-256 強」。如果問你 Keccak 的內部結構、為什麼它能抵抗量子攻擊、以及以太坊如何利用它的獨特屬性，多數人可能就啞巴了。這篇文章，我來幫你把這些坑填上。

為什麼要聊 Keccak？

因為它是 Ethereum 最重要的密碼學基礎。從帳戶地址生成到智慧合約驗證，Keccak 無處不在。Vitalik 當初選擇 Keccak 而不是 NIST 標準化的 SHA-3，有他自己的考量——這個選擇影響了整個生態系統的安全性設計。

在量子計算威脅越來越真實的今天，理解 Keccak 的數學基礎變得尤其重要。傳統觀點認為，Grover 演算法可以將暴力破解雜湊函數的複雜度從 O(2^n) 降低到 O(2^(n/2))。這聽起來很可怕，但 Keccak 的結構設計讓這種攻擊變得更加困難。

海綿結構：Keccak 的核心設計

Keccak 採用了一種叫做「海綿結構」(Sponge Construction) 的創新架構。這種設計讓 Keccak 不僅是一個雜湊函數，還能衍生出可變長度輸出、偽隨機數生成、訊息認證等多種功能。

雙階段工作模式

海綿結構分為兩個階段：

┌─────────────────────────────────────────────────────────┐
│                    吸收階段 (Absorbing)                  │
├─────────────────────────────────────────────────────────┤
│  輸入分割 → Padding → 與 State 異或 → f 函數運算       │
│     ↑                                                   │
│     └──────────────── 循環迭代 ────────────────────────┤
└─────────────────────────────────────────────────────────┘
                         ↓
┌─────────────────────────────────────────────────────────┐
│                    擠出階段 (Squeezing)                 │
├─────────────────────────────────────────────────────────┤
│  f 函數運算 → 輸出部分 State → 截取需要的位元數        │
│     ↑                                                   │
│     └──────────────── 循環迭代 ────────────────────────┤
└─────────────────────────────────────────────────────────┘

數學上，我們可以這樣描述：

令 r = 速率 (rate)，c = 容量 (capacity)，b = 狀態大小

b = r + c = 1600 bits (Keccak-1600)

吸收階段：
狀態 S[0..b-1] = 0
for i = 0 to len(message)/r:
    P_i = message[i*r:(i+1)*r]
    S[0:r-1] = S[0:r-1] XOR P_i
    S = f(S)  // 輪函數

擠出階段：
Z = ""
while len(Z) < output_length:
    Z = Z || S[0:r-1]
    S = f(S)
return Z[0:output_length-1]

這裡的關鍵參數選擇至關重要。Ethereum 使用的 Keccak-256，意味著輸出長度為 256 位元。對於 SHA-3-256，攻擊者需要的複雜度是 2^(256/2) = 2^128；但 Keccak 的結構讓實際攻擊更困難。

輪函數 f：五步走的藝術

Keccak 的核心是輪函數 f，它由五個基本操作組成：

# Keccak-f[1600] 輪函數的五個步驟
def keccak_f(state):
    """
    state: 5x5x64 的三維陣列 (1600 bits)
    """
    R = 1  # 旋轉偏移的初始值
    
    for round in range(24):
        # 步驟 1: θ (Theta) - 校驗和擴散
        C = [xor(state[x][y][z] for x in range(5)) 
             for y in range(5) for z in range(64)]
        D = [C[(x+4)%5][z] ^ C[(x+1)%5][(z-1)%64] 
             for x in range(5) for z in range(64)]
        state = [[state[x][y][z] ^ D[x][z] 
                   for z in range(64)] for x in range(5) for y in range(5)]
        
        # 步驟 2: ρ (Rho) - 旋轉偏移
        for x in range(5):
            for y in range(5):
                state[x][y] = rotate(state[x][y], R)
                R = (R + (x+1)*(y+1)) % 64
        
        # 步驟 3: π (Pi) - 置換
        new_state = [[0]*64 for _ in range(5)]
        for x in range(5):
            for y in range(5):
                new_state[y][(2*x+3*y)%5] = state[x][y]
        state = new_state
        
        # 步驟 4: χ (Chi) - 非線性替代
        for y in range(5):
            for z in range(64):
                state[0][y][z], state[1][y][z], state[2][y][z], state[3][y][z], state[4][y][z] = \
                state[0][y][z] ^ ((~state[1][y][z]) & state[2][y][z]), \
                state[1][y][z] ^ ((~state[2][y][z]) & state[3][y][z]), \
                state[2][y][z] ^ ((~state[3][y][z]) & state[4][y][z]), \
                state[3][y][z] ^ ((~state[4][y][z]) & state[4][y][z]), \
                state[4][y][z] ^ ((~state[0][y][z]) & state[1][y][z])
        
        # 步驟 5: ι (Iota) - 輪常數
        RC = generate_round_constant(round)
        state[0][0] ^= RC
    
    return state

讓我逐一解釋這五步的密碼學意義：

θ (Theta)：全局擴散

這一步計算每個欄的 XOR 校驗和，然後用它來擾動相鄰欄：

C[x][z] = state[x][0][z] ⊕ state[x][1][z] ⊕ ... ⊕ state[x][4][z]
D[x][z] = C[x-1][z] ⊕ C[x+1][z-1]
state[x][y][z] = state[x][y][z] ⊕ D[x][z]

這個設計的巧妙之處在於，即使攻擊者能控制局部狀態，θ 操作也會讓影響擴散到整個狀態。這對抵抗差分分析攻擊至關重要。

ρ (Rho)：旋轉偏移

這步對每個狀態平面執行不同的位元旋轉：

偏移量表格（單位：位元）
     y=0  y=1  y=2  y=3  y=4
x=0   0   36   3   41   18
x=1  300  1   300  278  6
x=2  64  300  78   210  66
x=3  28  247  281  147  231
x=4  0   200  94   120  210

旋轉偏移增加了狀態位元之間的非線性混合。與簡單的置換不同，旋轉讓相鄰位元的信息混合到不同的位置。

π (Pi)：置換

這一步執行的是「深度置換」，將 (x,y) 位置映射到 (y, 2x+3y)：

# 置換映射
for x in range(5):
    for y in range(5):
        new_state[y][(2*x + 3*y) % 5] = state[x][y]

這個非標準置換打破了行列的對稱性，讓攻擊者難以利用線性結構。

χ (Chi)：非線性替代

這是 Keccak 中唯一的非線性操作：

new[a] = a ⊕ (NOT b AND c)

相比 AES 的 S-box，χ 操作簡單得多，但多輪迭代後仍能產生足夠的非線性。這種設計哲學是「簡單操作的複雜組合」vs「複雜操作的簡單組合」。

ι (Iota)：輪常數

最後一步將輪常數異或到狀態中，打破每輪的對稱性：

RC[round] 採用 LFSR (線性反饋移位寄存器) 生成
RC[0] = 0x01
RC[1] = 0x82
...
RC[23] = 0x8E

Keccak vs SHA-3：Vitalik 的選擇

說到 Keccak，不能不提它和 NIST SHA-3 的關係。2012 年 NIST 標準化了 SHA-3，但這個標準與原始的 Keccak 有細微差異。Ethereum 堅持使用原始的 Keccak，這讓一些人質疑 Vitalik 的決定。

讓我列出關鍵差異：

Keccak-256 (Ethereum) vs SHA3-256 (NIST)

1. 輸出偏移：
   Keccak: 吸收階段先填充訊息
   SHA-3: 使用 domain separation 填充

2. 填充方案：
   Keccak: 10*1 填充 (訊息 || 0x01 || 0x00...|| 0x01)
   SHA-3: 04 || 0x00...|| 0x06 填充

3. 實際差異：
   keccak256("") = 0xc5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470
   sha3_256("") = 0x36a9e7f1c95b82ffb26543bba5c6e1c2b7eefb2c2f3c5b0a7c8d4f5e6a7b8c9d

Vitalik 選擇 Keccak 的理由：

1. 避免 NIST 標準的不確定性：斯諾登事件後，社區對 NIST 標準的信任度下降
2. 避免專利問題：Keccak 完全免專利
3. 性能考量：Keccak 在軟體實現上比 SHA-2 快

後量子安全性分析

這大概是大家最關心的話題。Keccak 的後量子安全性到底怎麼樣？

對 Grover 演算法的抵抗

Grover 演算法可以將暴力破解雜湊函數的複雜度降低到 O(2^(n/2))。對於 256 位元輸出，這意味著理論上需要 2^128 次量子運算。

但 Keccak 的海綿結構提供了一個有趣的防禦：攻擊者無法同時獲取完整的內部狀態。

傳統攻擊（經典電腦）：
- 生日攻擊需要 2^128 次嘗試
- 理論可行但實際不可能

Grover 攻擊（量子電腦）：
- 量子搜索降低到 2^64 次「並行」嘗試
- 但需要量子記憶體存儲 2^64 個狀態
- 目前量子記憶體容量遠遠不夠

Keccak 的額外防禦：
- 內部狀態 1600 bits = 200 bytes
- 容量部分 c = 1024 bits 不直接暴露
- 攻擊者需要恢復完整的 c 值

對量子碰撞攻擊的抵抗

更準確地說，Keccak 對量子碰撞攻擊的抵抗來自於：

量子碰撞複雜度：
- 模擬攻擊：2^(n/3) (BHT 演算法)
- 對於 n=256：2^85 次量子查詢

實際評估：
- 需要穩定的 2^85 量子操作
- 需要大量量子記憶體
- 在可預見的未來不可行

以太坊中的 Keccak 應用

讓我快速過一遍 Ethereum 如何使用 Keccak：

1. 地址生成

address = keccak256(public_key)[12:]

這裡取公鑰的 Keccak-256 雜湊的最後 20 位元組作為以太坊地址。為什麼用 [12:]？這是歷史設計決策，當時認為 160 位元地址長度足夠安全。

2. 交易簽名

Ethereum 的交易使用 ECDSA 簽名，但簽名結果（r, s, v）會經過特定處理。我們使用 Keccak-256 計算交易雜湊作為簽名的輸入：

tx_hash = keccak256(rlp_encode(transaction))
signature = ecdsa_sign(tx_hash, private_key)

3. 智慧合約校驗

很多智慧合約使用 keccak256 來驗證資料完整性：

function verifyProof(bytes32 root, bytes32 hash, bytes proof) public pure returns (bool) {
    bytes32 computedHash = hash;
    for (uint i = 0; i < proof.length; i++) {
        bytes32 proofElement = bytes32(proof[i]);
        if (computedHash < proofElement) {
            computedHash = keccak256(abi.encodePacked(computedHash, proofElement));
        } else {
            computedHash = keccak256(abi.encodePacked(proofElement, computedHash));
        }
    }
    return computedHash == root;
}

結語：Keccak 的美學

說了這麼多數學推導，我想總結一下 Keccak 為什麼讓我著迷。

它的設計哲學是「簡單到極致」。每一步操作——旋轉、置換、簡單的 XOR 和 AND——在單獨看來都平平無奇。但 24 輪迭代後，這些簡單操作的組合創造出了一個在密碼學意義上幾乎無法突破的函數。

這給我的啟發是：複雜性可以來自簡單性的深度組合，而不是單一組件的複雜性。

在以太坊的世界裡，Keccak 就像一個默默耕耘的基礎設施。每天數百萬筆交易都依賴它的安全保障，但很少有人真正理解它的運作原理。希望這篇文章能幫你補足這個知識缺口。

如果你想深入研究，建議閱讀：

• Keccak Team 官方文件 (The Keccak Reference)
• Guido Bertoni 等人的論文
• 以太坊黃皮書中關於密碼學部分的規範

記住：理解密碼學的底層原理，是成為區塊鏈安全專家的第一步。

本篇文章為原創技術分析，僅供教育目的。如有錯誤，歡迎指正。