Modes-of-Operation

(AES-)GCM 是否可並行化?

  • August 14, 2015

我最近在使用 AES-GCM 時遇到了隨機訪問解密的問題。我說這個人說底層 CTR 應該允許並行化,但我不知道身份驗證是如何發揮作用的。

現在我知道 CTR 的一個很酷的功能是您可以解密任何塊而無需涉及任何其他塊。我也知道 CTR 是 GCM 基礎的一部分。

現在我的問題是:

  1. 是否可以以某種方式並行化 GCM 模式下的數據加密(僅 CTR 部分?MAC 的部分?)
  2. 是否可以隨機訪問解密的密文(+ 快速驗證?),或者至少可以以某種方式並行化解密和身份驗證(並行或內部並行?)?

與斯蒂芬所說的相反,您絕對可以並行計算標籤。

這是它的工作原理;標籤計算本質上是“組裝 AAD、數據、長度欄位和 $ Encr(Nonce) $ 成一系列值 $ x_n, x_{n-1}, x_{n-2}, …, x_0 $ ”,然後“計算多項式 $ x_nh^n + x_{n-1}h^{n-1} + x_{n-2}h^{n-2} + … + x_0h^0 $

該計算在現場進行評估 $ GF(2^{128}) $ ; 因為它是一個領域,所有重新排列多項式的標準方法都有效。

例如,如果我們想將其轉換為三向並行,我們可以計算 $ j = h^3 $ ,然後三個多項式並行:

$$ tag_2 = j^0x_2 + j^1x_5 + j^2x_8 + … $$ $$ tag_1 = j^0x_1 + j^1x_4 + j^2x_7 + … $$ $$ tag_0 = j^0x_0 + j^1x_3 + j^2x_6 + … $$ 然後將它們組合起來以獲得最終結果 $ tag = h^2tag_2 + h^1tag_1 + h^0tag_0 $

顯然,我們可以將其調整到適合我們的任何並行度,並且我們沒有以任何方式更改標記結果。

Stephen 還指出,需要掃描整個消息以計算標籤。對於任何具​​有作為整個消息的複雜函式的標籤的方法來說,這都是正確的。

引用自:https://crypto.stackexchange.com/questions/27466