What is RSA? How does it work?

RSA is a cryptosystem for secure data transfer over the net. The acronym comes from the surnames of Ron Rivest, Adi Shamir, and Leonard Adleman, who published it in 1977. As with all great creations, there was a little bit of wine involved in the making of this.

RSA is not the encryption itself but it refers to the algorithm that creates the keys needed for encryption. RSA algorithm creates a pair of keys. They are respectfully called Public Key and Private Key. As the name suggests, one of these keys is publicly distributed and the other one is kept private.

All data traffic coming towards the RSA user must be encrypted with Public Key. The user then decrypts the message with their Private Key to uncover the message. Since the message is encrypted at the source, any third-party listeners will only see the encrypted message is transmitted over the network and will not be able to eavesdrop. Only the end-user who has the Private Key can know the contents of the message.

The encryption and decryption of keys rely on modular arithmetic. And the simple mathematical formula that validates this is:

message ^ (Public Key * Private Key) = message (mod N)

We will learn how to compute everything in this formula.

To compute the keys we first need to find two big prime numbers, let’s call them p and q. For these two primes to be viable we must also ensure that (p-1) and (q-1) don’t have a big mutual prime number divider. Ideally nothing other than 2 as the mutual divider. p and q will be close in magnitude but have to have at least two digits difference between them for safety. Both primes are kept secret.

For the next step, we need to calculate the N number which is the modulus we use. N is simply the multiplication of primes.

N = p * q

Now we will compute λ(N), where λ is Carmichael’s totient function. Since N = p*q, λ(N) = lcm( λ(p), λ(q) ), and since p and q are prime, λ(p) = φ(p) = p − 1 and likewise λ(q) = q − 1. Hence λ(N) = lcm(p − 1, q − 1). λ(N) will be kept secret too.

We can now select an E number that validates 1 < E < λ(N). This will be our Public Key and it is usually chosen 2¹⁶ + 1 = 65537 for simplicity. A default key-value helps to mask the numbers we are keeping secret and we also do not want to make it so big that encryption takes too long.

Now we have a Public Key. What about the Private Key? We will calculate it, and we only have to do it once.

The Private Key D that complements Public Key E must validate

E*D = 1 (mod (λ(N)) )

so that

message ^ (E * D) = message (mod N)

holds true. D is called the modular multiplicative inverse of E modulo λ(N). One of the efficient ways of computing D is the Extended Euclidean algorithm.

Finally, we end up with Public Key E, modulus N, and Private Key D. Now we can distribute (N, E) as our public key through not necessarily a secret or secure connection and ask everyone in the network to encrypt every message before they send it. In return, we will decrypt every message we receive.

One question that may arise is: «If everybody is using the same default Public Key, then how do we validate any single person in the network?». Thankfully the operands in multiplication are interchangeable and keys are complementary, so defining message as M we can validate:

(M ^ E) ^ D = M ^ (E * D) = M ^ (D * E) = (M ^ D) ^ E

and show that any message encrypted by Public Key and can be decrypted by Private Key can also be encrypted by Private Key and decrypted by Public Key.

Now, why do we want this? Because we are the only one who knows the Private Key. If we encrypt a message with our Private Key anyone who decrypts the message with our Public Key will know that we are most likely the owner of the Private Key complement of that Public Key. In short, we are who we say we are.

A second question: «What message can we encrypt that everyone in the network already knows and can verify?». The answer is simple, our Public Key! We have distributed our Public Key to everyone in the network. So now, we can take our Public Key as the message and encrypt it with our Private Key and send out that encrypted message to everyone in the network. And everyone in the network can decrypt it using our Public Key and uncover that message was our Public Key all along.

For further reading and to learn about how it is already being used in our everyday lives, refer to the next blog post.