Incoming links: Extended Euclidean algorithm
Can be calculated efficiently with the Extended Euclidean algorithm.
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
1ande_max = lcm(p -1, q -1), wherelcmis the Least common multiple
Given a plaintext message This operation is called modular exponentiation can be calculated efficiently with the Extended Euclidean algorithm.
m, the encrypted ciphertext version is:c = m^e mod nThe 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.
Bibliography:
- www.comparitech.com/blog/information-security/rsa-encryption/ has a numeric example