NaCl Poly1305 實現如何進行模乘？

Poly1305的 NaClref實現執行模乘以計算多項式 $ \mod 2^{130} - 5 $ 使用以下模乘函式：

static void mulmod(unsigned int h[17],const unsigned int r[17])
{  
 unsigned int hr[17];
 unsigned int i, j, u;

 for (i = 0;i < 17;++i) {
   u = 0;
   for (j = 0;j <= i;++j) u += h[j] * r[i - j];
   for (j = i + 1;j < 17;++j) u += 320 * h[j] * r[i + 17 - j];
   hr[i] = u;
 }
 for (i = 0;i < 17;++i) h[i] = hr[i];
 squeeze(h);
}

…squeeze()減少在哪裡。一系列mulmod()操作用一個操作四捨五入freeze()：

static const unsigned int minusp[17] = {
 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 252
} ;

static void freeze(unsigned int h[17])
{
 unsigned int horig[17];
 unsigned int j, negative;

 for (j = 0;j < 17;++j) horig[j] = h[j];
 add(h,minusp);
 negative = -(h[16] >> 7);
 for (j = 0;j < 17;++j) h[j] ^= negative & (horig[j] ^ h[j]);
}

此實現沒有文件，並且已按字面意思復製到各種項目中（上面的程式碼實際上來自libsodium fork）。

我已經將其與Wikipedia 、Montgomery Reduction和Daniel Bernsteins 顯式 CRT 方法上的各種乘法算法進行了比較，但我不認為它是其中的任何一種。

整個 Poly1305 的最基本實現使用gmp簡單add/mul/mod的操作，因此在主循環中沒有什麼深奧的。

減少和凍結似乎表明這是某種殘基數係統，但我找不到關於它如何工作的明確描述。

Daniel Bernstein 寫這篇文章的動機之一可能是有一個恆定的時間實現，如果這有助於辨識算法。

有沒有人認識這裡使用的算法，並且知道/可以提供它的完整解釋（即解釋幻數320和minusp如何派生的解釋，以及凍結中所有異或操作的基礎）？

數字以 256 為基數表示，即 $ h = \sum_{i=0}^{17} h_i \cdot 256^i $ . 由於使用了比字節大得多的整數，因此您不需要立即傳播進位。

如果你忘記了模組化減少，那麼 $ i $ 結果的第 th 位計算為 $ \sum_{j=0}^i h_j\cdot r_{i-j} $ . 除了沒有進位之外，這與教科書乘法幾乎相同。

現在要考慮模組化歸約，您從第 130 位開始計算結果的高位。現在您可以將這 130 位右移，將它們乘以 5，然後將其添加到未歸約的結果中。現在右移 130 位可以通過右移 17 個字節然後左移 6 位來完成。向右移動 17 個字節是使用r[i + 17 - j]. 向左移動 6 位相當於乘以 64。將其與乘以 5 相結合，得到乘以 320。

for (i = 0;i < 17;++i)
{// compute the i-th byte of the output 
   u = 0;
   for (j = 0;j <= i;++j) u += h[j] * r[i - j];// schoolbook multiplication
   for (j = i + 1;j < 17;++j) u += 320 * h[j] * r[i + 17 - j];// 5 * overflow >> 130
   hr[i] = u;
}

所以第一個內循環是那些沒有溢出的數字的貢獻，第二個內循環是溢出的貢獻。

freeze似乎只是：

if(h > p)
   return h - p;
else
   return h;

除了它使用按位運算來避免分支。minusp是 $ 2^{8 \cdot 17}-(2^{130}-5) $ ，即它只是表示 $ -p $ . 它可以用來減少模 $ p $ 如果輸入小於 $ 2p $ .

由於 的各個元素h可以大於 256 但以 256 為基數，因此您需要在每次乘法結束時傳播進位。這是使用squeeze. 現在在傳播進位之後，你會得到一個介於 0 和 $ 2p-1 $ . 作為中間步驟的結果有一個稍微太大的值不是問題，因此預設情況下不會進一步減少。

但是在 MAC 你需要一個介於 0 和 $ p-1 $ , 所以freeze用作最終歸約。

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