數百萬俱有公共前綴的字元串的 SHA1 計算

我有一個需要計算 SHA1（common_prefix + random_string）的函式。我多次呼叫此函式，以便計算 SHA1 減慢函式的性能。至於所有呼叫，我使用的是 common_prefix，是否可以調整 SHA1，使其不會計算 (common_prefix+random_string) 的雜湊值，但是它對 (common_prefix) 進行預處理並使用此預處理（計算值）來計算 SHA1（common_prefix+random_string）？

有沒有可能做到這一點？

是的，如果公共前綴至少是一個 512 位塊，您可以省力。

用數學說話：用於填充資訊 $ m = m_1 \mathbin| m_2 \mathbin| \cdots \mathbin| m_\ell $ 的 $ \ell $ 512 位塊，$$ \operatorname{SHA1}(m) = f(\cdots f(f(\mathit{iv}, m_1), m_2) \cdots, m_\ell), $$在哪裡 $ f $ 是 SHA-1 的內部壓縮函式。例如，假設您有一對兩塊消息 $ m_1 \mathbin| m_2 $ 和 $ m_1 \mathbin| m_2’ $ 有一個共同的前綴 $ m_1 $ 和不同的後綴 $ m_2 $ 和 $ m_2’ $ . 然後

$$ \begin{align} \operatorname{SHA1}(m_1 \mathbin| m_2) &= f(f(\mathit{iv}, m_1), m_2), \ \operatorname{SHA1}(m_1 \mathbin| m_2’) &= f(f(\mathit{iv}, m_1), m_2’), \end{align} $$

共享公共子表達式 $ f(\mathit{iv}, m_1) $ . 如果你預先計算 $ h_0 = f(\mathit{iv}, m_1) $ ，那麼你可以更快地計算 $ \operatorname{SHA1}(m_1 \mathbin| m_2) = f(h_0, m_2) $ 和 $ \operatorname{SHA1}(m_1 \mathbin| m_2’) = f(h_0, m_2’) $ .

以程式方式說話：SHA-1 的大多數實現都支持 init/update/final API。例如，要hello world使用 OpenSSL 的 API 對字元串進行雜湊處理，您可以編寫：

SHA_CTX ctx;
unsigned char h[20];

SHA1_Init(&ctx);
SHA1_Update(&ctx, "hello", 5);
SHA1_Update(&ctx, " ", 1);
SHA1_Update(&ctx, "world", 5);
SHA1_Final(h, &ctx);

SHA-1 計算的狀態，包括將消息拆分為塊的緩衝，都儲存在對SHA_CTX像中。在某些情況下，例如在 OpenSSL 中，您可以複製上下文以節省已經為散列您迄今為止輸入的內容所做的任何工作：

SHA_CTX ctx, ctx0, ctx1;
unsigned char h0[20], h1[20];

SHA1_Init(&ctx);
SHA1_Update(&ctx, "Once before a console dreary, while I programmed, weak and weary", 64);

ctx0 = ctx;
SHA1_Update(&ctx0, "\nOver many a curious program which did TECO's buffer fill...", 60);
SHA1_Final(h0, &ctx0);

ctx1 = ctx;
SHA1_Update(&ctx1, "\nO vermin yak urea's pro-Grammy itched dt casbah fur fell...", 60);
SHA1_Final(h1, &ctx1);

結果雜湊是

• h0 =b2b36d39d4431b3a57b7c30630bbbde9553b50ae
• h1 =2a0dae0548307b4ef33c0f1fedd7cbad2c32d5d8

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