RSA Encryption Learning

Message Decryption in RSA

Step 9 of 9

Learn how to decrypt messages using the RSA algorithm, apply the private key to recover plaintext, and understand the mathematical principles behind secure decryption.

Understanding RSA Decryption

RSA decryption is the process of recovering the original plaintext message from ciphertext using the recipient's private key. This is the final step in the RSA cryptosystem that ensures only the intended recipient can read the encrypted message.

Formula: To decrypt a ciphertext C using the private key (n, d), we calculate:

M = Cd mod n

Where M is the recovered plaintext message, C is the ciphertext, d is the private exponent, and n is the modulus (same as in the public key).

Private Key Usage

The private key (n, d) is used exclusively for decryption. The security of RSA relies on keeping this key secret. Anyone with access to the private key can decrypt messages intended for the key owner.

Mathematical Basis

RSA decryption works because of the mathematical relationship between e and d: they are modular multiplicative inverses with respect to φ(n). This ensures that (Me)d ≡ M (mod n) for all M.

Converting Numbers Back to Text

After decryption, we need to convert the numerical values back to text. This is the reverse of the encoding process used during encryption.

Example: Converting a number back to "HELLO"

Using ASCII encoding:

Decimal Value ASCII Character Hexadecimal
72 H 48
69 E 45
76 L 4C
76 L 4C
79 O 4F

If the decimal number 310939249775 was decrypted, we would convert it to hexadecimal (48454C4C4F) and then parse each byte to get the ASCII characters: "HELLO".

Note: For longer messages that were broken into blocks before encryption, each block must be decrypted separately and then combined to recover the complete message.

The Decryption Process

RSA decryption involves several steps to transform encrypted ciphertext back into the original plaintext message using the recipient's private key.

1

Receive Ciphertext

Obtain the encrypted message (ciphertext) that was encrypted using your public key (n, e).

2

Apply Formula

For each ciphertext block C, calculate M = Cd mod n using your private key (n, d).

3

Convert to Text

Transform the numerical plaintext values back into readable text using the appropriate encoding scheme.

Step-by-Step Example

Example: Decrypting a Message

Let's decrypt the message that was encrypted in the previous lesson:

  • Private key: n = 3233 (product of primes 61 and 53), d = 2753
  • Encrypted message: (855, 2698) representing "HI"
  • Decrypt each part separately:
    • For ciphertext 855: M1 = 8552753 mod 3233 = 72 (ASCII for "H")
    • For ciphertext 2698: M2 = 26982753 mod 3233 = 73 (ASCII for "I")
  • Convert ASCII values back to text: 72 → "H", 73 → "I"
  • The decrypted message is "HI"

Mathematical Detail:

To calculate 8552753 mod 3233 efficiently, we use the "square and multiply" algorithm:

  • 8551 = 855 mod 3233
  • 8552 = 8552 mod 3233 = 1369
  • 8554 = 13692 mod 3233 = 1871
  • 8558 = 18712 mod 3233 = 2401
  • 85516 = 24012 mod 3233 = 1189
  • ...
  • 8552753 mod 3233 = 72

Decryption Visualization

RSA Decryption Calculator

Important Guidelines

  • Modulus (n) must match the one used for encryption
  • Private exponent (d) must be the modular multiplicative inverse of e with respect to φ(n)
  • Ciphertext value must be smaller than the modulus (n) to ensure correct decryption

Use this calculator to decrypt a message using RSA. Enter the ciphertext value and your private key components.

Must be the same modulus used for encryption. Example: 3233 (61 × 53)
The private key exponent. Must be the modular multiplicative inverse of e mod φ(n)

For multiple values, separate with commas (e.g., 855, 2698)

Enter values to decrypt a message

Number to Text Converter

This tool helps you understand how numerical values are converted back to text messages after RSA decryption.

Enter comma-separated ASCII values

Enter ASCII values to see the text representation

Mathematical Proof of RSA Decryption

Understanding why RSA decryption works requires exploring the mathematical foundations that guarantee the correctness of the algorithm.

Why Decryption Works

The core of RSA's correctness lies in the relationship between encryption and decryption operations:

For any message M, if we encrypt with e and then decrypt with d:

(Me mod n)d mod n = M

This works because e and d are chosen such that:

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

Which means:

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

According to Euler's theorem, for any integer M that is coprime to n:

Mφ(n) ≡ 1 (mod n)

Therefore:

Me×d ≡ M1+k×φ(n) ≡ M × (Mφ(n))k ≡ M × 1k ≡ M (mod n)

This mathematical relationship guarantees that applying the decryption formula to an encrypted message will always recover the original plaintext.

Example Proof

Let's verify this with our example:

  • p = 61, q = 53, n = 3233, φ(n) = 3120
  • Public exponent e = 17
  • Private exponent d = 2753 (because 17 × 2753 = 46801 = 1 + 15 × 3120)
  • For message M = 72 ("H"):
    • Encryption: C = 7217 mod 3233 = 855
    • Decryption: M = 8552753 mod 3233 = 72

This confirms that the decryption process successfully recovers the original message.

Edge Cases

The proof above assumes M is coprime to n. What about other cases?

  • If M is divisible by p or q: The proof still holds through the Chinese Remainder Theorem
  • If M = 0: 0e mod n = 0, and 0d mod n = 0, so decryption still works
  • If M = n: This would be equivalent to encrypting 0, since n mod n = 0

These mathematical properties ensure that RSA decryption works correctly for all valid message values (0 ≤ M < n).

Practical Considerations for RSA Decryption

When implementing RSA decryption in real-world applications, several important considerations must be taken into account.

Performance Optimization

RSA decryption (Cd mod n) is computationally expensive, especially since d is typically much larger than e:

  • Use the Chinese Remainder Theorem (CRT) to speed up decryption by a factor of 3-4x
  • Precompute values dp = d mod (p-1) and dq = d mod (q-1)
  • Compute Mp = Cdp mod p and Mq = Cdq mod q
  • Combine using CRT to get M

This optimization is critical for applications requiring frequent decryption operations.

Padding Schemes

Just as with encryption, proper padding must be removed during decryption:

  • PKCS#1 v1.5: Verify and remove padding after decryption
  • OAEP: Process the decrypted value through the OAEP reverse transformation

Improper padding removal can lead to security vulnerabilities, such as padding oracle attacks.

Security Considerations

Several security aspects must be considered during RSA decryption:

  • Side-channel attacks: Protect against timing attacks, power analysis, and fault attacks
  • Blinding: Use random values to blind the ciphertext before decryption to prevent certain side-channel attacks
  • Key management: Securely store private keys and consider using hardware security modules (HSMs)
  • Error handling: Be careful not to leak information through error messages during decryption failures

Example of Blinding:

  1. Generate a random value r
  2. Compute re mod n
  3. Multiply the ciphertext: C' = C × re mod n
  4. Decrypt C' to get M' = (C')d mod n
  5. Compute M = M' × r-1 mod n to get the original message

Practice Exercises

Test your understanding of RSA decryption with these exercises.

Exercise 1: Basic Decryption

Given the private key (n = 3337, d = 2753), decrypt the ciphertext C = 2143.

Exercise 2: Text Decryption

Using the private key (n = 2773, d = 157), decrypt the ciphertext C = 2790. What letter does this represent?

Exercise 3: Multiple Block Decryption

Using the private key (n = 3233, d = 2753), decrypt the message (855, 2698). What does this message say?

Knowledge Check

1. What is the formula used for RSA decryption?

2. What is the relationship between the public exponent e and private exponent d in RSA?

3. Which technique is commonly used to optimize RSA decryption performance?

Complete RSA Process Summary

Now that you've learned about both encryption and decryption, let's summarize the complete RSA cryptosystem process.

RSA Workflow

  1. Key Generation
    1. Choose two large prime numbers p and q
    2. Compute n = p × q
    3. Calculate φ(n) = (p-1) × (q-1)
    4. Select public exponent e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1
    5. Compute private exponent d such that e × d ≡ 1 (mod φ(n))
    6. Public key: (n, e)
    7. Private key: (n, d)
  2. Encryption
    1. Convert the plaintext message to a number M (0 ≤ M < n)
    2. For long messages, break into blocks smaller than n
    3. Compute ciphertext C = Me mod n using the recipient's public key
    4. Transmit the ciphertext C to the recipient
  3. Decryption
    1. Receive the ciphertext C
    2. Compute plaintext M = Cd mod n using your private key
    3. For multiple blocks, decrypt each block separately
    4. Convert the numerical value M back to the original message format

Key Security Properties

  • Confidentiality: Only the holder of the private key can decrypt messages encrypted with the corresponding public key.
  • One-way function: It's computationally infeasible to determine the private key from the public key, as this would require factoring n into p and q.
  • Mathematical guarantee: The correctness of RSA is based on modular arithmetic and number theory, ensuring that decryption correctly recovers the original message.
Back Complete Course