RSA

Proving correctness comes down to proving that \(D(E(x)) = x \; \forall x \in \{0, 1, \dots, N-1\}\).

Proof: Recall that \(E(x) = x^e \text{ mod } N\) and \(D(x) = y^d \text{ mod }N\) where \(y=x^e\). Also, \(d=e^{-1} \pmod{(p-1)(q-1)}\). So, it is equivalent to prove that \(x^{ed} \equiv x \pmod{N}\).

Equivalently, we have \(x(x^{ed-1} - 1) \equiv 0 \pmod{N}\). So, it is sufficient to prove that \(p | x(x^{ed-1}-1)\) and \(q | x(x^{ed-1}-1)\).

Note that \(ed = k(p-1)(q-1)+1\) for some \(k\in\mathbb{Z}\). Thus, \(ed-1 = k(p-1)(q-1)\). In other words, we now want to prove that \(p | x(x^{k(p-1)(q-1)}-1)\) and \(q | x(x^{k(p-1)(q-1)}-1)\).

If \(p|x\), then we are done. Otherwise, we need to prove that \(p | x^{k(p-1)(q-1)}-1\). Since we know that \(\text{gcd}(p,x)=1\), we know by Fermat’s Little Theorem that \(x^{p-1} \equiv 1 \pmod{p}\) for any prime \(p\). Then:

\begin{align} x^{k(p-1)(q-1)}-1 \equiv \left(x^{p-1}\right)^{k(q-1)}-1 \equiv 1-1 \equiv 0 \pmod{p} \notag \end{align}

Thus, \(p|x^{k(p-1)(q-1)}-1\). We can use the same argument to show the same for \(q\), and we are done. \(\square\)

Alternate Proof (Rivest-Shamir-Adleman): Recall that Euler’s Theorem states that \(x^{\phi (m)} \equiv 1 \pmod{m}\) for all \(x\) such that \(m\) and \(x\) are coprime. Then, when \(m=N=pq\), we have \(\phi(N)=pq-p-q+1 = (p-1)(q-1)\). This is because the only numbers less than \(N\) that are not coprime to \(N\) are the multiples of \(p\) and the multiples of \(q\).

Thus, by Euler’s Theorem, we have:

\begin{align} x^{ed} \equiv x^{k(p-1)(q-1)+1} \equiv \left(x^{(p-1)(q-1)}\right)^kx\equiv x \pmod{N} \notag \end{align}

For the special case \(x\) where \(x\) and \(N\) are not coprime, then we have \(p|x\) and \(q|x\) as before and it is true. \(\square\)

We want to argue that Eve learns nothing about the message \(x\) by observing \(E(x), N, e\). There are several approaches that Eve can take, but we can show that each of these is not a problem:

1. Eve can try guessing \(x\). However, if we are working with \(1024\) bit numbers, there are \(2^{1024} \approx 10^{308}\) possibilities for \(x\), which is clearly not feasible.
2. Eve can try to figure out the factors \(p\) and \(q\). However, there is no known way to efficiently factor \(N\), especially when \(N\) is very large.
3. Eve can try to solve the equation \(x^e \equiv y \pmod{N}\) for \(x\). However, this is equivalent to the discrete log problem, which is known to be very hard.

In other words, it is realistically infeasible (basically impossible) for these attacks to succeed due to the amount of computation required to calculate any of these values from what is publicly known. However, a theoretical quantum computer can efficiently factorize large numbers.° This has led to a new field of post-quantum cryptography.

Efficiency of the algorithm comes down to two main parts: computing \(e, d, E(x), D(y)\), and choosing the large primes in order to compute those.

1. Computing \(e, d, E(x), D(y)\): for \(e\), we can trivially choose anything coprime to \((p-1)(q-1)\) (often this is \(2^{16} +1\), which is prime). For \(d\), we can use extended Euclid to find the inverse of \(e\). Finally, for \(E(x)\) and \(D(y)\), we can efficiently calculate these via repeated squaring.
2. Choosing large primes: The following algorithm works to choose a large prime. First, we pick a random \(1024\) bit number. Test to see if the number is prime; if it is, we are done, and if it isn’t, we just try again. We can see that this is efficient because the Prime Number Theorem tells us that on average, \(1\) in every \(\text{ln }m\) numbers is prime.

ALGORITHM Fermat(n)
CHOOSE a FROM {2, 3, ..., n-1} AT RANDOM
IF gcd(a, n) != 1
    OUTPUT "not prime"
ELSE IF a ** (n - 1) != 1 (mod n)
    OUTPUT "not prime"
ELSE
    OUTPUT "prime"