Understanding RSA Cryptography - Theory and Practical Exploitation
Abstract
RSA is one of the most widely used public-key cryptographic algorithms in modern cybersecurity, protecting HTTPS connections, software signatures, email encryption, and authentication systems. This monograph provides a comprehensive exploration of RSA cryptography—from its mathematical foundations to practical exploitation techniques. It explains how RSA works, why it is secure when implemented correctly, and how weak implementations can be exploited. A practical walkthrough of the "Tiny Crown" CTF challenge demonstrates a real-world vulnerability where a small public exponent (e=3) and lack of padding allow the plaintext to be recovered by computing a simple cube root. This write-up highlights the critical importance of proper implementation, padding schemes (OAEP, PKCS#1), and secure parameter selection in cryptographic systems.
Full Text
1. The Idea Behind RSA
RSA relies on a simple mathematical principle: multiplying large prime numbers is easy, but factoring their product is extremely difficult.
2. RSA Key Structure
RSA uses two keys: Public Key (n, e) for encryption and Private Key (n, d) for decryption.
3. RSA Encryption
c = m^e mod n
4. RSA Decryption
m = c^d mod n
5. Why RSA Works
RSA relies on Euler's theorem: d × e ≡ 1 (mod φ(n))
6. When RSA Becomes Vulnerable
Several mistakes can make it vulnerable: small primes, primes too close, small public exponent, no padding, shared modulus.
7. Small Exponent Weakness
When e = 3 and m^3 < n, the modulus operation never applies: c = m^3
8. Example Challenge — Tiny Crown
The kingdom trusted RSA, but the king was too impatient for big exponents and secure padding.
9. Analyzing the Challenge
The key observation is e = 3, suggesting we check if c = m^3.
10. Solving the Challenge
Using gmpy2.iroot(c,3) to compute the integer cube root.
11. Result
G24{tiny_rsa_big_problem}
12. Why This Happens
RSA implementations in real systems always use padding schemes such as OAEP and PKCS#1.
13. Lessons for Secure Cryptography
Secure RSA implementations must ensure: proper padding (OAEP), large random primes, safe exponent choices, and no direct encryption of raw data.
Conclusion
RSA is a powerful cryptographic system built on deep mathematical principles, but small implementation mistakes can completely break the system. Understanding these weaknesses is essential for both offensive security analysis and defensive cryptographic design.
Originally published on G24SEC Community Blogs
Citation (BibTeX)
@article{ouma2026understandingrsa,
author = {Meshack Bahati Ouma},
title = {Understanding RSA Cryptography — Theory and Practical Exploitation},
journal = {G24SEC Community Blogs},
year = {2026},
month = {March},
url = {https://www.g24sec.com/blog/understanding-rsa-cryptography-theory-and-exploitation},
note = {Includes practical walkthrough of the Tiny Crown CTF challenge demonstrating small exponent vulnerability}
}