Using python, how do I implement ElGamal system? Problem 1:Implement ElGamal systemYour code will accept prime p and a generator a. Then a user will pick either key generation (k),message signature (s) or message verification (v) option.Key generation: program will randomly pick a secret X, and output private and public key.Message signature: user will provide m. Program will use random k. You should use EEA tocomputer k-¹. Output (S₁, S₂). Instead of using H(m), just use m. So for us H(m)-m identity function.This will make computations slower as value of m can be large.Message verification: user provides all required information and program will decide if the signatureis valid.

In this question we have to write a python code for implementation of the ElGamal system, specifically focusing on key generation, message signing, and signature verification.The ElGamal system is a public-key cryptosystem that provides both encryption and digital signatures.Let's code and hope this helps, If you have any queries please utilize threaded question feature.Algorithm:1Function generate_key(p, g): 2 X = RandomNumber(2, p-2) 3 Y = (g ^ X) % p 4 Return X, Y 5 6Function sign_message(p, g, X, m): 7 k = RandomNumber(2, p-2) 8 while GCD(k, p-1) != 1: 9 k = RandomNumber(2, p-2) 10 11 r = (g ^ k) % p 12 k_inv = ModularInverse(k, p-1) 13 s = (k_inv * (m - X*r)) % (p-1) 14 Return r, s 15 16Function verify_signature(p, g, Y, m, r, s): 17 If r not in (1, ..., p-1) or s not in (1, ..., p-2): 18 Return False 19 20 v1 = (g ^ m) % p 21 v2 = (Y ^ r * r ^ s) % p 22 Return v1 == v2 23 24Function main(): 25 p = Input("Enter prime number (p): ") 26 g = Input("Enter generator (g): ") 27 X, Y = generate_key(p, g) 28 29 While True: 30 Print("Menu:") 31 Print("1. Key Generation") 32 Print("2. Message Signature") 33 Print("3. Message Verification") 34 Print("4. Exit") 35 36 option = Input("Choose option (1, 2, 3, 4): ") 37 38 If option == '1': 39 Print("Private Key (X):", X) 40 Print("Public Key (Y):", Y) 41 ElIf option == '2': 42 m = Input("Enter the message (m): ") 43 r, s = sign_message(p, g, X, m) 44 Print("Signature (S1, S2):", r, s) 45 ElIf option == '3': 46 m = Input("Enter the message (m): ") 47 r = Input("Enter the first part of the signature (S1): ") 48 s = Input("Enter the second part of the signature (S2): ") 49 If verify_signature(p, g, Y, m, r, s): 50 Print("Signature is valid.") 51 Else: 52 Print("Signature is not valid.") 53 ElIf option == '4': 54 Break 55 Else: 56 Print("Invalid option. Please choose again.")Explanation:Key Generation (generate_key):Randomly selects a private key X and computes the corresponding public key Y using the given prime p and generator g.Message Signature (sign_message):Randomly selects a temporary value k ensuring it is coprime to p-1.Computes the first part of the signature r and the second part s using the private key X, message m, and temporary value k.Message Verification (verify_signature):Checks if the provided signature (r, s) is within valid ranges.Computes two values v1 and v2 and compares them to verify the signature's validity.Menu-Based Interface (main):Takes user input for prime number p and generator g.Provides a menu for the user to choose between key generation, message signature, and message verification.Outputs the results based on the user's choice.Code:1from random import randint 2from sympy import mod_inverse 3import math 4 5def generate_key(p, g): 6 # Key generation 7 X = randint(2, p-2) 8 Y = pow(g, X, p) 9 return X, Y 10 11def sign_message(p, g, X, m): 12 # Message signature 13 k = randint(2, p-2) 14 15 # Ensure that k is coprime to p-1 16 while math.gcd(k, p-1) != 1: 17 k = randint(2, p-2) 18 19 r = pow(g, k, p) 20 k_inv = mod_inverse(k, p-1) 21 s = (k_inv * (m - X*r)) % (p-1) 22 return r, s 23 24 25def verify_signature(p, g, Y, m, r, s): 26 # Message verification 27 if not (0 < r < p) or not (0 < s < p-1): 28 return False 29 30 v1 = pow(g, m, p) 31 v2 = (pow(Y, r, p) * pow(r, s, p)) % p 32 33 return v1 == v2 34 35def main(): 36 p = int(input("Enter prime number (p): ")) 37 g = int(input("Enter generator (g): ")) 38 X, Y = generate_key(p, g) 39 40 while True: 41 print("\nMenu:") 42 print("1. Key Generation") 43 print("2. Message Signature") 44 print("3. Message Verification") 45 print("4. Exit") 46 47 option = input("Choose option (1, 2, 3, 4): ") 48 49 if option == '1': 50 print(f"\nPrivate Key (X): {X}") 51 print(f"Public Key (Y): {Y}") 52 elif option == '2': 53 m = int(input("Enter the message (m): ")) 54 r, s = sign_message(p, g, X, m) 55 print(f"Signature (S1, S2): ({r}, {s})") 56 elif option == '3': 57 m = int(input("Enter the message (m): ")) 58 r = int(input("Enter the first part of the signature (S1): ")) 59 s = int(input("Enter the second part of the signature (S2): ")) 60 if verify_signature(p, g, Y, m, r, s): 61 print("Signature is valid.") 62 else: 63 print("Signature is not valid.") 64 elif option == '4': 65 break 66 else: 67 print("Invalid option. Please choose again.") 68 69if __name__ == "__main__": 70 main()Output: