At its core, RSA encryption is modular exponentiation. That is, given a message m, the encrypted form of m is

x = me mod n

where e is a publicly known exponent and n is a product of two large primes. The number n is made public but only the holder of the private key knows the factors of n, and without knowing the factors of n you can’t recover m from x, or so we assume.

You can implement RSA encryption in just a few lines of code as long as you have a way to work with very large integers.

In principle you could divide your message into segments each less than n and encrypt each segment. In practice, that would be inefficient. Instead, asymmetric (public key) cryptography is only used to exchange symmetric cryptography keys. So, for example, someone wishing to send you a long message would use RSA to share the AES key used to encrypt the rest of the transmission.

So RSA is used to transfer keys, but that’s not the whole story. As is often the case, the real world implementation of cryptography is more complicated than the mathematical core.

In 1993 RSA published its PKCS#1 standard specifying that messages should be padded a certain way. That was an improvement, but then in 1998, Daniel Bleichenbacher published what has become known as the “million message attack” against the PKCS#1 standard. There were multiple proposed fixes, but these were complicated and often implemented incorrectly.

Now the standard is RSA-OAEP (Optimal Asymmetric Encryption Padding) which combines the message with random bits before applying the RSA algorithm per se. So there’s a bit of symmetric encryption, before using asymmetric encryption to share symmetric encryption keys!

My point here is not to get into the details of the OAEP protocol, but only to point out that it’s not trivial. It is, however, secure in the sense that you can prove that if someone can break RSA-OAEP then they can break the core RSA algorithm too.

“Cryptography is a mixture of mathematics and muddle, and without the muddle the mathematics can be used against you.” — Ian Cassels

Related posts

Image above CC BY-SA 4.0 by Jm-lemmi

The post RSA encryption in practice first appeared on John D. Cook.

Previous Post
Next Post