Overview
Alice first generates primes
and
and
such that
. This is half of the public key, with the other half being the public exponent
, which should be coprime to
(meaning
). These two values are then made public.
If Bob wants to send a message
to Alice using RSA, he calculates:
Where
is now the ciphertext and is sent to Alice.
Alice calculates
and then calculates the modular multiplicative inverse
of
.
is the private key used for the decryption which is known only to Alice.
To decrypt, the Alice calculates
again:
The proof for this is based on Euler's Formula. Because we calculated
such that
, then we know that there is an integer
such that
. 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
efficiently!
Last modified 1yr ago