So why does the

RSA cryptosystem work? First, let's recall

*how* it works. You pick two

primes `p` and

`q` of roughly the same size. You then let

`n = pq`. This is the

modulus you'll use. The public "

exponent of encryption"

`e` you set to a small constant (so that people who are sending you messages can do so at little computational cost). Then you find the

multiplicative inverse `d` of

`e` modulo `phi(n)` where

phi(n) is the number of integers less than

`n` to which it is

relatively prime. This

`d` is your private key (the "

exponent of decryption"). So you publish the pair

`(n,e)` and keep

`d` secret. You can compute

`d` because you know

`p` and

`q` and therefore

`phi(n)`. Other people cannot compute

`d` because they don't know

`p` and

`q` and therefore don't know

`phi(n)`.

Whew. OK. Now for *why* it works:

Fact 1: if x = y mod phi(n)
then m^{x} = m^{y} mod n for all m
Fact 2: ed = 1 mod phi(n)
because d is selected as e's inverse mod phi(n)
Therefore:
m^{ed}= m^{1} mod n for all m by fact 1
So when someone encrypts m to you she computes: c = m^{e} mod n
When you decrypt you compute:
c^{d} = (m^{e})^{d} mod n
= m^{ed} mod n by high school math
= m^{1} mod n by fact 1
= m mod n
And we're done!

Note that you can prove Fact 1 above (the important part of the math, IMHO), using

Fermat's Little Theorem or

Euler's Theorem.

This cryptosystem is conjectured to be strong because given `n and e`, there is no known (efficient) algorithm that can find `d`. In fact, if you can find such an algorithm you will be very very *very* famous because then you will have found an efficient way to factor large numbers.