RSA, Diffie-Hellman, DSA: the pillars of asymmetric cryptography

The world of modern cryptography is built upon the concept of Asymmetric Encryption, and the pillars of Asymmetric Encryption are these three algorithms:  RSA, Diffie-Hellman, and DSA (Digital Signature Algorithm).

But unfortunately, there are many misconceptions about these algorithms, and about Asymmetric Cryptography itself. In this article, we’re going to look at each of these topics from a practical perspective.

What is Asymmetric Encryption?

Asymmetric Encryption is often described as merely “encrypting with a public key and decrypting with a private key”. Regrettably, however, that definition is woefully incomplete.

Asymmetric Encryption is a set of mathematical operations that can be performed with one key and verified or undone with another key.

This contrasts with Symmetric Encryption, which is a set of mathematical operations that can be performed and verified or undone with the same key.

That’s an important distinction, because of the three asymmetric algorithms (RSA, DH, and DSA), only one of them can “encrypt with one key and decrypt with the other key”.

In fact, some might even hesitate to use the term “Asymmetric Encryption” for these algorithms, and instead elect to use “Asymmetric Cryptosystem” – since again, only one of these algorithms involves actual “encryption”.

Terminology aside, Asymmetric Cryptosystems can be used for three purposes:  Encryption, Key Exchanges, and Signatures.

• The RSA Algorithm can do all three:  Encryption, Key Exchange, and Signatures.
• The Diffie-Hellman (DH) Algorithm can only be used as a Key Exchange.
• The Digital Signature Algorithm (DSA) can only be used for Signatures.

What is the RSA Algorithm?

The RSA algorithm creates a pair of “commutative” keys – two keys which allow you to “encrypt with one key, and decrypt with the other.”   (RSA is in fact the source of the somewhat incomplete definition for Asymmetric Encryption alluded to earlier)

The term “key” here simply means a numerical value. And the terms “encrypt” and “decrypt” simply represent an arithmetic formula.

What makes the keys “commutative” is that it works in either direction. Notice here, the Plaintext is encrypted with Key 2, and decrypted with Key 1.

The general strategy is to keep one of those keys to yourself and never share it. And give the other key out freely.

The key you give out freely, the Public Key, can be used by anyone to encrypt messages that only you can decrypt with the correlating key which you kept as your Private Key.

Of course, there are performance drawbacks for encrypting and decrypting with RSA keys, but those are negligible if the content you are encrypting and decrypting is small enough.

Apart from the evident use case of exchanging a (small) secret message, RSA can be used to generate Signatures and exchange Secret Keys. The process for either are outlined in this video:

RSA Math

But of course, the real magic of RSA is the actual math which makes it all possible.

If you’re anything like me, you were told that RSA can encrypt with one key and decrypt with the other. And while I understood that conceptually, I didn’t fully comprehend how it could be possible. At least, not until I saw the math myself.

To that end, I created a video which walks you through the actual RSA math:

What is the Diffie-Hellman algorithm?

To truly understand the Diffie-Hellman algorithm, you must first understand the problem it tries to solve.

In any sort of secure communication protocol (SSH, SSL, TLS, IPsec, etc…) the parties want to use Symmetric Encryption:

The critical difference between Symmetric encryption and the Asymmetric Encryption depicted above is Symmetric encryption uses identical keys for Encryption and Decryption.

The problem though, is if two people on either side of the Internet mean to communicate securely, how will they both come to agreement upon a matching secret key?

It almost creates a chicken or the egg problem: A Secret Key is needed so we can communicate securely, but we cannot exchange a Secret Key because we cannot communicate securely.

This problem is known as the key exchange problem, and the most common solution to this problem is the Diffie-Hellman Key Exchange.

Diffie-Hellman allows two parties to establish a shared secret over an unsecured medium.

With Diffie-Hellman, two parties can exchange certain public values, and then combine those with private values they never shared. The result is a third value, known only to the two parties. This third value is the Diffie-Hellman Shared Secret.

In the illustration above, the Green and Blue user exchange public values of 26 and 39, and use a private value (not displayed) to create the shared secret of 42. The red users who “heard” the conversation are unable to combine the public values to re-create the shared secret.

The math behind Diffie-Hellman is fascinating, and I encourage everyone to watch this video and try a few iterations on their own to really prove to yourself that it works as they say it does.

Generating Symmetric Keys with Diffie-Hellman

The result of the Diffie-Hellman Key Exchange is both parties have an identical Shared Secret.

However, the shared secret itself should not be used directly as a Symmetric Key. Instead, it should be used as a seed value, from which to derive any amount of required symmetric keys.

The math for Diffie-Hellman involves (relatively) expensive CPU operations. And often, secure communication protocols require multiple sets of keys, or choose to rotate keys periodically.

Using the Shared Secret as a Seed value allows you to generate as many symmetric keys as necessary without having to do the hard work of a new Diffie-Hellman exchange every time.

But beyond that, there is another reason you don’t want to use the DH shared secret as a Symmetric Key directly… and that has to do with the assurances that Diffie-Hellman grants:

Diffie-Hellman can only assure that the other side has the same secret as you.

Diffie-Hellman cannot provide any assurance as to who the other side is.

If someone can set themselves up in between the two parties in communication (also known as a Man in the Middle attack), they can perform the DH exchange on behalf of the other party:

In this illustration, the Red user is (maliciously) proxying the Diffie-Hellman exchange and performing DH on both sides with the Green and Blue users. The Green and Blue users now have different resulting Shared Secrets (31 and 78), and the Red user knows them both!

Therefore, the Shared Secret must be combined with values known only to the intended parties to create the final symmetric keys.

In this way, if someone is performing a MITM attack, they might intercept the Diffie-Hellman exchange, but they cannot create the final Symmetric Keys.

What is the Digital Signature Algorithm?

Which finally brings us to the Digital Signature Algorithm. As the name suggests, the DSA algorithm is merely a signature algorithm.

With DSA, there are no commutative keys, there is no encryption and decryption, and there is no possibility of a key exchange.

DSA can only be used for two operations:  Signature Generation and Signature Verification.

In simplistic terms, the DSA Signature Generation operation takes as input Data and a Private Key, and produces as output a Signature.

The DSA Signature Verification operation takes as take as input Data, a Public Key (correlating to the Private Key which created the Signature), and the Signature.

The output is either a 1 or a 0, indicating True or False. Meaning, yes, the Signature is valid, or No, the Signature is not valid.

If the Signature is valid, this proves the Integrity and Authentication of the Data. Integrity assures the data hasn’t been modified since it was signed, and Authentication assures we know who created and vouched for the data which was Signed.

The above is a simplistic illustration of the DSA operations. In reality, there are a few more values that are involved. I go into slightly more depth in this video:

The actual math of the DSA algorithm is similar in structure to the Diffie-Hellman algorithm. But DSA’s math is notably more complicated than that of DH or RSA.

Therefore, the video above doesn’t go into the actual DSA math. But, the video and explanation above is enough to give you a practical understanding of the DSA algorithm.

Wait… what about Elliptic Curves?

There is a concept that is notably missing from this article… the concept of Elliptic Curve Cryptography.

I have plans to create a dedicated article/video unpacking the concept of Elliptic Curves… but for now, I will provide a high level definition:

The asymmetric algorithms above (RSA, DH, DSA) use Real Numbers as their mathematical basis. Real numbers are the numbers you and I are most familiar with (1, 2, … 300, 301, …, 1001, 2002, etc…). 

Elliptic Curve Cryptography performs the same formulas as outlined above (RSA, DH, DSA), but uses points on an elliptic curve as their mathematical basis. This then creates what is known as ECRSA, ECDH, and ECDSA.

But we’ll unpack that in more detail in another article (and also answer why ECRSA is rarely encountered compared to ECDH and ECDSA).

Practical TLS

The purpose of explaining each of these algorithsm from a practical perspective is that they are all involved in securing today’s world of online communication. Namely, they are all involved with SSL and TLS — the protocols which secure the Internet.

If you’re looking for a comprehensive, deep dive into the SSL protocol, then look no further than my course: Practical TLS.

Related Posts:

Cryptography

Asymmetric Encryption

Confidentiality

Using Asymmetric Keys