Python实现ElGamal加密算法的示例代码

在密码学中，ElGamal加密算法是一个基于迪菲-赫尔曼密钥交换的非对称加密算法。它在1985年由塔希尔·盖莫尔提出。GnuPG和PGP等很多密码学系统中都应用到了ElGamal算法。

ElGamal加密算法可以定义在任何循环群G上。它的安全性取决于G上的离散对数难题。

使用Python实现ElGamal加密算法，完成加密解密过程，明文使用的是125位数字（1000比特）。

代码如下：

import random
from math import pow
a = random.randint(2, 10) #产生小于p的随机常数a

def gcd(a, b):
 if a < b:
   return gcd(b, a)
 elif a ％ b == 0:
   return b;
 else:
   return gcd(b, a ％ b)
 # Generating large random numbers

def gen_key(q):
 key = random.randint(pow(10, 20), q)
 while gcd(q, key) != 1:
   key = random.randint(pow(10, 20), q)
 return key

# Modular exponentiation
def power(a, b, c):
 x = 1
 y = a
 while b > 0:
   if b ％ 2 == 0:
     x = (x * y) ％ c;
   y = (y * y) ％ c
   b = int(b / 2)
 return x ％ c

# Asymmetric encryption
def encrypt(msg, p, h, r):
 en_msg = []
 b = gen_key(p) # 得b
 K = power(h, b, p)#K=(Sa)^b mod p
 C1 = power(r, b, p) #C1=Sb=r^b mod p
 for i in range(0, len(msg)):
   en_msg.append(msg[i])
 print("C1 : ", C1)
 # print("(Sa)^b mod p used : ", K)
 for i in range(0, len(en_msg)):
   en_msg[i] = K * ord(en_msg[i])
 print("C2 : ", en_msg)
 return en_msg, C1

def decrypt(C2, C1, a, p):
 dr_msg = []
 h = power(C1, a, p)
 for i in range(0, len(C2)):
   dr_msg.append(chr(int(C2[i] / h)))
 return dr_msg

# Driver code
def main():
 msg = '01234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234'        # 共125位数字，1000bit
 print("明文 :", msg)
 p = random.randint(pow(10, 20), pow(10, 50))# 获得大素数q
 r = random.randint(2, p)#得r
 a = gen_key(p) # Private key for receiver
 h = power(r, a, p)
 C2, C1 = encrypt(msg, p, h, r)
 dr_msg = decrypt(C2, C1, a, p)
 dmsg = ''.join(dr_msg)
 print("解密后文 :", dmsg);

if __name__ == '__main__':
 main()

来源：https://blog.csdn.net/I_canjnu/article/details/106807142