本程序演示如下过程：

# ============================================================================
# Copyright (c) 2021 Zhou Jin, Shandong University. All rights reserved.
# Elgamal.py - The core part of this algorithm
# Last edited time: 2021/11/3 15:48
#
# THIS PROGRAM IS FREE SOFTWARE
# If you have any question, email elford@foxmail.com
# ============================================================================import random# Find the greatest common divisor
def gcd(a, b):if a < b:return gcd(b, a)elif a % b == 0:return belse:return gcd(b, a % b)# Quick power & modulo
def power(a, b, c):ans = 1while b != 0:if b & 1:ans = (ans * a) % cb >>= 1a = (a * a) % creturn ans# Detection of large prime numbers
def Miller_Rabin(n):a = random.randint(2, n - 2)  # Randomly find 'a' which is belong to [2,n-2]s = 0  # S is the power of factor 2 in dd = n - 1while (d & 1) == 0:  # Let's factor out all the 2's in d.s += 1d >>= 1x = power(a, d, n)for i in range(s):  # Perform s secondary probesnewX = power(x, 2, n)if newX == 1 and x != 1 and x != n - 1:return False  # Using the inverse of the quadratic theorem, n is determined to be composite.x = newXif x != 1:  # If x=a^(n-1) (mod n), then n is determined to be composite.return Falsereturn True  # Judge by the converse of Fermat's little theorem. The number that survives this test# is most likely prime.# Extended Euclidean algorithm, ab=1 (mod m), yields the multiplicative inverse b of A under module m
def Extended_Eulid(a: int, m: int) -> int:def extended_eulid(a: int, m: int):if a == 0:  # boundary conditionreturn 1, 0, melse:x, y, gcd = extended_eulid(m % a, a)  # recursionx, y = y, (x - (m // a) * y)  # Recursively, the left end is the upper layerreturn x, y, gcd  # Returns the result of the first level calculation.# The final return y value is the multiplication inverse of b in mode a# If y is complex, y plus a is the corresponding positive inversen = extended_eulid(a, m)if n[1] < 0:return n[1] + melse:return n[1]# Generate the field parameter alpha
def Generate_alpha(p: int) -> int:return random.randint(2, p)# Generate a prime number less than p, approximately 512bits long, as the private key
def Generate_private_key(p: int) -> int:pri = random.randint(2, p - 2)while gcd(pri, p) != 1:pri = random.randint(2, p - 2)return pri# Bob or Alice uses the field parameter P and the resulting mask to encrypt the message
def encrypt(message, p, Key_mask) -> int:ciphertext = (message * Key_mask) % preturn ciphertext# Bob or Alice decrypts the ciphertext using the field parameter P and the masks obtained by them
def decrypt(ciphertext, p, Key_mask):# Inverse maskinverse_element = Extended_Eulid(Key_mask, p)# Decodeplaintext = (ciphertext * inverse_element) % preturn plaintextdef quick_power(a: int, b: int) -> int:ans = 1while b != 0:if b & 1:ans = ans * ab >>= 1a = a * areturn ansif __name__ == '__main__':print("Message: ")message = int(input())if type(message) != int:raise ValueError("Must be an integer!")p = 11483166658585481347156601461652228747628274304826764495442296421425015253161813634115028572768478982068325434874240950329795338367115426954714853905429627alpha = 9312361210673900259563710385567927129060681135208816314239276128613236057152973946513124497622387244317947113336161405537229616593187205949777328006346729# Alice selects her own private key, calculates her own public key, and passes the public key to BobPrivate_Alice = Generate_private_key(p)Public_Alice = power(alpha, Private_Alice, p)# Bob selects his private key, calculates his public key, and places the public key on the networkPrivate_Bob = Generate_private_key(p)Public_Bob = power(alpha, Private_Bob, p)# Bob and Alice calculate the mask key separately, and the results should be the sameKey_mask_Alice = power(Public_Alice, Private_Bob, p)Key_mask_Bob = power(Public_Bob, Private_Alice, p)# Bob encrypts the messageciphertext_Alice = encrypt(message, p, Key_mask_Bob)# Alice encrypts the messageciphertext_Bob = encrypt(message, p, Key_mask_Alice)# Alice decrypts the messageplaintext_Alice = decrypt(ciphertext_Bob, p, Key_mask_Alice)# Alice decrypts the messageplaintext_Bob = decrypt(ciphertext_Alice, p, Key_mask_Bob)print("Alice to Bob: ")print(Public_Alice)print("Bob to Alice: ")print(Public_Bob)print("Result (Alice view):")print(plaintext_Alice)print("Result (Bob view):")print(plaintext_Bob)

输出结果：