 RSA (cryptosystem)

Ciro Santilli 34  Updated 2024-12-15  +Created 1970-01-01

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:

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: