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 , one can define the group . An element is invertible if and only if . The cyclic group is the group of invertible elements belonging to .

The Euler’s Totient Function, or Euler’s function is defined as: .

Notable properties:

  • if is a prime number, then
  • if with and primes, then

The Euler’s Theorem, also known as Fermat-Eluer Theorem, states that

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

  1. Choose with and large primes;
  2. Choose integers ;
  3. Cipher the message obtaining the ciphertext ;
  4. Decipher obtaining : .