Mac
具有增量屬性的 Carter-Wegman MAC 的並行變體
Carter-Wegman MAC 算法的變體是否存在快速、並行且具有增量加密屬性的變體？
GMAC怎麼樣？它是一個 Carter-Wegman MAC，滿足快速計算和可並行化的要求。
此外，它可以安全地更新，也就是說，給定一個長消息，您可以比重新計算整個 MAC 更快地計算該消息的修改版本的 MAC。例如，假設您有一個 message/nonce/tag 三元組 $ (N, M, T) $ ，並且您想更改塊 $ i $ 消息的 $ M $ 從價值 $ a $ 到價值 $ b $ （在哪裡 $ i $ 倒數； $ i=0 $ 是最後一個塊， $ i=1 $ 是倒數第二個塊）。為此，您創建一個新的（以前從未使用過的）隨機數 $ N’ $ ，併計算：
$ T’ = T \oplus (H^{i+2} \times (a \oplus b)) \oplus AES_k(Pad(N)) \oplus AES_k(Pad(N’)) $
結果是三倍 $ (N’, M’, T’) $ ， 在哪裡：
- $ k $ 和 $ H $ 是 GMAC 中的密鑰和秘密值
- $ \times $ 和 $ H^{i+2} $ 計算在 $ GF(2^{128}) $
- $ \oplus $ 是排他的或（在 $ GF(2^{128}) $ )
- $ i+2 $ 用正常加法計算（不是 $ GF(2^{128}) $ 添加）。
- $ AES_k(X) $ 是 128 位塊的 AES 塊加密（ECB 模式） $ X $
- $ Pad $ 將 nonce 轉換為 128 位值（對於 96 位 nonce，這只是後掛 4 個 0x00 字節；對於其他大小，它更複雜）。
這需要 $ O(\log(i)) $ 時間（如果您預先計算，可以更快地完成 $ H^x $ 的各種值 $ x $ )，我認為這符合增量要求。