RSA (Rivest–Shamir–Adleman)

To set the context clear, RSA in fact can refer not just to Asymmetric Encryption but also Digital Signature (which we would cover in later chapter). Here, we will only focus on the Encryption/Decryption protocol using RSA.

What can this protocol do?

RSA allows one party to encrypt a message with a recipient's public key, ensuring that only the recipient (who possesses the private key) can decrypt it.

Why Matters?

RSA is widely used in securing email information. When Alice wants to send her email to Bob, she makes sure that only Bob can read her email by getting Bob's public key (from a key's server or Bob's email signature). Then, she encrypts her email message with this public key, hence only the one with Bob's private key can decrypt and read this message! (Hopefully, the only one having Bob's private key is Bob)

Setup

Private Key and Public Key Generation

• Choose Two Large Prime Numbers:

Select two large primes $p$ and $q$. Their product $n=p⋅q$ will define the modulus. $n$ must be large (at least 2048 bits) to ensure security.

• Calculate Euler’s Totient:

Compute $\phi(n) = (p-1)(q-1)$

• Choose Public Exponent $e$

Select an integer $e$ such that $1< e < \phi(n)$ and gcd$(e, \phi(n))$ = 1. A common choice is $e=65537$, as it is efficient for encryption and verification.

• Calculate Private Exponent $d$

Compute $d$, the modular multiplicative inverse of $e$ modulo $\phi(n)$ This satisfies: $d⋅e≡1 (mod ϕ(n)).$ Note that this step is pretty easy due to a thing called "Extended Euclidean Algorithm" (more on this later..)

Key Pair:

• Public Key: $(e,n)$

• Private Key: $(d,n)$

Encryption

• Represent the message $M$ as an integer $m$ such that $0≤m<n.$

• Compute the ciphertext $c$ using the recipient’s public key: $c≡m^e\ mod\ n$

Decryption

• Use the private key to compute the original message: $𝑚 ≡ c^d\ mod\ n$

• Convert $m$ back to the original message $M$