Understanding RSA

6 August 2018 in #cryptography

RSA is an Asymmetric cryptography algorithm. Asymmetric cryptography means that the key you use to encrypt messages is different to the key that the recepient uses to decrypt messages.

This is an interactive demonstration of the algorithm, powered by Vue.js. Click the button below to begin the demonstration. You can click the button multiple times to update the initial primes, and the whole demonstration will update.

This demo uses very small primes, so it is not suitable for actual cryptographic use.

Generating Keys

Firstly, two random primes, p and q, are generated. These would usually be very long, and would differ in length by a few numbers.

p = {{ p }}

q = {{ q }}

Now, we calculate n, where n = pq. n is used as a modulus. The modulus finds the remainder when you perform a division. For example 10 mod 3 is 1, because 3 goes into 10 three times, giving a remainder of 1.

n = {{ p }} × {{ q }} = {{ n }}

Now, we calculate φ (the greek letter phi).

φ = (p-1)(q-1) = ({{p}}-1)({{q}}-1) = {{ t }}

We generate another prime, e, between 1 and φ.

e = {{ e }}

And finally, we calculate d with d = e-1 mod φ

d = {{ e }}-1 mod {{ t }} = {{ d }}

This calculation is called the Modular Multiplicative Inverse. It's important to note that the power of -1 is just notation, it doesn't actually mean that e should be raised to the -1st power. You can learn more about it here.

We now have our two keys, public and private.

Public Key

This key can be given to anyone, and they will use it to send you encrypted messages

Private Key

This key is kept secret, and used to decrypt messages sent to you

Encrypting a Letter

You send your public key to your friend, Bob, who wants to encrypt a message with it. How can he do that?

We'll start sending a single letter. However, we encrypt it using an equation, so we need to turn it into a number.

You'll notice that encrypting 1 will always result in a ciphertext of 1. In real RSA, we'd use something called padding to ensure that we never try and do this, but that's out of scope for this simple demo.

We'll call this plaintext number m, and the encrypted number c.

Use the equation c = me mod n

{{ aOneLetterPlain }}{{e}} mod {{n}} = {{aOneLetterEncrypted}}

So, Bob will send you the number {{aOneLetterEncrypted}}.

Decrypting a Letter

Bob has sent you the number {{aOneLetterEncrypted}}. To decrypt it, you need to use your private key d. We'll call the encrypted message c and it's decrypted form m. Only you can decrypt this because only you have d, your private key.

m = cd mod n

m = {{ aOneLetterEncrypted }}{{ d }} mod {{n}} = {{ decrypt(aOneLetterEncrypted) }}

If you turn that number into a letter you get {{ getLetterFromNumber(aOneLetterPlain) }}

Encrypting and Decrypting Multiple Letters

The simplest way to encrypt and decrypt multiple numbers is to encrypt and decrypt them individually.

Plaintext letter Plaintext number Encrypted number
H 8 {{ encrypt(8) }}
E 5 {{ encrypt(5) }}
L 12 {{ encrypt(12) }}
L 12 {{ encrypt(12) }}
O 15 {{ encrypt(15) }}


Your public and private keys also work the opposite way, that is you can encrypt something with your private key and anyone can decrypt it with your public key. Doing this proves that you are the person that said the message.

You decide to send the number 10.

s = md mod n

s = 10{{ d }} mod {{ n }} = {{ sign (10) }}

Only you know your private key, so only you can produce s.

Anybody can then decrypt the message using your public key.

u = se mod n

u = {{ sign(10) }}{{ e }} mod {{ n }} = {{ unsign(sign(10)) }}

If you publish your message (10) along with the signed message (s), anyone can verify that it was you that sent the message. If someone else's private key was used, then um.

In real cryptography you wouldn't sign the actual message, especially if the message is long. RSA only works if the message is shorter than the modulus. Instead, you'd use a hash function first (which will always produce a relatively short message) and sign that.