密码学/布鲁姆-戈德瓦瑟

布鲁姆-戈德瓦瑟（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