RSA Public & Private Keys

We're going to generate our own public and private keys using the RSA algorithm. We can these keys as a form of encryption.

Step 1 : Choose values for p & q

The first step of RSA is to choose two prime numbers, p & q. They should be greater than 2.

p & q should be considered secret values as if someone discovered them, they could derive your private key.

p :

Um... are you sure that's a prime number?

q :

Um... are you sure that's a prime number? Hey... Make sure p & q are not the same! Awesome. Those are some nice prime numbers you've got there!

Step 2 : Calculate n for the keys

The value n is included in both the public and private key, so it's a value that's publicly known to everyone. We will calculate it now, but we don't need it until we include it in the public & private keys. So, I want you to think of n as - not used until the end.

Fortunately its very easy to calculate n using the formula :

n = p * q

n = p * q

n = 257 * 337

n = 86609

Step 3 : Calculate Euler's totient (ϕ)

This step uses fancy maths words - but don't be scared.

We're calculating something called Euler's totient (ϕ), but its super easy to do.

ϕ is pronounced as 'phi' so we will also call it that.

ϕ is used to create your private key, so should be considered confidential.

ϕ(n) = ( p-1 ) * ( q-1)
ϕ(n) = ( 257-1 ) * ( 337-1 )
ϕ(n) = 256 * 336
ϕ(n) = 86016

Step 4 : Choose a value e for the public key

e will become one of the two values that make up the 'public' key.

Pick a random number e, that is 'relatively co-prime' with the Euler's totient in the range [3,ϕ(n)).

'Relatively co-prime' means we have to choose a value for e that doesn't share any factors with phi.[Remind me what a factor is again?].

In other words, e must be a prime number, and if you divide phi by it, phi should not evenly divide into e.

e :

Factors of ϕ : 1,2,3

Factors of e : Please pick an e first - tip : choose the next prime not listed above

Ah oh... e must be coprime with phi, so cannot share any factors with phi. Pick another value. Oh no... e must be greater than or equal to 3, and less than phi. Pick another value. Awesome! e is coprime with phi because e doesn't share any factors with phi

Your Public Key

Congratulations! You've just created your first public key!

Public Key : (e=17, n=86609)

In RSA, public keys are comprised of two values e and n. So most private keys look like this - Private Key : (e, n)

Its easy to get all the letters mixed up, so its good to remember that e stands for encrypting, which is usually what you use the public key for.

Step 5 : Choose a value d for the private key

To come up with the value d (which will be used in the private key) we must solve this equation.

e * d mod ϕ = 1

That means we need to guess a value of d, which when multiplied with e and then divided by ϕ will have a remainder of 1.

d :

e * d mod ϕ = ?

e * d mod ϕ = 1

17 * d mod 86016 = 1

Oh no... Try again. When you divide (e*d) by ϕ, the 'remainder' needs to be 1 Awesome!

Your Private Key

Congratulations! Now you have a private key!

Private Key : (d=65777, n=86609)

d is used in the private key to decrypt any messages encoded with the public key (e).

Remember that d stands for decrypting, which is usually what you use the private key to do.

Your Final Private & Public Keys

Public Key : (d, n)

Public Key : (123123123, n)

Private Key : (d, n)

Private Key : (123123123, n)

When the n value is paired with e it becomes the public key, and when n is paired with d it becomes the private key.

RSA Encryption

Now we're going to use the public/private keys that we just generated to encrypt and decrypt messages. Often the things we end up encrypting with RSA is other keys - symmetric keys which can be used in less computationally intensive block ciphers. For that reason, RSA more often considered a key-exchange protocol than an encryption algorithm.

Encrypting with Public Key

To encrypt a message 'm', we first convert it to a large number then we calculate the following :

c = m^e mod n

Where c stands for cipher-text, m stands for the plain-text (the character we are trying to encrypt), and e and n come from the public key.

Enter a letter to encrypt:

To encrypt 'A' we use the following formula with the public key (e=17,n=86609).

c = m^e mod n

c = m^e mod n (character converted to ASCII value )

c = m^e mod n

c = m¹⁷ mod 86609

c = c

To decrypt a cipher 'c', we apply the same process, but using the private key (d,n).

m = c^d mod n

m = c^d mod n (c substituted for actual cipher text in number form )

m = c^d mod n

m = 12448

Test it out yourself

To encrypt a message 'm', we first convert it to a large number then we calculate the following :

Enter a Public Key

e : n :

Enter a Private Key

d : n :

Plain Text:

Cipher Text