Encryption and Decryption Explained

Due to these properties:

• Prime numbers / prime factors
• Modular multiplicative inverses
• Big freaking numbers

RSA is a secure algorithm that allows us to encrypt and decrypt messages.

Encryption Formula

c = m^e (mod n)

• c is the ciphertext
• m is the message
• e is the public key exponent
• n is the public key modulus

Why Is “c” a Secure Ciphertext?

It's secure because it's not possible to get the original message m back from c. There is no mathematical inverse of this formula without knowing the private key d.

Decryption Formula

m = c^d (mod n)

• m is the message
• c is the ciphertext
• d is the private key exponent
• n is the public key modulus

First, let's remember how d was generated: it's the modular multiplicative inverse of e in "mod phi":

ed ≡ 1 (mod ϕ(n))

Which, according to what we learned about these equations being equivalent:

n ≡ r (mod q)
n = qk + r

Can be converted to this equation for the key:

ed = ϕ(n)k + 1

Next, remember that the equation for decryption is:

c^d (mod n)

Which, through substitution of the encryption formula, is the same as:

(m^e)^d (mod n)

Which is the same as:

m^(ed) (mod n)

So we can plug the key equation into the ed in the decryption equation:

m^(ϕ(n)k + 1) (mod n)

Which can be rewritten as:

(m^(ϕ(n)))^k * m (mod n)

Euler's Theorem tells us that:

m^ϕ(n) ≡ 1 (mod n)

So we can rewrite the equation as:

1^k * m (mod n)

Which is just:

m (mod n)

Which is the original unencrypted message m!

Here's another good reference if you're curious to read more.