What mathematical problem does RSA's security rely on, and who invented it?

RSA was invented by Rivest, Shamir, and Adleman in 1978. Its security relies on the difficulty of factoring large numbers $N = p \cdot q$ and computing e-th roots mod N.

The RSA hard problem:

• Forward: $c \equiv m^e \mod N$ — easy (square-and-multiply)
• Inverse: $m \equiv \sqrt[e]{c} \mod N$ — hard without knowing $p$ and $q$

The factoring connection:

• If you can factor $N = p \cdot q$ → you can compute $\varphi(N) = (p-1)(q-1)$ → you can compute $d \equiv e^{-1} \mod \varphi(N)$ → you can decrypt
• Factoring ⇒ e-th root (proven)
• e-th root ⇒ factoring (believed but not proven)
• There might be a way to compute e-th roots without factoring — but nobody has found one

Current recommendations (BSI 2023): RSA modulus $N$ must be at least 3000 bits (practically 3072 bits). Primes $p, q$ are each ~1536 bits (~462 decimal digits), making $N$ about $10^{1000}$.

Go deeper:

• Rivest, Shamir & Adleman — the original 1978 paper (PDF) — "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems", where it all began.
• RSA cryptosystem (Wikipedia) — full scheme, history and attacks.
• The RSA problem (Wikipedia) — why RSA security is the e-th-root problem, not exactly factoring.