Modern cryptography forms the backbone of secure digital communication, protecting everything from online banking to private messaging. At the heart of many public-key cryptosystems lies the RSA algorithm, a groundbreaking innovation that relies on deep mathematical principles such as modular arithmetic, prime factorization, and number theory. This comprehensive guide explores the inner workings of RSA, its encryption and digital signature schemes, and the essential mathematical concepts that make it both powerful and secure.
Whether you're a student diving into cryptography or a professional seeking clarity on foundational topics, this article breaks down complex ideas into digestible explanations—complete with real-world examples and practical insights.
Core Concepts in Cryptographic Encoding
From Characters to Integers and Bits
In cryptography, messages composed of human-readable characters must first be converted into numerical formats before any cryptographic operation can be applied. This is because asymmetric algorithms like RSA and ElGamal operate on integers using modular arithmetic, while symmetric systems like AES work directly on bits.
Computers naturally represent text using encoding standards such as ASCII (American Standard Code for Information Interchange), which maps each character to a unique integer and its corresponding 8-bit binary representation:
| Character | Decimal | Binary |
|---|---|---|
| (space) | 32 | 00100000 |
| A | 65 | 01000001 |
| a | 97 | 01100001 |
| ! | 33 | 00100001 |
For example, the message "Hey Bob!" becomes:
- Decimal:
72 101 121 32 66 111 98 33 - Binary:
01001000 01100101 01111001 00100000 01000010 01101111 01100010 00100001
While ASCII suffices for English text, modern systems use UTF-8, a superset that supports international characters by encoding them in 2–4 bytes.
🔍 Important Note: Encoding (e.g., ASCII or UTF-8) is not encryption. It’s a reversible, standardized transformation with no secret key involved. True encryption requires keys and cryptographic algorithms to ensure confidentiality.
👉 Discover how cryptographic encoding powers secure blockchain transactions today.
Exponentiation and Modular Arithmetic
Laws of Exponents in Cryptography
Exponentiation plays a central role in public-key cryptography. The basic rules govern how powers interact:
- $ x^1 = x $
- $ x^0 = 1 $
- $ x^{-n} = \frac{1}{x^n} $
- $ x^m \cdot x^n = x^{m+n} $
- $ (x^m)^n = x^{m \cdot n} $
These laws are crucial in algorithms like RSA, where operations involve raising large numbers to exponents modulo another number.
Efficient Computation: Square-and-Multiply Algorithm
Direct computation of large exponents (e.g., $3^{65537}$) is infeasible. Instead, cryptographers use the square-and-multiply method, reducing complexity to $O(\log n)$:
To compute $3^{13}$ where $13 = 1101_2$:
- Start with result = 1
- For each bit: square the result; if bit is 1, multiply by base
- Final result: $3^{13} = 1,594,323$
This technique enables fast encryption and decryption in real-world applications.
Modular Arithmetic: The Clock of Cryptography
Modular arithmetic computes remainders after division. For instance:
- $ (11 + 3) \mod 12 = 2 $ — just like clock time
Formally, $a \mod n$ returns the remainder when $a$ is divided by $n$. The result always lies between $0$ and $n-1$.
Key Properties
Modular arithmetic preserves standard operations:
- $(a + b) \mod n = [(a \mod n) + (b \mod n)] \mod n$
- $(a \cdot b) \mod n = [(a \mod n) \cdot (b \mod n)] \mod n$
- $a^b \mod n = (a \mod n)^b \mod n$
These allow efficient computation even with very large numbers.
Modular Inverse and Coprime Numbers
An integer $a$ has a modular inverse modulo $n$ if there exists an integer $a^{-1}$ such that:
$$ a \cdot a^{-1} \equiv 1 \pmod{n} $$
This inverse exists only if $\gcd(a, n) = 1$, meaning $a$ and $n$ are coprime.
Finding this inverse is vital in RSA key generation and is efficiently done using the extended Euclidean algorithm.
Greatest Common Divisor and the Euclidean Algorithm
Definition and Importance
The greatest common divisor (GCD) of two integers is the largest number that divides both evenly. For example:
- Divisors of 12: {1, 2, 3, 4, 6, 12}
- Divisors of 16: {1, 2, 4, 8, 16}
- $\gcd(12, 16) = 4$
Two numbers are relatively prime if their GCD is 1 (e.g., $\gcd(15, 28) = 1$).
The Euclidean Algorithm
An efficient way to compute GCD:
gcd(48, 18):
48 = 18×2 + 12
18 = 12×1 + 6
12 = 6×2 + 0 → gcd = 6This recursive process underpins much of modern cryptography.
Extended Euclidean Algorithm: Finding Modular Inverses
Beyond computing GCDs, the extended version finds integers $\lambda$ and $\mu$ such that:
$$ a\lambda + b\mu = \gcd(a,b) $$
If $\gcd(a,b)=1$, then:
$$ a\lambda \equiv 1 \pmod{b} \Rightarrow a^{-1} = \lambda \mod b $$
This is essential for deriving private keys in RSA.
👉 Learn how modular inverses secure digital signatures in blockchain networks.
Groups, Units, and Euler’s Phi Function
The Ring of Integers Modulo $n$
The set $\mathbb{Z}_n = \{0, 1, ..., n-1\}$ supports addition and multiplication under modulo $n$. Within this set, some elements have multiplicative inverses—these are called units.
The group of units $\mathbb{Z}_n^*$ includes all integers in $\mathbb{Z}_n$ coprime to $n$. For example:
- $\mathbb{Z}_8 = \{0,1,2,3,4,5,6,7\}$
- $\mathbb{Z}_8^* = \{1,3,5,7\}$
When $n = p$ (prime), every non-zero element has an inverse:
$$ \mathbb{Z}_p^* = \{1,2,...,p-1\} $$
Euler’s Totient Function $\phi(n)$
$\phi(n)$ counts the number of units in $\mathbb{Z}_n$, i.e., the size of $\mathbb{Z}_n^*$:
- If $p$ is prime: $\phi(p) = p - 1$
- If $n = p \cdot q$: $\phi(n) = (p-1)(q-1)$
- General formula: $\phi(n) = n \prod_{p|n}(1 - \frac{1}{p})$
For $n=36=2^2\cdot3^2$:
$$ \phi(36) = 36 \cdot (1 - \frac{1}{2}) \cdot (1 - \frac{1}{3}) = 36 \cdot \frac{1}{2} \cdot \frac{2}{3} = 12 $$
This function is foundational to RSA’s security model.
Chinese Remainder Theorem (CRT)
Accelerating RSA Decryption
CRT allows solving systems of congruences efficiently. Given pairwise coprime moduli $m_1,...,m_k$, there exists a unique solution modulo $M = m_1\cdots m_k$.
In RSA, CRT speeds up decryption by splitting computations modulo $p$ and $q$, then combining results—reducing computational load significantly.
Prime Factorization Problem: The Security Backbone of RSA
Why Factoring Is Hard
RSA’s security hinges on the difficulty of factoring large composite numbers into primes. While multiplying two primes is easy:
$$ p=67,\ q=79 \Rightarrow n=5293 $$
Reversing this—finding $p$ and $q$ from $n$—becomes computationally infeasible for large values (e.g., 2048-bit keys).
No known classical algorithm can factor such numbers efficiently. The best method—the General Number Field Sieve (GNFS)—still requires astronomical time for secure key sizes.
Quantum Threat: Shor’s Algorithm
Peter Shor’s quantum algorithm can factor integers in polynomial time. If scalable quantum computers emerge, RSA could be broken. This has spurred research into post-quantum cryptography.
Current recommendation: Use RSA keys of at least 2048 bits for long-term security.
Security Models: CPA and CCA in Asymmetric Cryptography
Chosen Plaintext Attack (CPA) Security
A cryptosystem is CPA-secure if an attacker cannot distinguish between encryptions of two chosen messages—even with access to the public key.
Basic ("textbook") RSA fails CPA because it's deterministic—same input yields same output.
✅ Solution: Use randomized padding schemes like OAEP (Optimal Asymmetric Encryption Padding).
Chosen Ciphertext Attack (CCA) Security
CCA is stronger: attackers can request decryptions of chosen ciphertexts. Only properly padded schemes like RSA-OAEP achieve CCA2 security, the gold standard for modern encryption.
RSA Encryption Scheme Explained
Key Generation
Alice generates her key pair:
- Choose two large primes $p$, $q$
- Compute $n = p \cdot q$, $\phi(n) = (p-1)(q-1)$
- Pick public exponent $e$ such that $\gcd(e,\phi(n))=1$
- Compute private exponent $d = e^{-1} \mod \phi(n)$
- Public key: $(n,e)$; Private key: $(n,d)$
Encryption and Decryption
Bob encrypts message $m$:
$$ c = m^e \mod n $$
Alice decrypts:
$$ m = c^d \mod n $$
Correctness follows from Euler’s theorem: $m^{ed} \equiv m \pmod{n}$ when $ed \equiv 1 \pmod{\phi(n)}$
Digital Signatures with RSA
How Signing Works
To sign message $m$, Samantha:
- Computes hash $\mathcal{H}(m)$
- Signs: $\sigma = \mathcal{H}(m)^s \mod n$, where $s$ is her private signing key
Victor verifies using her public key:
$$ \sigma^v \mod n \stackrel{?}{=} \mathcal{H}(m) $$
Using hashes prevents existential forgery via homomorphic properties.
Practical Considerations and Real-World Applications
Common Uses of RSA
- HTTPS/TLS: Securing web traffic during handshakes
- Digital Certificates: Authenticating websites via X.509 certs
- Software Signing: Ensuring code integrity and origin authenticity
- Secure Email: S/MIME and PGP use RSA for key exchange and signing
Preventing Side-Channel Attacks: RSA Blinding
Timing attacks exploit variations in decryption time. RSA blinding mitigates this by randomizing ciphertexts before decryption:
$$ c' = c \cdot r^e \mod n,\quad m' = (c')^d,\quad m = m' \cdot r^{-1} $$
This ensures computation time doesn’t leak private key information.
Frequently Asked Questions (FAQ)
What makes RSA secure?
RSA relies on the computational hardness of factoring large integers into primes. Without knowing the prime factors of $n$, an attacker cannot compute $\phi(n)$ or derive the private key.
Why do we use OAEP padding in RSA?
Textbook RSA is deterministic and vulnerable to attacks. OAEP introduces randomness, making encryption probabilistic and resistant to chosen plaintext and ciphertext attacks.
Can RSA be broken by quantum computers?
Yes—Shor’s algorithm can factor integers efficiently on a quantum computer. Once large-scale quantum computers exist, RSA will no longer be secure unless replaced with post-quantum alternatives.
What is the difference between encryption and digital signatures in RSA?
In encryption, the sender uses the receiver’s public key; in signing, the sender uses their own private key. Both rely on modular exponentiation but serve different purposes: confidentiality vs. authentication.
How long should an RSA key be?
As of now, 2048-bit keys are considered secure for most applications through at least 2030. For higher assurance or long-term security, 3072-bit or 4096-bit keys are recommended.
Is RSA still used today?
Yes—despite newer algorithms like ECC gaining popularity, RSA remains widely used in TLS certificates, code signing, and legacy systems due to its simplicity and broad support.
👉 Explore how next-generation cryptographic protocols are evolving beyond traditional RSA.