= RSA
{disambiguate=cryptosystem}
{c}
{wiki}
Based on the fact that we don't have a <P (complexity)> algorithm for <integer factorization> as of 2020. But nor proof that one does not exist!
The private key is made of two randomly generated prime numbers: $p$ and $q$. How such large primes are found: <how large primes are found for RSA>.
The public key is made of:
* `n = p*q`
* a randomly chosen integer exponent $e$ between `1` and `e_max = lcm(p -1, q -1)`, where `lcm` is the <Least common multiple>
Given a plaintext message `m`, the encrypted <ciphertext> version is:
``
c = m^e mod n
``
This operation is called <modular exponentiation> can be calculated efficiently with the <Extended Euclidean algorithm>.
The inverse operation of finding the private `m` from the public `c`, `e` and $n$ is however believed to be a hard problem without knowing the factors of `n`.
However, if we know the private `p` and `q`, we can solve the problem. As follows.
First we calculate the <modular multiplicative inverse>. TODO continue.
Bibliography:
* https://www.comparitech.com/blog/information-security/rsa-encryption/ has a numeric example