Alice first generates primes
. This is half of the public key, with the other half being the public exponent
, which should be coprime to
). These two values are then made public.
If Bob wants to send a message
to Alice using RSA, he calculates:
is now the ciphertext and is sent to Alice.
and then calculates the modular multiplicative inverse
is the private key used for the decryption which is known only to Alice.
To decrypt, the Alice calculates
The proof for this is based on Euler's Formula. Because we calculated
, then we know that there is an integer
. Also note that
Attacks on RSA generally fall into several categories, including weak public exponent or a poor choice of
which results in a value of
which can be factorised or attacked in another way. Remember that the trapdoor function in RSA is the difficulty of factoring
into the primes that make it up so only Alice is able to compute