1
Calculate Euler's Totient φ(n)
φ(n) = (p-1)(q-1)
Since n = p × q where p and q are primes, we calculate φ(n) which counts integers coprime to n. This is essential for finding the private key.
2
Find Modular Multiplicative Inverse
d ≡ e⁻¹ (mod φ(n))
Find d such that (e × d) ≡ 1 (mod φ(n)). This means e × d leaves remainder 1 when divided by φ(n).
3
Use Extended Euclidean Algorithm
gcd(e, φ(n)) = 1
Apply the Extended Euclidean Algorithm to find integers d and k such that: e × d + φ(n) × k = 1
Extended Euclidean Algorithm Process
This algorithm finds d by working backwards through the Euclidean algorithm steps, expressing the GCD as a linear combination of e and φ(n).
Private Exponent (d)
d = e⁻¹ mod φ(n)
• Secret component
• Used for decryption
• Same bit length as n
• Used for decryption
• Same bit length as n
Modulus (n)
n = p × q
• Same as public key
• Shared component
• Links public and private
• Shared component
• Links public and private
🔒 CRITICAL: Private key (d) must be kept absolutely secret!
Complete Private Key Derivation Flow
Given: p, q (primes), e = 65537
→
Calculate: n = p × q
→
Calculate: φ(n) = (p-1)(q-1)
→
Find: d ≡ e⁻¹ (mod φ(n))
→
Result: Private Key = (d, n)
Interactive Demonstrations
Click a button above to see interactive demonstrations!