The Internet Chronicles – Part 9 of 12: RSA and Prime Numbers

Andrei Mihai

We take it for granted nowadays, but the internet is one of the most impactful inventions of modern times – possibly even of all time. But how did it all start? The story of the internet is a fascinating journey through the minds of visionary thinkers and relentless innovators, many of them coming from mathematics and computer science. In this 12-part series, we will dive into some of the stories and contributions of the trailblazers who laid the foundations for the interconnected world we live in today.

Previously, we looked at the rebels who brought encryption out of the shadows. Whitfield Diffie and Martin Hellman showed that two people could establish a shared secret over an insecure channel. It was a revolutionary idea, but it was not the end of the story. The internet still needed a way for anyone to send a secret message to anyone else without first agreeing on a shared secret. It needed a way to sign digital documents and prove identity; a lock that could be made public without giving away the key. That lock was RSA.

A Special Algorithm

The story of RSA starts with three researchers at MIT: Ron Rivest, Adi Shamir, and Leonard Adleman. Their last name initials make up the “RSA.” The trio was inspired by the work of Diffie and Hellman, who had proposed the concept of public-key cryptography but had not yet provided a general-purpose encryption system that could do everything the idea promised.

The three of them must have felt like they were hitting a brick wall.

They had spent roughly a year searching for a function that would be easy to compute in one direction but hard to reverse. Rivest and Shamir, both computer scientists, kept proposing candidates. Adleman, as a mathematician, kept breaking them. They explored approaches based on knapsacks and permutation polynomials, but nothing seemed to work. It almost seemed contradictory: The function had to be public enough for anyone to use, but private enough that only one person could reverse it.

Then came one night in April 1977 that would change the course of the internet, and possibly the world. The three spent Passover dinner at a student’s house and consumed “liberal quantities of wine” before returning to their respective homes at around 12 in the night. Rivest went home and could not sleep. He lay on his couch with a mathematics textbook and returned to the problem, but tried a different approach.

By morning, he had worked out the core of the idea and drafted much of what would become the RSA paper.

A Prime Revelation

Suppose Alice wants people to send secret messages. In traditional cryptography, she would first need to share a secret key with each person. That secret key would both lock and unlock the message. But sharing the key securely was the whole problem. Anyone who intercepted the key could read the messages.

RSA reversed the arrangement. Alice could publish a public key that anyone could use to encrypt messages. But only Alice, who had the private key, could decrypt them. It is a bit like taking a padlock and bringing it to the public. Anyone can see or touch it, but only Alice has the key to open it again.

The trick came from number theory. RSA relies on the fact that multiplying two very large prime numbers is easy, while factoring their product back into those two primes is much more difficult. If you take two very large prime numbers (p and q) and multiply them, this number n = p × q becomes part of the public key. Everyone is allowed to see it.

But given only this n number, an attacker would need to recover both p and q. For small numbers, this is trivial. If n = 33, we can quickly see that 33 = 3 × 11. But if n is a 2,048-bit number, the two prime factors are so large that there is no known classical algorithm that can recover them efficiently. The best factoring methods can do much better than trial division, but they still become infeasible at properly chosen key sizes.

This is, of course, a simplified version. In the original RSA paper, they used something called Euler’s totient function: φ(n) = (p − 1)(q − 1). Subsequent RSA algorithms, including the ones used routinely in today’s internet, use several elegant improvements.

Yet prime numbers remain a key part of RSA.

The primes must be large, random, and not too close together. They must not be reused across keys and must also pass strong primality tests. If the primes are poorly chosen, the entire private key can be reconstructed with much more ease. In that case, RSA does not fail because the mathematics is wrong, but rather because the “hard” problem can be made easier.

Ultimately, though, RSA is not based simply on large prime numbers. It is based on the gap between the difficulty of multiplication and factorization. RSA turns that gap into a cryptographic mechanism. This is the one-way function.

A More Rigorous Approach

RSA gave the internet a practical public lock, but it also exposed a deeper, fundamental problem: Encryption was not properly defined. What does it actually mean for an encryption scheme to be secure? What does it mean for the prime numbers to be “too close”?

This may sound like a philosophical question, but it has very practical components.

Early public-key cryptography often had an empirical component. A system was considered secure if no one knew how to break it. That was useful and excellent for the early days of the internet, but it had obvious limitations. Computers were, even in those early days, getting much more powerful. How could computer scientists know their systems would withstand attacks?

There was another problem: Encryption was deterministic. If you encrypted the same word twice with the same key, you’d get the same result. This allowed attackers to spot patterns or try clever ways to hack systems.

This is when Shafrira Goldwasser comes in.

Working with Silvio Micali UC Berkeley in the early 1980s, Goldwasser pushed cryptography toward a more rigorous standard. Security should not just mean that a message is hard to decrypt. It should mean that an attacker cannot learn anything useful from the ciphertext at all.

This seemingly subtle change was actually profound. Suppose an attacker cannot recover the whole message but can still learn whether a payment is large or small, or whether two encrypted messages contain the same text. In many real systems, that is already a serious failure. So Goldwasser and Micali asked cryptography to satisfy a much stronger requirement. An encrypted message should reveal no partial information about the plaintext, beyond what the attacker already knew before seeing it.

Along with Micali, she introduced probabilistic encryption. In essence, this injects a bit of randomness into the RSA algorithm. For every encryption operation, the sender’s computer generates a fresh, unique random bitstring. This randomness is mathematically combined with the plaintext message before or during the encryption process.

Modern encryption uses these randomized padding schemes to prevent simple comparison attacks and thus makes RSA more resilient in the face of attacks.

But Goldwasser’s most famous contribution may be even more counterintuitive than probabilistic encryption. With Silvio Micali and Charles Rackoff, she introduced zero-knowledge proofs. These are protocols in which one party, the prover, convinces another party, the verifier, that a statement is true without revealing anything beyond the truth of that statement. We will not get into the details of how this works here, but it is a topic often discussed by laureates at the Heidelberg Laureate Forum, an annual event that brings together recipients of the most prestigious prizes in mathematics and computer science with the next generation of young researchers. While zero-knowledge proofs are still not universally used, they have their applications, most notably in blockchains.

The Internet as a Verification Machine

RSA turned public-key cryptography into a practical tool, essentially providing the internet a way to authenticate, sign, encrypt, and transact. Every day, computers check whether that is really your bank, your email, your password, and so on. This is how we ensure that certificates can be trusted and users should be allowed to access files.

In a curious turn of events, just as with Diffie and Hellman’s work, this public version was not quite the first. In 1973, Clifford Cocks, a mathematician at Britain’s GCHQ, had described a strikingly similar system in a classified internal document. But his work stayed hidden inside the intelligence world until 1997. Instead, RSA became the version that changed the internet because it was published, shared, tested, and eventually built into the open machinery of digital life.

Ron Rivest, Adi Shamir, and Leonard Adleman received the 2002 ACM A.M. Turing Award for their role in creating RSA public-key cryptography. Shafi Goldwasser received the 2012 ACM A.M. Turing Award, together with Silvio Micali, for transformative work in cryptography.

Yet a shadow is starting to loom over the decades-long success of RSA. That shadow is quantum computing.

A sufficiently powerful quantum computer running Shor’s algorithm could factor large numbers efficiently. That would break RSA and other systems based on similar number-theoretic problems. Such a machine does not yet exist at the required scale, but the threat is serious enough that governments, companies, and standards bodies are already preparing for post-quantum cryptography.

This does not mean RSA is done. Far from it. RSA secured the internet through some of its most important decades, and it has a lot of work left to do. It made digital commerce possible and shaped online trust. But cryptography is not something you can finish.

Every cryptographic system rests on assumptions about what attackers can compute. When computation changes, those assumptions must be revisited. The move toward post-quantum systems is part of the same story that began with RSA and continued with Goldwasser: Security is not a product. It is a process.

The post The Internet Chronicles – Part 9 of 12: RSA and Prime Numbers originally appeared on the HLFF SciLogs blog.