Motivation§

RSA is a public-key cryptosystem that differs from Elgamal in that it does not rely on the difficulty of the discrete logarithm problem, but rather factorization.

Modular Exponentation§

RSA works by raising the message to a power mod p. We first want to inspect whether raising a message to an exponent over $\mathbb{F}_p$ will create an injective or a surjective endomorphism.

We now check in $\mathbb{F}_{11}$ exponent values of $5$ and $7$:

$$ \begin{array}{ r c l c r c l } 1^5 \mkern-.8em&\equiv& \mkern-.8em1&\quad&1^7 \mkern-.8em&\equiv&\mkern-.8em 1\\ 2^5 \mkern-.8em&\equiv& \mkern-.8em10&&2^7 \mkern-.8em&\equiv&\mkern-.8em 7\\ 3^5 \mkern-.8em&\equiv& \mkern-.8em1&&3^7 \mkern-.8em&\equiv&\mkern-.8em 9\\ 4^5 \mkern-.8em&\equiv& \mkern-.8em1&&4^7 \mkern-.8em&\equiv&\mkern-.8em 5\\ 5^5 \mkern-.8em&\equiv& \mkern-.8em1&&5^7 \mkern-.8em&\equiv&\mkern-.8em 3\\ 6^5 \mkern-.8em&\equiv& \mkern-.8em10&&6^7 \mkern-.8em&\equiv&\mkern-.8em 8\\ 7^5 \mkern-.8em&\equiv& \mkern-.8em10&&7^7 \mkern-.8em&\equiv&\mkern-.8em 6\\ 8^5 \mkern-.8em&\equiv& \mkern-.8em10&&8^7 \mkern-.8em&\equiv&\mkern-.8em 2\\ 9^5 \mkern-.8em&\equiv& \mkern-.8em1&&9^7 \mkern-.8em&\equiv&\mkern-.8em 4\\ 10^5 \mkern-.8em&\equiv& \mkern-.8em10&&10^7 \mkern-.8em&\equiv&\mkern-.8em 10 \end{array} $$

Using $7$, we see that we get an injection from $a \rightarrowtail a^7$, which also happens to be a bijection; i.e. raising a base $a$ by $7$ permutes the residues modulo $11$. We then notice that $\varphi(11) = 10$ and that $(5, \varphi(11)) \neq 1$; therefore, any exponent coprime to the totient will produce a unique mapping.

Lemma 13.1

Sps. $a, m \in \mathbb{N}$ and that $(a, m) = 1$. Then, if $k, \overline{k} \in \mathbb{Z}_{\varphi(m)}$ such that $k\overline{k} \equiv 1 \pmod{\varphi(m)}$, then $a^{k\overline{k}} \equiv_m a$.

Using Euler’s theorem and the fact that there exists some $\ell$ such that $k\overline{k} = 1 + \ell\varphi(m)$, we get that

$$ a^{k\overline{k}} \equiv \left(a^{\varphi(m)}\right)^{\ell}\cdot a\equiv a \pmod{m}. $$

Lemma 13.2

Let $(k, \varphi(m)) = 1$, and $(a, m) = 1$. Then, the mapping $a \rightarrowtail a^k$ permutes the residues modulo $m$ (excluding 0). As a result, $a_i^k \equiv_m a_j^k \iff a_i \equiv_m a_j$.

$a_i \equiv a_i^{k\overline{k}} \equiv \left(a_i^k\right)^{\overline{k}} \equiv \left(a_j^k\right)^{\overline{k}} \equiv a_j \pmod{m}.$

The RSA Algorithm§

RSA

Setup:

  1. Alice chooses two distinct large primes $p, q$ and let $m = pq$.
  2. Alice can easily compute $\varphi(m) = (p-1)(q-1)$.
  3. Then, Alice chooses a random $k \in (0\dots\varphi(m))$ satisfying $(k, \varphi(m)) = 1$.
  4. Finally, Alice makes the numbers $m, k$ available publicly.

Encryption: If Bob wants to send a message $a$ to Alice, he uses Alice’s public key values and sends to Alice:

$$ a^k \pmod{m}. $$

Decryption: Alice can decrypt Bob’s message by computing $\overline{k}$ via Euclidean algorithm that satisfies Lemma 13.1. Alice then decrypts the message by computing

$$ \left(a^k\right)^{\overline{k}} \equiv a \pmod{m}. $$

As mentioned in the Totient function discussion, the Carmichael function shows up in lieu of Euler’s totient function in modern formulations of the RSA algorithm.

It can be shown that $\forall n, \lambda(n) \vert \varphi(n)$, meaning that the RSA algorithm works regardless of choice of totient functions. The RSA algorithm generates equivalent keys with either Carmichael or Euler functions, ceteris paribus.

It’s favorable to use the Carmichael function due to the fact that it generates a number that is a divsor of the Euler’s totient. As $\lambda(n)$ is a divisor of $\varphi(n)$, it is sometimes less than $\varphi(n)$, thus using the Carmichael function reduces the amount of computations in RSA.