El Gamal and RSA Algorithms

El Gamal

In the previous article, we discussed the Diffie-Hellman algorithm. In this article, we will cover two more asymmetric encryption algorithms, El Gamal and RSA.

El Gamal Algorithm

The El Gamal algorithm is essentially an updated and extended version of the original Diffie-Hellman algorithm based on discrete logarithms. The security of the algorithm is roughly on par with that of the Rivest-Shamir-Adleman (RSA) algorithm. El Gamal has a few drawbacks, mainly its larger output and random input requirement. Encrypted El Gamal ciphertext is much longer than the original plaintext input, so it should not be used in places where bandwidth is a limiting factor, such as over slow wide area network (WAN) links. The El Gamal algorithm also requires a suitable source of randomness to function properly. It is worth noting that the Digital Signature Algorithm (DSA) was based on the El Gamal algorithm. DSA is a complementary protocol to RSA that is widely used in the OpenSSH implementation of the Secure Shell (SSH) protocol.

RSA Algorithm

Shortly after the appearance of the Diffie-Hellman algorithm, Ron Rivest, Adi Shamir and Leonard Adleman proposed another public key encryption system. Their proposal is now known as the RSA algorithm, named for the last initials of the researchers.

The RSA algorithm shares many similarities with the Diffie-Hellman algorithm in that RSA is also based on multiplying and factoring large integers. However, RSA is significantly faster than Diffie-Hellman, leading to a split in the asymmetric cryptography field that refers to Diffie-Hellman and similar algorithms as Public Key Distribution System (PKDS), and RSA and similar algorithm as Public Key Encryption (PKE). PRDS systems are used as session-key exchange mechanisms, while PKE systems are considered fast enough to encrypt small messages. However, PKE systems like RSA are not considered fast enough to encrypt large amounts of data such as entire file systems or high-speed communications lines.

RSA involves a public key and a private key. The public key can be known by everyone and is used for encrypting messages. Messages encrypted with the public key can only be decrypted in a reasonable amount of time using the private key. The keys for the RSA algorithm are generated the following way:

  1. Choose two distinct prime numbers p and q: For security purposes, the integers p and q should be chosen at random and should be of similar bit-length.
  2. Compute n = pq: n is used as the modulus for both the public and private keys; its length is the key length.
  3. Compute φ(n) = φ(p)φ(q) = (p-1)(q-1), where φ is Euler’s totient function.
  4. Choose an integer e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1; i.e. e and φ(n) are coprime.
  5. Determine d and d^-1 ≡ e(mod φ(n)), i.e., d is the multiplicative inverse of e (modulo φ(n)).

The public key consists of the modulus n and the public (or encryption) exponent e. The private key consists of the modulus n and the private (or decryption exponent d, which must be kept secret. p, q and φ(n) must also be kept secret because they can be used to calculate d.

External Links:

ElGamal encryption on Wikipedia

RSA on Wikipedia

Asymmetric Encryption

asymmetric encryptionThe biggest disadvantage to using symmetric encryption algorithms relates to key management. In order to ensure confidentiality of communication between two parties, each communicating pair needs to have a unique secret key. As the number of communicating pair needs to have a unique secret key, As the number of communicating pairs increases, there is a need to manage a number of keys related to the square of the communicators, which quickly becomes a complex problem.

Introducing Asymmetric Encryption

Asymmetric encryption algorithms were developed to overcome this limitation. Also known as public-key cryptography, these algorithms use two different keys to encrypt and decrypt information. If cleartext is encrypted with an entity’s public key, it can only be decrypted by the public key. The basic principle is that the public key can be freely distributed, while the private key must be held in strict confidence. The owner of the private key can encrypt cleartext to create cyphertext that can only be decoded with its public key, thus assuring the identity of the source, or it can use the private key to decrypt cyphertext encoded with its public key, assuring the confidentiality of the data. Although these keys are generated together and are mathematically related, the private key cannot be derived from the public key.

Instead of relying on the techniques of substitution and transportation that symmetric key cryptography uses, asymmetric encryption algorithms rely on the use of large-integer mathematics problems. Many of these problems are simple to do in one direction but difficult to do in the opposite direction. For example, it is easy to multiply two numbers together, but it is more difficult to factor them back into the original numbers, especially if the integers used contain hundreds of digits. Thus, in general, the security of asymmetric encryption algorithms is dependent not upon the feasibility of brute-force attacks, but the feasibility of performing difficult mathematical inverse operations and advances in mathematical theory that may propose new “shortcut” techniques.

Asymmetric encryption  is much slower than symmetric encryption. There are several reasons for this. First, it relies on exponentiation of both a secret and public exponent, as well as generation of a modulus. Computationally, exponentiation is a processor-intensive operation. Second, the keys used by asymmetric encryption algorithms are generally larger than those used by symmetric algorithms, because the most common asymmetric attack, factoring, is more efficient than the most common symmetric attack: brute force.

Because of this, asymmetric encryption algorithms are typically used only for encrypting small amounts of information. In subsequent articles, we will example different asymmetric algorithms, such as Diffie-Hellman, RSA, and El Gamal.

External Links:

Public-key cryptography at Wikipedia

© 2013 David Zientara. All rights reserved. Privacy Policy