Blog | RSA v/s Diffie-Hellman Algorithm...

RSA and the Diffie-Hellman are the two most popular encryption algorithms used during the Key Exchange phase of establishing a secured connection on the web.

In a nutshell, the Diffie Hellman algorithm generates a public and private key on both sides of the transaction, but only shares the public keys while generating the private keys.

On the other hand, the RSA algorithm requires the transfer of a public key generated beforehand. As long as the two communicating parties hold different parts of the public-private key pair, they can decrypt each other's encrypted messages.

RSA Algorithm:

RSA is an asymmetric cryptographic algorithm for public-key encryption widely used for encrypting sensitive data shared over an insecure network such as the Internet.

RSA was first described in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman of the Massachusetts Institute of Technology (MIT). RSA uses two different but mathematically linked keys, one public and one private. In general, the public key can be shared with everyone, whereas the private key is kept secret.

In the RSA Algorithm, both public and private keys can encrypt a message. The message encrypted by a public key can only be decrypted by the corresponding private key of the pair and vice versa. This attribute is one reason why RSA has become the most widely used asymmetric (both parties have different keys) algorithm.

RSA relies on the difficulty of factoring large integers that are the product of two large prime numbers for its security. Multiplying two large prime numbers is easy, but determining the original numbers from the resultant product is considered infeasible due to the computational power necessary for the task.

How does the RSA algorithm work?

Let the two parties trying to communicate, be Bob and Alice.

Alice generates her RSA keys by selecting two primes: p=53 and q=59. The resulting product, n=p×q=3127, is the first part of the public key.

We also need an exponent, say e with the following constraints:

1. e must be an integer

2. e must not be a factor of n

3. 1<e<ϕ(n) (where, ϕ(n) = (p−1)x(q−1))

In this example, ϕ(n)=(p−1)x(q−1) = 52*58 = 3016.

She chooses e = 3 for her RSA public key.

To calculate her RSA private key we need to use the extended Euclidean algorithm:

d = (2ϕ(n) + 1)/e = (2*3016 + 1)/3 = 2010.666... = 2011

Now,
Our public key is (n,e) = (3016,3)
And the private key is d = 2011

Bob wants to send Alice an encrypted message, M, so he obtains her RSA public key (n, e) which, in this example, is (3016,3).

His message is just the number 15 and is encrypted into C, as follows:
15^e mod n = 15^3 mod 3127 = 248 = C

When Alice receives Bob's message, she decrypts it by using her RSA private key (d, n) as follows:
C^d mod n = 248^2011 mod 3127 = 15 = M

Diffie-Hellman Algorithm:

Diffie-Hellman, also known as "exponential key exchange algorithm", is a method of digital encryption that uses numbers raised to specific powers to produce decryption keys using components that are never directly transmitted.

Diffie–Hellman Algorithm was published in 1976 by Whitfield Diffie and Martin Hellman. It is the earliest publicly known work that proposed the idea of a private key and a corresponding public key.

The Diffie–Hellman Algorithm establishes a shared secret between two parties that can be used for encrypted communication of data over a public network. The method by which this shared secret is established is what makes the algorithm special.

How does the Diffie-Hellman Algorithm work?
Let the two parties trying to communicate, be Bob and Alice.

Let's say the key Bob has decided to use is, k1 = 3
and a public key let's say, p = 5
and another number for mod let's say, m = 7.

So now Bob will send (5^3) mod 7, which evaluates to 6, along with the public key and modulo.

Alice gets the encrypted key ek1 = 6,
the public key p = 5
and the modulo number, m = 7.

Alice also has a secret key k2 = 2, which she returns using the same algorithm. (5^2) mod 7, which evaluates to ek2 = 4.

Finally, Alice will evaluate the final key (fk):
((ek1) ^ 2) mod 7
= (6^2) mod 7
= 36 mod 7
= 1

Similarly, Bob will also evaluate the final key (fk):
((ek2) ^ 3) mod 7
= (4^3) mod 7
= 64 mod 7
=1

Now that both Bob and Alice have the same key, they can send encrypted messages back and forth.

Conclusion

So which one is better? Well, that's a difficult question to answer.

RSA is susceptible to "low exponent", "common modulus" and "cycle attack". On the other hand, Diffie-Hellman is prone to "man in the middle" attack.

Although performance rarely matters, encryption with Diffie-Hellman is expensive compared to RSA.

As for security, Diffie-Hellman 1024 bits is much more robust than RSA. Moreover, it is easy to generate ephemeral keys for Diffie-Hellman compared to RSA, making it more secure.

The choice is up to you.

Stay tuned to Finocontrol for more exciting content. Feel free to ask your queries in the comments below.

credits

knowledgebooster