BearSSL 的 GCM 模組化縮減是如何工作的？

BearSSL（在src/hash/ghash_ctmul.c 中）似乎正在做我不完全理解的模組化縮減。這是程式碼：

/*
* GHASH specification has the bits "reversed" (most
* significant is in fact least significant), which does
* not matter for a carryless multiplication, except that
* the 255-bit result must be shifted by 1 bit.
*/
zw[0] = c0 << 1;
zw[1] = (c1 << 1) | (c0 >> 31);
zw[2] = (c2 << 1) | (c1 >> 31);
zw[3] = (c3 << 1) | (c2 >> 31);
zw[4] = (d0 << 1) | (c3 >> 31);
zw[5] = (d1 << 1) | (d0 >> 31);
zw[6] = (d2 << 1) | (d1 >> 31);
zw[7] = (d3 << 1) | (d2 >> 31);

/*
* We now do the reduction modulo the field polynomial
* to get back to 128 bits.
*/
for (i = 0; i < 4; i ++) {
   uint32_t lw;

   lw = zw[i];
   zw[i + 4] ^= lw ^ (lw >> 1) ^ (lw >> 2) ^ (lw >> 7);
   zw[i + 3] ^= (lw << 31) ^ (lw << 30) ^ (lw << 25);
}

這種減少是如何工作的？

這裡有三個重要的點需要考慮。

1. 我們在 $ \mathbb{F}_2[X] $ . 這意味著我們對二進制多項式進行加法和乘法運算，即係數為 0 或 1 的多項式。兩個多項式的加法是按位異或；沒有進位傳播。類似地，乘法被稱為“無進位”乘法。這裡有一些解釋。

特別是，“模約簡”是關於多項式的除法，而不是整數。模數是二元多項式 $ X^{128} + X^7 + X^2 + X + 1 $ （這是一個不可約多項式 $ \mathbb{F}_2 $ ，這意味著當計算以該多項式為模的東西時，我們在有限域中工作）。

**2. 關於編碼存在相當多的混淆。**這是 GCM 規範中的一個問題。輸入字節將被解釋為位，即二進制多項式的係數。“字節序”是關於如何將元素的塊（例如字節中的位）映射到它們的數學值。例如，如果您考慮一個數值字節 0xC9（十進制的 201）並將其寫為位序列，您通常使用大端表示法，即您將其寫為“11001001”：最左邊的位是具有最高值（ $ 2^7 = 128 $ ), 最右邊的是具有最低值的那個 ( $ 2^0 = 1 $ ）。這就是整數發生的情況；對於二進制多項式，字節的大端解釋是將最左邊的位映射到 $ X^7 $ ，最右邊的係數 $ X^0 $ ; 因此，“11001001”將被解碼為 $ X^7 + X^6 + X^3 + 1 $ .

字節順序的概念適用於所有級別；即不僅字節內的位，而且字節序列內的字節。對 16 個字節序列的“純大端”解釋將是在大端（如上）中解碼每個字節，然後將所有字節組合在一起，最重要的字節首先出現，即序列中的第一個字節對應於二進制係數 $ X^{127} $ 至 $ X^{120} $ ，第二個字節是係數 $ X^{119} $ 至 $ X^{112} $ ， 等等。BearSSL 在純大端解釋中解碼輸入值；在內部，它不是將它們儲存為字節，而是儲存為 32 位字：

           /*
            * Decode the block. The GHASH standard mandates
            * big-endian encoding.
            */
           yw[3] ^= br_dec32be(src);
           yw[2] ^= br_dec32be(src + 4);
           yw[1] ^= br_dec32be(src + 8);
           yw[0] ^= br_dec32be(src + 12);

在這裡，yw[0]將包含係數 $ X^0 $ 至 $ X^{31} $ ,yw[1]係數 $ X^{32} $ 至 $ X^{63} $ ， 等等。

現在這裡有一個謊言。GHASH 標準並沒有真正要求大端編碼。事實上，它要求完全相反，即純小端編碼，即不僅第一個字節應該用於係數 $ X^0 $ 至 $ X^7 $ ，但該字節內的位以“非自然”順序解釋，即最高有效位（數值 128）用於係數 $ X^0 $ ， 不是 $ X^7 $ . 這種字節內比特的小端約定對於計算來說非常不方便，尤其是因為 BearSSL 通過對普通整數進行乘法來實現無進位乘法（即與進位相乘，但在必要時使用遮罩和孔來刪除這些進位）。如果 BearSSL 使用純 little-endian 約定，那麼它將不得不在字節內交換位，這是一個繁瑣的操作，會降低性能並增加程式碼大小。

相反，BearSSL 使用了一種適用於二進制多項式的技巧。即，如果您定義位反轉： $$ \mathrm{rev}n \Big(\sum{i=0}^{n-1} a_i X^i\Big) = \sum_{i=0}^{n-1} a_{n-1-i} X^i $$ 那麼，當兩個多項式相乘時 $ A $ 和 $ B $ 學位小於 $ n $ （即適合 $ n $ 位）： $$ \mathrm{rev}_n(A) \times \mathrm{rev}n(B) = \mathrm{rev}{2n-1}(A \times B) $$ 即如果你顛倒兩個操作數，你會得到相反的乘積。這在純整數上根本不起作用，因為純整數上的加法具有進位，並且進位在確定的方向（從右到左，在通常的符號中）傳播，並且“在鏡子中”不起作用。但是使用無進位乘法，沒有進位，一切都可以鏡像。

這意味著，通過使用純大端符號解碼 16 個字節，BearSSL 沒有得到預期的多項式 $ A $ ， 但 $ \mathrm{rev}_{128}(A) $ . 然後在反轉的操作數上計算乘積，並產生期望值的反轉。如果要使用純大端符號重新編碼該結果，那麼一切正常！操作與位反轉（“鏡像”）的兼容性意味著您可以真正選擇您想要的編碼約定，並且您會得到正確的結果，前提是您始終堅持您的約定。

…除了一個小細節。如果您查看上面的等式，兩個位反轉的 128 位多項式的乘積會產生 255 位而不是 256 位的位反轉結果。BearSSL 程式碼最終得到 256 位結果zw[]，並且該值被移位一點點，因為那個顛倒的約定問題。因此，程式碼必須包含一個移動步驟，以將其放回應有的位置，這是您在問題中重現的程式碼的前半部分：

          /*
            * GHASH specification has the bits "reversed" (most
            * significant is in fact least significant), which does
            * not matter for a carryless multiplication, except that
            * the 255-bit result must be shifted by 1 bit.
            */
           zw[0] = c0 << 1;
           zw[1] = (c1 << 1) | (c0 >> 31);
           zw[2] = (c2 << 1) | (c1 >> 31);
           zw[3] = (c3 << 1) | (c2 >> 31);
           zw[4] = (d0 << 1) | (c3 >> 31);
           zw[5] = (d1 << 1) | (d0 >> 31);
           zw[6] = (d2 << 1) | (d1 >> 31);
           zw[7] = (d3 << 1) | (d2 >> 31);

因此，這些行實際上是為了讓它好像一切都是在純小端約定中完成的，而它是在純大端約定中完成的。

**3. 模約簡是二元多項式。**我們工作模多項式 $ M = X^{128} + X^7 + X^2 + X + 1 $ . 這意味著對於任何多項式 $ P $ ，我們可以加（或減，但在 $ \mathbb{F}_2[X] $ , 加減法是一回事, 即異或) 的任意倍數 $ M $ . 255 位結果的“模組化縮減” $ P $ 真的是倍數的加法 $ M $ 直到我們得到適合 128 位的東西。

寫多項式以減少 $ P = \sum_{i=0}^{254} p_i X^i $ . 取一個係數 $ p_i $ 對於一些 $ i \ge 128 $ ; 我們想“取消那個位”，以防它作為值 $ 1 $ ; 訣竅是添加 $ M\times X^{i-128} $ . 換句話說，我們添加： $$ p_i M \times X^{i-128} = p_i X^i + p_i X^{i-121} + p_i X^{i-126} + p_i X^{i-127} + p_i X^{i-128} $$

第一部分 （ $ p_i X^i $ ) 僅清除位置處的位 $ i $ （這是一個 XOR $ p_i $ 與自身），但其他部分“注入”（XOR）位 $ p_i $ 在係數序列的其他位置。至關重要的是，這些距離相對較遠（序列向下 121 位或更多位），這使我們能夠按大塊處理位（這就是使用該值選擇模數的原因）。考慮該循環的第一次迭代：

           /*
            * We now do the reduction modulo the field polynomial
            * to get back to 128 bits.
            */
           for (i = 0; i < 4; i ++) {
                   uint32_t lw;

                   lw = zw[i];
                   zw[i + 4] ^= lw ^ (lw >> 1) ^ (lw >> 2) ^ (lw >> 7);
                   zw[i + 3] ^= (lw << 31) ^ (lw << 30) ^ (lw << 25);
           }

這個詞zw[0]包含係數 $ X^{255} $ 至 $ X^{224} $ . 由於係數為 $ X^i $ 必須在位置注入 $ X^{i-121} $ , $ X^{i-126} $ , $ X^{i-127} $ 和 $ X^{i-128} $ , 這 32 位最終被注入到zw[3]和的不同位置zw[4]。在更新的行中zw[i+4]（即zw[4]在第一次迭代期間），我們看到與 的異或lw，這是在位置注入位 $ X^{i-128} $ ; 這lw >> 1是在位置注入位 $ X^{i-127} $ ; 等等。

名義上，我們應該清除高位（zw[0]to zw[3]），但這是優化的，因為我們不再查看這些位；減少後的有用結果zw[4]是zw[7]：

           memcpy(yw, zw + 4, sizeof yw);

這就是完整的模組化減少。

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