Ciro Santilli
🔗

RSA (cryptosystem) | 🗖 nosplit | ↑ parent "Public-key cryptography" | 203, 2, 346

🔗
Based on the fact that we don't have a p 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: and . 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 between 1 and e_max = lcm(p -1, q -1), where lcm is the Least common multiple
🔗
Given a plaintext message m, the encrypted cyphertext 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 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.
🔗
🔗
🔗