RSA algorithm

The RSA algorithm is the best known public key encryption algorithm. Like any public key system, it can be used to create digital signatures as well as for secrecy.

It is named for its inventors Ron Rivest, Adi Shamir and Leonard Adeleman. The original paper defining it, "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems" by those three authors is still available [people.csail.mit.edu/rivest/Rsapaper.pdf].

How it works

To generate an RSA key pair, the system first finds two primes p, q and the product N = pq. The strength parameter of the system is the length of N in bits. As of 2008, 1024 bits is considered secure but some users choose larger sizes to be on the safe side. Then the original paper says to find T = (p-1)(q-1); a later optimisation is to use T = lcm( p-1, q-1). Either way, choose d, e such that d*e == 1 modulo T. The public key is then the pair (N,e) and the private key (N,d).

Using t for plaintext and c for ciphertext, encryption is then:

 c = te  modulo N

and decryption, using m for the decrypted message is:

 m = cd modulo N

so we have:

 m = (te)d modulo N
 m = (tde) modulo N

But since Fermat, back in the 17th century, we have known that for prime p and any x:

 xp == x   modulo p

and for non-zero x:

 xp-1 == 1   modulo p

whence, for any k and non-zero x:

 xk(p-1) == 1   modulo p

so with two primes and x non-zero modulo either:

 x(p-1)(q-1) == 1   modulo p or modulo q, hence modulo pq

Whether or not x is zero modulo either prime, we get:

 xk(p-1)(q-1)+1 == x   modulo pq

but we have:

 de == 1 mod T
 de = k(p-1)(q-1)+1   for some k

and

 m = (tde)    modulo N

so

 m = t      in all cases

That is, the encrypt/decrypt pair of operations always give the correct result.

RSA and factoring

Given an efficient solution to the integer factorisation problem, breaking RSA would become trivial. The attacker is assumed to have the public key (N,e). If he can factor N, he gets p, q and therefore p-1, q-1 and T. He knows e and can calculate its inverse mod T. That gives him d and e already has N, so now he knows the private key (N,d).

The problem with that is that no efficient solution for factoring is known, despite considerable effort by quite a few people over several decades to find one. It seems possible no such algorithm exists, though no-one has proven that.