定期高效加倍高飛_(2n)GF(2n)GF(2^n)

一種計算乘法的簡單方法 $ a \cdot b $ 在形式的伽羅瓦域中 $ GF(2^n) $ 是俄羅斯農民算法。但是，它不是在恆定時間內執行的，因此對定時攻擊並不安全。

是否存在要實施的優化技術 $ 2 \cdot a $ 為了 $ a \in GF(2^n) $ 以正常方式？

如果我們考慮 $ GF(2^4) $ 由多項式定義 $ X^4 + X + 1 $ （0x13以十六進製表示），我發現最有效的解決方案是計算 $ 2 \cdot a $ 如下所述（在 C 程式碼中）

(a<<1) ^ (0x20 - ((a & 0x8) >> 3)) & 0x13

如果沒有預先計算，我們能否在效率方面做得更好？

是的，只要支持足夠寬的算術，問題中的原理就可以概括和稍微簡化。在 $ \text{GF}(2^k) $ 表示為範圍內的整數 $ [0,2^k) $ a最初在這個範圍內，我們可以兼作a：

( P & -( a >> S ) ) ^ ( a + a )

S定義為 $ k-1 $ ，以及P通過計算整數獲得的常數 $ x=2 $ 多項式 $ P(x) $ 表徵的特徵 $ \text{GF}(2^k) $ 作為整數。

該表達式採用 C99 的算術規則，或普遍存在的有符號整數的補碼表示。它適用於大多數忽略算術溢出的語言。位 XOR 的左操作數的^計算結果P為零或為零，具體取決於S數量的位a是否設置或清除（假設沒有設置的高階位a）。XOR 因此執行減少模 $ P(x) $ 的正確術語a + a（相當於a << 1）。

例如，在 $ \text{GF}(2^8) $ 多項式 $ x^8+x^4+x^3+x+1 $ ，我們設置P為 $ 2^8+2^4+2^3+2+1 $ . 表達式為：

( 0x11B & -( a >> 7 ) ) ^ ( a + a )

如果結果被截斷為 $ k $ 位（例如，因為它儲存在該大小的變數中），那麼P可以（並且應該）類似地截斷的值。這允許所有 $ k\le64 $ 使用 64 位寄存器（而不是 $ k\le63 $ 如果我們不使用這種截斷技術）。

在將所涉及的數量表示為固定數量的電腦單詞的大多數現代電腦和語言（甚至解釋）上，評估時間與 的值無關a。這可能不適用於表示為可變大小結構的整數，包括long在 Python 和BigIntegerJava 中，尤其是在 $ k $ 是字長的倍數。

已知一種編譯器會發出“應用於無符號類型的一元減運算符”警告，即使 C99 標準明確定義了將一元減運算符應用於無符號數量的行為。向供應商投訴，同時用 消除警告#pragma warning (disable : 4146)。或者，鞠躬和寫字

( 0x11B & ( 0 - ( a >> 7 ) ) ) ^ ( a + a )

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