Understand the RSA encryption algorithm

Hot on the heels of Diffie-Hellman upending the cryptography applecart in 1976 came three more crypto newcomers that further revolutionized the field: Ron Rivest, Adi Shamir, and Leonard Adleman. The trio devised a way to negotiate secure communication between unknown parties over distance, which turns out to be centrally important to the operations of the internet. The algorithm they came up with became known by their initials: RSA.

Rivest, Shamir, and Adleman were inspired by the Diffie-Hellman paper to conceive of a new but related way to achieve public key, or asymmetric, encryption. This article describes how RSA works at a practical level.

The RSA innovation

The RSA algorithm, along with Diffie-Hellman, stars in one of the more fascinating chapters of technology’s impact on society. Previously, secure communications was the exclusive domain of sovereign states or global corporations. This was due to the high cost of maintaining key infrastructure associated with symmetric algorithms. With the advent of Diffie-Hellman and RSA, secure communications between individuals became practicable. (And with the advent of PGP in the 1990’s, it became simple.)

Predictably, the security agencies of the U.S. government, led by the NSA, were in an uproar about this sudden explosion of unreadable communication. The battle between surveillance and privacy is ongoing, but the mathematical underpinning of algorithms like RSA means that small organizations and individuals have the power to secure their communications from prying eyes, even against state actors.

RSA vs. Diffie-Hellman

At the highest level, RSA works similar to Diffie-Hellman by exchanging public information that is then used to establish a secret key known only to the participants. The secret key is resistant to eavesdropping by virtue of a one-way function.

There are significant differences between the two algorithms in the details. For starters, in Diffie-Hellman, both parties exchange public key information and then arrive at a shared secret key. In RSA, one party generates a key pair, both the public key and the secret key, then the other party uses the public key to encrypt the communication. The private key is used to decrypt.

RSA in action

Let’s follow the RSA algorithm step by step, with an example. Let’s say Bob wants to send a private message to Alice. The first step is for Alice to generate the keys, both public and private. In step two, Alice provides the public key to Bob. In step three, Bob uses the public key to encrypt his message for Alice. In the fourth and final step, Alice decrypts the message with the private key.

Because Alice is the only person who has the private key, she is the only person who can read Bob’s message.

Generating RSA keys

The first step in generating an RSA key pair is to pick two large primes, p and q. We then multiply these large primes together to arrive at n.

In practice, p and q are very large primes indeed, as current best practices recommend arriving at a key size of at least 2048 bits, or 617 digits long. For demonstration purposes, we’ll use more modest numbers here.

Alice picks p = 41 and q = 53

It is significant that these are prime numbers, as the use of prime numbers ensures that certain characteristics are obtained with the following computations. The next thing Alice does is to arrive at the number n, which is the product of p * q. (As the product of two prime numbers, n is a semiprime.)

n = p * q = 2173

Note that p and q must be kept secret. However, n is part of the public key, so n can be distributed.

The Carmichael function

The next step is to arrive at a number, d, which will provide the private key. The trick is to find d using math that is easy for us who know p and q, but that will be very difficult for anyone who does not know p and q (despite their knowing the product of p and q, n).

This trick begins with computing the Carmichael function, which is written as λ(n), or lambda(n), for the number n. The Carmichael function is like a reduction of the Euler function φ, and it works very similarly. (In fact, in the original RSA paper, the Euler function was used.) The Carmichael function says: For every number between 1 and the argument n which is coprime to n, what is the smallest integer m that will satisfy the criteria 1 (mod n). In other words:

a^m = 1 (mod n)

Let’s unpack that a bit. First, two numbers are coprime if no integers besides 1 divide evenly into both numbers. In our case, the Carmichael function is scanning every integer between 1 and n that has no common factors with n except 1.

The Carmichael function asks what is the smallest number to which we can raise each of these coprimes, and get a result that when divided by n, leaves a remainder of 1. Remember, the mod operator returns the remainder of dividing by n.

Discovering the Carmichael function λ(n) for a very large number would be a very expensive operation, but we have a shortcut. Because n is the product of two primes, the Carmichael function can be found by finding the least common multiple (lcm) of n – 1 and p – 1:

λ(n) = lcm(n-1, p-1)

This is a non-obvious outcome, but is part of the result the RSA creators made use of. Our next step is to find that least common multiple:

λ(n) = lcm(n-1, p-1) = lcm(41-1, 53-1) = lcm(40, 52) = 520

This number is kept secret.

Now we will calculate e, the last step on our way to d. e is a number coprime with λ(n) that is less than λ(n) and greater than 1.

We can find a coprime for 520 by selecting a known prime and ensuring it’s not a divisor of 520, or we can use an algorithm. In this example, Alice uses e = 11.

Finally, we will obtain d by computing the following:

d ≡ e⁻¹ (mod λ(n))

Where the three-bar equals means modular congruence, which is to say that the two sides have the same remainder. In our example, Alice has the following equation for d:

d ≡ 11^-1 (mod 520)

Which we can rewrite as

1 = (11 * d) mod 520

Which is to say: What number, d, times 11, when divided by 520 leaves a remainder of 1? Solving for this, Alice arrives at

d = 331

d is the private key, while e is the public key, and n is the non-secret number used to derive both. The RSA algorithm works because, when n is sufficiently large, deriving d from a known e and n will be an impractically long calculation — unless we know p, in which case we can use the shortcut. This is why p and q must remain secret.

Let’s see how Alice and Bob use these numbers to encrypt and decrypt Bob’s secret message.

Encryption with RSA

In real-world usage, messages are padded for increased security. Also, it bears repeating that RSA (and Diffie-Hellman) are typically used to establish a shared secret, which is then used as the key for symmetric encryption, like AES. This is because of the limitations in speed and size implied by asymmetric encryption.

The caveats above are mentioned because Alice and Bob will be encrypting a number, not a message. Remember, Alice will use RSA only to exchange keys for a subsequent symmetric exchange with Bob.

Let’s say Bob’s number is 101, which he will send securely to Alice using the public key (n = 2173, e = 11). So Bob does the following:

cyphertext = message^e mod n = 101^11 mod 2173 = 1305

Bob sends 1305 to Alice.

Decryption with RSA

Alice receives Bob’s message and decrypts it with the private key (n = 2173, d = 331). So Alice does the following:

plaintext = cyphertext^d mod n = 1305^331 mod 2173

If you plug that equation into Wolfram Alpha, the result is Bob’s original number, 101.

Message signing with RSA

As you can see, RSA is more involved than Diffie-Hellman. It has different use cases. One of the interesting capabilities in RSA is the signing of messages. Simply put, digital signing allows for proof that a message came from the person holding the private key. This is possible because of a property of the RSA keys: An encrypted message hashed with the private key can only be decrypted with the corresponding public key.

In short, the ability to decrypt a hashed message with the public key proves definitively that the sender was in possession of the private key.

Diffie-Hellman and RSA are both feasts of genius, combining theoretical math and practical coding into working asymmetric cryptography. In the case of RSA, it is the trick of taking the p and q primes and turning them into numbers that can be broadcast, n and e, that makes the algorithm both practical and secure.

How secure? Best modern estimates are that a classic deterministic (non-quantum) computer would take around 300 trillion years to crack RSA-2048 (where n has 2048 bits). That’s pretty secure.