Why RSA Works, and What the Chinese Remainder Theorem Changes

Most people who use RSA know its recipe: multiply two secret primes, publish the product and a small exponent, keep a matching private exponent, and raise numbers to these powers to lock and unlock them. Far fewer can say why the recipe works at all. Why does raising a number to one power and then to another bring back exactly the number you started with, for every possible message, and not merely most of them? Why must the public exponent obey certain rules, and why do real implementations not even use the private exponent directly, but split the work across the two secret primes instead? This article answers those questions from first principles. It uses one tiny key, small enough to check on a phone calculator, and builds the reasoning step by step: the repeating cycles that hide inside clock arithmetic, the condition that ties the two exponents together, the shortcut known as the Chinese remainder theorem that makes private-key operations roughly four times faster, and the extra numbers and consistency checks that shortcut brings with it. None of the arithmetic here is secure at this size. The point is to understand the machine well enough to judge real keys, real libraries and the code an artificial intelligence (AI) assistant writes for you.

What a working RSA key has to guarantee

RSA, named after its inventors Ron Rivest, Adi Shamir and Leonard Adleman, works on clock arithmetic, which mathematicians call modular arithmetic. On a clock with n positions, every result wraps around and only the remainder after dividing by n is kept. A key pair consists of the modulus n, which is the product of two secret primes p and q, a public exponent e, and a private exponent d. To encrypt a message number m, you raise it to the power e on the n-position clock. To decrypt, you raise the result to the power d on the same clock.

Our running example uses p = 5 and q = 11, so n = 55. The public exponent is e = 3 and the private exponent is d = 27. Encrypt the message 7: seven cubed is 343, and 343 wraps to 13 on a 55-position clock, because 55 times 6 is 330 and 13 is left over. Decrypt by raising 13 to the 27th power on the same clock, and you get 7 back.

That one round trip is reassuring but proves nothing. A key is only usable if decryption undoes encryption for every message from 0 up to 54, with no exceptions. If even one message failed to come back, data would be silently corrupted. This property is called correctness, and it is the first thing any public-key scheme has to get right. Security is a separate question that comes later. The rest of this article explains why correctness holds, which turns out to depend on a hidden repeating cycle, and then what happens when implementations speed the arithmetic up.

The hidden cycle inside clock arithmetic

Pick a small prime clock, say 11 positions, and keep multiplying 3 by itself, wrapping as you go. You get 3, then 9, then 27 which wraps to 5, then 15 which wraps to 4, then 12 which wraps to 1. The next step multiplies 1 by 3 and lands on 3 again, so the sequence repeats forever. Every number that shares no factor with the clock size behaves this way: its powers eventually return to 1 and then cycle.

In the 1600s Pierre de Fermat noticed a regularity in these cycles. On a clock whose size is a prime p, raising any number that is not a multiple of p to the power p minus 1 always lands exactly on 1. On the 11-position clock, every such number raised to the 10th power gives 1. The cycle for 3 has length 5, which divides 10, so 3 to the 10th is 1 as well. This result is known as Fermat's little theorem.

In the 1700s Leonhard Euler extended the idea to clocks whose size is not prime. For a modulus n that is the product of two distinct primes p and q, the right exponent is the product of p minus 1 and q minus 1, a number usually written with the Greek letter phi and called Euler's totient. For our key, phi is 4 times 10, which is 40. Any message that shares no factor with 55, raised to the 40th power on the 55-position clock, comes back to 1.

This is the hidden cycle that RSA depends on. Anyone can see the clock size 55. Only someone who knows the factors 5 and 11 can compute the cycle length 40 directly. That gap between the public modulus and the private cycle length is what separates the key holder from everyone else.

Why the two exponents undo each other

The rule that ties the exponents together is simple to state. The product of e and d must be one more than a whole number of cycles. With e = 3 and d = 27, the product is 81, which is two full cycles of 40 plus 1. Mathematicians write this as e times d being congruent to 1 modulo phi, and the private exponent is called the modular inverse of e.

Now follow a message through. Encrypting and then decrypting raises m to the power e and then to the power d, which is the same as raising m to the power e times d, here 81. Split 81 into two cycles of 40 plus 1. Each full cycle of 40 brings the message back to 1, and multiplying by 1 changes nothing, so what remains is m to the first power, which is m itself. Decryption returns the original message because the exponents add up to whole laps of the hidden cycle plus one extra step.

There is a subtle gap in that argument. Euler's result only covers messages that share no factor with n. In our key, messages such as 10, 15 or 22 are multiples of 5 or 11, so the shortcut does not apply to them directly. They still decrypt correctly, and the reason is worth seeing because it introduces the idea the rest of this article relies on. Look at the message on each prime clock separately. On the 5-position clock, a multiple of 5 is simply 0, and 0 raised to any positive power stays 0. On the 11-position clock it behaves like any ordinary number and obeys Fermat's cycle. Since the message comes back correctly on both small clocks, it comes back correctly on the 55-position clock as well, because a number between 0 and 54 is completely determined by its remainders on the 5-clock and the 11-clock.

Try it with the message 10. Raising 10 to the 3rd on the 55-position clock gives 1,000, which wraps to 10 itself, and decrypting 10 gives 10 again. Correctness holds. But notice that this message locked to itself: the ciphertext is the plaintext. That is a first glimpse of why the bare arithmetic, often called textbook RSA, must never be used on its own. Correctness says the round trip works; it says nothing about whether the locked value hides anything.

1. Choose e and compute d so that e times d is one more than a whole number of cycles.
2. Encrypting then decrypting raises the message to the power e times d.
3. Every full cycle returns to 1, leaving the message multiplied by 1.
4. Messages sharing a factor with n still return, checked prime by prime.

The rules the exponents must obey

Not every public exponent works. For a matching private exponent to exist, e must share no factor with the cycle length. With a cycle of 40, the exponent 5 would fail, because 5 divides 40 and no multiple of 5 can ever be one more than a multiple of 40. Key generation therefore picks e first and then chooses primes for which e has no common factor with p minus 1 or with q minus 1. The private exponent is then found with the extended Euclidean algorithm, an ancient and fast procedure for computing modular inverses.

The cycle length phi is not the only one that works. A smaller number, called the Carmichael function and written with the Greek letter lambda, is the least common multiple of p minus 1 and q minus 1. For our key, the least common multiple of 4 and 10 is 20, so every message already repeats on a cycle of 20. Computing d against 20 instead of 40 gives d = 7, because 3 times 7 is 21, one more than 20. Raise 13 to the 7th on the 55-position clock and you get 7, exactly as with 27. Both private exponents are correct; the smaller one is the one that the United States federal signature standard, Federal Information Processing Standard (FIPS) 186-5, specifies for key generation.

In practice the public exponent is almost always 65,537, which is 2 to the 16th plus 1. It is prime, so it rarely shares a factor with p minus 1 or q minus 1, and its binary form has only two 1 bits, so raising a number to that power takes just 17 squarings and multiplications. That makes encryption and signature verification fast. Very small exponents such as 3 are correct but leave less margin when padding is weak or missing, because a short message cubed may never wrap around the clock at all and can then be recovered by an ordinary cube root.

The private exponent has the opposite constraint: it must not be small. In 1990 Michael Wiener showed that a private exponent much shorter than a quarter of the modulus length can be recovered from the public key alone. Standard key generation, which derives d from e, naturally produces a private exponent about as long as the modulus, so the danger arises mainly when someone deliberately picks a short d to speed up decryption. The fast route that real implementations take is a different one, and it keeps d at full length.

The Chinese remainder theorem: two small clocks instead of one big one

Private-key operations, decryption and signing, are the slow part of RSA. The private exponent is as long as the modulus, so a 3,072-bit key needs thousands of squarings of 3,072-bit numbers. The holder of the private key has an advantage nobody else has, though: they know p and q. A result first recorded by the Chinese mathematician Sunzi, now called the Chinese remainder theorem (CRT), says that if two clock sizes share no factor, knowing a number's remainder on each small clock determines its remainder on the big clock uniquely. The ciphertext 13 is 3 on the 5-clock and 2 on the 11-clock, and no other number from 0 to 54 has that pair of remainders.

So the key holder can do the expensive work on the two small clocks and combine the answers. On each small clock the exponent can also shrink, because powers there repeat on cycles of p minus 1 and q minus 1. The private key therefore stores two reduced exponents: d modulo p minus 1, written dP, and d modulo q minus 1, written dQ. For our key, dP is 27 modulo 4, which is 3, and dQ is 27 modulo 10, which is 7.

Decrypt 13 this way. On the 5-clock, 13 is 3, and 3 cubed is 27, which wraps to 2. On the 11-clock, 13 is 2, and 2 to the 7th is 128, which wraps to 7. Now recombine with Garner's method, which uses one more stored number, the inverse of q on the p-clock, written qInv. Here 11 wraps to 1 on the 5-clock, so qInv is 1. Take the difference of the two partial answers, 2 minus 7, multiply by qInv and wrap on the 5-clock to get 0, then multiply by q and add the 11-clock answer: 0 times 11 plus 7 is 7. The message comes back, exactly as before.

The saving is large. The effort of one modular exponentiation grows roughly with the cube of the number size, so working on numbers half as long costs about one eighth as much, and doing it twice costs about a quarter. That is why CRT decryption and signing are commonly described as about four times faster, and why essentially every production RSA library uses them.

What CRT adds to the private key, and the invariants to keep

The speed-up changes what a private key is. The Public-Key Cryptography Standards number 1 (PKCS #1), published as Request for Comments (RFC) 8017, describes a private key not as the pair n and d but as a bundle: the modulus n, the public exponent e, the private exponent d, the primes p and q, the reduced exponents dP and dQ, and the coefficient qInv. Most real key files store all of them, and most libraries use only the CRT parts when they compute.

A bundle of redundant numbers can contradict itself, and nothing in the arithmetic will complain. If dQ was stored wrongly, decryption still produces a number; it is just the wrong one. So the components carry invariants that must hold together: p times q equals n, e times dP leaves remainder 1 on the p minus 1 cycle, e times dQ does the same on the q minus 1 cycle, and qInv times q leaves remainder 1 on the p-clock. FIPS 186-5 and related NIST guidance describe key-pair validation checks of this kind, and careful libraries run them when a key is imported.

The redundancy also creates a sharper risk. If a computation goes wrong in only one of the two halves, because of a hardware glitch, a bug or a deliberately induced fault, the faulty output still agrees with the correct message on one prime clock but not the other. Researchers showed in the late 1990s that a single such faulty signature can reveal one of the secret primes to anyone who sees it, which hands over the whole key. The detailed mechanism belongs to fault analysis, but the defensive habit is simple and cheap: after computing a private-key result with CRT, check it by applying the public exponent, which is fast because e is small, and release the result only if it maps back to the input.

Thinking of the key as layers makes these duties easier to see. The outer layer is public and harmless. Each layer inward holds information that can reconstruct everything outside it, and the innermost CRT values are the ones the computer touches most often, so they are the ones that most need protection from leaks and from silent corruption.

What correctness does not give you

Everything so far shows that RSA's arithmetic is correct. None of it shows that the arithmetic is safe to use directly, and the difference matters. Textbook RSA is deterministic: the same message always encrypts to the same ciphertext, so an attacker can test guesses. It is malleable: multiplying a ciphertext by the encryption of 2 gives the encryption of twice the message, without knowing either. And, as the message 10 showed, some inputs barely change at all. Real systems fix these problems with padding schemes, Optimal Asymmetric Encryption Padding (OAEP) for encryption and the Probabilistic Signature Scheme (PSS) for signatures, which add randomness and structure before the arithmetic runs.

Correctness also says nothing about how the primes were chosen. Security rests on nobody being able to factor n, and that fails if the primes come from weak randomness, are too close together, or are shared with another key. Standards therefore require primes of equal length drawn from a strong random source, with checks that reject unlucky choices. The arithmetic in this article is the engine; padding, prime generation and careful implementation are what make it roadworthy.

Decisions for practitioners and AI agents

For engineers, the practical lessons are concrete. Use a mature cryptographic library rather than writing modular exponentiation yourself, keep the public exponent at 65,537, and use keys of at least 2,048 bits, with 3,072 bits for data that must stay protected for many years, as NIST Special Publication 800-57 recommends. When a key arrives from elsewhere, a partner, a backup or a migration, validate it: confirm that the CRT components are consistent with each other and with the public key before trusting it. Prefer libraries that verify CRT results before releasing them.

For AI agents the stakes are higher than they first appear. An agent that signs requests or unwraps keys holds an RSA private key that is, in effect, its identity. That key bundle should live in a key store or hardware security module (HSM), a device that performs private-key operations without ever exporting the key, so neither the agent's prompts nor its logs can expose p, q or the CRT values. Code assistants deserve scrutiny too. Asked to implement RSA, an assistant may produce a few lines that raise numbers to powers. The code will run and round trips will succeed, because, as this article showed, the arithmetic is correct. That is precisely why such code is dangerous: it is unpadded, unchecked and unvalidated, and nothing about it fails loudly.

A simple decision path captures the habits worth enforcing whenever an agent or service is handed an RSA key to use.

• Use a mature library; never hand-roll modular exponentiation.
• Keep e at 65,537 and keys at 2,048 bits or more.
• Validate imported keys, including every CRT component.
• Check private-key results with the public exponent before release.
• Keep agent keys in a key store or HSM, never in prompts or logs.

Glossary

Modular arithmetic

Arithmetic on a clock of a fixed size where every result wraps around and only the remainder is kept.

Euler's totient

For a product of two distinct primes, the product of each prime minus one; a length on which every coprime number's powers repeat.

Carmichael function

The smallest exponent that returns every coprime number to 1 on a given clock; for RSA, the least common multiple of p minus 1 and q minus 1.

Modular inverse

The number that multiplies another to leave remainder 1 on a given clock; the private exponent is the inverse of the public one.

Chinese remainder theorem (CRT)

The result that remainders on two clocks with no common factor determine a number's remainder on their product clock uniquely.

Garner's method

A short procedure that rebuilds a number from its remainders on two prime clocks using one stored coefficient.

Textbook RSA

The bare RSA arithmetic with no padding, which is correct but deterministic, malleable and unsafe to use directly.

Hardware security module (HSM)

A tamper-resistant device that performs private-key operations without ever exporting the key.

Further reading

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