# How RSA works: Euler's Totient Function

Present post is an experiment on how to include math formulas in a Jekyll site. It is demonstrated with few steps the working principle of RSA, a widely used public key cryptographic algorithm.

Given a natural positive number $N$, one can define the group $\mathbb{Z}_N = \{0,1,...,N-1\}$. An element $x \in \mathbb{Z}_N$ is invertible if and only if $\exists a \in \mathbb{Z}_N : ax = 1 \in \mathbb{Z}_N$. The cyclic group $\mathbb{Z}_N^* \subset \mathbb{Z}_N$ is the group of invertible elements belonging to $\mathbb{Z}_N$.

The Euler’s Totient Function, or Euler’s $\varphi$ function is defined as: $\varphi(N) = \| \mathbb{Z}_N^* \|$.

Notable properties:

• if $N$ is a prime number, then $\varphi(N) = N-1$
• if $N = p \cdot q$ with $p$ and $q$ primes, then $\varphi(N) = (p-1)(q-1)$

The Euler’s Theorem, also known as Fermat-Eluer Theorem, states that $\forall x \in \mathbb{Z}_N^* : x^{\varphi(N)} = 1 \in \mathbb{Z}_N^*$

RSA cryptography is based on the above theorem and the listed properties. So the RSA algorithm can be summarized with following steps:

1. Choose $N= pq$ with $p$ and $q$ large primes;
2. Choose integers $e,d : e\cdot d = 1(\mbox{mod }\varphi(N))$;
3. Cipher the message $m$ obtaining the ciphertext $c = m^e \in \mathbb{Z}_N$;
4. Decipher $c$ obtaining $m$: $c^d = m^{ed} = m^{\varphi(N)+1} = m^{\varphi(N)} \cdot m = m \in \mathbb{Z}_N$.