Overview

Encryption

Alice first generates primes
pp
and
qq
and
NN
such that
N=pqN=pq
. This is half of the public key, with the other half being the public exponent
ee
, which should be coprime to
ϕ(N)\phi (N)
(meaning
gcd(ϕ(N),e)=1gcd(\phi (N), e) = 1
). These two values are then made public.
If Bob wants to send a message
MM
to Alice using RSA, he calculates:
c=MemodNc = M^e \mod N
Where
cc
is now the ciphertext and is sent to Alice.

Decryption

Alice calculates
ϕ(N)=(p1)(q1)\phi (N) = (p-1)(q-1)
and then calculates the modular multiplicative inverse
dd
of
emodϕ(N)e \mod \phi (N)
.
dd
is the private key used for the decryption which is known only to Alice.
To decrypt, the Alice calculates
MM
again:
M=cdmodNM = c^d \mod N
The proof for this is based on Euler's Formula. Because we calculated
dd
such that
de1modϕ(N)de \equiv 1 \mod \phi (N)
, then we know that there is an integer
kk
such that
de=kϕ(N)+1de = k\phi (N) + 1
. Also note that
cd(Me)dMdec^d \equiv (M^e)^d \equiv M^{de}
:
MdeMkϕ(N)+1Mkϕ(N)×M(Mϕ(N))k×M1k×MMmodNM^{de} \equiv M ^ {k\phi (N) + 1} \equiv M^{k\phi (N)} \times M \equiv (M^{\phi (N)})^k \times M \equiv 1^k \times M \equiv M \mod N

Attacks on RSA

Attacks on RSA generally fall into several categories, including weak public exponent or a poor choice of
p,qp,q
which results in a value of
NN
which can be factorised or attacked in another way. Remember that the trapdoor function in RSA is the difficulty of factoring
NN
into the primes that make it up so only Alice is able to compute
ϕ(N)\phi(N)
efficiently!