Implementing the RSA Scheme

Remark

In order for RSA to be secure, it must be computationally infeasible to compute the private key from the public key .
The adversary should be incapable of factoring (otherwise, they would have and and then compute ).
As of 2018, it is recommended that the primes and be at least 300 digits long, so is at least 600 digits long.

Setting up RSA

Let and be two random, large, distinct primes, and let:

Let and be arbitrary integers such that:

, (See GCD)
, (See congruence)
Note that by linear congruence theorem, a solution exists for

Public key: (known to everyone)
Private key: : known by receiver only

RSA Encryption

With being the ciphertext, and being the message, find , such that:

RSA Decryption

With being the ciphertext, and being the message, find , such that:

We claim that