RSA was the first truly practical public-key system, and for decades it has been the backbone of HTTPS, encrypted email and digital signatures. It is named after its three authors, Ron Rivest, Adi Shamir and Leonard Adleman, who presented it in 1977. Its workings can be understood with a little high-school arithmetic.
The core idea: a one-way door
RSA relies on a mathematical asymmetry. Multiplying two large prime numbers is easy; starting from the product and working back to the two factors is extremely hard when the numbers have hundreds of digits. Nobody knows an efficient way to do it on classical computers.
Whoever creates the key knows the two primes and therefore holds a "shortcut"; everyone else sees only the product.
How a key pair is built
The procedure, simplified, is as follows:
- choose two large prime numbers, p and q, and keep them secret;
- compute n = p ร q, called the modulus;
- compute a value tied to p and q, ฯ(n) = (p โ 1) ร (q โ 1);
- choose a public exponent e that shares no divisors with ฯ(n); in practice 65537 is almost always used;
- compute the private exponent d, so that e ร d leaves a remainder of 1 when divided by ฯ(n).
The public key is the pair (n, e). The private key is d, together with the primes p and q used to compute it.
An example with small numbers
With toy numbers, the mechanism becomes visible:
- p = 61, q = 53, so n = 3233;
- ฯ(n) = 60 ร 52 = 3120;
- we choose e = 17;
- the private exponent turns out to be d = 2753, because 17 ร 2753 = 46801, which divided by 3120 leaves a remainder of 1.
To encrypt the message m = 65, you raise 65 to the power of 17 and take the remainder of the division by 3233: the result is c = 2790. To decrypt, you raise 2790 to the power of 2753, again modulo 3233, and get 65 back.
In reality n has 2048 bits or more, about 617 decimal digits. Factoring a number like that is beyond the reach of today's computers.
Encrypting and signing
The same key pair can be used for two different things.
- Encryption: anyone uses the public key (n, e) to encrypt; only the holder of d can decrypt.
- Signing: the holder uses d to produce a signature over a document's fingerprint (hash); anyone with the public key can check that the signature matches.
In practice RSA almost never encrypts the actual data: it is slow and can only handle small blocks. It is used to protect a symmetric key or to sign a cryptographic fingerprint.
The detail that makes the difference: padding
"Textbook" RSA as described above, applied as it is, is insecure. It has mathematical properties an attacker can exploit: the same message always produces the same ciphertext, and some messages can be manipulated in predictable ways.
That is why padding schemes are used, meaning rules for preparing the message before the mathematical operation by adding structure and randomness:
- OAEP for encryption;
- PSS for signatures.
The old PKCS#1 v1.5 encryption scheme has been at the centre of several practical attacks, in which a server that reported padding errors differently allowed an attacker to decrypt messages piece by piece. The lesson is clear: in cryptography the right algorithm is not enough, you also need the right way of using it.
How long should an RSA key be?
| Length | Current assessment |
|---|---|
| 1024 bits | Should be considered obsolete |
| 2048 bits | Minimum acceptable today |
| 3072 bits | Recommended for a longer horizon |
| 4096 bits | Greater margin, at the cost of more slowness |
RSA keys grow quickly as the desired security increases, and so do computation times. That is why many modern systems prefer elliptic curves, which offer comparable security with much shorter keys.
The real threats
Successful attacks against RSA rarely "break" the mathematics. More often they exploit:
- badly generated primes, for example from a faulty random number generator, so that different keys share a factor;
- keys that are too short and remain in use out of habit;
- vulnerable implementations that leak information about the private key through computation times or error messages;
- poorly protected private keys, copied onto servers, backups or unprotected computers.
Then there is a future threat: a sufficiently large quantum computer running Shor's algorithm could factor n efficiently. No such machine exists today, but it is the reason work is under way to migrate to post-quantum algorithms.
In short
- RSA relies on the difficulty of factoring the product of two large prime numbers.
- The public key is (n, e); the private key d is computed from the secret factors p and q.
- It is used both to encrypt small amounts of data, such as session keys, and to sign.
- Without correct padding (OAEP, PSS), RSA is vulnerable.
- Today at least 2048 bits are used, and the post-quantum transition is being planned for the future.
