Here you can find an explanation of the
mathematics
behind the
RSA cryptosystem.
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 xa
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 yb modulo n.
This really works because (xa)b=xab,
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 xab is congruent
to x mod p. So assume not. Then Fermat's Little Theorem
says that xp-1 is congruent to 1 modulo p.
Thus
xab=x.(x(p-1))q(k-1)
is congruent to x modulo p. The same argument shows
that xab is congruent to x modulo q
also, and so xab 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.
There is some overlap with posthumous's writeup but there's
quite a bit more detail here.