這個 POLYVAL 模縮減算法是如何工作的？
我最近在AES-GCM-SIV 論文中發現了用於進行測量的 GitHub 儲存庫，其中他們使用 POLYVAL 實現了多項式雜湊。
這意味著在這種情況下計算通常的 $ \tau=\sum_{i=0}^nm_iH^{n-i} $ 對於 16 字節的消息塊 $ m_i $ 和一個 128 位密鑰 $ H $ 以通常的方式 $ H_{i+1}=(m_i+H_i)\cdot H $ 帶有消息和 $ H $ 被解釋為多項式 $ \mathbb F_2[x]/(x^{128}+x^{127}+x^{126}+x^{121}+1) $ .
現在實際計算使用 x86 硬體內在函式（可以在此處查找）。
有問題的程式碼是
Polyval_Horner（polyval.c第 137 行），特別是以下摘錄（從 repo 中採用和評論）：__m128i TMP0, TMP1, TMP2, TMP3, TMP4, T, POLY, H; H = _mm_loadu_si128(((__m128i*)pH)); T = _mm_loadu_si128(((__m128i*)TAG)); // ordering of the inputs is reversed, last is most significant // 0xc2000000 corresponds to the top 3 POLYVAL coefficients POLY = _mm_setr_epi32(0x1,0,0,0xc2000000); T = _mm_xor_si128(T, _mm_loadu_si128((__m128i*)inp)); // This instruction takes two 64-bit halves and carrylessly multiplies them // If the lower nibble is 0, take the lower half of the first input, else the upper half // likewise with the upper nibble for the second input TMP1 = _mm_clmulepi64_si128(T, H, 0x00); TMP4 = _mm_clmulepi64_si128(T, H, 0x11); TMP2 = _mm_clmulepi64_si128(T, H, 0x10); TMP3 = _mm_clmulepi64_si128(T, H, 0x01); // TMP2 and 3 contain the range of coefficients from 64 to 191, add them TMP2 = _mm_xor_si128(TMP2, TMP3); // now extract the upper and lower halves of these coefficients and add them // into either TMP1 or 4 depending on whether they are the lower or the upper coefficients TMP3 = _mm_slli_si128(TMP2, 8); TMP2 = _mm_srli_si128(TMP2, 8); TMP1 = _mm_xor_si128(TMP3, TMP1); TMP4 = _mm_xor_si128(TMP4, TMP2); // reduction starts here // multiply the lower half of TMP1 with the upper half of POLY TMP2 = _mm_clmulepi64_si128(TMP1, POLY, 0x10); // This re-orders the 32-bit subwords // 78 should exactly swap the 64-bit halves TMP3 = _mm_shuffle_epi32(TMP1, 78); TMP1 = _mm_xor_si128(TMP3, TMP2); TMP2 = _mm_clmulepi64_si128(TMP1, POLY, 0x10); TMP3 = _mm_shuffle_epi32(TMP1, 78); TMP1 = _mm_xor_si128(TMP3, TMP2); T = _mm_xor_si128(TMP4, TMP1);（我沒有轉換為虛擬碼以保留我可能出錯的任何特定指令行為）。此程式碼載入一個密鑰
pH，之前的迭代TAG將它與一些 16 字節的輸入相加，並以無進位的方式inp將其與它相乘pH，然後以 Polyval 多項式為模將其減少為 的新值T。我對上面程式碼的閱讀是
- 在歸約之前
TMP4持有乘法結果的 128 個最顯著多項式係數- 歸約前
TMP1保持乘法結果的128個最不顯著多項式係數現在我的問題是：
這種減少算法是如何工作的？
因為對我來說，如果我在紙上嘗試 $ x^{127} $ 和 $ x $ 我應該回來 $ x^{127}+x^{126}+x^{121}+1 $ 但相反，我認為算法返回了我 $ 1 $ .
這是我對如何閱讀歸約內在函式的解釋：
- 取乘法結果的低 128 位的低 64 位，將它們與多項式的高 64 位相乘（在我的範例中 $ 0 $ 乘以高位），稱之為
TMP2- 交換原始 128 位結果的 64 位一半，將其稱為
TMP3( $ 0 $ 在我的例子中，因為TMP1將是 0)- 加
TMP2和TMP3，呼叫結果TMP1( $ 0+0 $ )- 重複前三個步驟一次
- 返回目前
TMP1和TMP4（高 128 位）的加法，在我的情況下是 $ 0+1=1 $
所以，我終於想通了。對此的主要參考資料是來自 RWC'13 的 Shay Gueron 的幻燈片、應用密碼學手冊（第 14 章 PDF）和RFC 8452。
事實證明，POLYVAL的核心運營其實不是 $ a\cdot b\bmod p $ 而是相反 $ a\cdot b\cdot x^{-128}\bmod p $ （如RFC 8452中所述）。為此，問題中的算法計算了教科書無進位乘法的蒙哥馬利約簡，該乘法將結果的高 128 位儲存在 中，將結果
TMP4的低 128 位儲存在TMP1. 接下來是蒙哥馬利縮減（算法 14.23），手冊中描述的縮減參數如下：
- 模數 $ m $ 是 $ m(x)=x^{128}+x^{64}p(x)+1 $ 和 $ p(x)=x^{63}+x^{62}+x^{57} $ 這對應於
0xc2...程式碼中的常量。- 輸入 $ X $ 是 $ X_3,X_2 $ 從
TMP4和 $ X_1,X_0 $ 從TMP0.- 使用的基礎是 $ b=x^{64} $ 因為 PCLMULQDQ 提供 64x64 位無進位乘法。
- 反模數 $ m’=-m^{-1}\bmod b= (x^{64}+p(x))x^{64}+1 \bmod x^{64}=1 $
- 從上面的結果的基礎中使用的單詞數是 $ n=2 $ .
- 蒙哥馬利價值觀 $ R $ 是 $ R=x^{128} $ .
然後手冊中的算法要求計算結果 $ A=x^{-128}(X_3x^{192}+X_2x^{128}+X_1x^{64}+X_0+X_0m+X_1mx^{64}) $ 一旦擴展了所有步驟。替代 $ m $ 並簡化產生表達式 $ A=x^{-128}(X_3x^{192}+X_2x^{128}+X_0x^{128}+X_0x^{64}p(x)+X_1x^{128}p(x)+X_1x^{192}) $ 產生 $ A=X_3x^{64}+X_2+X_1x^{64}+X_0+X_0x^{-64}p(x)+X_1p(x) $ 唯一棘手的子表達式是 $ X_0x^{-64}p(x) $ 這可以通過將這個 128 位值分成兩半來解決 $ \operatorname{high64}(X_0p(x))+\operatorname{low64}(X_0p(x))x^{-64} $ 因為高 64 個係數可以立即相乘。然後我們觀察到 $ x^{-64}\equiv p(x)+x^{64}\pmod{x^{128}+x^{64}p(x)+1} $ 屈服 $ \operatorname{low64}(X_0p(x))p(x)+\operatorname{low64}(X_0p(x))x^{64} $ .
根據我們得到的幻燈片的描述：
- $ A=X_0p(x) $ （符合
TMP2 = _mm_clmulepi64_si128(TMP1, POLY, 0x10);說明）- $ B=X_0x^{64}+X_1+X_0p(x) $ （符合
TMP3 = _mm_shuffle_epi32(TMP1, 78); TMP1 = _mm_xor_si128(TMP3, TMP2);說明）- $ C=X_1p(x)+\operatorname{low64}(X_0p(x))p(x) $ （匹配第二
TMP2 = _mm_clmulepi64_si128(TMP1, POLY, 0x10);條指令）- $ D=X_1p(x)+\operatorname{low64}(X_0p(x))p(x)+X_0+X_1x^{64}+\operatorname{low64}(X_0p(x))x^{64}+\operatorname{high64}(X_0p(x)) $ （匹配第二
TMP3 = _mm_shuffle_epi32(TMP1, 78); TMP1 = _mm_xor_si128(TMP3, TMP2);條指令）- $ \text{Out}=X_3x^{192}+X_2x^{128}+X_1x^{64}+X_0+X_1p(x)+\operatorname{low64}(X_0p(x))p(x)+\operatorname{low64}(X_0p(x))x^{64}+\operatorname{high64}(X_0p(x)) $ （符合
T = _mm_xor_si128(TMP4, TMP1);說明）最後一個值與完全展開的匹配 $ A $ 我們從上面的蒙哥馬利約簡算法推導出來的表達式。
如果您查看第 2.3 節，您會從論文中找到有關減少的解釋。通過減少 GHASH 的操作數量來減少程式碼執行預期。
從理論的角度來看，論文作者對第一個歸納證明的推導方向不正確。然而，他們的錯誤導致發現 POLYVAL 和 GHASH 之間存在差異集連結。
其中A ^ B —> D0 和Z * 是確定****D0值的檢查次數。完成執行 GHASH 後，函式返回D *。由此操作員可以說B —> D0和Z < Z *。