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 $\phi :\mathbb{\mathbb{N}}\to \mathbb{\mathbb{N}}$

$\phi (n)=n\prod _{p|n}(1-\frac{1}{p})$

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{array}{rl}\phi (pq)& =p\cdot q(1-\frac{1}{p})(1-\frac{1}{q})\\ & =(p-1)(q-1)\end{array}$

---

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{g}\mathrm{c}\mathrm{d}(e,\phi (n))=1$

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

In other words, $ed\equiv 1mod\phi (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}modn$
4. alice uses her secret key $(d,n)$ and raises it to the $d$ power:

   $C^d\equiv M^{ed}\equiv Mmodn$

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{\mathbb{Z}}}^{+}$ such that $ed=1+k\phi (n)$.

$M^{ed}\equiv Mmodn$

Proof

By the Chinese Remainder Theorem, we can show that

$\begin{array}{rl}{M}^{ed}& \equiv Mmodp\\ M^{ed}& \equiv Mmodq\end{array}$

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

By Fermat's Little Theorem,

$\begin{array}{c}M\equiv 0modp⟶M^{ed}\equiv Mmodp\\ M\equiv ̸0modp⟶M^{p-1}\equiv 1modp\end{array}$

Hence,

$\begin{array}{rl}{M}^{ed}& \equiv M^{1+k\phi (n)}\\ M^{ed}& \equiv M(M^{p-1}{)}^{k(q-1)}\\ M^{ed}& \equiv Mmodp\end{array}$