# RSA: Part II

PDF of Eric’s handwritten notes is here.

### RSA Protocol

We will look at the setting where Alice has some message $m$ that she wants to send to Bob. She encodes this message using the public key that Bob publishes, which will be a pair of numbers $(N,e)$. Bob uses a secret, private key to decrypt incoming messages. This way, even if an eavesdropper gets the encrypted message, she can’t decipher the message provided that the encryption is secure.

Protocol:
Bob:
1) Choose two random $n$-bit primes $p$ and $q$ for $n \approx 2000$.
Choose a random $n$-bit $r$. Check if it’s prime (we’ll see how to do this in a moment). The probability that it will be prime is $\approx 1/n$.
2) Find $e$ which is relatively prime to $(p-1)(q-1)$
(i.e., find $e$ where gcd($e, (p-1)(q-1)$) = 1).
3) Let $N = pq$
4) Publish public key $(N,e)$
5) Bob’s private key is $d = e^{-1} \mod (p-1)(q-1)$, which we find using the extended Euclid algorithm.
Alice (wants to send a message $m$ to Bob):
1) Looks up Bob’s public key: $(N,e)$
2) Computes $y \equiv m^e \mod N$ using the fast modular exponentiation algorithm.
3) Sends $y$ to Bob.
Bob:
1) Gets $y$.
2) Computes $y^d \mod N$.

Note:  $de \equiv 1 \mod (p-1)(q-1)$.  Therefore, we know that $de = 1+k(p-1)(q-1)$ for some integer $k$.
Then $y^d \equiv (m^e)^d \equiv m^{de} \equiv m\times (m^{(p-1)(q-1)})^{k} \equiv m \mod N$ by Euler’s theorem when $gcd(m,N)=1$.
If gcd($n,N) >1$, then the statement is still true ($y^d \equiv m \mod N$) but to prove it we need to use the Chinese remainder theorem so we’ll skip that here.
Assumption: Given $N,e,y$, where $y\equiv m^e$, it is computationally difficult to determine $m$. The natural way would be to factor $N$, but there is no known polynomial time algorithm for factoring.

#### Other issues

If the message corresponds to a small number where $m^e < N$, then $mod N$ doesn’t do anything so to decrypt the message one just computes $m^{1/e}$ which is easy if $e$ is small.  To avoid this issue, Alice can choose a random string $r$ and pad the message. Alice sends two messages: $(m+r)^e$ and $r^e$, and Bob can decrypt both and use $r$ to get $m$.

We also need that $m < N$, but we can break a large message into smaller messages and encode each smaller message separately.

### Primality testing

How do we test whether or not some number $x$ is prime?
If $x$ is prime, then $\forall a\in \{1,...,x-1\}, a^{x-1} \equiv 1 \mod x$.
If $x$ is composite, then $\exists a$ where $a^{x-1}\not \equiv 1\mod x$. Such an $a$ will be a witness (or certificate) that $x$ is not prime. Our goal will be to find such an $a$, if it exists. We call $a$ a Fermat witness (FW).

To see why a composite $x$ always has such an $a$, consider some composite $x$ and some $a$ such that $gcd(a,x) = d>1$. (Note, $x$ is composite so $x$ has at least one factor $a$ and this factor $a$ has $gcd(a,x)>1$.)  Then $a^{x-1}$ and $x$ are multiples of $d$, say $a^{x-1}=di, x=dj$ for integers $i,j$.  Hence, $a^{x-1} \mod x = a^{x-1} - kx = d(i-kj)$ for some integer $k$.  Therefore,   $a^{x-1} \mod x$ is also a multiple of $d>1$, so $a^{x-1} \mod x \neq 1$.

This was a trivial Fermat witness because from the gcd statement, we see that $d$ divides $x$ already.

We are looking for nontrivial format witnesses (NFWs). We are looking for an $a$ where $gcd(a,x) = 1$ and $a^{x-1} \not \equiv 1 \mod x$.

Not every composite $x$ will have a NFW. The Carmichael numbers are composite $x$‘s with no NFWs.  Carmichael numbers are rare, the smallest one is 561. We will ignore these “pseudo-primes” for the moment and deal with them later.  It turns out for non-Carmichael composite numbers there are a lot of Fermat witnesses.  By definition, non-Carmichael composite numbers have at least one NFW, and from that we can prove the following lemma saying that there are a lot of Fermat witnesses.

#### Proof:

Let $a$ be a NFW such that $gcd(a,x) = 1$ and $a^{x-1} \not \equiv \mod x$. We will prove the lemma by breaking up $\{1,...,x-1\}$ into $W$ and $B$, where all $w\in W$ satisfy $a^{x-1} \not\equiv 1 \mod x$ and all $b\in B$ satisfy $b^{x-1} \equiv 1 \mod x$. (So $W$ are Fermat witnesses and $B$ is the “bad” set of non-witnesses.)  Then the lemma is equivalent to saying that $|W| \ge |B|$. To prove this, we will map elements in $B$ to elements in $W$ such that every element of $B$ is mapped to a unique element of $W$, and hence $W$ has at least as many elements as $B$, which proves the lemma.

The mapping that we use for any $b\in B$ is $f(b) = ab \mod x$. Then $(ab)^{x-1} \equiv a^{x-1}b^{x-1} \equiv a^{x-1} \not \equiv 1 \mod x$, so $f(b)\in W$.

Suppose two $b$‘s map to the same $w \in W$. Then $b'a \equiv ba \mod x$. Since $a$ is a NFW so $gcd(a,N)=1$ which means $a^{-1} \mod x$ exists, so we get $b' \equiv b\mod x$.  $\square$

That proves the theorem.  Now (ignoring Carmichael numbers) we have an algorithm to test primality.  Choose a random $a$ from $\left\{1,2,\dots,x-1\right\}$, and compute $a^{x-1} \mod x$ to see if this $a$ is a Fermat witness or not.  This will work with probability $\geq 1/2$ because of the lemma.  To boost the probability we instead choose $k$ numbers from  $\{1,2,\dots,x-1\}$ and test to see if any of these $k$ numbers are Fermat witnesses.  Here is the algorithm in detail:

Primality testing algorithm:

Input: $x$
Choose $a_1,...,a_k$ randomly from $\{1,...,x-1\}$.

For $i=1 \rightarrow k$:

Compute $a_i^{x-1} \mod x$

If $\forall i$, $a_i^{k-1} \equiv 1 \mod x$, output “$x$ is a prime number”
If $\exists i$ such that $a_i^{x-1} \not\equiv 1 \mod x$, then output “$x$ is composite ”.

If $x$ is prime, then Pr[algorithm says $x$ is prime] = 1. If $x$ is composite and not Carmichael, then Pr[algorithm is wrong] $\le (\frac{1}{2})^k$.

### Dealing with Carmichael numbers

Recall that we put off Carmichael numbers from earlier. Carmichael numbers are composite but have no NFW. For example, 561 is a Carmichael number.

For $x,N$ if $x^2 \equiv 1 \mod N$, then $x$ is a square root of $1 \mod N$. $x \equiv 1 \mod N$ and $x \equiv -1 \equiv N=1 \mod N$ are always square roots of $1 \mod N$. Any other square root is a nontrivial square root of $1 \mod N$.

#### Proof:

Take $z$ where $z^2 \equiv 1 \mod x$. Then $z^2 -1 \equiv 0 \mod x$. Then $z^2 -1 = kx$. Note that $z^2 = (z-1)(z+1)$. Then $z-1 \equiv 0 \mod x$ or $z+1 \equiv 0 \mod x$. Then $z \equiv 1\mod x$ or $z \equiv -1 \mod x$. Thus, $z$ is a trivial square root of $1 \mod x$.

Thus, to prove some number $N$ is not prime, it suffices to find a nontrivial square root of $1 \mod x$.

Suppose $N$ is composite and odd (if $N$ is even, then things are easy). Then $N-1$ is even, so $N-1 = 2^t v$, where $v$ is odd (we take out as many factors of 2 as possible). We will use Fermat’s test, which checks if $a^{N-1} \equiv 1 \mod N$ for a random $a\in \{1,...,N-1\}$. First, we compute $a^{N-1} \mod N$ by repeated squares:

$a^{v} \mod N$
then  $a^{2v} \mod N$
$a^{2^2v} \mod N$

$a^{2^tv} \mod N$

If $a^{n-1} \not \equiv 1 \mod N$, then we know that $N$ is composite by Fermat’s little theorem. Suppose $a^{n-1} \equiv 1 \mod N$. Then go back to the first point where $a^{2^i v} \equiv 1 \mod N$. We know that $a^{2^{i-1} v} \mod N$ is a square root of $1\mod N$. If this is non-trivial, then we have proved that $N$ is composite.

#### Fact: At least $3/4$ of the choices for $a$ in $\{1,...,x-1\}$ lead to a nontrivial square root in this manner.

This algorithm works for all composite numbers (including Carmichael numbers).

This leads us to a new algorithm that works for any composite number. We run our algorithm as before and find the first $i$ where $a^{2^i v}\not\equiv 1 \mod N$, but which is a square root of $1\mod N$. If it is $-1$, output “prime”. Else, output “not prime”.