RSA Algorithm: Working and Solved Numerical Example

What is the RSA Algorithm?

The RSA Algorithm is the world’s most famous and widely used Asymmetric (Public-Key) Cryptographic Algorithm.

It was invented in 1977 at MIT by three computer scientists, and its name comes from the first letters of their surnames:

• R — Ron Rivest
• S — Adi Shamir
• A — Leonard Adleman

What Makes RSA Secure? (The Prime Factorization Problem)

RSA’s security is based on a simple mathematical fact:

• It is very easy for a computer to multiply two large prime numbers together (p × q = n).
• However, if someone gives you only the huge product n (say, a 600-digit number / 2048 bits), it is practically impossible even for supercomputers to work backwards and find the two original prime factors p and q! This is called the Integer Factorization Problem.

1. The 3 Phases of the RSA Algorithm

The RSA Algorithm consists of three main phases:

1. Key Generation (Creating the Public Key and Private Key)
2. Encryption (Locking the message M into Cipher Text C)
3. Decryption (Unlocking the Cipher Text C back into message M)

2. Mathematical Formulas of RSA (Must Write in Exams!)

Phase A: Key Generation Steps

1. Select two large, distinct prime numbers p and q (p ≠ q).
2. Calculate the system modulus n:

   Formula: n = p × q

3. Calculate Euler’s Totient Function φ(n):

   Formula: φ(n) = (p - 1) × (q - 1)

4. Choose an integer e (the Public Key exponent) such that:
   • 1 < e < φ(n)
   • \gcd(e, φ(n)) = 1 (meaning e and φ(n) share no common factor other than 1).
5. Calculate d (the Private Key exponent) as the multiplicative inverse of e mod φ(n):

   Formula: (d × e) mod φ(n) = 1 (In simple words: find a number d such that when you multiply d × e and divide by φ(n), the remainder is 1).

• Public Key (PU): {e, n} — Shared with everyone.
• Private Key (PR): {d, n} — Kept secret by the receiver.

Phase B: Encryption Formula

To encrypt a Plain Text number M (where M < n) using the Public Key {e, n}:

Formula: C = M^e mod n

Phase C: Decryption Formula

To decrypt the Cipher Text C using the Private Key {d, n}:

Formula: M = C^d mod n

3. 📝 Solved Numerical Example 1 (Easy Exam Example)

Question: Perform encryption and decryption using the RSA Algorithm for the following values:

• Prime numbers: p = 3, q = 11
• Public key exponent: e = 7
• Plain Text message: M = 2

Solution:

Step 1: Given Prime Numbers

Formula: p = 3, q = 11

Step 2: Calculate n = p × q

Formula: n = 3 × 11 = 33

Step 3: Calculate φ(n) = (p - 1) × (q - 1)

Formula: φ(n) = (3 - 1) × (11 - 1) = 2 × 10 = 20

Step 4: Verify Public Key Exponent e

• Given e = 7.
• Since 1 < 7 < 20 and \gcd(7, 20) = 1, e = 7 is valid!

Step 5: Calculate Private Key Exponent d

We need (d × e) mod φ(n) = 1, which means:

Formula: (d × 7) mod 20 = 1 Let’s test small values of d:

• If d = 1: 1 × 7 = 7 mod 20 = 7 ≠ 1

• If d = 2: 2 × 7 = 14 mod 20 = 14 ≠ 1

• If d = 3: 3 × 7 = 21 mod 20 = 1 ✅ So, d = 3!

• Public Key (PU): {e, n} = {7, 33}

• Private Key (PR): {d, n} = {3, 33}

Step 6: Encryption of Message M = 2

Formula: C = M^e mod n Formula: C = 2^7 mod 33 Formula: C = 128 mod 33 (Since 33 × 3 = 99, remainder is 128 - 99 = 29) Formula: C = 29 So the encrypted Cipher Text is 29.

Step 7: Decryption of Cipher Text C = 29

Formula: M = C^d mod n Formula: M = 29^3 mod 33 Formula: M = 24389 mod 33 (Since 33 × 739 = 24387, remainder is 24389 - 24387 = 2) Formula: M = 2 We got back our exact original Plain Text message M = 2!

4. 📝 Solved Numerical Example 2 (Practice Question)

Question: In an RSA system, p = 5, q = 11, e = 3, and Plain Text M = 9. Find the Public Key, Private Key, and Cipher Text.

Quick Solution:

1. n = p × q = 5 × 11 = 55
2. φ(n) = (5 - 1)(11 - 1) = 4 × 10 = 40
3. Given e = 3. Find d such that (d × 3) mod 40 = 1:
   • Try d = 27: 27 × 3 = 81, and 81 mod 40 = 1 ✅. So d = 27.
4. Public Key: {3, 55}, Private Key: {27, 55}.
5. Encryption (M = 9):

   Formula: C = M^e mod n = 9^3 mod 55 = 729 mod 55 = 14 (Since 55 × 13 = 715, and 729 - 715 = 14).

💡 DAVV Exam Preparation Tips

10-Mark Question (Asked Almost Every Year!): “Explain the RSA Algorithm step by step with a suitable numerical example.”

• Even if the question does not give numbers, always write and solve Example 1 (p = 3, q = 11, e = 7, M = 2) on your own! Those small numbers (2^7 = 128) are super easy to calculate without a calculator and guarantee 10 out of 10 marks.