RSA: Building a Public Key from Secret Ingredients

Some things are easy to do and very hard to undo. Stirring two spoonfuls of paint together takes a second; separating them again is close to impossible. RSA, one of the oldest and most widely used tools for keeping information private online, is built on a mathematical version of that kitchen trick. It lets you publish a set of numbers that anyone can use to lock a message for you, while only you can unlock it. Most explanations stop at that promise. This one opens the box. We will build a complete, working RSA key pair from two small secret numbers, lock and unlock a real message with it, and see exactly which number does which job. The numbers will be tiny on purpose, small enough to check on a phone calculator, so nothing is hidden behind the word 'mathematics'. By the end you will know what the public key really contains, why the private key works, where the protection actually comes from, and why nobody uses the simple version you are about to build without extra safety layers.

The puzzle RSA was invented to solve

Imagine you want a stranger to send you a private note, but every message between you passes through other people's hands. If you and the stranger had met before and agreed on a secret code, the problem would be easy. You haven't. Anything you send to set up a code can be read on the way, so the code itself would leak.

For most of history there was no good answer to this. Secret codes, called ciphers, needed both sides to share the same secret beforehand. In the 1970s researchers found a way around it. In 1977 three researchers at the Massachusetts Institute of Technology, Ron Rivest, Adi Shamir and Leonard Adleman, described a scheme now named after their initials: RSA. Their paper appeared in 1978 and it is still used today.

RSA splits the secret into two halves that do different jobs. The public key is a pair of numbers you can hand to anyone, print on a website, or attach to an email. Anyone can use it to scramble a message, a step called encryption, and the scrambled result is called ciphertext. The private key is a number you keep to yourself, and it is the only practical way to unscramble that ciphertext again, a step called decryption.

That sounds like magic until you see the parts. The rest of this article builds those parts one at a time. We need only three ideas: arithmetic that wraps around like a clock, prime numbers, and the difference between multiplying numbers and splitting them apart again.

Arithmetic that wraps around like a clock

Look at an ordinary twelve-hour clock. If it is 9 o'clock and you add 8 hours, you don't say it is 17 o'clock. You say it is 5 o'clock. The clock wrapped around after 12 and kept counting from the start. Mathematicians call this modular arithmetic, which simply means arithmetic where numbers wrap around after reaching a chosen size. The chosen size is called the modulus. On a clock, the modulus is 12.

There is an easy way to find where you land: divide by the modulus and keep only the remainder. Seventeen divided by twelve is one, with five left over, so 17 wraps to 5. People write this as '17 mod 12 equals 5', and you can read 'mod' as 'wrap around at'.

RSA uses exactly this kind of arithmetic, just with a strange-sized clock. In our example the clock will have 55 positions, numbered 0 to 54. To find where 343 lands on that clock, divide 343 by 55. Fifty-five fits in six times, which is 330, and 13 is left over. So 343 wraps to 13. That is all '343 mod 55 equals 13' means.

Why does wrapping matter so much? Because it scrambles the trail. On an ordinary number line, if you know that a number multiplied by itself three times gives 343, you can work backwards to 7 easily. Once the answer has been wrapped around a clock, you only see where it landed, not how many times it went around. Many different starting numbers could have landed on 13. That loss of information is the first ingredient of RSA's protection.

The secret ingredients: two prime numbers

A prime number is a whole number bigger than 1 that can only be divided evenly by 1 and by itself. Five is prime, because nothing except 1 and 5 divides it evenly. Eleven is prime. Twelve is not, because 2, 3, 4 and 6 all divide it. Primes are the building blocks of every whole number: each number can be written as primes multiplied together in exactly one way.

Building an RSA key starts with choosing two different prime numbers and keeping them secret. Mathematicians usually call them p and q. For our example we pick p = 5 and q = 11. Real keys use primes hundreds of digits long, chosen at random by a computer, but small primes let us see every step.

Next we multiply them: 5 times 11 is 55. This product is called the modulus, written n, and it is the size of the clock we just met. Here is the key point of the whole scheme: n goes into the public key, but p and q do not. Everyone gets to see 55. Nobody else is told that it came from 5 and 11.

With numbers this small, anyone could guess 5 and 11 in a moment. That is fine for learning. The protection in real RSA comes from a stubborn fact about scale. Multiplying two large primes takes a computer a tiny fraction of a second. Going the other way, starting from the product and finding the two primes, is called factoring, and for well-chosen numbers hundreds of digits long the best methods known on ordinary computers would take far longer than anyone could wait. Easy to stir together, very hard to separate: that is the one-way kitchen trick from the opening, written in numbers.

It helps to see the key as layers of secrecy, from the numbers the whole world sees down to the ones that must never leave your hands. The next sections fill in the layers that are still empty.

Choosing the two exponents

Locking and unlocking in RSA are both done by raising a number to a power, which means multiplying it by itself a certain number of times, then wrapping around the clock. The number of times is called the exponent. RSA needs two exponents: a public one for locking, written e, and a private one for unlocking, written d. Choosing them is where the secret primes earn their keep.

First we use the primes to compute a hidden number that describes how our 55-position clock behaves. Subtract one from each prime and multiply: (5 minus 1) times (11 minus 1) is 4 times 10, which is 40. Think of 40 as the clock's hidden cycle length. It controls when repeated multiplication comes back around to where it started. It is easy to calculate if you know 5 and 11, and hard to calculate if all you know is 55. Hold on to that thought; it is the heart of the security.

Now we pick the public exponent e. The rule is that e must share no common factor with 40, other than 1. We can't use 2, because 2 divides 40. We can't use 5 either. Three works: nothing except 1 divides both 3 and 40. So e = 3, and our public key is the pair of numbers 55 and 3.

Then we find the private exponent d. We need a number that, multiplied by 3, lands exactly one step past a multiple of 40. Try a few: 3 times 27 is 81, and 81 is two lots of 40 plus 1. So d = 27. Finding d this way needs the number 40, and finding 40 needs the primes 5 and 11. Without them, you are stuck before you start.

In real systems, the public exponent is almost always 65,537, a prime that makes locking fast and safe, and the private exponent ends up as large as the modulus itself. Some standards also use a smaller relative of the cycle length when computing d; the idea is the same.

A full round trip with small numbers

RSA works on numbers, so a message first has to become a number. Computers do this all the time, because every letter is already stored as a number underneath. To keep things simple, say the secret message is the number 7. It must be smaller than the modulus, so anything from 0 to 54 is allowed.

Locking uses only the public key. Multiply 7 by itself three times, because e is 3: 7 times 7 times 7 is 343. Then wrap around the 55-position clock: 343 lands on 13. The ciphertext is 13. Anyone with the public key could have done this, and anyone watching the network sees only the number 13.

Unlocking uses the private exponent. Multiply 13 by itself 27 times and wrap around at 55. That sounds enormous, and the full number would be dozens of digits long, but there is a shortcut: you may wrap after every single multiplication instead of waiting until the end, and the final answer is the same. For example, 13 times 13 is 169, and 169 wraps to 4. Keep going in small steps like that and the numbers never grow large. When the 27 multiplications are done, you land on 7. The original message is back.

Why does it come back? Locking multiplied by itself 3 times, and unlocking did 27 more rounds on top, so overall the message was raised to the power 81. Remember that 81 is two full cycles of 40 plus one extra step. A result proved in the 1700s by the mathematician Leonhard Euler guarantees that on this clock, raising any number to a power that is one more than a multiple of 40 hands you back the number you started with. The two exponents were chosen to be exactly that pair, so they cancel each other out.

You can check the whole round trip yourself. The short program below uses Python's built-in pow function, which raises a number to a power and wraps around a clock in one go.

n, e, d = 55, 3, 27          # public modulus, public exponent, private exponent
ciphertext = pow(7, e, n)    # lock: 7 to the power 3, wrapped at 55 -> 13
recovered = pow(ciphertext, d, n)  # unlock: 13 to the power 27, wrapped at 55 -> 7
print(ciphertext, recovered) # 13 7

Why the lock holds, and exactly where it would break

Put yourself in the shoes of an eavesdropper. You have the public key, 55 and 3, and you have intercepted the ciphertext, 13. What you want is the private exponent 27, because with it you could unlock this message and every future one.

To get 27 you need the cycle length 40. To get 40 you need the two primes. To get the primes you must factor 55. With our toy numbers that takes a second. With a real modulus it is a different story. A common key size today is 2,048 bits, which written out in ordinary digits is a number about 617 digits long. Each secret prime is roughly half that length. The largest RSA-style numbers publicly reported as factored, using large research efforts and specialised methods, are far shorter than that.

This is why people say RSA's security rests on factoring being hard. It is a careful statement, not a proof. Nobody has proved that factoring must be hard, and nobody has proved that factoring is the only way to break RSA. Decades of serious effort have simply failed to find a fast general method on ordinary computers, which is why standards bodies keep recommending key sizes with a comfortable margin, such as at least 2,048 bits today and 3,072 bits for information that must stay protected for many years.

The more practical lesson is about where real attacks go. When the mathematics is strong, attackers look for an easier door: a private key copied off a server, primes generated from poor randomness that someone else can guess, software that leaks timing or error details, or a system that uses raw RSA without the safety layers described next. The decision tree below shows the attacker's choices. Notice that the good outcome for the defender depends on more than the size of the numbers.

Why nobody uses the textbook version as it stands

What we built is often called textbook RSA, and it has two weaknesses you can see with our own toy key. Lock the message 2 with the public key: 2 times 2 times 2 is 8, and 8 is smaller than 55, so it never wraps around the clock at all. The ciphertext is just 8, and anyone can work out that 8 came from 2 by asking which number multiplied by itself three times gives 8. Without the wrap, there is no protection. Real systems that lock short messages with a small public exponent can fall into this trap at full size.

The second weakness is that textbook RSA always gives the same output for the same input. If an attacker suspects your message is either 'yes' or 'no', they can lock both guesses with your public key and compare the results with the ciphertext they intercepted. Whichever matches is your answer. The lock was never opened; the attacker simply guessed and checked.

The fix is called padding: before locking, the message is surrounded with carefully structured extra data, including fresh random bytes each time, so that it fills the whole size of the modulus and never repeats. The current standard for this, known as PKCS #1 (Public-Key Cryptography Standards number 1), defines a padding method called OAEP for encryption and a related method called PSS for signatures. The details are a story of their own. What matters here is that RSA without padding should be treated as broken by design.

One more practical point. RSA is slow compared with the ciphers used for bulk data, and each lock can only hold a message smaller than the modulus. So in practice RSA is rarely used to lock documents directly. Instead a computer creates a short random key for a fast cipher, locks the document with that, and uses RSA to protect only the short key, or uses RSA to sign something rather than to hide it.

What this means for practitioners and for AI agents

Knowing how the key is built turns several everyday decisions from rules to remember into choices you understand. The size of the modulus decides how hard factoring is, so size is a policy decision with a lifetime attached: information that must stay private for a decade deserves a larger key than a session that lasts an hour. The secrecy of the primes and the private exponent is the entire defence, so where those numbers live, who can copy them, and how quickly they can be replaced matter as much as the key size.

This applies directly to AI agents, which are software programs that use a large language model (LLM) to decide on steps and then carry them out through tools. When an agent calls a tool or an online service over a secure web connection, RSA keys are often part of what proves the service is genuine. When an agent signs in to a service using a certificate instead of a password, a private key, frequently an RSA key, is doing the proving. That private key is as powerful as the agent's identity. It should live in a dedicated key store or hardware module that performs operations for the agent, not in a configuration file, a prompt, a log, or anything a model can read back out.

Coding assistants raise a related risk. Ask one to 'encrypt this with RSA' and it may produce something that looks like the toy example above: a direct power-and-wrap with no padding. It will run, and it will appear to work, which is exactly why it is dangerous. Review generated cryptography code for the use of a well-known library and a named padding mode, not for whether it produces output.

1. Use a mature cryptography library; never implement RSA arithmetic or padding yourself.
2. Use at least 2,048-bit keys, and 3,072-bit keys for anything that must stay protected for many years.
3. Require OAEP padding for encryption and PSS padding for signatures in new designs.
4. Generate keys on systems with a trustworthy source of randomness, and never reuse or copy primes between keys.
5. Keep private keys in a key store or hardware security module, out of agent prompts, memory and logs.
6. Know where each RSA key is used and how you would replace it, so a leak becomes an inconvenience rather than a crisis.

Glossary

RSA

A public-key scheme named after Rivest, Shamir and Adleman that locks with a public key and unlocks with a private key built from two secret primes.

Prime number

A whole number bigger than 1 that can only be divided evenly by 1 and itself.

Modular arithmetic

Arithmetic in which numbers wrap around after reaching a chosen size, like hours on a clock.

Modulus

The size of the wrap-around clock; in RSA it is the product of the two secret primes and is part of the public key.

Public exponent

The public number of times a message is multiplied by itself when it is locked.

Private exponent

The secret number of times a ciphertext is multiplied by itself to unlock it.

Factoring

Finding the prime numbers that multiply together to give a particular number.

Ciphertext

A message after it has been scrambled by encryption.

Padding

Structured extra data, including fresh randomness, added to a message before RSA locks it so the result is safe.

Further reading

1. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems (Rivest, Shamir, Adleman, Communications of the ACM, 1978)
2. RFC 8017: PKCS #1 RSA Cryptography Specifications Version 2.2 (IETF)
3. NIST SP 800-57 Part 1 Rev. 5: Recommendation for Key Management (NIST)