RSA Algorithm
Module 03 / Lesson 02
Visual Explanation
The Concept of Asymmetric Encryption
The RSA algorithm (Rivest–Shamir–Adleman) is the foundation of modern secure communication. Unlike DES, it uses two different keys: a Public Key to encrypt data and a Private Key to decrypt it.
Key Generation Process:
- Choose two large prime numbers $p$ and $q$.
- Calculate $n = p \times q$. ($n$ is the modulus for both keys).
- Calculate $\phi(n) = (p-1)(q-1)$.
- Choose an integer $e$ (Public Exponent) such that $GCD(e, \phi(n)) = 1$.
- Calculate $d$ (Private Exponent) such that $(d \times e) \equiv 1 \pmod{\phi(n)}$.
Encryption & Decryption:
Encryption: $C = M^e \pmod{n}$
Decryption: $M = C^d \pmod{n}$
Decryption: $M = C^d \pmod{n}$
Python Implementation (RSA Logic)
def rsa_demo():
# 1. Simple Primes
p, q = 61, 53
n = p * q
phi = (p-1) * (q-1)
# 2. Public Key (e, n)
e = 17
# 3. Private Key (d, n)
# Finding d (multiplicative inverse)
def get_d(e, phi):
for d in range(1, phi):
if (e * d) % phi == 1:
return d
return None
d = get_d(e, phi)
# 4. Message
m = 65 # Example Character 'A'
print(f"Original Message: {m}")
# Encryption
c = pow(m, e, n)
print(f"Encrypted (Cipher): {c}")
# Decryption
m_decoded = pow(c, d, n)
print(f"Decrypted (Plain): {m_decoded}")
rsa_demo()