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

Computing the Private Exponent d

Find the modular inverse d of e modulo φ(n) so that ed ≡ 1 (mod φ(n)), forming the private key (n, d).

Computing the Private Exponent d

You'll learn how to calculate the private RSA decryption exponent by finding the modular inverse of your public exponent.

The Core Idea

In RSA cryptography, once you've chosen your public exponent e and computed φ(n), you need to find the private exponent d. This is the secret key that will allow you to decrypt messages.

The requirement is simple but crucial: d must satisfy the equation:

ed ≡ 1 (mod φ(n))

In other words, d is the modular inverse of e modulo φ(n).

Why This Works

Think of d as the "undo button" for e. When you encrypt with e, you raise a message to the power e. To decrypt, you need d such that raising the result to the power d brings you back. The equation ed ≡ 1 (mod φ(n)) ensures this mathematical reversibility thanks to Euler's Theorem.

Finding d Using the Extended Euclidean Algorithm

You already know how to find modular inverses! Use the Extended Euclidean Algorithm:

  1. Run the algorithm on e and φ(n) to find Bézout coefficients
  2. Find integers x and y such that ex + φ(n)y = gcd(e, φ(n)) = 1
  3. The coefficient x (taken modulo φ(n) if negative) is your d

Example: If e = 7 and φ(n) = 40:

  • Extended Euclidean Algorithm gives: 7(23) + 40(-4) = 1
  • Therefore d = 23, since 7 × 23 = 161 ≡ 1 (mod 40)

Key Takeaway: The private exponent d is the modular inverse of e modulo φ(n), computed using the Extended Euclidean Algorithm to solve ed ≡ 1 (mod φ(n)).