Explain RSA

ExplainRSA is an interactive demonstration of the RSA Algorithm, written in Javascript.

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 φ (pronounced '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 }}

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

n = {{n}}

e = {{e}}

Private Key

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

d = {{d}}

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.

Pick the letter that Bob will send to you

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

Use the equation c = m^e 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 = c^d 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) }}