ElGamal Cryptosystem
The ElGamal cryptosystem was first discovered by Taher ElGamal in the year of 1984. It is based on Discrete Logarithm. When the discrete logarithm cannot find the assumption at the appropriate time, then we can take the help of the ElGamal cryptosystem. With the help of the inverse operation property, we can calculate the power of the ElGamal cryptosystem.
The original public key cryptography was suggested by Diffie and Hellman. Then discover this for calculating standard cipher keys for encryption and decryption. With the help of this cryptosystem, both parties can compute the common cipher key within the appropriate time period, and communication takes place between them very securely. So, ElGamal cryptosystem uses a random exponent "k" that simplifies the Diffie and Hellman public key cryptography. That random exponent replaces the private exponent for both the cryptosystem. Due to this simplicity of the ElGamal cryptosystem, the key is used in only one direction, without taking part of the other party.
Generation of Cipher key
As discussed above, the ElGamal cryptosystem needs at least only one cipher key for the encryption or decryption process. In the ElGamal cryptosystem, we can create a new cipher key with the help of one receiver. Let's take an example of the generation of necessary procedures.
Alex takes the following steps to generate the keys:
- Prime and group generation
First, Alex generates a sizeable prime number "p" and a generator "g" from the integer module "p".
- Selection of private key
Now, Alex needs to choose an integer "b" from the group "Z" and a constant 1 <b<p-2. That generated integer is known as a private integer.
- Assembling of Public key
By the formula gb mod p, we can calculate the public key. In the ElGamal cryptosystem, the public key Alex is (p,g,gb ), and "b" is his private key.
- Publishing of public key
Now, this generated public key should be published with the help of a key server so that Lucy can able to catch the public key.
Encryption Procedure
First, Lucy needs to catch her public key to encrypt a message "M" to Alex. She can generate her public key from a local key server via unencrypted electronic mail. As there is only one transmission, it occurs in a secret part, so there are no security issues arise during the whole transmission process. So the assumption of the ElGamal cryptosystem says that it is so infeasible to compute the value of a discrete logarithm. So this is safe.
To encrypt the message "M", Lucy needs to follow the below steps.
1. Obtain the public key
First, Lucy needs to obtain the essential public part (p,g,gb ) of Alex from an official and trusted vital server.
2. Prepare the message "M" for the encryption process
Write the message "M" as a series of integers (m1, m2, m3 …….) in a range of (1, 2,………., p-1). These messages are encoded one by one serially.
3. Selection of random exponent
In this step, Lucy will select an exponent "k" that is used in the generation of the private key for the second party s private exponent In the Diffie and Hellman key exchange algorithm. The unique feature of this secret key is its randomness, that difficult to guess by any third-party user.
4. Compute of public key
Lucy must compute gk mod p to transmit the random exponent "k" to Alex. Then she combined it with cipher text and sent this to Alex.
5. Encrypt the plain text
In this step, Lucy needs to encrypt her message" M" to cipher text "C". For this, she needs to calculate the value of Ci by the below formula.
Ci=mi * (gb)k
The value of cipher text" C" is set e.
The result of this encrypted message sends to Alex along with the public key and private key. Even if any third-party user listens to all the transmissions and then obtains the public key, they cannot access the message because of the discrete logarithm problem.
ElGamal always advises using a random key, "k" for every single message. Doing this helps to increase the security level of the transmitted message, and the encryption level also increases.
Then, we can calculate the m1 and m2 by the following formula.
M1/m2=c1/c2
Decryption Procedure
After knowing the value of the encrypted message "C" and the importance of randomized public key gk, Alex used the encryption details to decrypt the message to plain text "M". The decryption process takes the following steps. These are as follows:
1. Compute shared key
With the help of the ElGamal cryptosystem, Lucy is able to derive and share a private key without knowledge of Alex. This secret key is created by combining Alex's private key "b" and the random exponent "k" chosen by Lucy. We can calculate the shared key by the following equation.
(gk)p-1-b = (gk)-b = b-bk
2. Decryption
Alex can compute the plain text for each cipher text by the following formula.
Mi= (gk)-b * ci mod p
After combining the keys, we can send this message to Lucy.
ElGamal Signature
The ElGamal cryptosystem not only supports both encryption and decryption but also supports the electronic signature technique. The ElGamal signature has three main characteristics. These are as follows.
1. Creation
First, Lucy needs to discover the electronic signature of Alex by using Alex's private key. Then she can send a message to Alex by combining the signature pair with Alex.
2. Verification
Then Alex has to verify the electronic signature by using the Public key. The verification process ensured that Lucy received the Alex message. Another piece of information that Alex received from that verification is that the news has not tempered during the transmission process.
3. Prevention of forgery
With the help of the Elgamal signature, it is impossible to create a signature which is the same as Alex or Lucy's electronic signature.
The ElGamal cryptosystem is defined by the following equation.
gM =(ga)rrs mod p
The procedure of electronic signature is similar to the process of encryption.
- Choose the random value of "k", which belongs to G.
- Then compute the importance of "r" by the formula gk mod p.
ElGamal Summary
As has been shown, the ElGamal cryptosystem is as secure as it is hard to solve the
Discrete Logarithm problems, given no weak random exponents or primes, are chosen. It further prevents a chosen plaintext attack by using a randomized encryption exponent k. As this k is chosen uniformly before encryption, the same plaintext can result in p-1 different ciphertexts, one of which is uniformly selected by choosing a k. One shortcoming of ElGamal is the Message Expansion. The size of the transferred message increases by factor 2. This comes from choosing a new random k for each block of the plaintext message mi. The public key derived from this k has to be sent together with the ci as the pair (ci; gk), the set of all these pairs giving the ciphertext C. Another problem that can arise is that Lucy relies on the authenticity of the public key she retrieves from Alex. This is a lesser problem if the public key is handed over in direct contact, but using the system on a large network like the Internet, other means have to be found. The most common installation is a central keyserver. Users send their public keys after that generation so others can download them and use them for encryption or signature validation. If a malicious attacker manages to supply Lucy with her crucial and make him believe it is the key Alex, she will encrypt the message to the attacker and not to the intended receiver Alex. If the message is not signed, the attacker can then encrypt the message again, this time with Alex's key and send it to Alex. This is called the Man-In-The-Middle attack. At least the man in the middle would be detected if Lucy both signs and encrypt the message since Alex would notice the changed contents when verifying the signature. To overcome the problem of forged signatures, webs of thrust can be built up where users sign their keys against each other, thereby assuring the authenticity of the key. Another possibility is a central certification authority that signs or even gives out the keys only after validating the owner of the key.