1
$\begingroup$

We have a scenario where two people A,B have the same modulus $N$ but different exponents $e_1, e_2$ respectively for RSA encryption. They have decryption exponents $d_1, d_2$ respectively.

Suppose for some message $m$, it is sent to B and A intercepts it, i.e. A has $c \equiv m^{e_2} \pmod N$. Assuming $e_1,e_2$ are coprime, how might A be able to obtain $m$?

My thoughts are that $\exists u,v \in \mathbb Z$ such that $ue_1 + ve_2 = 1 \Rightarrow re_2 = 1 - ue_1$

Then A may obtain $c_1 \equiv c^r \equiv m^{re_2} \equiv m^{1-ue_1} \pmod N$ which subsequently lets A compute $c_2 \equiv c_1 ^ {d_1} \equiv m^{d_1-ud_1e_1} \equiv m^{d_1 - u} \pmod N$

Now if $n = gcd(d_1-u, e_2),$ we may find $x,y \in \mathbb Z$ such that $x(d_1-u) + ye_2 = n$.

A then computes $c_3 \equiv c_2^x * c^y \equiv m^n \pmod N$

Now if $n=1$ then we are done. However, if $n>1$ then I am not sure what else to do. I would like to show something along the lines of either $n = 1$ always or that we may find $k\in \mathbb Z$ such that $nk \equiv 1 \pmod {\phi(N)}$ where $\phi$ is the Euler Totient Function.

Any help would be greatly appreciated, thank you!

$\endgroup$
  • $\begingroup$ If they share the same modulus, either party should be able to infer the other party's private key from their public key just given their own key-pair... $\endgroup$ – SEJPM Apr 14 '18 at 17:07
  • 1
    $\begingroup$ @user366818: we don't need to know $\phi(N)$ (or $\text{lcm}(p-1,q-1)$), it suffices to know $k\phi(N)$, for any $k > 0$. $\endgroup$ – poncho Apr 14 '18 at 17:19
  • 1
    $\begingroup$ @user366818: the observation that you may have missed is that if $e_2d_2 \equiv 1 \pmod{k\lambda(N)}$, then $e_2d_2 \equiv 1 \pmod{\lambda(N)}$. Now, this $d_2$ is likely not the minimal $d_2$ value, however it'll work to recover $m$ and that's all we care about $\endgroup$ – poncho Apr 14 '18 at 17:53
  • 1
    $\begingroup$ Also if you don't like this approach, you can always factor $n$ given $e,d$... $\endgroup$ – SEJPM Apr 14 '18 at 17:54
  • 1
    $\begingroup$ @user366818: not in general; I suspect you're trying small $e$'s; that yields small $k$ values, and $\phi(N)$ has small factors. For a counterexample, consider $N = 19 \times 23$, $e = 25$, $d = 301$. $\endgroup$ – poncho Apr 14 '18 at 21:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.