What are ElGamal Signature Schemes?

ElGamal Signature Schemes

By now, you have a brief understanding of digital signatures. Taher ElGamal expressed the ElGamal signature scheme in 1985, but it is one of the lesser-used digital signature schemes. It is based on the premise of complex discrete logarithmic computation. We can apply the same signature scheme in actual documents and RSA. But, this scenario is different in the ElGamal signature scheme. Often, we need a specific signature for a particular document. So, ElGamal changes the key for every message. 

Despite this, it is not much used by users. The digital signature scheme (DSA) developed by the US NSA is used widely. DSA uses ElGamal Signature Scheme as its base algorithm.

Message Encryption Using ElGamal Algorithm

User2 must choose specific settings to commence the communication's encryption. User2 will also be required to select one of the cyclic group's p values. The cyclic group will be identical to that of the user1. The value should be chosen so that Inc passing with an in the specific function produces the result 1.

• User2 chooses an element k from cyclic group F such that gcd(x, y) = 1.
• She then computes p = gx and s = hx = gax.
• Then multiply s with M.
• Then she transmits (p, M*s) = (gx, M*s).

ElGamal Operation

Suppose Daphne and Simon want to communicate with each other and verify the sender's authenticity. Daphne will announce a public base ‘a’ and the public modulus ‘N.’

Simon wants to sign the message m. So, Daphne will:

• Take x and evaluate p= a^x  mod N
• Take k and evaluate S₁= a^k mod N
• Evaluate S₂= k^-1(m-S1x) mod ψ (N)
   

This shows us that for the message m, the encryption key by Daphne is p. So, her signed document is (S₁, S₂)

Now, if Simon wants to verify this, he will check the following:

L= P^S1S₁^S2 mod N

R= a^m mod N      

Now, if L=R checks out, the message is genuine.

ElGamal Code

Here is the ElGamal encryption algorithm in Java.

import random
from math import pow
 
a = random.randint(2, 10)
 
def calc_gcd(num1, num2):
    if num1 < num2:
        return calc_gcd(num2, num1)
    elif num1 % num2 == 0:
        return num2;
    else:
        return calc_gcd(num2, num1 % num2)

# Generating large random prime numbers
def generate_key(q):
 
    key = random.randint(pow(10, 20), q)
    while calc_gcd(q, key) != 1:
        key = random.randint(pow(10, 20), q)

    return key
 

def find_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
 
# Encryption Using Elgamal
def encrypt(msg, q, h, g):
 
    encrypted_msg = []

    # Private key for sender
    k = generate_key(q)
    s = find_power(h, k, q)
    p = find_power(g, k, q)
     
    for i in range(0, len(msg)):
        encrypted_msg.append(msg[i])

    for i in range(0, len(encrypted_msg)):
        encrypted_msg[i] = s * ord(encrypted_msg[i])

    return encrypted_msg, p

# Decryption using Elgamal
def decrypt(encrypted_msg, p, key, q):
 
    decrypted_msg = []
    h = find_power(p, key, q)
    for i in range(0, len(encrypted_msg)):
        decrypted_msg.append(chr(int(encrypted_msg[i]/h)))
         
    return decrypted_msg
 
# Driver code
def main():
    print("Enter Message to Encrypt:")
    msg = input()
    print("\nOriginal Message :", msg)

    q = random.randint(pow(10, 20), pow(10, 50))
    g = random.randint(2, q)

    # Private key for receiver
    key = generate_key(q)
    print("\nKey Generated: ", key)
    h = find_power(g, key, q)

    # Calling the Encrypt Function
    encrypted_msg, p = encrypt(msg, q, h, g)
    emsg = ''.join(map(str, encrypted_msg))
    print("\nEncrypted Message:", emsg)

    # Calling the Decrypt Function
    decrypted_msg = decrypt(encrypted_msg, p, key, q)
    dmsg = ''.join(decrypted_msg)
    print("\nDecrypted Message :", dmsg);
 
# Calling the driver code. 
main()

You can also try this code with Online Python Compiler

Run Code

The above code generates a random private and public key using the Python “random” function to perform the encryption and decryption function. 

Output

Frequently Asked Questions

How does the ElGamal algorithm work?

Public-key cryptography is used in ElGamal encryption. It encrypts the message and employs asymmetric key encryption for two-party communication.

Can ElGamal signatures be forged?

In rare circumstances, it is possible to fake ElGamal signatures without the secret key. By limiting the parameters that make a signature valid, the attacks can be prevented.

What is randomized encryption?

The randomization of the encrypted message is crucial for public key encryption. Because the encryptor chooses a random exponent as part of the encryption process, ElGamal is non-deterministic. 

What is the difference between RSA and ElGamal?

Both RSA and ElGamal employ asymmetric key strategies. The number of variables employed makes a fundamental difference. While ElGamal employs three variables for encryption, RSA only uses two.

Is ElGamal a public encryption system?

Taher Elgamal created the ElGamal encryption system, a public key encryption technique, in 1985. It is based on the Diffie-Hellman key exchange.

Conclusion

In this article, we discussed what digital signatures are. We also learned what ElGamal signature schemes are, along with their encryption algorithms. To learn more about how the ElGamal signature schemes work, refer to the articles below:

• Security of the ElGamal Signature Scheme
• Cryptanalysis of Substitution Cipher
• What is Cryptography?
• Public Key Cryptography
• Cryptanalysis of Hill Cipher
• RSA Signature Scheme in Cryptography
   

Also, check out some of the Guided Paths, Contests, Interview Preparation, and many more on Coding Ninjas Studio.

Happy coding!