rsa theory

Public Key Cryptosystem

A public key cryptosystem is a crypotsystem such that there are two keys, a public key which anyone can know used for encoding, and a private key which only a decoder knows .

Each person has a pair of keys $(e, d)$ , and publishes that in a directory which everyone can see, and they keep their private key $d$ on their system.

If A wants to send a message to B, they look up B's public key in the directory and then encrypt their plaintext message using it to produce the ciphertext.

In order to decipher the message, one has to decrypt it using B's private key which means that no-one else can read messages intended for B.

RSA Protocol

Suppose you want to allow someone to send you a message on your computer securely using the RSA protocol, then you do the following:

Start with two large primes $p, q$ . Compute $n = p q$ and $ϕ (n) = (p - 1) (q - 1)$ .
Choose some $1 \leq e \leq ϕ (n)$ relatively prime to $ϕ (n)$ and compute an inverse $d$ to $e$ modulo $ϕ (n)$ (i.e., $d e \equiv 1 (mod ϕ (n)))$ .
The public key is $(e, n)$ , the private key is $d$ .
From the point of view of a sender, to send a message, they take that message and break it into blocks which can be encoded as numbers $1 \leq m \leq n$ . They send each block as a ciphertext given by $c : = m^{e} % n$
To decipher a ciphertext $c$ , compute $m \equiv c^{d} (mod n)$ .

Why Raising the Ciphertext to the Power of The Private Key Yields the Plaintext

Suppose that

c

is the ciphertext and

d

is the private key then the plaintext is given by

c^{d} % n

Recall that

c = m^{e} % n

therefore we have that

c^{d} \equiv {(m^{e})}^{d} = m^{d e}

At the same time we know that

d e \equiv 1 (\mod ϕ (n))

therefore

d e = 1 + k ϕ (n)

so that

m^{d e} = m^{1 + k ϕ (n)} = m {(m^{ϕ} (n))}^{k} \equiv m \cdot 1 = m (\mod n)

🏗️ ΘρϵηΠατπ🚧 (under construction)

🏗️ $Θ ρ ϵ η Π α τ π$ 🚧 (under construction)