Based on the fact that we don't have a P algorithm for the discrete logarithm of the cyclic group as of 2020, but we do have an efficient algorithm for modular exponentiation. But nor do we have proof that one does not exist! Living on the edge as usual for public-key cryptography.
This is the discrete logarithm problem where the group is a cyclic group.
In this case, the problem becomes equivalent to reversing modular exponentiation.
This computational problem forms the basis for Diffie-Hellman key exchange, because modular exponentiation can be efficiently computed, but no known way exists to efficiently compute the reverse function.
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
ande_max = lcm(p -1, q -1)
, wherelcm
is 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 n
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.
Bibliography:
- www.comparitech.com/blog/information-security/rsa-encryption/ has a numeric example