Course contentsShow
← Mathematics
Lesson 2767 of 3,12154. Number TheoryFree lesson

RSA Decryption

Decrypt a ciphertext c by computing m ≡ c^d (mod n) using the private key and verify correctness.

RSA Decryption

What You'll Learn

You'll learn how to decrypt an RSA ciphertext using the private key and verify that you recover the original message.

The Core Idea

After a message has been encrypted using RSA (where someone computed c ≡ m^e (mod n) with the public key), you—the holder of the private key—can reverse this process. RSA decryption means taking the ciphertext c and computing:

m ≡ c^d (mod n)

where d is your private exponent and n is the modulus.

Think of it like this: encryption "locks" the message with the public exponent e, and decryption "unlocks" it with the private exponent d. The mathematical magic that makes this work is Euler's Theorem and the careful relationship between e and d (specifically, ed ≡ 1 (mod φ(n))).

How It Works in Practice

Suppose you receive ciphertext c = 82, and you know:

  • n = 3233 (the public modulus)
  • d = 2753 (your private exponent)

To decrypt, compute: m ≡ 82^2753 (mod 3233)

Using repeated squaring and modular arithmetic techniques (from earlier lessons on computing large powers), you'd find that m = 65.

Verification

After decrypting, you should verify correctness by re-encrypting the result with the public exponent e and checking that you get back the original ciphertext c. This confirms both the decryption and that the RSA parameters are working correctly.

Key Takeaway: RSA decryption recovers the plaintext message by computing m ≡ c^d (mod n) using the private exponent d; the correctness can be verified by re-encrypting the result.