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:
- Run the algorithm on
eandφ(n)to find Bézout coefficients - Find integers
xandysuch thatex + φ(n)y = gcd(e, φ(n)) = 1 - The coefficient
x(taken moduloφ(n)if negative) is yourd
Example: If e = 7 and φ(n) = 40:
- Extended Euclidean Algorithm gives:
7(23) + 40(-4) = 1 - Therefore
d = 23, since7 × 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)).