Textbook RSA
This is a tutorial on how to do RSA key generation, encrypt and decrypt message and hack an insecure RSA public key. I am assuming that you have already had an introduction to RSA and need to do something like what I will show you for homework or a project. The purpose of this article is to give you a better understanding of RSA — not to teach it to you.
It's called textbook RSA because it's used to teach the basics of asymmetric encryption. Don't try to implement something like this for an application, it's not secure! For real life applications something like RSAOAEP should be used.
Key Generation
To calculate the modulo, choose two random primes p
and q
. Multiplying them gives you
n
, which is our modulo.
To calculate the public and secret key multiply (p  1)
with (q  1)
. This gives us
phi
, now choose a random prime that is smaller than phi
, this is our public exponent
e
.
For the secret exponent d
we just need to find a number that fulfills e * d mod phi = 1
.
That's it, now we have our public key (n,e)
and our secret key (n,d)
.
Encryption and Decryption
To encrypt a plaintext we just need to use the following formula. plaintext ^ e mod n
or
pow(plaintext,e,n)
in Python.
For decryption we simply need to switch the plaintext with our ciphertext and e
with our secret
exponent
d
. So
ciphertext ^ d mod n
or
pow(ciphertext,d,n)
in Python.
Example
Say we choose the primes 17
and 23
, this means
17 * 23 = 391
, so n = 391
.
For phi
we get (17  1) * (23  1) = 352
. Lets choose 173
for our
e
, remembering that e
has to be smaller than phi
.
Having chosen e = 173
we get d = 213
. I use SageMathCell with the function inverse_mod(173, 391)
to
calculate d
.
Now we have our two keys:

Public key:
(391,173)

Secret key:
(391,213)
Encryption
To encrypt a plaintext 15
we do the calculation 15 ^ 173 mod 391
or
pow(15,173,391)
in
Python. This gives us the ciphertext 71
.
Decryption
To decrypt our ciphertext 71
we do the calculation 71 ^ 213 mod 391
or
pow(71,213,391)
in Python. This gives us the original plaintext of 15
.
Hacking the RSA key
The keys we have come up with for this example are completely insecure. Lets see how you would go about hacking them.
The public key is — as the name suggests — public. This means that n
is known. If we can factor
n
then it gives us our two primes
p
and q
. Once we have the primes we can calculate the secret exponent d
.
To get d
we calculate phi
by doing (p  1) * (q  1)
. Once we have
phi
we can calculate d
just like we would for key generation.
The security of RSA is based on the hardness of factoring. If p
and q
are large enough
numbers, then n
becomes so large that it's unrealistic to factor. Hence, safe.
Example
Let's say we want to find the secret key for our public key (391,173)
.
First we need to factor n
. Here we can use SageMathCell with the function factor(391)
.
The result is 17 * 23
— our two primes!
Now that we know p = 17
and q = 23
we can calculate (17  1) * (23  1)
which gives us phi = 352
. With phi
we have the last piece of the puzzle. We can use it
together with
e
to calculate d
. Again I use SageMathCell with the function inverse_mod(173, 352)
which gives us
293
— our secret exponent d
!
I hope that has helped you better understand RSA. Try to go through the process of generating the keys, encrypting/decrypting a message and then hacking the public key using your own numbers.