CSCE 222 Lecture 34

(and 35)« previous | Friday, April 29, 2011 | next »

RSA Public Key Encryption

RSA stands for last names of inventors

RSA invented to solve problem of easy crackability of bitstreams. Basically It establishes a common secret between two parties. But before we begin…

Euler's Totient Function

Denoted by $\varphi :\mathbb {N} \to \mathbb {N}$

$\varphi (n)=n\prod _{p|n}\left(1-{\frac {1}{p}}\right)$

When the product ranges over all primes $p$ that divide $n$ (prime factorization).

Example

Suppose $n$ is a product of two distinct primes $p$ and $q$, then:

${\begin{aligned}\varphi (pq)&=p\cdot q\left(1-{\frac {1}{p}}\right)\left(1-{\frac {1}{q}}\right)\\&=(p-1)(q-1)\end{aligned}}$

---

Key Generation

Alice selects two distinct large (2000 bits) prime numbers $p$ and $q$, and computes their product $n=pq$.

She selects an odd integer $e>0$ such that $\mathrm {gcd} (e,\varphi (n))=1$

She then computes positive integers $d$ and $k$ such that $ed-k\varphi (n)=1$.

In other words, $ed\equiv 1\mod {\varphi (n)}$

She publishes the pair $P=(e,n)$ ($p$ and $q$ are kept secret because factoring $n$ is very difficult to do)

Encryption and Decryption

Overview: Suppose we want to send Alice a message. This message is chopped into blocks of 1024 bits and encrypt it using the public key. To decrypt it, Alice uses her private key.

Process:

1. For simplicity, we'll assume that the message is encoded as an integer $M$ in the range [2,n).
2. If Bob wants to send the message $M$ to Alice, he gets the public key $P=(e,n)$…
3. and raises it to the $e$, modulo $n$: $C=M^{e}\mod {n}$
4. alice uses her secret key $(d,n)$ and raises it to the $d$ power:

   $C^{d}\equiv M^{ed}\equiv M\mod {n}$

Correctness of RSA

Why does this work?

Prerequisites:

• Fermat's Little Theorem
• Chinese Remainder Theorem

The RSA Algorithm States:

• Let $n=pq$ be a product of two distinct primes $p$ and $q$.
• Let $e,d,k\in \mathbb {Z} ^{+}$ such that $ed=1+k\varphi (n)$.

$M^{ed}\equiv M\mod {n}$

Proof

By the Chinese Remainder Theorem, we can show that

${\begin{aligned}M^{ed}&\equiv M\mod {p}\\M^{ed}&\equiv M\mod {q}\end{aligned}}$

since $\mathrm {gcd} (p,q)=1$ are distinct primes.

By Fermat's Little Theorem,

${\begin{matrix}M\equiv 0\mod {p}\quad \longrightarrow \quad M^{ed}\equiv M\mod {p}\\M\not \equiv 0\mod {p}\quad \longrightarrow \quad M^{p-1}\equiv 1\mod {p}\end{matrix}}$

Hence,

${\begin{aligned}M^{ed}&\equiv M^{1+k\varphi (n)}\\M^{ed}&\equiv M(M^{p-1})^{k(q-1)}\\M^{ed}&\equiv M\mod {p}\end{aligned}}$