添加一個數字000確保 mod 操作需要恆定數量的指令周期

我一直在查看HMAC 的 s2n 實現，並且在“更新”功能（第 175 行）中，它說

/* Keep track of how much of the current hash block is full
     *
     * Why the 4294949760 constant in this code? 4294949760 is the highest 32-bit
     * value that is congruent to 0 modulo all of our HMAC block sizes, that is also
     * at least 16k smaller than 2^32. It therefore has no effect on the mathematical
     * result, and no valid record size can cause it to overflow.
     * 
     * The value was found with the following python code;
     * 
     * x = (2 ** 32) - (2 ** 14)
     * while True:
     *   if x % 40 | x % 48 | x % 64 | x % 128 == 0:
     *     break
     *   x -= 1
     * print x
     *
     * What it does do however is ensure that the mod operation takes a
     * constant number of instruction cycles, regardless of the size of the
     * input. On some platforms, including Intel, the operation can take a
     * smaller number of cycles if the input is "small".
     */

然後它繼續做

state->currently_in_hash_block += (4294949760 + size) % state->hash_block_size;
state->currently_in_hash_block %= state->block_size;

我不明白您為什麼要添加一個與零模一致的數字state->hash_block_size-它可以實現什麼？它如何保證恆定數量的指令周期？

正如您引用的評論所指出的：

在包括英特爾在內的某些平台上，

$$ modulo $$如果輸入“小”，則操作可能需要較少的周期數。

這是真的嗎，這意味著什麼？Google搜尋一下，我找到了Intel® 64 and IA-32 Architectures Optimization Reference Manual，在表 C-16 中將DIV指令的吞吐量（用於計算除法和模數）列為“~20-26”每條指令周期（在 Ivy Bridge 上約為 19-25 個週期），並帶有以下腳註：

10. “DIV/IDIV r32”的吞吐量隨輸入 EDX:EAX 中的有效位數和/或除數 r32 中給定有效位大小的除法商的變化而變化。吞吐量隨著輸入 EDX:EAX 或輸出商中有效位數量的增加而降低（循環中的數值增加）。“DIV/IDIV r32”的延遲也隨著輸入值的有效位而變化。對於給定的一組輸入值，延遲與週期中的吞吐量大致相同。

那麼這在簡單的英語中是什麼意思呢？

• 在 Intel x86 CPU 上，整數除法和模約簡不是恆定時間操作。
• 劃分或減少數字所需的時間取決於（主要是？）被劃分或減少的數字的位長度。

因此，計算所需的時間x % y可能會洩露有關x大小的資訊。但是，我們可以通過計算 來最小化這種洩漏(x + c) % y，其中c是y的一個很大的常數倍數。特別是，應該選擇常數c ，以便：

1. x + c的位長度對於x的所有可能值都是相同的，
2. 對於x的任何可能值， x + c的計算都不會溢出，並且
3. 當然，c需要被模數y整除。

當然，根據可能的x值的範圍，可能並不總是可以找到滿足這些要求的常數c 。

但是，在您上面引用的程式碼中，常數 4294949760 似乎已被選為最大值c當添加到任何數字 0 ≤ x < 2 14時不會溢出 32 位無符號寄存器，這也是一個整數可能模數 40、48、64 和 128 的倍數。鑑於 4294949760 ≥ 2 31，這也確保它滿足第一個條件：bitlength(4294949760 + x ) = 32 對於所有 0 ≤ x < 2 14。

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