Up to now, we have seen how symmetric algorithms achieve encryption. For example, we’ve seen that RC4 is a simple but insecure stream cipher. We’ve also seen two block ciphers: The historically interesting DES cipher and the AES cipher, the current US standard. All these ciphers attempt to achieve the perfect forward secrecy of the One-Time Pad—that is, an incapability of being broken—with varying degrees of success.
We observed the major drawback for these symmetric ciphers is that the key must be exchanged somehow, which is bad since the key is used for both encryption and decryption. For example, if Bob wants to communicate securely with Alice using AES, then he must send his key to her. This exchange must take place over a secured channel, or Bob risks exposing his key to an attacker like Eve. This is a major security liability, and it’s costly in terms of time and resources. Ideally, we would like a cryptosystem that solves this key-exchange problem. Fortunately for us, we have asymmetric algorithms, also known as public-key encryption.
The Asymmetric Approach
The initial idea for asymmetric algorithms was developed by the British GCHQ in 1973, and it was independently developed by American academics in 1977. An asymmetric algorithm solves the key-exchange problem quite elegantly. Instead of establishing and exchanging one key, we establish two keys and exchange one. That is, we use a public key and a private key.
In our example, Bob uses his public key to encrypt his message. Since his encryption key is publicly available, it doesn’t matter how it is sent to Alice. In fact, it doesn’t really matter if Bob’s public key is intercepted by Eve—it’s public, after all. The important part is that Bob keeps his private key secret, for it’s this key that’s used to perform decryption. If Bob were to accidentally leak his private key, then Eve would be able to decrypt Alice and Bob’s messages. Hence, the security of an asymmetric system depends in large part upon the security of the private key. How can we guarantee the security of a private key?
There’s a mathematically intuitive, simple way to secure private keys. The idea is to use big integers—numbers on the order of hundreds of digits. The underlying reason is that computers are good at representing integers in terms of bits up to a certain point. Once we reach that threshold, it becomes much more difficult to represent larger integers. Worse, the larger the integer, the more complex the computations. This is all good news for Alice and Bob, but it’s bad news for Eve. And that’s exactly the way we want it.
How big is big enough? A standard size may be something on the order of 2048 bits, which would translate to just over 600 decimal digits. That’s pretty formidable given the limitations of today’s computing hardware and software. We could go further yet and use 4096 bits, which could represent numbers just over 1200 decimal digits in length.[1] Is this overkill? Perhaps, but it’s always better to be safe than sorry. The obvious assumption here is that there is no real maximum size to guarantee security, but the more bits there are in the key, then the better. The longer a key is, the more computational time and resources it will take to break.
The RSA Cryptosystem
The Rivest-Shamir-Adleman Cryptosystem (RSA) is the classical example of big-integer asymmetric algorithms. It was invented in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman of RSA Security.[2] Since then, the cipher has seen an explosion in popularity; it’s probably the most widely used public-key cryptosystem.[3] The beauty of RSA is its mathematical simplicity, as we can express the algorithm in just two equations.
Beauty is obviously in the eye of the beholder, but trust us when we say that RSA is a fairly simple cipher. While it’s based on some potentially “scary” mathematics, it’s actually pretty easy to use in practice. Once we get past the initial shock of the new mathematics, it all becomes fairly intuitive. For the mathematically faint-hearted, though, you may wish to skip the next two paragraphs, but we highly recommend coming back and reading them later. If you do try to power through, take comfort in the knowledge that there is an example not far below to help you on your way. If this is where we part ways, we’ll see you again soon. For the rest of us, let’s see how we can mathematically derive the components of the RSA cipher.
We start by choosing two large prime integers p and q.[4] We multiply p and q to compute another integer n. Next, we use Euler’s Totient Function to compute Φ(n) = (p-1)(q-1). We then choose an integer e that is less than Φ(n) such that e and Φ(n) have a greatest common divisor of one—that is, no numbers evenly divide both of them. Finally, we use the Extended Euclidean Algorithm to compute d * e ≡ 1 mod Φ(n). This gives us two integers e and d that are inverses modulo Φ(n).[5] The integers e and d are used in RSA encryption and decryption, respectively.
This key generation process gives us our public and private keys. Strictly speaking, the public key consists of the pair (e, n), and the private key is just d. The trick is to make sure the initial values p and q are sufficiently large. We come back to an important question, though: How big is big enough? If p and q are both 512 bits, then n will be 1024 bits.[6] That may seem large, but this size is easily breakable today. We should really choose p and q greater than 1024 bits each at bare minimum. This will give us an n of at least 2048 bits, which is fairly secure today, though not the best.[7] Supposing we do choose sufficiently large prime integers, how do we actually use RSA?
We’re ready to see what equations constitute RSA and how to use them. We suggested that RSA is simple to express mathematically. In fact, it can be described in just two equations. Suppose we have a plaintext message m. We can use our public key (e, n) to compute the ciphertext: c ≡ me mod n. We can then decrypt using the private key d to compute the plaintext: m ≡ cd mod n. Remember that the integers e and d are inverses—that is, we can use one to “undo” what we do with the other. We’ll use e for encryption, and we’ll use d to “undo” that encryption (i.e., decrypt). It’s really that easy.[8] Let’s see an example of RSA in action.
Suppose Alice wants to communicate with Bob, but she doesn’t want to hassle with symmetric key exchange. She can use RSA to compute public and private keys and send the public key to Bob. For the sake of example, we’ll use small numbers. In the real world, of course, we would use much larger numbers.
Let’s say Alice begins the process by choosing the primes p = 23 and q = 41. She computes n = 23 * 41 = 943 and Φ(943) = (23-1)(41-1) = 880. Next, she chooses any integer e such that 0 < e < Φ(n) and e and 880 are coprime. Let’s say she chooses e = 301. Remember that Alice needs to decrypt messages. Since Bob will use e to encrypt, she needs to use its inverse to “undo” that encryption (i.e., decrypt). Thus, Alice finally computes d such that d * e ≡ 1 mod 880, which gives her private key d = 421 . Alice now sends her public key (e,n) = (301,943) to Bob, who will use that public key to encrypt his message. Alice will use her private key d to decrypt Bob’s ciphertext.
Bob wants to encrypt his message “HELLO” using Alice’s public key. Since RSA is based on integers, Bob is going to encrypt the decimal equivalent of each character in his message.[9] So, instead of “HELLO”, he will encrypt the sequence {72, 69, 76, 76, 79}. Bob uses the equation to compute c ≡ me mod n each ciphertext value:
Bob sends the ciphertext sequence {564, 874, 129, 129, 741} to Alice. Supposing Bob’s ciphertext sequence arrives safely, Alice can decrypt it using her private key. She uses the equation m ≡ cd mod n to compute each plaintext value:
Thus, Alice has successfully decrypted Bob’s ciphertext sequence to retrieve his message “HELLO”. If someone like Eve were to intercept Bob’s ciphertext in transit, she would be totally incapable of decrypting it because she lacks Alice’s private key d. On the other hand, if Eve were to intercept Alice’s public key (e, n), then she could send encrypted messages to Alice, potentially posing as Bob.
Remember that the public key for RSA is the pair (e, n). If Eve has both of these, then she can easily compute d. Recall that Φ(n) = (p-1)(q-1). If Eve successfully factors n, then she will retrieve p and q. It’s then trivial for her to compute Φ(n). Since she has e and now Φ(n), she can compute d * e ≡ 1 mod Φ(n) to discover Alice’s private key d. Once Eve does this, she’s broken Alice and Bob’s encryption system forever (or until Alice changes the keys).
Security and Alternatives
The security of RSA depends almost exclusively upon the difficulty of integer prime factorization, especially for large integers. The simple fact is that it’s really hard to break a sufficiently large integer into its prime components. Why is this important?
It may seem like RSA is easily breakable and should be abandoned. Well, therein lies the beauty of RSA: We can make it securer by using ever-larger integers. In the early days, people were using small numbers of a hundred bits or so (approximately 30 decimal digits). Nowadays, it’s not uncommon for people to use integers upwards of 2048 bits or even 4096 bits. This moving-target approach is unsustainable, however.
Quantum computers are rapidly outpacing traditional computing hardware and software in terms of computational power. Advances in quantum computing designs will enable these machines to break today’s strongest encryption schemes in 10-20 years. These machines pose special threats to RSA, as quantum computers can easily solve computationally complex tasks like integer factorization using special algorithms. At some point, traditional computers will be unable to represent and handle excessively large integers. Then we’ll see the true demise of RSA.
Although the RSA cryptosystem may be threatened by quantum computers, it’s still strong against today’s hardware and software.[10] It allows users to exchange keys across an unsecured channel, but its approach makes it very vulnerable to attacks. In the next post, we’ll see how Diffie-Hellman Key Exchange and the ElGamal cryptosystem attempt to solve the asymmetric encryption problem without relying only on big integers.
[1] For perspective, the closest named number is a Quadringentillion, or 101203, which consists of 1204 decimal digits. That’s just over a googol to the twelfth power. In short, 1234 digits is a lot.
[2] You may remember that Ron Rivest is the inventor of the RC4 stream cipher.
[3] Better yet, the US patent on RSA lapsed in 2000. Anyone is now freely able to implement the system.
[4] You can see huge lists of primes at the University of Tennessee at Martin’s Prime Pages.
[5] We gloss over a lot of the underlying mathematics here, but the main point is that RSA is predicated on the difficulty of factoring sufficiently large prime integers. If you’re curious, the reason why this all works can be traced to Fermat’s Little Theorem and Euler’s Totient Theorem.
[6] Suppose we choose p and q such that they are both 512 bits. This means p and q are both 2512 in length. (Remember binary really means powers of two.) So, when we multiply, we have 2512 * 2512 = 2512+512 = 21024, which tells us the resulting number will be 1024 bits.
[7] Per convention, we typically refer to an RSA implementation by the size of the modulus n. So, if we have an n of size 2048, then we say we’re using RSA-2048.
[8] You may remember that all these integers are big integers. We can’t even fathom how difficult it is to perform exponentiation on integers with twenty digits, let alone hundreds of digits. Fortunately, we can use the Square and Multiply Algorithm to quickly compute these exponents.
[9] Very rarely would we encrypt a message directly like this. Usually we would use another cryptographic tool like a symmetric cipher or hash function to obscure the plaintext message. For example, we might encrypt our plaintext message using AES and then encrypt that ciphertext using RSA. This allows us to exploit the principles of confusion and diffusion, which provide an extra layer of security. The combination of symmetric and asymmetric algorithms is generally good practice.
[10] We won’t list them here, but there have existed public tools for a number of years that enable normal, off-the-shelf computers to break RSA keys relatively quickly.
