RSA Encryption

RSA is like putting information into a locked mailbox. Anyone can encrypt, but only the person with the key can open and read its contents.

Setting up our encryption / decryption system

Before we start sending messages, we need to do some setup. We need to establish a system that allows us to encrypt and decrypt.

  1. First, we arbitrarily pick a set of primes pp and a qq and we set N=pqN = pq. Often times, pp and qq are very large (512 bits each) and we don't want the hacker to know them.
N=pq p and q arbitrarily chosenN = pq \quad \text{ p and q arbitrarily chosen}
  1. Second, we pick an encryption key ee relatively prime to (p1)(q1)(p-1)(q-1).
emod(p1)(q1)e is arbitrarily chosene \mod{(p-1)(q-1)} \quad \quad e \text{ is arbitrarily chosen}

Our public key, something we distribute to anyone, is (N,e)(N,e). With these two numbers, anyone can have the power to encrypt information into a specific format only we can decrypt.

  1. Now we derive a decryption key. We don't want the hacker to know this number!
d=e1mod(p1)(q1)d = e^{-1} \mod{(p-1)(q-1)}

Note, that ee and dd are derived in mod(p1)(q1)\mod{(p-1)(q-1)}. The reason will become more apparent later in the proof. The decryption key is the inverse of the encryption key, which is astronomically hard for a classical computer to create without knowing p,qp, q. This decryption key is kept only for us to know.

To recap, we have our public and private keys!

Encrypting / Decrypting Messages

Let's say we have a message xx in the modspace of NN.

  • Encrypting: xemodNx^e \mod{N} is our encrypted message
  • Decrypting: (xe)d=xedmodN=xmodN(x^{e})^{d} = x^{ed} \mod{N} = x \mod{N} is our decrypted message

It's that simple! Just by using messageencryption key\text{message}^{\text{encryption key}}, we have our encrypted message. And with received messagedecryption key\text{received message}^{\text{decryption key}}, we'd have our original message! We use modspace because computers have finite memory.

Why does this work?

We've setup our system such that:

  • ed1mod(p1)(q1) ed \equiv 1 \mod{(p-1)(q-1)}
    • This is because our setup:
      • d=e1mod(p1)(q1)d = e^{-1} \mod{(p-1)(q-1)}
      • emod(p1)(q1)e \mod{(p-1)(q-1)}

Using this property we can rewrite the expression above as (will come in handy later):

  • ed=k(p1)(q1)+1ed = k(p-1)(q-1) + 1

We can use the previous relationship to rewrite the message after applying a decryption key:

  • xedxk(p1)(q1)+1xmodpqx^{ed} \equiv x^{k(p-1)(q-1) + 1} \equiv x \mod{pq}

In this form, we can reduce using the following.

  • x(xk(q1)(p1))x0modp x (x^{k(q-1)(p-1)}) - x \equiv 0 \mod{p}
    • If xx is not a multiple of pp, then we can use Fermat's Little Theorem to reduce the expression.
      x((xk(q1))p11)0modpx(0)0modpx ((x^{k(q-1)})^{p-1} - 1) \equiv 0 \mod{p} \\ x (0) \equiv 0 \mod{p}
    • If xx is a multiple y pp, then expression reduces to 00 by definition
  • x(xk(p1))(q1)x0modq x (x^{k(p-1)})^{(q-1)} - x \equiv 0 \mod{q}
    • By symmetrical argument as above.

It is divisible by both pp and qq invididually. Since pp and qq are primes it must be divisible by their product, pq=Npq = N