RSA and public-key cryptography
Rivest, Shamir, and Adleman published their construction in 1977, less than a year after Diffie and Hellman had described the abstract goal of public-key cryptography without proposing a concrete realization. The construction is short enough that the textbook description fits in a postcard, but the security argument relies on the believed hardness of a specific number-theoretic problem, and that hardness is far from settled even half a century later.
The setup picks two large primes p, q, lets
n = pq, picks an exponent e coprime to
φ(n) = (p-1)(q-1), and computes d such that
ed ≡ 1 (mod φ(n)). The public key is (n, e);
the private key is d. Encryption is c = m^e mod n;
decryption is m = c^d mod n. The correctness follows from
Euler's theorem.
The security is not the hardness of factoring n
per se; it is the hardness of the "RSA problem" — given (n, e, c),
recover m. We do not have a proof that this is exactly as hard
as factoring (though it is no harder). For specific moduli, no efficient
algorithm is known; for moduli with structure (small prime factors, close
factors, common factors with other keys in the wild), several attacks
exist, which is why moduli are now expected to be at least 2048 bits and
generated by reputable libraries.
Textbook RSA — used directly, without padding — is fragile in
ways that have produced a steady stream of papers. It is malleable (one can
multiply ciphertexts), it leaks one bit of m (the Jacobi
symbol), and it is deterministic. Real implementations use OAEP for
encryption and PSS for signatures; the underlying RSA primitive is wrapped
inside enough randomization that none of the textbook attacks apply.