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 mx = my mod n for all m
Fact 2: ed = 1 mod phi(n)
because d is selected as e's inverse mod phi(n)
Therefore:
med= m1 mod n for all m by fact 1
So when someone encrypts m to you she computes: c = me mod n
When you decrypt you compute:
cd = (me)d mod n
= med mod n by high school math
= m1 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.