4
$\begingroup$

If $m^{ed} \bmod n = m$ for message $m$, public key $e$ and private key $d$, then adding any integer multiple of $n$ to $m^{ed}$ still equals $m$ modulo $n$.

Supposing it exists, how do I find an equivalent key, d', such that $m^{ed'} = m^{ed} + kn$?

$\endgroup$
1
  • 5
    $\begingroup$ If $d$ is a private key, then $d + k \cdot \lambda(n)$ is also a private key for arbitrary $k$. $\endgroup$ Jul 3, 2016 at 10:44

1 Answer 1

7
$\begingroup$

The formula at the heart of RSA is:

$$x^{\lambda(n)} = 1 \pmod n$$

where $\lambda$ is the Carmichael function. In the case of two-prime RSA it's $\operatorname{lcm} (p - 1, q-1)$.

$$m^{k \cdot \lambda(n)+1} = m \pmod n$$

We choose $d$ such that $e\cdot d = 1 \pmod {\lambda(n)}$. If $\operatorname{GCD}(e,\lambda(n)) = 1$ then there is exactly one solution in the interval $0 \leq d < \lambda(n)$ but you can construct infinitely many solutions outside this interval by adding $k \cdot \lambda(n)$.


(There are some complications when $\operatorname{GCD}(x,n)\neq 1$, which I'll ignore, since it'll still work in that case)

$\endgroup$
1
  • 2
    $\begingroup$ So an answer is: make $d'=d+\lambda(n)$, or perhaps $d'=d-\lambda(n)$. This still works with a rule that $0<d<n$ or $0<d<\varphi(n)$ (assuming $n$ is odd). $\endgroup$
    – fgrieu
    Jul 3, 2016 at 16:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.