RSA (Rivest-Shamir-Adleman) is an algorithm for asymmetric key encryption that generates a public-private key pair. > [!NOTE] Definiton (RSA) >Output: > >Procedure: >1. Alice choses two [[Prime numbers|prime numbers]] $p$ and $q.$ >2. Alice computes $n=pq$ and $\phi(n)=(p-1)(q-1)$ >3. Alices choses $e\in \mathbb{Z}$ such that $1<e<\phi(n)$ and $\gcd(e,\phi(n))=1$ and publishes the values of $n$ and $e.$ >4. Alice then computes $d=e^{-1} \pmod{\phi(n)}$ as the private $k.$ The point is that it is hard to factorise $n$ when it is very large and so it is difficult to recover $p$ and $q$ and thus $d.$ **Sharing procedure**: plaintext $m$ that is not divisible by $p$ nor $q.$ Compute cipher text $m^{e} \pmod{n}.$ Alice decrypts by computing $(m^{e})^{d}.$ Since $ed\equiv 1 \pmod{\phi(n)},$ we have $ed=1+k\phi(n)$for some $k.$ So using [[Euler's theorem (Number Theory)]], $m^{ed}\equiv m(m^{\phi(n)})^{k}\equiv m \pmod{n}$