# How the ElGamal cryptosystem works ## How the ElGamal cryptosystem works

The ElGamal cryptosystem is making use of the discrete logarithm problem to make it secure, therefore it's fundamental to know what that is about.

## The discrete logarithm problem

The discrete logarithm problem is a numerical procedure that is hard to evaluate on one way and easy another. In the congruence , p is a large prime number and e is a primitive root mod p, or e at least has a high order. To find y when you know x, e, and p is easy. To find the exponent e when you know x, y and p is hard.

## ElGamal Cryptosystem

For the public key in the ElGamal cryptosystem, you choose a large prime number  and a primitive root , and a secret number  between 1 and . Then you calculate , and your public key consists of the integers  and . If someone wants to use your public key to send you an encrypted message m they first have to choose a number k between 1 and , and then compute  and . The ciphertext consists of the numbers  and .

Since , you can find the message m by using Euclid’s algorithm to find the inverse of , and then compute .

## ElGamal signature

To make sure the message is coming from the person you’re expecting it to come from, the other person can sign it. Suppose that the other persons public key depend on the numbers ,  and , where . The random number k should be chosen such that so the inverse I of  can be computed. The signed message consists of m, , and. These three numbers are encrypted with your public key. When you have decrypted the ciphertext, you can check if the signed message is valid by checking if the congruence holds.

Author ### Articles with similar tags Public-key Cryptosystem

Introduction to cryptography methods that uses a public key The Knapsack Problem

Introduction to the knapsack problem The Merkle-Hellman Knapsack Cipher

Introduction to the Merkle-Hellman Knapsack Cipher