# Decrypt Ciphertext Using different private key, given knowledge of original private key [duplicate]

A message, m is encrypted using a private key d.

p = prime()
q = prime()
e = 65537
c = pow(m, e, n)
PHI = (p-1)*(q-1)
d = mod_inverse(e, PHI)


Assume all these values are known to the attacker, except for the message (m) and ciphertext (c).

Is it possible to find an alternate value for d such that:

c ^ d_alternative % n == m (the ciphertext decrypts correctly to the message)


And

d_alternative % PHI != d (the new d modulus PHI does not equal the old d)


This second part is the catch: d and d_alternative cannot be modularly congruent.

Is this possible, and if so, how?

• In addition p and q must be distinct, and p-1,q-1 both coprime to e for this to work at all. d_alternative = d + k*lambda where lambda = lcm(p-1,q-1) aka Carmichael's totient and k is any integer not divisible by gcd(p-1,q-1) . This is because a valid d could have been computed in the first place as mod_inverse(e,lambda) as covered by dozens of existing Qs and wikipedia. Commented Jun 16, 2021 at 1:27
• Yes, that's possible for any definition of RSA that allows $d=e^{-1}\bmod\varphi(n)$. See answers there and there. One simple option is to use $$d'=\begin{cases}d-\varphi(n)/2&\text{if }2d>\varphi(n)\\d+\varphi(n)/2&\text {otherwise}\end{cases}$$
– fgrieu
Commented Jun 30, 2021 at 14:11