2. RSA

RSA is an asymmetric encryption method using trapdoor function, which is discrete logarithm, to realize asymmetric computation.

2.1. Knowledge required

2.1.1. Problem

Alice wants to receive message \(M\) from Bob. She also knows that Eve is monitoring their conversation. Alice decides to use RSA to encrypt the transmission.

2.1.2. How It Works

2.2. Preparation Work

Alice chooses two large prime numbers \(p\) and \(q\). The modulo \(N = pq\). Euler’s Totient function, \(\phi(N) = (p-1)(q-1)\).

Alice then chooses public key \(e\) such that \(1 \leq e \leq \phi(N)\) and \(gcd(e, \phi(N)) = 1\). \(1 \leq e \leq \phi(N)\) is easy to understand. \(gcd(e, \phi(N)) = 1\) is to make sure the multiplicative inverse of \(e\) in modulo \(\phi(N)\) exists.

Alice computes the multiplicative inverse \(d\) such that \(ed \equiv 1 ~mod~\phi(N)\). \(d\) is the private key.

Alice tells Bob \(N, e\) and keeps \(p, q, d\) private.

2.3. Encryption

Bob sends \(C = M^e ~mod~N\)

2.4. Decryption

Alice recovers the message by doing \(M = C^d~mod~N\).

2.4.1. Feasibility

  • Let’s check why Alice can get \(M\) from \(C\) using \(d\).

\[\begin{split} C^d ~mod~N =& (M^e)^d~mod~N\\ =& M^{ed}~mod~N\\ =& M^{k\phi(N) + 1}~mod~N\\ =& M (M^{\phi(N)})^k~mod~N\\ =& M \cdot 1~\mod~N\end{split}\]

Recall that \(M^{\phi(N)}~mod~N = 1\) according to Euler’s theorem.

  • Let’s discuss why Eve cannot decrypt the message easily.

Eve knows \(C, e, N\). It doesn’t know \(p, q, \phi(N), d\). If Eve wants to decode the message, he has to do factorization of \(N\) which is difficult because the two factors \(q\) and \(p\) are large. Also, \(d\) is not small, it also takes Eve a lot of time to brutal force \(d\).

2.4.2. Tips

Don’t choose a small \(e\), because the adversary can brutally try \(C^{-1}, C^{-2}, \cdots, C^{-3}\) by multiplying \(C^{-1}\) to the previous value.

Don’t reuse \((p, q, e)\), otherwise there is a risk of leaking private keys by conducting Indistinguishable Chosen Ciphertext Attack.