RSA
Alice receives c from Bob, and knows her private key d. She can recover n from c by the following procedure:
Alice can then extract n, since n < N. Given n, she can recover the original message m.
The decryption procedure works because
and ed ≡ 1 (mod p-1) and ed ≡ 1 (mod q-1). Fermat's little theorem yields
- and
which implies (as p and q are different prime numbers)