Print

Principle of Elgamal encryption

Elgamal encryption is an encryption technique that follows logically from the Diffie-Hellman key exchange.  The big advantage of Elgamal encryption is its great simplicity and it has most of its utility when the clear text is rather short.  Elgamal encrypted messages are about twice as long as the clear text entropy.

The principle is the following: the person wanting to send a secret message (let's say, Alice) to another person (say, Bob), asks Bob to establish a D-H system, and to provide her with a permanent public key, exactly like in D-H key exchange.  Bob (the future receiver of the secret message) will have to generate only one key pair and send the public key to Alice.   Alice can also obtain Bob's public key from some or other key server, so there's no active role required from Bob if he has a public key somewhere.

On the other hand, Alice will have to generate a new key pair per message block.  The size of the block is determined by the size of the prime number in the basis of the D-H system.  For instance, if the D-H system is based upon a 2048 bit prime number, then the blocks will have to be somewhat smaller than 2048 bits.

For a block Bi, Alice will have to calculate a private key Si and a public key Pi.  She will calculate the common key with Bob and her key pair: Ki and she will encrypt the clear text block in the following way:

Ci = Bi . Ki mod p

This is the basis of the Elgamal encryption: one uses the product in the modular group p (the prime number of the D-H system that was chosen) with the common key as encryption.

Alice sends both the encrypted block Ci and the public key Pi to Bob.  Bob can calculate the common  key Ki between his (permanent) key pair and Alice's ephemeral key Pi and can easily decrypt the block:

Bi = Ci . (Ki)-1 mod p

There is hence a Diffie-Hellman key exchange per block.  It is important that Alice generates a new ephemeral key for each block, because otherwise, when an attacker gets hold of a single clear text, he can solve easily for the common key and decrypt all the other blocks encrypted with the same key.

Code

We would like to recall some generalities concerning Code examples

void elgamalencrypt(number* dhprime, number* key, number* cleartext, number* cypher)
/* given a common D-H key and its prime, a cleartext is encrypted with the Elgamal technique */
  {
  number oldmodulo;
  int i;

  /* we put the current modulus away and set the modulus to the D-H value */
  for (i = 0 ; i < nofdigits ; i++)
    {
    oldmodulo.digit[i] = modulo.digit[i];
    modulo.digit[i] = dhprime->digit[i];
    }

  timesnum(key,cleartext,cypher);

  /* we put the original modulo parameter back */
  for (i = 0 ; i < nofdigits ; i++)
    {
    modulo.digit[i] = oldmodulo.digit[i];
    }  
  }  // end elgamalencrypt

The Elgamal encryption consists simply in multiplying the clear text with the common key in the modular group.   The decryption consists in inverting the common key in the modular group, and then multiplying the cypher text with this inverted key:

void elgamaldecrypt(number* dhprime, number* key, number* cypher, number* cleartext)
/* given a common D-H key and its prime, a cleartext is encrypted with the Elgamal technique */
  {
  number oldmodulo;
  int i;
  number inversekey;

  /* we put the current modulus away and set the modulus to its maximum */
  for (i = 0 ; i < nofdigits ; i++)
    {
    oldmodulo.digit[i] = modulo.digit[i];
    modulo.digit[i] = dhprime->digit[i];
    }
  inversenum(key,&inversekey);
  timesnum(&inversekey,cypher,cleartext);

  /* we put the original modulo parameter back */
  for (i = 0 ; i < nofdigits ; i++)
    {
    modulo.digit[i] = oldmodulo.digit[i];
    }  
  }  // end elgamaldecrypt

/* ----------------------------------------------- */

Of course, all this is only valid after the establishment of a Diffie-Hellman key exchange in which a common key was established.