NaCl Poly1305 實現中的擠壓功能如何工作？
Poly1305 算法的 NaCl
ref實現使用以下歸約函式（稱為squeeze()）：static void squeeze(unsigned int h[17]) { unsigned int j; unsigned int u; u = 0; for (j = 0;j < 16;++j) { u += h[j]; h[j] = u & 255; u >>= 8; } u += h[16]; h[16] = u & 3; u = 5 * (u >> 2); for (j = 0;j < 16;++j) { u += h[j]; h[j] = u & 255; u >>= 8; } u += h[16]; h[16] = u; }我全面了解第一個 for 循環中所做的事情，即 h 中的每個整數減少到 256 位，進位被轉移到下一個整數。我只是不明白從那以後會發生什麼
h[16] = u & 3;。從哪裡來u & 3;？和u = 5 * (u >> 2);？另外，如果我想在此處更改基數，例如從 2^8 位更改為 2^16，是否需要更改上述片段？我需要將所有 8 更改為 16，將 255 更改為 2^16-1，但會是這樣嗎？
有誰知道這個
squeeze功能是如何工作的，並提供解釋，以及我的第二個問題的答案？實現本身沒有提供任何文件，關於NaCl Poly1305 實現如何進行模乘？沒有深入研究擠壓功能。有關完整程式碼，請參閱此 stackexchange 問題。
這裡有兩個想法：
- 帶有延遲進位的基數 256 算術。
這裡我們代表一個整數 $ x $ 經過 $ x_0 + 2^8 x_1 + 2^{16} x_2 + \dots + 2^{128} x_{16} $ . 在規範形式中，數字 $ x_i $ 位於 $ {0,1,2,\dots,255} $ ，但在 Poly1305 計算中，我們盡可能延遲進位的傳播以節省計算量，因此 $ x_i $ 可能更大，為每個整數提供多種可能的表示 $ x $ 以這種形式。 2. Poly1305 還原 $ 2^{130} x_{\mathrm{hi}} + x_{\mathrm{lo}} \equiv 5 x_{\mathrm{hi}} + x_{\mathrm{lo}} \pmod p $ .
我們正在模數工作 $ p = 2^{130} - 5 $ ， 其中有 $ 2^{130} - 5 \equiv 0 \pmod p $ 所以 $ 2^{130} \equiv 5 \pmod p $ . 這個想法是，如果我們有一個整數 $ x $ ，我們可以取它的 130 個低位 $ x_{\mathrm{lo}} = x \mathbin& (2^{130} - 1) $ , 和高位 $ x_{\mathrm{hi}} = x \mathbin\gg 130 $ ， 以便$$ x = (x_{\mathrm{hi}} \ll 130) \mathbin| x_{\mathrm{lo}} = 2^{130} x_{\mathrm{hi}} + x_{\mathrm{lo}}, $$然後通過計算做一個減少步驟$$ x \equiv 5x_{\mathrm{hi}} + x_{\mathrm{lo}} \pmod p; $$ 即，移位/乘法/加法。
這兩個想法是同時進行的。我建議你嘗試從這兩個想法中自己解決，但是——劇透警告！- 如果您仍然完全卡住，這裡是完整的血腥細節：
static void squeeze(unsigned h[17])入境時， $ h $ 表示一個整數 $ x $ 在基數 256 中，由於延遲進位，數字可能超過 255，只要它們有一定的界限 $ B $ 所以攜帶並不過分。
$ x = h[0] + 2^8 h[1] + 2^{16} h[2] + \dots + 2^{128} h[16] \ h[0], h[1], \dots, h[16] < B $
首先，我們傳播所有延遲的進位，並以基數限制每個數字，最多 128 位：
u = 0; for (j = 0; j < 16; j++)
- 循環不變數：
$ x = h[0] + 2^8 h[1] + \dots + 2^{8j} (h[j] + u) + \dots + 2^{128} h[16] \ h[0], h[1], \dots, h[j] < 256 \ h[j + 1], \dots, h[16] < B $
{ u += h[j]; h[j] = u & 255; u >>= 8; }現在 $ h[0], \dots, h[15] $ 減少，留下我們 $ h[16] $ 和一個 128 位進位。我們將進一步獲得 130 位進位：
$ x = h[0] + 2^8 h[1] + \dots + 2^{128} (h[16] + u) \ h[0], h[1], \dots, h[15] < 256 \ h[16] < B $
u += h[16]; h[16] = u & 3;現在請注意 $ 2^{130} \equiv 5 \pmod p $ . 所以——在我們轉移之後 $ u \gg 2 $ 下面——當我們有
$ x = h[0] + 2^8 h[1] + \dots + 2^{128} h[16] + 2^{130} u \ h[0], h[1], \dots, h[15] < 256 \ h[16] < 4 $
我們可以減少 $ x = h[0] + \dots + 2^{130} u \equiv h[0] + \dots + 5 u \pmod p $ .
u = 5 * (u >> 2);現在我們可以添加 $ 5 u $ 從第一個數字開始，並傳播進位：
$ x = h[0] + 2^8 h[1] + \dots + 2^{128} h[16] + 5 u \ h[0], h[1], \dots, h[15] < 256 \ h[16] < 4 $
for (j = 0;j < 16;++j)
- 循環不變數：
$ x = h[0] + 2^8 h[1] + \dots + 2^{8j} (h[j] + u) + \dots + 2^{128} h[16] \ h[0], h[1], \dots, h[15] < 256 \ h[16] < 4 $
{ u += h[j]; h[j] = u & 255; u >>= 8; }現在我們又有了一個 128 位進位，但是還有足夠的空間，因為 $ h[16] $ 在這一點上只有兩位，從上面
h[16] = (u & 3).$ x = h[0] + 2^8 h[1] + \dots + 2^{128} (h[16] + u) h[0], h[1], \dots, h[15] < 256 \ h[16] < 4 $
u += h[16]; h[16] = u;最後， $ h $ 再次表示以 256 為基數的整數，其數字以基數為界：
$ x = h[0] + 2^8 h[1] + \dots + 2^{128} h[16] \ h[0], h[1], \dots, h[16] < 256 $
但是，它不一定是最不具有代表性的模數 $ p $ . 為此，我們需要
freeze；squeeze只是傳播一批延遲進位並執行單個歸約步驟，因此有更多算術空間。（弄清楚什麼 $ B $ 是並在進位上設置相應的界限 $ u $ 留給讀者作為練習的每一步。）
另外，如果我想在此處更改基數，例如從 2^8 位更改為 2^16，是否需要更改上述片段？我需要將所有 8 更改為 16，將 255 更改為 2^16-1，但會是這樣嗎？
數組 $ h $ 表示整數 $ x = h[0] + 2^8 h[1] + 2^{16} h[2] + \dots + 2^{128} h[16] $ 入境時，和 $ x - (2^{130} - 5) k $ 對於一些 $ k \geq 0 $ 在我們替換的還原步驟後退出 $ 2^{130} u $ 經過 $ 5 u $ . （拋出 $ 2^{130} - 5 $ 的。）
如果要更改基數，請說從 $ 2^8 $ 至 $ 2^{17} $ , 然後數組 $ h $ 而是代表 $ x = h[0] + 2^{17} h[1] + 2^{34} h[2] + \dots + 2^{119} h[7] + 2^{136} h[8] $ . 目標是計算相同的減少， $ x - (2^{130} - 5) k $ 對於一些 $ k \geq 0 $ ，但找到倍數 $ 2^{130} $ 替換為的倍數 $ 5 $ 因為減少步驟將發生在不同的數字位置， $ h[i] $ ，以及該數字或進位內的不同位位置， $ u \gg j $ .
找到這些位置是一個簡單的練習。對於更簡單的練習，您可以嘗試編寫算術模 $ 2^{31} - 1 $ 基數 $ 2^8 $ ，您可以在其中輕鬆地徹底測試歸約步驟的正確性。我建議您進行此練習，而不是要求網際網路上的假名陌生人用勺子餵您答案！