RSA Algorithm Explained: Step-by-Step Manual Calculation

Understanding RSA Encryption Fundamentals

Public-key cryptography seems magical, but its elegance lies in mathematical principles. After analyzing this cryptographic demonstration, I believe the core insight is how prime number properties create secure communication. When you need to grasp asymmetric encryption, the RSA algorithm remains foundational. We'll walk through manual calculations using small numbers (P=3, Q=11) to reveal the mechanics without advanced math.

Why Prime Numbers Matter

RSA relies on prime factorization difficulty. Primes like 3 and 11 are whole numbers divisible only by themselves and 1. Multiplying them creates the RSA modulus (n = P × Q). Here, n=33 has only two prime factors—a critical property. Larger primes make factorization exponentially harder, which is why modern RSA uses 2048-bit numbers. I've seen students underestimate this, but remember: security scales with prime size.

Generating RSA Keys Step-by-Step

Calculating Euler's Totient

The totient (φ) counts numbers co-prime to n up to n-1. Two numbers are co-prime if they share no common factors except 1. For n=33, φ = (P-1)×(Q-1) = 2×10=20. This means 20 numbers between 1-33 are co-prime with 33. Non-prime pairs like 8 and 9 can be co-prime too—their factors (1,2,4,8 and 1,3,9) intersect only at 1.

Selecting Public Key Components

Choose a public exponent (k) that's prime and co-prime with φ. Options between 1-20 include 3,7,11,13,17,19. Avoid 5 (shares factor 5 with 20). Using k=7 gives the public key: (n=33, k=7). In practice, 65537 is common for efficiency, but small numbers clarify the logic.

Deriving the Private Key

Find the modular inverse (j) where (k × j) mod φ = 1. With k=7 and φ=20:

7×1 mod 20 = 7 ✗
7×2 mod 20 = 14 ✗
7×3 mod 20 = 21 mod 20 = 1 ✓
Thus j=3 forms the private key: (n=33, j=3). The extended Euclidean algorithm solves this for large numbers, but trial works here.

Encrypting and Decrypting Messages

Encryption Process

Convert "SECRET" to numerical positions (S=19, E=5, C=3, R=18, E=5, T=20). Encrypt each using public key:

Compute ciphertext = plaintextᵏ mod n
S: 19⁷ mod 33 = 893871739 mod 33 = 13
Repeat for all letters: [13,14,9,6,14,26]

Decryption Process

Decrypt ciphertext using private key:

Compute plaintext = ciphertextʲ mod n
13³ mod 33 = 2197 mod 33 = 19 (S)
Regenerated original values: [19,5,3,18,5,20]. Trapdoor functionality allows swapping keys: encrypting with j=3 and decrypting with k=7 works identically.

Scaling Challenges with Larger Primes

Using P=47 and Q=61:

n = 47×61 = 2867
φ = 46×60 = 2760
k=13 (co-prime choice)
j solves 13×j mod 2760=1 → j=1183
Encrypting "A" (value 1): 1¹³ mod 2867=1 (trivial). But encrypting "B" (2): 2¹³=8192 → 8192 mod 2867=2459. Decrypting 2459¹¹⁸³ mod 2867 requires computational power beyond spreadsheets. This illustrates real-world RSA demands optimized algorithms.

Practical Implementation Guide

Action Checklist

Select two distinct primes (start small like 5 and 13)
Calculate n = P × Q and φ = (P-1)(Q-1)
Choose k >1 co-prime with φ
Derive j using modular inverse
Test encryption/decryption with short messages

Recommended Resources

Cryptool 1: Open-source for visualizing RSA with large numbers (ideal for beginners)
Python Cryptography Library: For real implementations (requires coding experience)
"Understanding Cryptography" by Paar & Pelzl: Best academic reference for mathematical proofs

Key Takeaways and Engagement

RSA's brilliance lies in transforming prime factorization into practical security. While manual calculations work with tiny primes, modern RSA relies on computational infeasibility of factoring large composites. When implementing this yourself, which step do you anticipate being most challenging? Share your experience in the comments!