Understanding RSA Cryptography

A Mathematical Journey

Bridging Pure Mathematics and Computer Science

Want to understand the mathematical foundations of one of the most important cryptographic systems in the digital world? read through this article …

Introduction

This article explores RSA cryptography from a mathematical perspective, designed to bridge the gap between pure mathematics and its real-world applications in computer science. Through clear explanations and practical examples, we'll discover how elegant

mathematical concepts like prime numbers, modular arithmetic, and Fermat's Little Theorem come together to create one of the most important encryption systems in the digital world.

RSA was developed by Ron Rivest, Adi Shamir, and Leonard Adleman at the Massachusetts Institute of Technology (MIT) in 1977. This asymmetric cryptosystem revolutionized secure communication by using the mathematical difficulty of factoring large composite numbers as its foundation.

Foundation Concepts: Prime Numbers and Coprimality

Before diving into RSA, let's establish the fundamental mathematical building blocks.

Prime Numbers

A prime number is a natural number greater than 1 that has exactly two distinct positive divisors: 1 and itself.

Examples:

1. 5 is prime because its only factors are 1 and 5

2. 17 is prime because it cannot be divided evenly by any number except 1 and 17

Note: The number 1 is not considered prime because it has only one factor (itself).

Coprime Numbers

Two integers a and b are coprime (or relatively prime) if their greatest common divisor equals 1:

gcd(a, b) = 1

This means they share no common positive factors other than 1.

Examples:

1. (8, 15) are coprime because:
     Factors of 8:  {1, 2, 4, 8}
     Factors of 15: {1, 3, 5, 15}
     Common factors: {1} only

2. (8, 12) are NOT coprime because they share factors 2 and 4 besides 1

Division and Modular Arithmetic

Understanding Division with Remainders

When we divide one integer by another, we can express the relationship using the division algorithm:

\(B= q × A + r\)

Where:

• B is the dividend (number being divided)

• A is the divisor

• q is the quotient (how many times A goes into B)

• r is the remainder (what's left over)

Important constraint: 0 ≤ r < A (the remainder is always less than the divisor)

Examples:

1. A = 4, B= 12 : We get 12 = 3 × 4 + 0, so q= 3, r = 0
2. A = 4, B= 13 : We get 13 = 3 × 4 + 1, so q= 3, r = 1

Modular Arithmetic

Modular arithmetic is the mathematics of remainders. When we divide B by A, we write: B mod A = r

By the division algorithm, there exist integers q and r such that:

\(B = q \times A + r \quad \text{with} \quad 0 \leq r < |A|\)

Key Properties:

• The remainder ‘r’ is unique when 0 ≤ r < |A|

• We use the notation B ≡ C (mod A) meaning B and C are congruent modulo A

• This means B and C leave the same remainder when divided by A

• Congruence modulo A is an equivalence relation (reflexive, symmetric, transitive)

The Circular Nature of Modular Arithmetic

Modular arithmetic behaves like circular (clock) arithmetic: residues 0 to A− 1 sit on a cycle and operations wrap around when they reach A.

Figure 1: Modular arithmetic cycle for x mod 4, showing how numbers with the same remainder are grouped together

For example, if we consider x mod 4 where x > 0, we see a natural cycle:

• 1 mod 4 = 1, 5 mod 4 = 1, 9 mod 4 = 1, 13 mod 4 = 1

• 2 mod 4 = 2, 6 mod 4 = 2, 10 mod 4 = 2, 14 mod 4 = 2

• 3 mod 4 = 3, 7 mod 4 = 3, 11 mod 4 = 3, 15 mod 4 = 3

• 4 mod 4 = 0, 8 mod 4 = 0, 12 mod 4 = 0, 16 mod 4 = 0

Figure 2: Concentric circle representation showing how 8 mod 4 = 0, demonstrating the cyclical nature of modular arithmetic

These visual representations help us understand that modular arithmetic creates natural groupings or "equivalence classes" of numbers that share the same remainder.

Cryptography Fundamentals

Cryptography is the science of protecting information by transforming it so that only authorized parties can access it.

Key Terms:

• Plaintext: The original, readable message

• Ciphertext: The encrypted, protected message

• Encryption: The process of converting plaintext to ciphertext

• Decryption: The process of recovering plaintext from ciphertext

Building Up to RSA: Simple Cipher Examples

Additive Cipher (Caesar Cipher)

The Caesar cipher shifts each letter by a fixed number of positions in the alphabet using modular arithmetic.

Encryption Formula:

C = (P − 65 + k) mod 26 + 65

Where:

• P = ASCII value of plaintext letter

• C = ASCII value of ciphertext letter

• k = shift key (0− 25)

Decryption Using Additive Inverse

To decrypt, we need the additive inverse of the key k in mod 26 arithmetic.

By definition, the additive inverse of k is the number -k such that:

k + (-k) ≡ 0 (mod 26)

Practically, this means:

additive inverse of k mod 26 = (−k) mod 26

General formal for finding additive inverse of k mod n is
(−k) mod n = ( n − (k mod n) ) mod n;

(-k) mod 26 = (26 - (17 mod 26 ) mod 26;
(-k) mod 26 = (26 - 17) mod 26 = 9 mod 26;

∴ additive inverse of 17 mod 26 is 9 mod 26

Decryption Formula:
P = ( (C - 65) + 9 ) mod 26 + 65; 

getting the plain text from above cipher values is left as an exercise to the reader.

The Concept of Modular Inverses

The "walk forward until you return home" principle applies to different types of operations:

Multiplicative Inverse

The multiplicative inverse of modulo n is a number a^-1 such that:

a × a−1 ≡ 1 (mod n)

Example: In mod 7 , we have 3 × 5 = 15 ≡ 1 (mod 7), so 5 is the multiplicative inverse of 3.

Exponential Inverse

In RSA, we use the fact that raising to some power e can be "undone" by raising to another power d, provided:

e × d ≡ 1 (mod φ(n))

Fermat's Little Theorem: The Foundation for RSA

Fermat's Little Theorem states that if p is prime and a is not divisible by p, then:

a^p−1 ≡ 1 (mod p)

Euler's Theorem (generalization): If gcd(a, n) = 1, then:

aφ(n) ≡ 1 (mod n)

Where φ(n) is Euler's totient function, counting how many numbers ≤ n are coprime to n.

Key Formulas:

• For prime p: φ(p) = p− 1

• For product of two primes: φ(pq) = (p− 1)(q− 1)

• The generalised formula for the total of Euler’s totient function for any positive integer is:

  \({\varphi(n) = n \prod_{i=1}^{k} \left(1 - \frac{1}{p_i}\right)} \)

  Where p1, p2, …,pk are the distinct prime factors of

Example: For n = 10 = 2 × 5 :

\(\varphi(10) = 10 \times \left(1 - \tfrac{1}{2}\right) \times \left(1 - \tfrac{1}{5}\right) = 10 \times \tfrac{1}{2} \times \tfrac{4}{5} = 4 \)

The numbers 1, 3, 7, 9 are exactly the four integers between 1 and 10 that are coprime to 10.

RSA Cryptosystem: A Complete Walkthrough

Now let's see how all these mathematical concepts come together in RSA:

The security of RSA relies on the difficulty of factoring n back into its prime components p and q.

Why This Matters: φ(n) counts how many numbers from 1 to n are coprime with n. This creates the mathematical space where our encryption/decryption exponents will operate.

RSA String Encryption Demo, Pick two distinct primes from this set:
11 13 17 19 23 29 31 37 41 43 47 53

Step-by-Step RSA Implementation, Let's work through RSA using p = 13 and  q = 17:

Step 1: Build modulus n = p × q;  n = p × q = 13 × 17 = 221
Step 2: Euler's Totient φ(n) = (p-1)(q-1)
        φ(n) = (13-1)(17-1) = 12 × 16 = 192
Step 3: Choose public exponent e with gcd(e, φ(n)) = 1
        Count of valid public exponents e in [2, φ(n)-1]:  
        φ(n)=(p−1)(q−1)=12⋅16=192; 
        φ( φ(n) ) = φ(192) = 64; 
        Some valid e values: 5 7 11 13 17 19 23 25 29 31 35 37

        Selected: e = 5
Step 4: Compute private exponent d = e⁻¹ (mod φ(n))
        d is the modular inverse of e modulo φ(n)

        e × d ≡ 1 (mod φ(n)) → 5 × 77 ≡ 1 (mod 192)
        Therefore: d = 77

Public Key  : (e = 5, n = 221)
Private Key : (d = 77, n = 221)

Encryption and Decryption Demo

Now let's encrypt the message "HELLO":

Demo: Encrypt/Decrypt a string message

Mathematical Verification

Encryption Formula:

C = P^e mod n = P⁵ mod 221

• H (72): 72⁵ mod 221 = 89 ✓

• E (69): 69⁵ mod 221 = 205✓

• L (76): 76⁵ mod 221 = 111✓

• O (79): 79⁵ mod 221 = 27 ✓

Decryption Formula:

P= C^d mod n = C⁷⁷ mod 221

• 89⁷⁷ mod 221 = 72 (H) ✓

• 205⁷⁷ mod 221 = 69 (E) ✓

• 111⁷⁷ mod 221 = 76 (L) ✓

• 27⁷⁷ mod 221 = 79 (O) ✓

Why RSA Decryption Works

The mathematical elegance of RSA lies in Euler's theorem. Since we choose e and d such that:

e × d ≡ 1 (mod φ(n))

This means e × d= 1 + k × φ(n) for some integer k.

Therefore: (P^e)^d = P^ed = P^1+kφ(n) = P × (P^φ(n))k

By Euler's theorem, if gcd(P , n) = 1, then P φ(n) ≡ 1 (mod n).

Thus:

P × (1)k ≡ P (mod n)

This guarantees that encryption followed by decryption recovers the original message.

Additional Mathematical Insights

φ(n) = 192 factors into: 2⁶ × 3¹
φ(φ(n)) = φ(192) = 64 = 192 × ∏(1 - 1/p) over its prime factors p

The factorization reveals that there are 64 valid choices for the public exponent e.

RSA Security, The Hard Problem

RSA's security relies on the integer factorization problem: given a large composite number n = p × q , it is computationally infeasible to find p and q when they are large primes (typically hundreds of digits long).

Why this matters:

• Anyone can see the public key (n, e)

• To decrypt without the private key d, one would need to factor n to find p and q

• With p and q, one could compute φ(n) and then find d

• Current factoring algorithms cannot handle sufficiently large n in reasonable time

From Toy Example to Real World

In this demonstration, n = 221 can be factored easily. But with real RSA:

• Key sizes are typically 2048 bits or larger

• Prime numbers p and q are hundreds of digits long

• Factoring such large n is computationally infeasible with current technology

RSA’s effective security is much less than its key size for example, 1024 ≈ 80 bits, 2048 bits RSA ≈ 112 bits, 3072 bits RSA ≈ 128 bits, and so on. Due to the mathematical structure and patterns within RSA keys, as well as the efficiency of integer factorization algorithms. we shall discuss on that in another article, that also covers Attack Algorithms, Symmetric Ciphers like AES and more.

Conclusion

RSA cryptography demonstrates the beautiful intersection of pure mathematics and practical computer science. Starting from elementary concepts like prime numbers and modular arithmetic, we've built up to understanding one of the most important cryptographic systems in use today.

Key insights:

• Mathematical Foundation: Prime numbers and modular arithmetic provide the building blocks

• Elegant Design: Fermat's Little Theorem and Euler's theorem enable the encryption/decryption process

• Practical Security: The difficulty of factoring large numbers protects real-world communications

• Asymmetric Nature: Public and private keys enable secure communication without prior key sharing

This mathematical exploration illustrates how abstract mathematical concepts can have profound practical applications, protecting everything from online banking to private messaging in our digital world. The elegant interplay between number theory and

cryptographic security continues to be one of the most beautiful examples of applied mathematics in computer science.

If you want to understand more about practical applications using openssl or libsodium you can reach out to us at Prabodh.

References and Further Reading

Introduction to Modern Cryptography by Katz and Lindell

A Course in Number Theory and Cryptography by Neal Koblitz

Khan Academy's course on modular arithmetic

The original RSA paper: "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems" (1978)