22 ELGAMMAL Cryptosystem

Learning Objectives

• To know about Elgamal public key crypto system
• To Learn about the Elgamal Encryption process
• To Understand the key generation process
• Example to understand the Elgamal process

1. Introduction

In 1976, Whiteld Diffie and Martin Hellman proposed a paper where they proposed the thought of public key cryptography in which two diverse yet scientifically related keys are used-a public key and a private key. A public key frame-work is constructed to the point that configuring of one key (the ‘private key’) is computationally infeasible from the other (the ‘public key’), despite the fact that they are essentially related. Rather, both keys are produced secretly, as an interrelated pair.

Diffie and Hellman distributed the first public-key algorithm known as a “Diffie-Hellman key exchange” that year, at long last making exchange of the keys genuine and secure. Public key cryptographic algorithm here implies that sender encrypts with its receiver’s public key and receiver decode with its own private key. The purported public key cryptosystem utilizes distinctive keys as a part of encryption and decryption, which is a cryptosystem taking into account the infeasibility in count of decoding key from the known encryption key. Then, after Diffie-Hellman, one of the most well-known public key cryptographic algorithms came: the ElGamal Algorithm.

The ElGamal algorithm is used as a part of the free GNU Privacy Guard Software, late forms of PGP, and different cryptosystems. Additionally, the Digital Signature Algorithm (DSA) variant, in view of the ElGamal algorithm (called the ElGamal signature scheme), is used to sign digital documents. The ElGamal cryptosystem includes three major processes: the key generation, the encryption, and the decryption. Let us consider a chance to think about that as a sender called Alice needs to send a private message to the recipient Bob, and a third individual called Eve tries to know this message. The ElGamal PKC procedure works as follows: In the first step, Bob (Receiver) has to compute a public key and send it to the Alice(Sender).After receiving the Bob’s public key she do the Encryption, which comprises of computing the cipher text from the plaintext .She sends this ciphertext to Bob. Then Bob decrypts the cipher text to compute a plaintext using his private key.In this whole process, Eve(third person) could not be able to know the secret key because its security is based on solving the Discrete Logarithm Algorithm. So,ElGamal PKC is one of many algorithms that utilizes randomization in the encryption process.

2. ElGamal Cryptosystem

The ElGamal Algorithm provides an alternative to the RSA for public key encryption.

•  Security of the RSA depends on the (presumed) difficulty of factoring large integers.
•  Security of   the   ElGamal   algorithm   depends   on   the

(presumed) difficulty of computing discrete logs in a large prime modulus.

The encryption process requires two modular exponentiations. ElGamal has the disadvantage that the cipher text is twice as long as the plaintext. It has the advantage the same plaintext gives a different cipher text (with near certainty) each time it is encrypted.

Overall Process

In ElGamal, only the receiver needs to create a key in advance and publish it. As we discussed above, we will now follow Bob through his procedure of key generation. Bob will take the following steps to generate his key pair:

1- Generate a large random prime number (p)

2- Choose a generator number (a)

3- Choose an integer (x) less than (p-2) ,as secret number.

4-Compute (d) where     d= a^x mod p

5- Determine the public key (p, a, d) and the private key (x)

Receiver A must do the following:

1- Generate a large random prime number (p)

2- Choose a generator number (a)

3- Choose an integer (x) less than (p-2), as secret number.

4. Compute (d) where d= a^x mod p
5. Determine the public key (p, a, d) and the private key (x)

3 Encryption

To encrypt a message M to Bob, Alice first needs to obtain his public key triplet (p; g; gb) from a key server or by receiving it from him via unencrypted electronic mail. There is no security issue involved in this transmission, as the only secret part, b, sent in qb. Since the core assumption of the ElGamal cryptosystem says that it is infeasible to compute the discrete logarithm, this is safe. For the encryption of the plaintext message M, Alice has to follow these steps:

1 Obtain the public key (p , a , d ) from the receiver A.
2 Choose an integer k such that 1 < k < p-2
3 Represent the plaintext as an integer m where 0 < m < p-1.
4 compute (y) as follows y = ak mod p
5 Compute (z) as follows: z = (dk * m) mod p
6 Find the cipher text (C) as follows: C= ( y , z )
7 The sender B sends C to The receiver A

4. Decryption

After receiving the encrypted message C and the randomized public key gk, Bob has to use the encryption algorithm to be able to read the plaintext M. This algorithm can be divided in a few single steps:

Obtain the cipher text (C) from B.

2 compute (r) as follows:

r = y^p-1-x mod p

3 Recover the plaintext as follows:

m = ( r * z ) mod p

Let p = 11 and a generator number = 2 and select integer number x = 5

Calculate d = 2⁵ mod 11 = 10

Then

Public key = (11, 2, 10)

Private Key = (5)

5. Generator number

The following steps are to be executed to find whether the number a is generator or not?

1 (a) must be between 1 and p-1

2 Find Ø = p-1

3 Find the all factors of Ø {f1,f2,….,fn} – { 1 }

4 Find {q1,q2,…..,qn} where qi = fi for the redundant factors

qi = fifreq

5 (a) generator number if and only if wi= a ^Ø/qi mode p <> 1 , for all qi . For example let p= 11 , a=2 ,test a is generator number or not ? Solution:

Ø= p-1 = 10, factors of 10 = {2 , 5}

q1 = 2, q2 = 5

w1 = 210/2 mod 11 = 10 <> 1

w2 = 210/5 mod 11 = 4 <> 1  i.e. a generator number.

6. Applications

The ElGamal cryptosystem does not only support encryption and decryption, but also the electronically signing of messages M. A signature scheme has three main characteristics:

1. Creation

Alice needs to be able to find the signature for M by using her private key a. She will then send the message together with the signature as the pair (M,S) to Bob.

2. Verification

Bob has to be able to verify the signature by using the public key ga.The verification of the signature assures Bob that Alice has signed the message as he received it. It does not deliver information about if Alice wrote the message herself or if she intended to send it at all. The second information Bob can draw from the verification is that the message has not been altered on the transmission path between him and Alice.

3. Forgery prevention

It should not be possible for a malicious user to use the public key ga ofAlice to create a signature for an arbitrary message. A signature in the ElGamal

cryptosystem is the pair (r; s) with 0 r; s < p 1 designed by the equation gM (ga)r(r8)modp. The procedure of signing follows similar steps as the encryption procedure:

4. Choose random k 2 G
5. Compute r gkmodp
6. Fill the signature equation from above as gM gargksmodp and solve it for s using m ar + ksmod(p 1). This has a solution for s if k is Chosen such that gcd(k; p 1) = 1.Bob received (M, r, s) and wants to verify the signature now. For this, he only needs to compute both sides of the equation and check for equality.

Summary

–  Elgamal public key crypto system

–  Key generation using Elgamal

–  Check for a Generator

–  Elgamal Encryption process