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].

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