# Apr 6. RSA

RSA

We have the following setup for the RSA algorithm:

• Pick two distinct primes $p, q$.
• Compute $n = pq$.
• A message $m$ is a number such that $1 \le m \le n-1$.
• Let $k$ be a number relatively prime to $(p-1)(q-1)$.
• Note that $\exists l$ such that $kl = 1 \pmod{(p-1)(q-1)}$

The following are publicly available: $n, k$. Here $k$ is also called the public key and $l$ is the private key. The following is the encryption algorithm for message $m$.

Encrypt(m, n, k):

• Return $M = m^k \pmod{n}$.

Decrypt(m, n, l):

• Return $m = M^l \pmod{n}$.

Let us prove some of the assumptions we made in the algorithm.

Claim: For any $k$ relatively prime to $(p-1)(q-1)$, there exists $l$ such that $kl = 1 \pmod{(p-1)(q-1)}$.

Given $k$, we can compute $l$ in polynomial time using Euclid’s algorithm for computing gcd. (We’ll do this on Friday).

We will need the following theorem also called the Fermat’s little theorem.

Theorem (Fermat’s little theorem): For any prime $p$ then for any integer $a$, $a^p = a \pmod{p}$.

Proof: If $p$ divides $a$ then both sides are $0$. If $p$ does not divide $a$ then consider the sequence $S = \{a, 2a, 3a, \cdots, (p-1)a\}$ modulo $p$. We claim that this set is the same as $\{1, 2, 3, \cdots, p-1\}$. Clearly no number in the set $S$ can be $0$. Further if $ra = sa \pmod{p}$ then $p$ divides $(r-s)a$. Since $p$ does not divide $a$, it follows that it must divide $(r-s)$ and so $r = s$. Take the product of the two sets, we get $a^{p-1} \prod_{i=1}^{p-1} = \prod_{i=1}^{p-1} \pmod{p}$. Thus $a^{p-1} = 1 \pmod{p}$ implying the theorem.

Claim: Let $n = pq$, $p \neq q$ and $k$ be relatively prime to $(p-1)(q-1)$ and $kl = 1 \pmod{(p-1)(q-1)}$. Then for any $m$, if $M = m^k \pmod{n}$ then $M^l = m \pmod{n}$.

Proof: We claim that $m^{kl} = m \pmod{p}$. Note that since $kl = 1 \pmod{(p-1)(q-1)}$, it follows that $kl = 1 + t(p-1)(q-1)$ for some $t$. Thus $m^{kl} = m (m^{p-1})^{t(q-1)} = m \pmod{p}$.By symmetry $m^{kl} = m \pmod{q}$. We claim that this implies $m^{kl} = m \pmod{pq}$. Note that if $x$ is a multiple of $p$ and a multiple of $q$ where $p$ and $q$ are relatively prime then $x$ must be a multiple of $pq$. Thus setting $x = m^{kl} - m$ we infer that $m^{kl} = m \pmod{pq}$. Since $n = pq$, we are done.

Note that one can show that factoring reduces to decrypting the message in the absence of the knowledge of $l$. Thus the security of the RSA cryptosystem is based on the hardness of the factoring problem.