Computational cryptography › Public-key encryption and key exchange › Classical number theory › Factoring
Hardness assumptionKE: gives key exchangeTD: gives trapdoor functions

RSA problem

In plain words

The exact puzzle behind RSA: undo a "raise to a power" step without knowing the secret primes. Anyone who can factor can solve it.

The idea: RSA scrambles a number by raising it to a public power e and keeping the remainder after dividing by N. Toy example: with N = 33 (3 × 11) and e = 3, the message 4 becomes 4³ = 64, which leaves 31. Undoing that means taking a "cube root" in remainder arithmetic, which nobody knows how to do fast for big N. But knowing 3 and 11 lets you compute a secret power d = 7 that undoes it: 31⁷ leaves 4 again. Encryption: anyone can apply e, only you can apply d. Signatures run it backwards: only you can make a number that turns into the document's hash when anyone applies e.

Why it matters: If it falls, RSA encryption and signatures fall with it.

The details

On the map: e-th roots mod N

Given a modulus N, an exponent e and a number y, find x with x^e = y (mod N), without knowing the factors of N. Knowing the factors (the trapdoor) makes this easy. That is how RSA decryption and signing work[1].

If you can factor, you can solve the RSA problem. The reverse isn't known, so it could in principle be easier than factoring, which makes it a slightly stronger assumption[2].

Rests on

If any of these breaks, this breaks too.

If it falls

If this breaks, these break with it.

Everything that falls with it (4 boxes)

About the tags

KE
This assumption gives key exchange on its own, so it needs more than one-way functions and falls if public-key encryption is impossible.
TD
This assumption gives trapdoor functions on its own (computable by anyone, invertible only with a secret), so it falls if trapdoor functions don't exist. Schemes built on it need not use a trapdoor: ElGamal doesn't.

References

  1. R. L. Rivest, A. Shamir and L. Adleman. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Defense Technical Information Center, 1978. doi:10.21236/ada606588
  2. Dan Boneh and Ramarathnam Venkatesan. Breaking RSA may not be equivalent to factoring: Extended abstract. Advances in Cryptology — EUROCRYPT'98, 1998. doi:10.1007/bfb0054117