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.

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= a^{x }mod N

Take k and evaluate S_{1}= a^{k} mod N

Evaluate S_{2}= 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_{1}, S_{2})

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

L= P^{S1}S_{1}^{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()

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: