我們計算雜湊 $ H(M_0\mathbin|M_1) $ 大小的 $ d\ge1 $ 對於一些恆定的標題 $ M_0 $ 大小的 $ m_0 $ ， 和 $ \nu\ge1 $ 消息 $ M_1 $ 隨機內容和大小 $ m_1 $ .

對於Merkle-Damgård雜湊，一個簡單的優化預計算第一個 $ \left\lfloor m_0/r\right\rfloor $ 輪次（其中 $ r $ 是塊大小），以及一些最小的額外大小 $ \mu $ ，計算的總輪數為 $$ \text{rounds}=\left\lfloor\frac{m_0}r\right\rfloor+\nu\left\lceil\frac{\left(m_0\bmod r\right)+m_1+\mu}r\right\rceil $$ 對於一些雜湊： $$ \begin{array}{l|rrrl|rrrl} \text{hash} & d&r&\mu&\text{(bits)}&\tilde d&\tilde r&\tilde \mu&\text{(bytes)}\ \hline \operatorname{SHA-256} & 256 & 512 & 65 && 32 & 64 & 9 \ \operatorname{SHA-512} & 512 & 1024 & 129 && 64 & 128 & 17 \ \end{array} $$

注意：表格右側假定數量以字節而不是位表示。公式的唯一變化是變數得到一個波浪號，除了 $ \nu $ .

對於更常見的雜湊和 XOF¹，對應的公式和參數是什麼？

我對 SHA-3 的常見變體特別感興趣（或者 KECCAK，如果它與 SHA-3 不同，除了padding 的值）；搖; 各種布萊克；也許還有一些可並行的雜湊。

更新：我已經多次更改符號以與 KECCAK/SHAKE 中的符號保持一致 $ r $ 和輸出大小 $ d $ , 並使用希臘字母以避免與現有的雜湊規範混淆。

---

¹ 可擴展輸出函式本質上是輸出大小的雜湊值 $ d $ 是一個參數而不是固定的。一個例子是SHA-3系列的 SHAKE256。

標題

$$ \begin{array}{l|rrrl|rrrl} \text{hash} & d&r&\mu&\text{(bits)}&\tilde d&\tilde r&\tilde \mu&\text{(bytes)}\ \hline \operatorname{MD5} & 128 & 512 & 65 && 16 & 64 & 9 \ \operatorname{SHA-1} & 160 & 512 & 65 && 20 & 64 & 9 \ \operatorname{RIPEMD-160} & 160 & 512 & 65 && 20 & 64 & 9 \ \operatorname{SHA-224} & 224 & 512 & 65 && 28 & 64 & 9 \ \operatorname{SHA-256} & 256 & 512 & 65 && 32 & 64 & 9 \ \hline \operatorname{SHA-512/224}& 224 & 1024 & 129 && 28 & 128 & 17 \ \operatorname{SHA-512/256}& 256 & 1024 & 129 && 32 & 128 & 17 \ \operatorname{SHA-384} & 384 & 1024 & 129 && 48 & 128 & 17 \ \operatorname{SHA-512} & 512 & 1024 & 129 && 64 & 128 & 17 \ \hline \operatorname{SHA3-224} & 224 & 1152 & 4 && 28 & 144 & 1 \ \operatorname{SHA3-256} & 256 & 1088 & 4 && 32 & 136 & 1 \ \operatorname{SHA3-384} & 384 & 832 & 4 && 48 & 104 & 1 \ \operatorname{SHA3-512} & 512 & 576 & 4 && 54 & 72 & 1 \ \hline \operatorname{SHAKE-128} & d & 1344 & 6 && \lceil d/8 \rceil & 168 & 1 \ \operatorname{SHAKE-256} & d & 1088 & 6 && \lceil d/8 \rceil & 136 & 1 \ \hline \operatorname{BLAKE2s-256} & 256 & 512 & 0 && 32 & 64 & 0 \ \operatorname{BLAKE2b-512} & 512 & 1024 & 0 && 64 & 128 & 0 \ \end{array} $$

---

SHA3​​-x

SHA3​​-x 用 KECCAK 定義為：

1. $ \operatorname{SHA3-224}(M) = \operatorname{KECCAK}[448] (M \mathbin| 01, 224) $
2. $ \operatorname{SHA3-256}(M) = \operatorname{KECCAK}[512] (M \mathbin| 01, 256) $
3. $ \operatorname{SHA3-384}(M) = \operatorname{KECCAK}[768] (M \mathbin| 01, 384) $
4. $ \operatorname{SHA3-512}(M) = \operatorname{KECCAK}[1024](M \mathbin| 01, 512) $

凱卡克

和 KECCAK 定義為

• $ \operatorname{KECCAK}[c] (N, d) = \operatorname{SPONGE}[\operatorname{KECCAK-p}[1600, 24], \operatorname{pad10*1}, 1600–c] (N, d) $

並註意 $ N = M\mathbin|01 $ 和 $ d $ 是所需的輸出大小，現在我們有

1. $ \operatorname{SHA3-224}(M) = \operatorname{SPONGE}[\operatorname{KECCAK-p}[1600, 24], \operatorname{pad10*1}, 1600–448] (N, 224) $
2. $ \operatorname{SHA3-256}(M) = \operatorname{SPONGE}[\operatorname{KECCAK-p}[1600, 24], \operatorname{pad10*1}, 1600–512] (N, 256) $
3. $ \operatorname{SHA3-384}(M) = \operatorname{SPONGE}[\operatorname{KECCAK-p}[1600, 24], \operatorname{pad10*1}, 1600–768] (N, 384) $
4. $ \operatorname{SHA3-512}(M) = \operatorname{SPONGE}[\operatorname{KECCAK-p}[1600, 24], \operatorname{pad10*1}, 1600–1024] (N, 512) $

填充

• $ \operatorname{pad10*1}(x, m) $ 不重要，因為消息尚未形成。

海綿

• $ \operatorname{SPONGE}[f, \operatorname{pad}, r](N, d) $

  1. 讓 $ P=N \mathbin| \operatorname{pad}(r, \operatorname{len}(N)) $ .
  2. 讓 $ n=\lfloor\operatorname{len}(P)/r\rfloor $ .
  3. 讓 $ c=\lfloor b/r\rfloor $ .
  4. 讓 $ P_0, \ldots, P_{n-1} $ 是長度字元串的唯一序列 $ r $ 這樣 $ P = P_0 \mathbin| \ldots\mathbin| P{n-1} $ .
  5. 讓 $ S=0^b $
  6. $ \textbf{For } i \textbf{ from }0 \textbf{ to } n-1 $

  $ \textbf{let } S=f (S \oplus (P_i\mathbin| 0c)) $ . 7. …

如我們所見，我們可以預先計算一條消息 $ M $ 最大倍數 $ r $ 小於 $ \operatorname{len}(M) $ . 更數學$$ \operatorname{precomputableLen} = \lfloor(\operatorname{len}(M)/r)\rfloor \cdot r. $$和 $ r $ 為了

1. $ \operatorname{SHA3-224}(M) $ 是 $ r = 1152 $
2. $ \operatorname{SHA3-256}(M) $ 是 $ r = 1088 $
3. $ \operatorname{SHA3-384}(M) $ 是 $ r = 832 $
4. $ \operatorname{SHA3-512}(M) $ 是 $ r = 576 $

和公式

$$ \text{rounds}=\left\lfloor\frac{m_0}r\right\rfloor+\nu\left\lceil\frac{\left(m_0\bmod r\right)+m_1+\mu }r\right\rceil $$

SHAKE128 和 SHAKE256

• $ \operatorname{SHAKE128}(M, d) = \operatorname{KECCAK}[256] (M \mathbin| 1111, d) $
• $ \operatorname{SHAKE256}(M, d) = \operatorname{KECCAK}[512] (M \mathbin| 1111, d) $

正如我們所看到的，主要區別在於容量和附加的額外兩位以進行域分離。

1. $ \operatorname{SHAKE128}(M, d) $ 是 $ r =1344 $
2. $ \operatorname{SHAKE256}(M, d) $ 是 $ r =1088 $

和公式

$$ \text{rounds}= \underbrace{\left\lfloor\frac{m_0}{r}\right\rfloor + \nu\left\lceil\frac{\left(m_0\bmod r\right)+m_1+\mu}r\right\rceil}{\text{Absorbing part}} + \underbrace{\nu \left\lceil \frac{d}{r} -1 \right\rceil }{\text{Squeezing part}} $$

BLAKE2b 和 BLAKE2s

BLAKE2 使用修改後的 ChaCha 作為 16 個字的壓縮函式。BLAKE2s 是 32 位版本，所以 $ r=512 $ 在這裡，對於 BLAKE2b $ r = 1024 $ ( $ s $ 對於小， $ b $ 大）。

和公式

$$ \text{rounds}=\left\lfloor\frac{m_0}r\right\rfloor+\nu\left\lceil\frac{\left(m_0\bmod r\right)+m_1+\mu } r\right\rceil $$

由於 BLAKE2 使用全零填充，他們稱之為最小填充。

---

引用自：https://crypto.stackexchange.com/questions/89663