密碼學/布魯姆-戈德瓦瑟

布魯姆-戈德瓦瑟（BG）密碼系統是由曼紐爾·布魯姆和沙菲·戈德瓦瑟在 1984 年提出的非對稱金鑰加密演算法。布魯姆-戈德瓦瑟是一種機率的、語義安全的密碼系統，具有恆定大小的密文擴充套件。加密演算法使用 Blum Blum Shub (BBS) 偽隨機數生成器來生成金鑰流，實現基於 XOR 的流密碼。解密透過使用私鑰操縱 BBS 生成器的最終狀態來實現，以便找到初始種子並重建金鑰流。

BG 密碼系統基於對整數分解的假設難處理性而語義安全；具體來說，分解一個複合值 $N=pq$，其中 $p,q$ 是大素數。BG 比早期機率加密方案（如 Goldwasser-Micali 密碼系統）具有多項優勢。首先，它的語義安全性僅減少到整數分解，不需要任何額外的假設（例如，二次剩餘問題的難度或 RSA 問題）。其次，BG 在儲存方面是有效的，無論訊息長度如何，它都會產生恆定大小的密文擴充套件。BG 在計算方面也相對高效，即使與 RSA 等密碼系統相比，其效率也很好（取決於訊息長度和指數選擇）。然而，BG 非常容易受到自適應選擇密文攻擊（見下文）。

由於加密是使用機率演算法執行的，因此給定的明文每次加密時可能會產生非常不同的密文。這具有顯著的優勢，因為它可以防止攻擊者透過將攔截的訊息與已知密文的字典進行比較來識別攔截的訊息。

方案定義

請注意，以下描述是草稿，可能包含錯誤！

布魯姆-戈德瓦瑟包括三種演算法：一種機率金鑰生成演算法，它產生公鑰和私鑰；一種機率加密演算法；以及一種確定性解密演算法。

金鑰生成

為了允許解密，布魯姆-戈德瓦瑟加密中使用的模數應該是布魯姆整數。此值的生成方式與 RSA 模數相同，只是素因子 $(p,q)$ 必須與 3 mod 4 同餘。（參見 RSA，金鑰生成以瞭解詳細資訊。）

1. 愛麗絲生成兩個大素數 $p\,$ 和 $q\,$，使得 $p\neq q$，隨機且彼此獨立，其中 $(p,q)\equiv 3$ mod $4$.
2. 愛麗絲計算 $N=pq$.

公鑰 是 $N$。私鑰是因式分解 $(p,q)$。

1. 愛麗絲將私鑰保密。

1. 愛麗絲將 $N$ 給鮑勃。

訊息加密

假設鮑勃希望將訊息 m 傳送給愛麗絲

1. 鮑勃首先將 $m$ 編碼成一個包含 $L$ 個位元的字串 $(m_{0},\dots ,m_{L-1})$。
2. 鮑勃隨機選擇一個元素 $r$，其中 $1<r<N$，並計算 $x_{0}=r^{2}~mod~N$。
3. 鮑勃使用 BBS 偽隨機數生成器生成 $L$ 個隨機位元 ${\vec {b}}=(b_{0},\dots ,b_{L-1})$（金鑰流），如下所示。
   1. 對於 $i=0$ 到 $L$
   2. 將 $b_{i}$ 設定為 $x_{i}$ 的最低有效位。
   3. 遞增 $i$。
   4. 計算 $x_{i}=(x_{i-1})^{2}~mod~N$。
4. 鮑勃使用來自 BBS 的位元作為流密碼金鑰流，將明文位元與金鑰流進行異或運算，從而計算出密文位元。
   1. 對於 $i=0$ 到 $L-1$
   2. ${\vec {c}}={\vec {m}}\oplus {\vec {b}}$

1. Bob 向 Alice 傳送了一條訊息——加密後的位元和最終的 $x_{L}$ 值 $(c_{0},\dots ,c_{L-1}),x_{L}$.

(值 $x_{L}$ 等於 $x_{L}=x_{0}^{2^{L}}~mod~N$。)

為了提高效能，BBS 生成器可以在每次迴圈中安全地輸出高達 $O(loglogN)$ 個 $x_{i}$ 的最低有效位。詳情請參閱 Blum Blum Shub。

訊息解密

Alice 收到 $(c_{0},\dots ,c_{L-1}),y$。她可以使用以下步驟恢復 $m$

1. 使用素數分解 $(p,q)$，Alice 計算 $r_{p}=y^{((p+1)/4)^{L}}~mod~p$ 和 $r_{q}=y^{((q+1)/4)^{L}}~mod~q$.
2. 計算初始種子 $x_{0}=(q(q^{-1}~{mod}~p)r_{p}+p(p^{-1}~{mod}~q)r_{q})~{mod}~N$
3. 從 $x_{0}$ 開始，使用 BBS 生成器重新計算位元向量 ${\vec {b}}$，如同加密演算法一樣。
4. 透過將金鑰流與密文進行異或運算來計算明文：${\vec {m}}={\vec {c}}\oplus {\vec {b}}$.

愛麗絲恢復明文 $m=(m_{0},\dots ,m_{L-1})$.

安全性和效率

Blum-Goldwasser 方案在語義上是安全的，其安全性基於僅給定最終 BBS 狀態 $y$ 和公鑰 $N$ 預測金鑰流位的能力。然而，形式為 ${\vec {c}},y$ 的密文容易受到自適應選擇密文攻擊，在攻擊中，攻擊者請求對所選密文 ${\vec {a}},y$ 的解密 $m^{\prime }$。原始密文的解密 $m$ 可以計算為 ${\vec {a}}\oplus m^{\prime }\oplus {\vec {c}}$.

根據明文大小，BG 的計算成本可能比 RSA 高或低。由於大多數 RSA 部署使用固定加密指數，該指數經過最佳化以最大程度地減少加密時間，因此 RSA 加密通常在除最短訊息之外的所有訊息中都優於 BG。但是，由於 RSA 解密指數是隨機分佈的，因此對於相同長度的密文，模冪運算可能需要與 BG 解密相當數量的平方/乘法。BG 的優勢在於它可以更有效地擴充套件到更長的密文，而 RSA 需要多個單獨的加密。在這些情況下，BG 可能顯著更有效。

參考文獻

1. M. Blum, S. Goldwasser, "An Efficient Probabilistic Public Key Encryption Scheme which Hides All Partial Information", Proceedings of Advances in Cryptology - CRYPTO '84, pp. 289–299, Springer Verlag, 1985.
2. Menezes, Alfred; van Oorschot, Paul C.; and Vanstone, Scott A. Handbook of Applied Cryptography. CRC Press, October 1996. ISBN 0-8493-8523-7

外部連結

• Menezes, Oorschot, Vanstone, Scott: Handbook of Applied Cryptography (free PDF downloads), see Chapter 8