# 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$.
{"extraction_info": {"found_math": true, "script_math_tex": 24, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.9830456972122192, "perplexity": 404.075225078335}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 20, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2019-04/segments/1547583684033.26/warc/CC-MAIN-20190119221320-20190120003320-00020.warc.gz"}