Overview

Encryption
Alice first generates primes ppp
 and qqq
 and NNN
 such that N=pqN=pqN=pq
. This is half of the public key, with the other half being the public exponent eee
, which should be coprime to ϕ(N)\phi (N)ϕ(N)
 (meaning gcd(ϕ(N),e)=1gcd(\phi (N), e) = 1gcd(ϕ(N),e)=1
). These two values are then made public.
If Bob wants to send a message MMM
 to Alice using RSA, he calculates:
c=Memod  Nc = M^e \mod Nc=MemodN
Where ccc
 is now the ciphertext and is sent to Alice.
Decryption
Alice calculates ϕ(N)=(p−1)(q−1)\phi (N) = (p-1)(q-1)ϕ(N)=(p−1)(q−1)
 and then calculates the modular multiplicative inverse ddd
 of emod  ϕ(N)e \mod \phi (N)emodϕ(N)
. ddd
 is the private key used for the decryption which is known only to Alice.
To decrypt, the Alice calculates MMM
 again:
M=cdmod  NM = c^d \mod NM=cdmodN
The proof for this is based on Euler's Formula. Because we calculated ddd
 such that de≡1mod  ϕ(N)de \equiv 1 \mod \phi (N)de≡1modϕ(N)
, then we know that there is an integer kkk
 such that de=kϕ(N)+1de = k\phi (N) + 1de=kϕ(N)+1
. Also note that cd≡(Me)d≡Mdec^d \equiv (M^e)^d \equiv M^{de}cd≡(Me)d≡Mde
:
Mde≡Mkϕ(N)+1≡Mkϕ(N)×M≡(Mϕ(N))k×M≡1k×M≡Mmod  NM^{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 NMde≡Mkϕ(N)+1≡Mkϕ(N)×M≡(Mϕ(N))k×M≡1k×M≡MmodN
Attacks on RSA
Attacks on RSA generally fall into several categories, including weak public exponent or a poor choice of p,qp,qp,q
 which results in a value of NNN
 which can be factorised or attacked in another way. Remember that the trapdoor function in RSA is the difficulty of factoring NNN
 into the primes that make it up so only Alice is able to compute ϕ(N)\phi(N)ϕ(N)
 efficiently!
Last modified 1yr ago