elgamal加密算法python代码

ElGamal加密算法是一种公钥密码体制，其安全性基于离散对数问题。该算法的加密过程包括密钥生成、加密和解密三个步骤。下面将详细介绍如何用Python实现ElGamal加密算法。

1. 密钥生成

在ElGamal加密算法中，每个用户都有一对公私钥。首先需要生成一个大素数p和一个原根g，这两个参数都是公开的。然后随机选择一个小于p-2的整数x作为私钥，计算y=g^x mod p作为公钥。最终返回(p, g, y, x)四个参数。

代码实现：

```python import random

def generate_key(p_bits): # 生成一个p位的大素数 p = get_large_prime(p_bits)

# 找到p-1的原根

g = find_primitive_root(p)

# 随机选择一个小于p-2的整数作为私钥 x = random.randint(0, p-3)

# 计算公钥 y = pow(g, x, p)

return (p, g, y, x)

def get_large_prime(bits): while True:

prime = random.getrandbits(bits) if is_prime(prime): return prime

def is_prime(n): if n <= 1: return False elif n <= 3: return True

elif n % 2 == 0 or n % 3 == 0:

return False i = 5

while i * i <= n:

if n % i == 0 or n % (i + 2) == 0: return False i += 6 return True

def find_primitive_root(p): factors = get_factors(p-1) for g in range(2, p):

if all(pow(g, (p-1)//f, p) != 1 for f in factors): return g

def get_factors(n): factors = [] while n % 2 == 0: factors.append(2) n //= 2

for f in range(3, int(n**0.5)+1, 2): while n % f == 0: factors.append(f) n //= f

if n > 2:

factors.append(n) return set(factors) ``` 2. 加密

加密过程中，需要先将明文转换为整数m，并随机选择一个小于p-2的整数k作为加密因子。然后计算c1=g^k mod p和c2=m*y^k mod p，最终返回密文(c1, c2)。

代码实现：

```python

def encrypt(m, pk): p, g, y, x = pk

# 随机选择一个小于p-2的整数作为加密因子 k = random.randint(0, p-3)

# 计算密文 c1 = pow(g, k, p)

c2 = (m * pow(y, k, p)) % p

return (c1, c2) ``` 3. 解密

解密过程中，需要用私钥x计算c1^x mod p的逆元，然后再用逆元乘以密文的第二部分c2，最终得到明文m。

代码实现：

```python

def decrypt(c, sk): p, g, y, x = sk

# 计算c1^x mod p的逆元 inv_c1x = pow(c[0], x, p) inv_c1x = pow(inv_c1x, -1, p)

# 计算明文

m = (c[1] * inv_c1x) % p

return m

```

完整代码如下：

```python import random

def generate_key(p_bits): # 生成一个p位的大素数 p = get_large_prime(p_bits)

# 找到p-1的原根

g = find_primitive_root(p)

# 随机选择一个小于p-2的整数作为私钥 x = random.randint(0, p-3)

# 计算公钥 y = pow(g, x, p)

return (p, g, y, x)

def get_large_prime(bits):

while True:

prime = random.getrandbits(bits) if is_prime(prime): return prime

def is_prime(n): if n <= 1: return False elif n <= 3: return True

elif n % 2 == 0 or n % 3 == 0: return False i = 5

while i * i <= n:

if n % i == 0 or n % (i + 2) == 0: return False i += 6 return True

def find_primitive_root(p): factors = get_factors(p-1) for g in range(2, p):

if all(pow(g, (p-1)//f, p) != 1 for f in factors):

return g

def get_factors(n): factors = [] while n % 2 == 0: factors.append(2) n //= 2

for f in range(3, int(n**0.5)+1, 2): while n % f == 0: factors.append(f) n //= f if n > 2:

factors.append(n) return set(factors)

def encrypt(m, pk): p, g, y, x = pk

# 随机选择一个小于p-2的整数作为加密因子 k = random.randint(0, p-3)

# 计算密文 c1 = pow(g, k, p)

c2 = (m * pow(y, k, p)) % p

return (c1, c2)

def decrypt(c, sk): p, g, y, x = sk

# 计算c1^x mod p的逆元 inv_c1x = pow(c[0], x, p) inv_c1x = pow(inv_c1x, -1, p)

# 计算明文

m = (c[1] * inv_c1x) % p

return m

if __name__ == '__main__':

# 测试密钥生成

pk = generate_key(1024) print('公钥：', pk[0], pk[1], pk[2]) print('私钥：', pk[3])

# 测试加密和解密 m = 123456789 c = encrypt(m, pk) print('密文：', c[0], c[1]) m2 = decrypt(c, pk) print('明文：', m2) ```

注意，由于ElGamal加密算法的计算量较大，所以在实际应用中需要选择适当的参数位数。此外，在生成大素数时可以使用Miller-Rabin素性测试来提高效率。