ElGamal Encryption and Digital Signatures

encrypt.py

# ElGamal encryption

import random
from sympy import isprime, mod_inverse

# Generate a large prime number for the modulus (p)
def generate_large_prime(bits=256):
    while True:
        p = random.getrandbits(bits)
        if isprime(p):
            return p

# Generate the keys for ElGamal encryption
def generate_keys(bits=256):
    p = generate_large_prime(bits)
    g = random.randint(2, p - 1)
    x = random.randint(1, p - 2)  # Private key
    h = pow(g, x, p)  # Public key component
    return (p, g, h), x

# Encrypt a message using the ElGamal encryption scheme
def encrypt(public_key, plaintext):
    p, g, h = public_key
    y = random.randint(1, p - 2)
    c1 = pow(g, y, p)
    s = pow(h, y, p)
    c2 = (plaintext * s) % p
    return c1, c2

# Decrypt a ciphertext using the ElGamal encryption scheme
def decrypt(private_key, public_key, ciphertext):
    p, g, h = public_key
    x = private_key
    c1, c2 = ciphertext
    s = pow(c1, x, p)
    s_inv = mod_inverse(s, p)
    plaintext = (c2 * s_inv) % p
    return plaintext

# Example usage
if __name__ == "__main__":
    public_key, private_key = generate_keys()
    print("Public Key:", public_key)
    print("Private Key:", private_key)

    plaintext = 0x12345678
    print("Plaintext:", hex(plaintext))

    ciphertext = encrypt(public_key, plaintext)
    print("Ciphertext:", ciphertext)

    decrypted_plaintext = decrypt(private_key, public_key, ciphertext)
    print("Decrypted Plaintext:", hex(decrypted_plaintext))

signature.py

# ElGamal signatures

from sympy import isprime, randprime, gcd, mod_inverse
import random
import hashlib

def generate_prime(bits):
    return randprime(2**(bits-1), 2**bits)

def find_generator(p):
    for g in range(2, p):
        if pow(g, (p-1)//2, p) != 1:
            return g
    return None

def H(message, p):
    return int(hashlib.sha256(message).hexdigest(), 16) % (p-1)

tau = 256
p = generate_prime(tau)
g = find_generator(p)
alpha = random.randint(1, p-2)
y = pow(g, alpha, p)

public_key = (p, g, y, lambda m: H(m, p))
private_key = (p, g, alpha, lambda m: H(m, p))

def pick_k(p):
    k = random.randint(1, p-2)
    while gcd(k, p-1) != 1:
        k = random.randint(1, p-2)
    return k

def sign_message(m, private_key):
    p, g, alpha, H = private_key
    k = pick_k(p)
    r = pow(g, k, p)
    h_mr = H(m.encode() + str(r).encode())
    k_inv = mod_inverse(k, p-1)
    s = (k_inv * (h_mr - alpha * r)) % (p-1)
    return (r, s)

def verify_signature(m, signature, public_key):
    p, g, y, H = public_key
    r, s = signature
    if not (1 <= r < p):
        return False
    v = (pow(y, r, p) * pow(r, s, p)) % p
    h_mr = H(m.encode() + str(r).encode())
    if v == pow(g, h_mr, p):
        return True
    else:
        return False

def print_keys(public_key, private_key):
    p, g, y, _ = public_key
    _, _, alpha, _ = private_key
    print(f"Public Key:\np: {p}\ng: {g}\ny: {y}\n")
    print(f"Private Key:\np: {p}\ng: {g}\nalpha: {alpha}\n")

# Generate keys
public_key = (p, g, y, lambda m: H(m, p))
private_key = (p, g, alpha, lambda m: H(m, p))

# Print keys
print_keys(public_key, private_key)

# Sign and verify a message
message = "Hello, World!"
signature = sign_message(message, private_key)
is_valid = verify_signature(message, signature, public_key)
print(f"Signature valid: {is_valid}")
print(f"Signature: {signature}")