ElGamal#
The ElGamal class implements the ElGamal public-key encryption algorithm, whose security is based on the difficulty of solving the Discrete Logarithm problem in a finite field.
- class ElGamal#
Creates a new ElGamal instance.
Introduction#
The ElGamal encryption algorithm is a public-key cryptosystem based on the Diffie-Hellman key exchange. It provides a high level of security for data transmission by utilizing asymmetric encryption. The algorithm uses modular arithmetic and relies on the difficulty of the discrete logarithm problem. The ElGamal encryption scheme consists of three main components: key generation, encryption, and decryption.
Mathematical Details#
ElGamal Key Generation#
The ElGamal key generation process involves the following steps:
Choose a large prime number: A large prime number \(p\) is selected.
Select a generator: A primitive root \(g\) (generator) modulo \(p\) is computed.
Choose a private key: A private key \(x\) is selected randomly from the range [1, p-2].
Compute the public key: The public key \(h\) is computed as:
The public key is then the pair \((p, g, h)\), and the private key is \((p, g, x)\).
ElGamal Encryption/Decryption Process#
Encryption: The plaintext message, \(m\), is encrypted using the public key \((p, g, h)\) as follows:
Select a random value \(k\) from the range [1, p-2].
Compute the ciphertext components \(c_1\) and \(c_2\):
\begin{gather*} c_1 = g^k \mod p\\ c_2 = m \cdot h^k \mod p \end{gather*}The ciphertext is then the pair \((c_1, c_2)\).
Decryption: The ciphertext \((c_1, c_2)\) is decrypted using the private key \((p, g, x)\) as follows:
\[m = c_2 \cdot (c_1^x)^{-1} \mod p\]which can be also done as:
\[m = c_2 \cdot (c_1^x)^{p-1-x} \mod p\]
ElGamal Signing/Verification Process#
Signature: The hash of the plaintext message, \(m_h\), is signed using the private key \(x\) as follows:
\begin{gather*} s_1 = g^k \mod p\\ s_2 = (k^{-1} \cdot (m_h - x \cdot s_1)) \mod (p-1) \end{gather*}The signature is the pair \((s_1, s_2)\).
Verification: The signature \((s_1, s_2)\) for a message \(m\) with hash \(m_h\), is verified using the public key \((p, g, h)\) as follows:
\begin{gather*} v_1 = g^{m_h} \mod p\\ v_2 = h^{s_1} \cdot s_1^{s_2} \mod p. \end{gather*}The result of the verification is given by:
\[v_1 \stackrel{?}{=} v_2\]
Usage#
# Example usage of ElGamal to encrypt and decrypt a message
from cryptosystems import ElGamal
cipher = ElGamal()
public_key, private_key = cipher.generate_keys() # Generate ElGamal keys
ciphertext = cipher.encrypt("Hello World", public_key)
print(ciphertext) # (123456, 654321)
plaintext = cipher.decrypt(ciphertext, private_key, "str")
print(plaintext) # 'Hello World'
signature, message_hash = cipher.sign("plaintext", private_key)
print(signature, message_hash, sep=", ") # (123456, 654321), b'\x12\x34\x56\x78\x90'
verification = cipher.verify(signature, message_hash, public_key)
print(verification) # True
Methods#
- generate_keypair() tuple#
Generates a new ElGamal key pair, in the form \(((p, g, h), (p, g, x))\).
- Returns:
A tuple containing the public key and private key.
- Return type:
- encrypt(plaintext: int | str | bytes, public_key: tuple) tuple#
Encrypts the given plaintext using the ElGamal algorithm and returns the ciphertext.
- decrypt(ciphertext: tuple, private_key: tuple, return_type: str)#
Decrypts the given ciphertext using the ElGamal algorithm and return the deciphered plaintext.
- Parameters:
ciphertext (tuple) – The ciphertext message to be decrypted, in the form \((c_1, c_2)\).
private_key (tuple) – The private key used for decryption, in the form \((p, g, x)\).
return_type (str) – The type in which plaintext is to be returned. It should be either ‘int’, ‘str’, or ‘bytes’. Default is ‘int’
- Returns:
The decrypted plaintext.
- Return type:
- sign(message: int | str | bytes, private_key: tuple) tuple#
Signs the given message using the ElGamal Algorithm and returns the signature and SHA256 hash.
- Parameters:
- Returns:
The tuple of signature for the message, in the form \((s_1, s_2)\), and the SHA256 hash (bytes) of the message.
- Return type: