RSA Encryption

RSA (Rivest–Shamir–Adleman) is the algorithmic backbone of modern digital security. It relies on the practical difficulty of factoring the product of two large prime numbers.

1. The Key Generation Process

The security of RSA rests on three main steps:

1. Choose two large primes $p$ and $q$.
2. Compute $n = pq$. This $n$ is used as the modulus for both public and private keys.
3. Compute Euler’s totient function $\phi(n) = (p-1)(q-1)$.
4. Choose an integer $e$ such that $1 < e < \phi(n)$ and $\gcd(e, \phi(n)) = 1$.
5. Determine $d$ as $d \equiv e^{-1} \pmod{\phi(n)}$.

def gcd(a, b):
  while b:
      a, b = b, a % b
  return a

def extended_gcd(a, b):
  if a == 0: return b, 0, 1
  d, x1, y1 = extended_gcd(b % a, a)
  x = y1 - (b // a) * x1
  y = x1
  return d, x, y

def mod_inverse(e, phi):
  d, x, y = extended_gcd(e, phi)
  return x % phi

p, q = 61, 53
n = p * q
phi = (p-1) * (q-1)
e = 65537 # Common choice for e
d = mod_inverse(e, phi)

print(f"Public Key (e, n): ({e}, {n})")
print(f"Private Key (d, n): ({d}, {n})")

2. Encryption and Decryption

A message $M$ is encrypted into ciphertext $C$ using the public key $(e, n)$: $C \equiv M^e \pmod n$

The original message is recovered using the private key $(d, n)$: $M \equiv C^d \pmod n$

# Use the keys from the previous step
p, q = 61, 53
n, e = p*q, 65537
d = 2753 # Computed in step 1

def encrypt(m, e, n):
  return pow(m, e, n)

def decrypt(c, d, n):
  return pow(c, d, n)

message = 42
ciphertext = encrypt(message, e, n)
decrypted = decrypt(ciphertext, d, n)

print(f"Original: {message}")
print(f"Encrypted: {ciphertext}")
print(f"Decrypted: {decrypted}")

3. Why it Works (Euler’s Theorem)

RSA works because $M^{ed} \equiv M^{k\phi(n) + 1} \equiv M \pmod n$. According to Euler’s Totient Theorem, if $\gcd(M, n) = 1$, then $M^{\phi(n)} \equiv 1 \pmod n$.

4. Key Takeaways

• One-way function: Multiplication of primes is easy, but factoring their product is hard.
• Asymmetric: You share the public key with everyone but keep the private key secret.