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

Be Sociable, Share!

Speak Your Mind


© 2013 David Zientara. All rights reserved. Privacy Policy