加解密模式分析 - ElGamal 加密算法 | Alice and Bobの神秘小屋

ElGamal 加密算法，作为非对称加密的经典方案之一，基于离散对数问题的困难性，为数据加密和数字签名提供了强大的安全保障。它在实际应用中被广泛采用，尤其是在需要高安全性的场景中。

在本章中，我们将深入分析 ElGamal 加密算法的核心原理和实现细节。我们将从 ElGamal 的数学基础开始，逐步揭示其加密和解密过程中的关键步骤。通过对 ElGamal 算法的详细解析，你将能够理解它是如何利用离散对数问题的困难性来确保数据安全的。

ElGamal 加密数学原理 😇

ElGamal 加密算法的安全性基于离散对数问题的困难性。
首先，对于乘法群 $(Z_p^*, \times)$，其阶数为 $p-1$，通过 $g$ 的幂次运算，可以生成群中的所有元素。

而对于一个足够大的素数 $p$ 和生成元 $g$，计算 $y = g^x \mod p$ 的离散对数 $x$ 是非常困难的。这意味着攻击者无法轻易地从公钥 $y$ 中推断出私钥 $x$，从而无法解密密文。

举个例子，在模数为 $p = 17627$ 和生成元 $g = 6$ 的情况下，其幂次的结果是非常离散的，没有规律可言，如下图：（仅列举100个）
离散对数问题示例

在 ElGamal 加密过程中，选择合适的 $p$ 和 $g$ 是至关重要的。通常，$p$ 被选择为一个大素数，而 $g$ 则被选择为 $p$ 的一个生成元，以确保算法的安全性。

ElGamal 加密过程 😁

一天，Alice 想要向 Bob 发送一条秘密消息。为了确保消息的安全性，Alice 决定使用 ElGamal 加密算法。

首先通信双方先共享两个公共参数，模数 $p$ 和生成元 $g$。

Alice本地随机生成一个私钥 $x$，并计算 $y ≡ g^x \mod p$，将 $y$作为公钥发送给Bob。

Bob收到 $y$ 后，选择一个随机数 $k$ （$1 < k < p-2$且 $k$与 $p-1$互素），计算临时公钥 $C_1 ≡ g^k \mod p$。
然后，计算共享密钥 $K ≡ y^k ≡ g^{xk} \mod p$。
对明文信息 $m$ 进行处理使得 $m < p$ （如果 $m$ 过大，可以分段加密），使用共享密钥 $K$ 对消息 $m$ 进行加密，计算 $C_2 ≡ m·K \mod p$。
Bob将密文对 $(C_1, C_2)$ 发送给Alice。

Alice收到密文对 $(C_1, C_2)$ 后，计算共享密钥 $K ≡ C_1^x ≡ g^{kx} \mod p$
Alice使用共享密钥 $K$ 对 $C_2$ 进行解密，计算 $m ≡ C_2 · K^{-1} \mod p$

加密侧（Bob）：$K = y_A^k = (g^x)^k = g^{xk}$ → $C_2 = M \times K \mod p$
解密侧（Alice）：$K = C_1^x = (g^k)^x = g^{xk}$ → $M = C_2 \times K^{-1} \mod p$

ElGamal 加密算法实现 🥰

下面是一个简单的 ElGamal 加密算法的 Python 实现示例：

from sage.all import random_prime, inverse_mod, primitive_root, randint, gcd

# 共享数据
bits = 256  # 素数位数
upper = pow(2, bits)
lower = pow(2, bits - 1)
p = random_prime(upper, lbound=lower) # 生成大素数 p
g = primitive_root(p) # 找模 p 的一个生成元 g

# Alice 生成私钥 x（随机整数 1 < x < p-1）
x = randint(2, p-2)
y = pow(g, x, p) # 计算公钥 y = g^x mod p

# Bob 操作
M = "hello_Alice"  # 待加密的消息
long_M = int.from_bytes(M.encode(), 'big') # 字符串转整数
assert long_M < p, f"消息太大！请分段，要求 long_M < p={p}"

# Bob 选择随机数 k（1 < k < p-1，且 gcd(k, p-1)=1）
while True:
    k = randint(2, p-2)
    if gcd(k, p-1) == 1:
        break
# 计算密文对 (C1, C2)
C1 = pow(g, k, p)          # 临时公钥
K = pow(y, k, p)           # 共享密钥 K = y^k = g^{xk}
C2 = (long_M * K) % p       # 加密消息
cipher = (C1, C2)

# Alice 解密消息
C1, C2 = cipher
K_decrypt = pow(C1, x, p) # 用私钥 x 恢复共享密钥 K 
K_inv = inverse_mod(K_decrypt, p) # 求 K 在模 p 下的逆元
decrypted_long_M = (C2 * K_inv) % p # 恢复消息的整数形式
# 整数转回字符串
byte_len = (decrypted_long_M.bit_length() + 7) // 8
# 由于python和sage的整数类型不同，所以需要转换一下
M = int(decrypted_long_M)
flag = int.to_bytes(M,length=byte_len,byteorder='big').decode()
print(flag) # 输出解密后的消息

实际上由于 sage 中的整数类型和 python 中的整数类型不同，所以在非必要情况下不要纯使用sage函数进行算法实现，可以多使用python的密码学库使用。

上一章：加解密模式分析 - Rabin 加密算法 👈
下一章：加解密模式分析 - ECC 加密算法 👈
回到开始：关于我 👈