RSA (thing)

Start with an integer n which is the product of two different primes p and q. n is going to be part of the public key but p and q have to be kept private.

Now suppose we have a message for encryption. We need to first convert it into numeric form. How we do this is not really important but as an example, if we have a plain text message then we could convert it into numeric form (not very efficiently) by stringing together the three digit numbers obtained from each character by the ASCII code plus 100. So the message Phear me! gets translated to 180204201197214132209201133.

Because we are going to be working modulo n so we have to break the numeric form of the message into blocks, each block being a nonnegative integer less than n.

The next stage is the encryption process. We need an integer a that is coprime to phi(n), where phi is the Euler Phi function. This means that a is invertible modulo n.

The pair (n,a) is the public key. Let us now encrypt our message with this key. We have converted our message into a sequence of blocks x each of which is a nonnegative integer and less than n. The encrypted version of x is just the uniquely determined nonnegative integer less than n that coincides with x^a modulo n.

How could we reverse the process and decrypt the message? The decryption algorithm depends on knowing an inverse b for a modulo phi(n). The pair (n,b) is the private key.

Suppose that we have an encrypted block of our original message, call it y. Then to decrypt all we have to do is find the residue of y^b modulo n.

This really works because (x^a)^b=x^ab, and we know that ab is congruent to 1 modulo phi(n); that is 1=ab-k.phi(n) and so ab=1+k(p-1)(q-1)

Now we work modulo p. There are two cases, if x is divisible by p then we certainly have that x^ab is congruent to x mod p. So assume not. Then Fermat's Little Theorem says that x^p-1 is congruent to 1 modulo p. Thus

x^ab=x.(x^(p-1))^q(k-1)

is congruent to x modulo p. The same argument shows that x^ab is congruent to x modulo q also, and so x^ab is congruent to x modulo n, as required.

It is believed that cracking the above encryption method is equivalent to factoring n and up to now the latter is a difficult problem. There isn't actually a rigorous proof of this equivalence, just some heuristic arguments, so it is possible, in priciple, that someone will come up with a way to break the encryption without factoring n but this seems fairly unlikely. This system has been use for quite a few years now and has proved to be secure in practice.

A good deal of care has to be taken in choosing the primes p and q. If they are too small then clearly we can easily factor n so we must choose large primes (we are talking over a 100 digits for very modest security). But we also have to avoid some obvious traps. For example we don't want p and q to be too close together, for then again, n is easily factored.