RSA (RSA encryption) is one of the first and most widely used public-key algorithms, named after Ron Rivest, Adi Shamir and Leonard Adleman, used for encryption and digital signatures.
How RSA works
RSA was published at MIT in 1977. Its security rests on the difficulty of factoring a very large number into its two prime factors:
- The key owner picks two large random primes and multiplies them; the product (the modulus) becomes part of the public key.
- Encryption raises the message to the public exponent modulo that number; only someone who knows the primes can compute the private exponent needed to reverse it.
- Signing works the other way round: the private key creates a digital signature that anyone can check with the public key.
In practice RSA encrypts only small values such as session keys and is always combined with padding schemes like OAEP (encryption) or PSS (signatures).
Why RSA matters
As a core public-key cryptography algorithm, RSA signs most TLS digital certificates, code-signing certificates and software updates, and secures SSH keys and email encryption. Its weaknesses are well documented:
- Short keys – the 829-bit RSA-250 challenge number was factored in 2020; 1024-bit keys are considered deprecated, and at least 2048 bits are recommended.
- Padding oracles – Bleichenbacher’s 1998 attack on PKCS #1 v1.5 padding returned in 2017 as the ROBOT vulnerability in many TLS servers.
- Weak key generation – the 2017 ROCA flaw in an Infineon library made keys in smart cards, including Estonian ID cards, factorable.
TLS 1.3 removed RSA key transport altogether in favour of ephemeral Diffie–Hellman, which provides forward secrecy.
RSA and quantum computing
Shor’s algorithm running on a sufficiently large quantum computer could factor RSA moduli efficiently. NIST has therefore proposed deprecating RSA and other classical public-key algorithms by 2030 and disallowing them after 2035, with migration to post-quantum cryptography. Organisations should inventory where RSA is used and plan that transition now.
