0
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$
    – dave_thompson_085
    Commented Jun 16, 2021 at 1:27
  • $\begingroup$ 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}$$ $\endgroup$
    – fgrieu ♦
    Commented Jun 30, 2021 at 14:11

0

Reset to default

Browse other questions tagged or ask your own question.