如何為 SHA256 填充 448 位消息？
我最近在 C++ 中實現了一個非常簡單的 SHA256 雜湊程序，因為 SHA256 雜湊函式的塊大小是 512 位或 64 字節，並且必須按照 FIPS 標準填充小於該大小的消息，我實現了一個填充函式規則。
$ (K+1+L) = 448 \mod 512 $ ， 在哪裡 $ K $ 是數量 $ 0 $ 應該在之後附加的位 $ 1 $ 位，之前附加到消息中。
我正在使用從該網站收到的測試向量測試我的程式碼：https ://www.di-mgt.com.au/sha_testvectors.html
不幸的是，它對於 448 位的測試向量 失敗
abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq了： 但對於之前的測試向量來說效果很好。這是我製作的一個簡單的 C++ 程式碼片段，它負責填充，顯然，由於我的誤解，其中存在算法缺陷！int blocks = 0; if (len % 64) // len is the message length { blocks = (len + (64 - (len % 64))) / 64; } else { // I realized (the hard way) that messages that are of size 512 bits or its multiples have an additional block that contains padding info and they run through the compression function. blocks = (len / 64) + 1; } unsigned char *s = (unsigned char *)calloc(blocks * 64, sizeof(unsigned char)); // Internal storage for the message with padding. for (int i = 0; i < len; i++) { s[i] = m[i]; // m is the message passed to the function, that has to be hashed. } int K = 0; uint64_t L = len * 8; uint64_t size = L; K = (448 - L - 1) % 512; if (K < 0) { K += 512; } s[len] = 0b10000000; // or 0x80 K -= 7; for (int i = 0; i < (K / 8); i++) { s[i + len + 1] = 0; // The zero bytes... } // Append the length of the message as a 64 bit big endian integer for (int i = 0; i < 8; i++) { s[blocks * 64 - 1 - i] = (unsigned char)(((uint64_t)size & (uint64_t)(0xff << i * 8)) >> 8 * i); }我想為任何位長度創建一個符合 FIPS 標準的填充方法……我意識到，對於長度為 448 位的消息，我的填充將溢出到另一個塊。是否應該以填充消息的相同方式填充另一個塊？我應該對算法進行哪些更改以適應所有消息長度？
前 10 行可以替換為
uint64_t blocks = (len+72)/64;，這將修復手頭範例的程式碼（以及擴展消息容量，如果int是 32 位和len64 位，這無法從程式碼中得知¹）。我建構的心理過程(len+72)/64，它適用於加密貨幣中的許多事物，將事物分成相等大小的塊，如下所示：
- 當我們將字節數增加
len64 時，必須正好多了一個 64 字節（512 位）的塊；並且塊的數量隨著單調增加len。這就是數學上暗示塊數是 $ \frac{\mathtt{len}+\mathtt{cst}}{64} $ 對於整數常量的某個值cst。根據 C 語言中整數除法的定義，只要沒有溢出(len+cst)/64就會計算。blocks它只剩下尋找cst。- 當
len為 55 時，填充字節 0b10000000 和 8 字節長度適合單個 64 字節塊，因為 55+1+8=64；但是當len是 56 時，我們需要第二個塊。這縮小cst到一個精確的值。找到它的一種方法是：len56 是使所需結果為 2 的最小值，因此56+cst必須是2*64，因此cst是2*64-56，即72。此外，
(unsigned char)(((uint64_t)size & (uint64_t)(0xff << i * 8)) >> 8 * i)不能按預期工作。對於許多平台，它將失敗len>536870911，len對於某些平台 >8191。問題在於在移位之後(uint64_t)(0xff << i * 8)轉換為 64 位的位置，這是在 的寬度上執行的，因為這是 的類型，並且在達到或超過 的位寬時會產生未指定的結果。這個問題可以解決（注意演員的不同位置）。但它比整個表達式更易於使用。int``0xff``i*8``int``((uint64_t)0xff << i * 8)``(unsigned char)(size >> i*8)
int用於循環索引的類型for (int i = 0; i < len; i++)通常會限制可以處理的字節數，即使 for 的類型len沒有。但這總是發生在大於len上述內容的情況下。與以
K結尾的計算K / 8，給出要附加的零字節數，可以簡化為63&(unsigned)(55-len)。找到這個的心理過程：所需的數量是一個整數，當len增加一時減少一，除非它小於零，在這種情況下，下一個計數是 63。因此，正確的表達式是數學上的 $ (\text{cst}-\text{len})\bmod64 $ 對於一些 $ \text{cst} $ . 什麼時候 $ \text{len} $ 是 55，期望的結果是零，因此一個合適的 $ \text{cst} $ 是 55（-7 也可以）。仍有待計算 $ (55-\text{len})\bmod64 $ 儘管缺少攜帶式模運算符²。由於模數是 2 的冪，我們可以³使用63&(unsigned)(55-len).的結果
calloc未檢查；如果記憶體不足，那將導致災難。這就是生產質量程式碼不應複製整個輸入數據的原因。另一個是性能⁴。我可能錯過了程式碼的其他問題（我在之前的閱讀中做過）。加密程式碼在所有情況下都需要準確，這比看起來更難確定。通常，當必須在備選方案中進行選擇時，我會盡量減少不可移植行為的構造，並作為次要標準使用較短的程式碼，尤其是在它刪除測試或變數的情況下，因為這往往會導致程式碼更容易被證明是正確的。
¹ 如果
len是 32 位或更窄，則後者將以合理的大小溢出（最多 256kiB 或 512kiB，具體取決於有符號性，如果是 16 位且有符號，uint64_t L = len * 8;則可能低至 8kiB ），這將在溢出之前發生。len``len+72² C 的
%運算符不是數學模運算符，因為對於否定參數，結果可能是否定的（至少在某些平台上），因此必須通過測試將其恢復為肯定，就像問題的來源在之後所做的那樣K = (448 - L - 1) % 512;。³ 更簡單的
63&(55-len)也可以。然而，這操縱了一個可能為負的數量，並且一些工具鏈會咆哮；結果也至少有 的寬度len，這可能是不必要的大。⁴ 關於性能：
確實為所有輸入的副本分配塊的程式碼沒有理由在（不
calloc）時使用（哪個為零） ，因為零是顯式附加的。malloc並非所有編譯器都會優化複製循環，從而增加了複製所帶來的速度損失。這是一個很好的跡象
memcpy。生成的程式碼通常比給出的更好
for (int i = K/8; --i>=0;)，for (int i = 0; i < (K / 8); i++)因為：
- 一個循環比較一個常數而不是一個變數來確定它的結束可以更快，常數 0 特別好。
- 編譯器不需要確定
K/8循環中沒有變化，因此可以預先計算，也不需要在循環期間儲存中間量。注意：這是主題的邊界，因為我們正在程式，甚至是 C 語言和微優化。然而，這些問題在密碼學的實現中經常出現，速度在密碼學中通常很重要，和/因此很多（可能是最常用的）密碼學實現是用 C 或類似語言，甚至更低級別的語言。