RSA Cryptosystem

17 Dec 2021

Notes Cryptography RSA Cryptosystem

§ 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 Fp\mathbb{F}_p will create an injective or a surjective endomorphism.

We now check in F11\mathbb{F}_{11} exponent values of 55 and 77:

15≡117≡125≡1027≡735≡137≡945≡147≡555≡157≡365≡1067≡875≡1077≡685≡1087≡295≡197≡4105≡10107≡10\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 77, we see that we get an injection from a↣a7a \rightarrowtail a^7, which also happens to be a bijection; i.e. raising a base aa by 77 permutes the residues modulo 1111. We then notice that φ(11)=10\varphi(11) = 10 and that (5,φ(11))≠1(5, \varphi(11)) \neq 1; therefore, any exponent coprime to the totient will produce a unique mapping.

Sps. a,m∈Na, m \in \mathbb{N} and that (a,m)=1(a, m) = 1. Then, if k,k‾∈Zφ(m)k, \overline{k} \in \mathbb{Z}_{\varphi(m)} such that kk‾≡1(modφ(m))k\overline{k} \equiv 1 \pmod{\varphi(m)}, then akk‾≡maa^{k\overline{k}} \equiv_m a.

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

akk‾≡(aφ(m))ℓ⋅a≡a(modm).a^{k\overline{k}} \equiv \left(a^{\varphi(m)}\right)^{\ell}\cdot a\equiv a \pmod{m}.

Let (k,φ(m))=1(k, \varphi(m)) = 1, and (a,m)=1(a, m) = 1. Then, the mapping a↣aka \rightarrowtail a^k permutes the residues modulo mm (excluding 0). As a result, aik≡majk  ⟺  ai≡maja_i^k \equiv_m a_j^k \iff a_i \equiv_m a_j.

ai≡aikk‾≡(aik)k‾≡(ajk)k‾≡aj(modm).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,qp, q and let m=pqm = pq.
  2. Alice can easily compute φ(m)=(p−1)(q−1)\varphi(m) = (p-1)(q-1).
  3. Then, Alice chooses a random k∈(0…φ(m))k \in (0\dots\varphi(m)) satisfying (k,φ(m))=1(k, \varphi(m)) = 1.
  4. Finally, Alice makes the numbers m,km, k available publicly.

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

ak(modm).a^k \pmod{m}.

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

(ak)k‾≡a(modm).\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 ∀n,λ(n)∣φ(n)\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 λ(n)\lambda(n) is a divisor of φ(n)\varphi(n), it is sometimes less than φ(n)\varphi(n), thus using the Carmichael function reduces the amount of computations in RSA.