Python实现ElGamal加密算法：原理与代码详解

青禾

发布时间：2026-10-14| 5人浏览过

原创

ElGamal是一种基于迪菲-赫尔曼密钥交换的非对称加密算法，其安全性依赖于循环群上的离散对数难题。本文通过Python代码示例，详细演示了如何生成密钥、执行加密与解密过程，并处理125位（1000比特）的大整数明文，适用于GnuPG和PGP等系统的算法理解。

ElGamal算法概述

在密码学领域，ElGamal加密算法是一种非对称加密方案，其核心基础是迪菲-赫尔曼密钥交换协议。该算法由塔希尔·盖莫尔于1985年提出，目前已被广泛应用于GnuPG和PGP等多种主流密码学系统中。

ElGamal算法可定义在任意循环群G之上，其安全性主要取决于该群上离散对数问题的计算难度。

Python实现与代码示例

本文将使用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()