Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What are Digital Signatures
3.
ElGamal Signature Schemes
4.
Message Encryption Using ElGamal Algorithm
5.
ElGamal Operation
6.
ElGamal Code
6.1.
Output
7.
Frequently Asked Questions
7.1.
How does the ElGamal algorithm work?
7.2.
Can ElGamal signatures be forged?
7.3.
What is randomized encryption?
7.4.
What is the difference between RSA and ElGamal?
7.5.
Is ElGamal a public encryption system?
8.
Conclusion
Last Updated: Mar 27, 2024
Medium

What are ElGamal Signature Schemes?

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

While sending messages, sometimes you need to confirm their authenticity. But what if the message is sent digitally? Nowadays, there are several ways to sign your documents digitally. One of those ways is the ElGamal Signature Scheme. ElGamal signature scheme is generally less famous among users. But let us have a look at the potential of this signature scheme.

ElGamal signature schemes

What are Digital Signatures

Suppose you send a message to someone, and they want to verify the authenticity of that document. In such cases, users often use Digital Signatures. But there can be multiple ways to forge them, right? That's the catch here!

The messages being sent have two encryption keys- A public key and a private key. The public key is sharable to everyone.

Meanwhile, the private key is not sharable. If someone sends an encrypted message using the private key, it can be classified as a Digital Signature. Digital signatures help us verify the message's origin and the sender's and receiver's authenticity.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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= amod N
  • Take k and evaluate S1= ak mod N
  • Evaluate S2= 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 (S1, S2)

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

L= PS1S1S2 mod N

R= am 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()


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

Output

Encryption using Elgamal 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:

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

Happy coding!

Previous article
Security Requirements for Signature Schemes
Next article
Security of the ElGamal Signature Scheme
Live masterclass