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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (d,n)} and raises it to the Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d} power:

   Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n=pq} be a product of two distinct primes Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle q} .
• Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e, d, k \in \mathbb{Z}^+} such that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle ed=1+k\varphi(n)} .

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

Proof

By the Chinese Remainder Theorem, we can show that

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} M^{ed} & \equiv M \mod{p} \\ M^{ed} & \equiv M \mod{q} \end{align}}

since Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathrm{gcd}(p,q)=1} are distinct primes.

By Fermat's Little Theorem,

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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}}$