Cryptography Academy

Understanding the mathematical foundations of modern cryptography is essential for anyone interested in secure communications, digital privacy, and data integrity. This guide dives into the core concepts behind one of the most widely used public-key cryptosystems: RSA. From character encoding to modular arithmetic and prime factorization, we’ll explore how these mathematical principles come together to enable secure encryption and digital signatures.

Whether you're a student, developer, or security enthusiast, this comprehensive overview will help you grasp the inner workings of RSA and its real-world applications.

From Characters to Cryptography: Data Encoding in Secure Systems

Before any cryptographic algorithm can process a message, it must first convert human-readable text into a format computers can manipulate—integers or binary data.

Asymmetric cryptosystems like RSA and ElGamal operate on integers using arithmetic operations, while symmetric systems such as AES work directly with bits (binary digits). Therefore, converting characters into numerical representations is a critical first step.

The standard method uses the ASCII (American Standard Code for Information Interchange) table, which maps characters to decimal, hexadecimal, and binary values. For example:

• 'H' → 72 → 01001000
• 'e' → 101 → 01100101
• 'y' → 121 → 01111001

So the message "Hey Bob!" becomes:

72 101 121 32 66 111 98 33 (decimal)
01001000 01100101 01111001 00100000 01000010 01101111 01100010 00100001 (binary)

While ASCII suffices for basic English text, modern systems use UTF-8, an extension that supports international characters by encoding them in 2–4 bytes.

👉 Discover how secure data encoding powers blockchain transactions and digital identity verification.

Related Encoding Schemes in Cryptography

Beyond ASCII and UTF-8, several encoding methods are crucial in cryptographic workflows:

• Base64: Encodes binary data (like keys or encrypted payloads) into ASCII text for safe transmission over text-based protocols.
• Hex encoding: Represents binary values (e.g., hashes, keys) in hexadecimal form for readability and debugging.
• Block padding: Ensures messages fit fixed-size blocks required by algorithms like AES (which uses 128-bit blocks).

Important distinction: Encoding is not encryption. It’s a reversible, standardized transformation without secrecy. Anyone knowing the scheme can decode it. Encryption, by contrast, requires a secret key to reverse.

The Mathematics Behind Cryptography

Modern cryptography relies heavily on number theory. Let’s break down the essential mathematical tools.

Exponent Rules and Modular Arithmetic

Exponentiation is central to public-key cryptography. For example:

4³ = 4 × 4 × 4 = 64

Here, 4 is the base, and 3 is the exponent.

Key exponent rules include:

• $ x^a \cdot x^b = x^{a+b} $
• $ (x^a)^b = x^{ab} $
• $ x^{-1} = \frac{1}{x} $

In cryptography, we compute exponents modulo a number:

$$ a^b \mod n $$

This means raising $a$ to the power $b$, then taking the remainder when divided by $n$. For instance:

$$ 3^4 \mod 7 = 81 \mod 7 = 4 $$

Modular exponentiation underpins key algorithms:

• RSA: Uses $ (m^e)^d \mod n = m $
• Diffie-Hellman: Relies on $ (g^a)^b \mod p = g^{ab} \mod p $

Efficient Computation: Square-and-Multiply Algorithm

Direct computation of large exponents (e.g., $3^{65537}$) is inefficient. The square-and-multiply algorithm reduces complexity to $O(\log n)$:

Steps:

1. Convert exponent to binary.
2. Start with result = 1.

3. For each bit:

   • Square the result.
   • If bit is 1, multiply by base.

Example: Compute $3^{13}$ where $13 = 1101_2$

• Bit 1: $1^2 × 3 = 3$
• Bit 1: $3^2 × 3 = 27$
• Bit 0: $27^2 = 729$
• Bit 1: $729^2 × 3 = 1,594,323$

This efficiency enables practical use in real-time encryption.

Modular Arithmetic: The Clockwork of Cryptography

Modular arithmetic works like a clock: after reaching a limit (modulus), it wraps around.

For example:

$$ (11 + 3) \mod 12 = 2 $$

General rule:

$$ a \mod n = \text{remainder when } a \text{ is divided by } n $$

So:

• $27 \mod 5 = 2$ (since $5×5=25$, remainder $2$)
• $-27 \mod 5 = 3$ (since $5×(-6) = -30$, difference is $3$)

Properties of Modular Arithmetic

These rules allow efficient computation:

• $(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 properties let us work with smaller numbers instead of unwieldy large ones.

Modular Inverse and Coprime Numbers

The modular inverse of $a$ modulo $n$ is an integer $a^{-1}$ such that:

$$ a \cdot a^{-1} \equiv 1 \pmod{n} $$

It exists only if $\gcd(a, n) = 1$, meaning $a$ and $n$ are coprime.

This concept is vital in RSA for computing the decryption key.

Key Theorems in Number Theory

• Fermat’s Little Theorem: If $p$ is prime and $a$ not divisible by $p$, then:

  $$ a^{p-1} \equiv 1 \pmod{p} $$

• Euler’s Theorem: If $\gcd(a,n)=1$, then:

  $$ a^{\phi(n)} \equiv 1 \pmod{n} $$

  where $\phi(n)$ is Euler’s totient function.

These theorems form the mathematical backbone of RSA and other public-key systems.

Greatest Common Divisor and the Euclidean Algorithm

The greatest common divisor (GCD) of two integers is the largest number that divides both evenly.

Example:

• Divisors of 12: {1,2,3,4,6,12}
• Divisors of 16: {1,2,4,8,16}
• So $\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 method to compute GCD:

Steps:
Given $a ≥ b$:

1. Divide $a$ by $b$: $a = bq + r$
2. If $r=0$, GCD is $b$
3. Else, repeat with $(b, r)$

Example: $\gcd(48, 18)$

• $48 = 18×2 + 12$
• $18 = 12×1 + 6$
• $12 = 6×2 + 0$ → GCD = 6

Extended Euclidean Algorithm

This version also finds integers $\lambda$ and $\mu$ such that:

$$ a\lambda + b\mu = \gcd(a,b) $$

If $\gcd(a,b)=1$, then $\lambda$ is the modular inverse of $a \mod b$.

This is essential for computing private keys in RSA.

Groups, Units, and Euler’s Phi Function

In abstract algebra:

• A group supports one operation (like multiplication) with closure, identity, inverses.
• A ring supports addition and multiplication.

We define:

• $\mathbb{Z}_n = \{0, 1, ..., n-1\}$: integers modulo $n$
• $\mathbb{Z}_n^*$: units modulo $n$ — elements with multiplicative inverses

An element $a$ has an inverse mod $n$ iff $\gcd(a,n)=1$.

For prime $p$:

$$ \mathbb{Z}_p^* = \{1,2,...,p-1\} $$

Euler’s Totient Function $\phi(n)$

Counts elements in $\mathbb{Z}_n^*$:

• If $n=p$: $\phi(p) = p−1$
• If $n=pq$: $\phi(n) = (p−1)(q−1)$

Used in RSA key generation to compute the decryption exponent.

👉 See how cryptographic groups secure blockchain wallets and decentralized identity systems.

Chinese Remainder Theorem (CRT)

CRT allows solving systems of congruences efficiently.

Given pairwise coprime moduli $m_1,...,m_k$, there’s a unique solution modulo $M=m_1⋯m_k$ to:

$$ x ≡ a_i \pmod{m_i} $$

Application in RSA:
Instead of computing $c^d \mod n$, CRT splits it into:

• $c^d \mod p$
• $c^d \mod q$

Then combines results — speeding up decryption by ~4x.

Prime Factorization: The Foundation of RSA Security

RSA’s security hinges on the prime factorization problem: given $n=pq$, it’s easy to multiply but computationally hard to factor back into primes.

For small numbers:
$n=15 → p=3, q=5$

But for large primes (e.g., 2048-bit), factoring takes billions of years with classical computers.

Factorization Algorithms

As of 2023, RSA-250 (829 bits) was factored — reinforcing recommendations for ≥2048-bit keys.

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 — driving research into post-quantum cryptography.

CPA and CCA Security in Public-Key Cryptography

Security models define how resistant a system is to attacks.

Chosen Plaintext Attack (CPA)

An attacker observes ciphertexts and tries to guess plaintexts. A scheme is CPA-secure if no attacker gains meaningful advantage beyond random guessing.

Textbook RSA fails CPA due to being deterministic — same input always yields same output.

Chosen Ciphertext Attack (CCA)

Stronger threat model: attacker can submit ciphertexts for decryption.

Levels:

• CCA1: Decryption queries before challenge
• CCA2: Queries before and after (except challenge ciphertext)

CCA2 is the gold standard for modern encryption.

Secure RSA Variants

OAEP adds randomness via padding — making encryption probabilistic and secure against active attacks.

Digital Signatures and EUF-CMA Security

Digital signatures ensure authenticity and non-repudiation.

Security is measured by Existential Unforgeability under Chosen Message Attack (EUF-CMA):

An attacker queries signatures for chosen messages. They win only if they forge a valid signature for a new message.

Common Signature Schemes

Hashing messages before signing prevents existential forgery via RSA's homomorphic property.

How RSA Works: Encryption and Decryption

Key Generation

Alice:

1. Chooses two large primes $p$, $q$
2. Computes $n = pq$, $\phi(n) = (p−1)(q−1)$
3. Picks public exponent $e$ such that $\gcd(e,\phi(n))=1$
4. Computes private key $d = e^{-1} \mod \phi(n)$ using extended Euclidean algorithm
5. Publishes $(n,e)$; keeps $(n,d)$ secret

Encryption

Bob:

• Converts message to integer $m$
• Computes ciphertext:
  $$ c = m^e \mod n $$

Decryption

Alice:
$$ m' = c^d \mod n = m $$

Correctness follows from Euler’s theorem and modular exponentiation rules.

Real-World Applications of RSA

• 🔐 HTTPS/TLS: Secures web browsing via key exchange
• 📄 Digital Certificates: X.509 certificates verify website identities
• 💻 Software Signing: Developers sign updates to prevent tampering
• 📝 Document Authentication: Legally binding digital contracts

Frequently Asked Questions (FAQ)

What makes RSA secure?

RSA relies on the computational difficulty of factoring large composite numbers into their prime components. While multiplication is fast, factoring is exponentially harder — especially for numbers over 2048 bits.

Why do we hash messages before signing?

Hashing prevents attacks exploiting RSA's homomorphic properties. Signing the hash ensures that even if an attacker combines signatures, they cannot forge a valid signature for a meaningful new message.

What is the difference between CPA and CCA security?

CPA assumes passive eavesdropping; CCA assumes active attackers who can request decryptions. CCA security is stronger and necessary for most real-world applications like secure messaging and financial transactions.

How does OAEP make RSA secure?

OAEP adds structured randomness during encryption, ensuring that encrypting the same message twice produces different ciphertexts. This prevents pattern analysis and chosen-ciphertext attacks.

Can quantum computers break RSA?

Yes — Shor’s algorithm can factor large integers efficiently on a quantum computer. While large-scale quantum machines don’t yet exist, this threat has spurred development of quantum-resistant algorithms.

What is RSA blinding?

RSA blinding prevents timing attacks by randomizing the decryption input. Before decrypting, a random value masks the ciphertext; after decryption, it's unmasked. This breaks correlation between computation time and secret key bits.

Final Thoughts: The Enduring Role of RSA

Despite newer algorithms like ECC gaining popularity for efficiency, RSA remains foundational in digital trust infrastructure. Its simplicity, wide adoption, and provable security under proper implementation make it indispensable in securing online communication.

Understanding its mathematical roots — from modular arithmetic to prime factorization — empowers developers and users alike to build and rely on secure systems in an increasingly connected world.

👉 Explore cutting-edge cryptographic tools transforming finance and identity management today.