The RSA cryptosystem, named after Ron Rivest, Adi Shamir, and Leonard Adleman, the MIT professors that first publicly described it in 1978, is the most copied software in history. It is an asymmetric encryption system, meaning that there are “public” and “private” keys which act as inverse operations and are mathematically related. Because RSA and other asymmetric cryptographic algorithms are slow, they are generally used to encrypt a shared symmetric key during initial communication (the handshake) which is then used for all further communication.
A British mathematician named Clifford Cocks actually discovered this in 1973 while working for Government Communications Headquarters (GCHQ), although this was not known until 1997 when the information was declassified.
Its strength relies upon the infeasibility of determining the prime factors of a large composite number n
.
First, Some Housekeeping
Symbols
≡ The congruence relation. Numbers are congruent if they have the same remainder some modulo
n
. For example, the following numbers 37 and 57 are said to be congruent modulo 10:37 ≡ 57 mod 10 37 mod 10 = 57 mod 10
ϕ or φ The Greek letter
phi
.Euler’s totient function
Also known as Euler’s phi function, this function counts the number of positive integers from 1 to a positive integer
n
that are coprime ton
.For example:
ϕ(10) = 4  In the range 110 (inclusive), 1,3,7,9 are coprime to 10. ϕ(9) = 6  In the range 19 (inclusive), 1,2,4,5,7,8 are coprime to 9.
Calculating ϕ(n) of large numbers can be difficult and timeconsuming except in one case…prime numbers! For them, simply do ϕ(n1). So:
ϕ(1117) = 1116 ϕ(13) = 12
This makes sense, since prime numbers have no factors besides itself and 1 (obviously, every number can be factored by 1).
The phi function is also multiplicative:
ϕ(a*b) = ϕ(a) * ϕ(b)
So, if
n
is the product of two distinct prime numbersp
andq
, this can be written as:ϕ(n) = ϕ(p) * ϕ(q) or ϕ(n) = (p1) * (q1)
Needless to say, the phi function is very important in the field of cryptography and for implementing RSA, specifically.
The Algorithm
We’re calculating the public key (e, n)
and the private key (d)
. Sometimes you’ll see the modulus included with the private key as well (d, m)
.
Steps to implement RSA:

Use two distinct large prime numbers
p
andq
. 
Calculate
n=pq
. The product of this will be the modulusn
, also known as the key length. 
Determine
ϕ(n)
, i.e., compute Euler’s totient function. This value must be kept private. The result counts the number of integers that are relatively prime ton
(up to a given integern
). It is from this set of numbers thate
is chosen in step 4.Recall:
ϕ(n) ≡ ϕ(p) * ϕ(q) or ϕ(n) ≡ (p  1)(q  1)
Note that this is easy to do only if the prime factorization of
n
is known, since determining the prime factors of some very large composite numbern
is a very difficult problem, even whenn
is publicly known (as it is).Remember that determing the
phi()
of a prime number is very easy…just subtract one! 
Choose an integer as the public key
e
using the result from the previous step. The choice must be constrained by the following two rules: 1 < e < ϕ(n)  Coprime to ϕ(n), that is, gcd(e, ϕ(n)) = 1
For example, given ϕ(10) = 6,
e
can only be 7, since 1, 2, 3, 4 are factors of eithern
or ϕ(n).Recall that the gcd of two or more integers is the greatest number that divides are of them evenly.

Determine the private key
d
from the public keye
. This is a oneway trapdoor function to reverse the public key(e, n)
. It is the modular multiplicative inverse of the public key, which says that for an integera
, the product of that number with an integerx
is congruent to 1 modulusm
:ax ≡ 1 mod (m)
Another way of thinking of this is that
ax  1
divides equally by the modulusm
.So, in the context of ϕ(n), if we start with:
d ≡ e^1 mod ϕ(n)
we can mulitply both sides by the inverse of
e^1
to get the statement:d*e ≡ 1 mod ϕ(n)
This statement will determine the modular multiplicative inverse of the number
e
that was chosen from the previous step. In essence, we need to find a value ford
that equals 1.
Again, take notice that the calculation depends on knowing ϕ(n)
, which in turn requires knowledge of the primes:
ϕ(n) ≡ (p  1)(q  1)
Knowing the prime factorization of the modulo n
is infeasible for traditional computing (not so with quantum computers!), and this is where the strength of the algorithm lies.
Also recall that
n
,e
and the encrypted result are publicly known. Because of math, this is still insufficient for an adversary to reverse the prime factorization!
Computing the Keys
I have written concise JavaScript helper scripts to calculate some of the steps outlined above. I found it to be very instructive to do, and I encourage anyone to do the same to assist in really internalizing how the algorithm works. In addition, the commandline calculator bc is invaluable.
Actually, forget all that. Use pencil and paper :)
Choose two distinct prime numbers:
$ ./is_prime.js 17
true
$ ./is_prime.js 19
true
Or, using Bash:
$ for i in {2..4}
> do
> if [[ $(bc <<< 17%$i) eq 0  $(bc <<< 19%$i) eq 0 ]]
> then
> echo $i
> fi
> done
If nothing printed to stdout
, then both numbers are prime!
Note the range
{2..4}
. This is because we only need to test to the square root of the numbern
, floored. In addition, we can exclude 1 since it factors into every number.
Calculate the ϕ function:
ϕ(n) ≡ (p  1)(q  1)
$ ./eulers_totient_func.js 17 19
phi(323) = 288
Or, using Bash:
$ bc <<< 17*19 && bc <<< 16*18
323
288
Now that ϕ(323) has been calculated, it’s time to choose a public key e
. Recall the two conditions:
 1 < e < ϕ(323)
 Coprime to ϕ(323), that is, gcd(e, ϕ(323)) = 1
So, in the range 1..287 (remember, one less than ϕ(n)), I’ll choose 5. But is 5 coprime with 288?
$ echo "288%5"  bc
3
Yes, it is. If 5 were a factor of 288, the result would be 0.
Now, there is the very important step of calculating the private key d
, which must be the modular multiplicative inverse of e
. In other words, it’s necessary to find a multiple d
by public key e
modulo n
where the result is 1.
Recall:
d ≡ e^1 mod ϕ(n)
or
d*e ≡ 1 mod ϕ(n)
So, in the context of the variables that have already been determined, the equation will look like this:
5d ≡ 1 mod ϕ(323)
In order to find a multiple of 5 that satisfies the equation, i.e., equals 1, substitute for d
with the range 1..ϕ(323)
.
5(1) mod 288 = 5 5(2) mod 288 = 10 5(3) mod 288 = 15 5(4) mod 288 = 20 5(5) mod 288 = 25 ... 5(172) mod 288 = 284 5(173) mod 288 = 1 < # Bingo! 5(174) mod 288 = 6 ... 5(287) mod 288 = 283 5(288) mod 288 = 0 5(289) mod 288 = 5 < # Pattern starts to repeat here! 5(290) mod 288 = 10 # If unfamiliar with this, 5(291) mod 288 = 15 # research modular arithmetic. 5(292) mod 288 = 20 5(293) mod 288 = 25 ...
$ ./priv_key.js 5 288 173
Note that in this example there was only one number whose result satisfied the equation, but oftentimes there is more than one number from which to choose.
Or, using Bash:
$ for i in {1..288} > do > if [[ $(bc <<< 5*$i%288) eq 1 ]] > then > echo $i > fi > done 173 for i in {1..288}; do if [[ $(bc <<< 5*$i%288) eq 1 ]]; then echo $i fi done
Now that the public/private keys have been computed, it’s a snap to use the oneway functions to encrypt and decrypt all of the secret communications.
Encryption and Decryption Operations
Given the public key:
( e = 5, n = 323 )
we’re calculating the cipher text c
given the plain text message m
:
c ≡ m^e mod n
$ bc <<< 10^5%323 193
Given the private key:
( d = 173 )
we’re calculating the message m
given the cipher text c
:
m ≡ c^d mod n
$ bc <<< 193^173%323 10
Again, the operations are inverses of each other, which satisfy the equation
d*e = 1 mod ϕ(n)
bc <<< 5*173%288
It’s also worth noting that the following are true:
(m^e)^d mod n = m^(e*d) mod n
(c^d)^e mod n = c^(d*e) mod n
Using Bash:
echo "(10^5)^173%323 == 10^(5*173)%323"  bc echo "(193^173)^5%323 == 193^(173*5)%323"  bc
So cool!
If you’ve made it this far, here is an RSA Calculator.