3
$\begingroup$

Suppose 2 entities have a different RSA key-pair, but have the same modulus n. Suppose also that a message M has been encrypted by both pairs. How can one recover M with a reasonable probability?

We know the public keys $e_1$ and $e_2$ of both entities, and we know $n$. From the RSA-algorithm, we also know that $gcd(e_1, \phi(n)) = 1$ and $gcd(e_2, \phi(n)) = 1$. Is it now possible to recover $phi(n)$ from these equations, or one of the private keys $d_1$ or $d_2$, or should I be looking at a completely different approach into solving this problem?

$\endgroup$
  • $\begingroup$ here one of ways is described: crypto.stackexchange.com/questions/16283/… . $\endgroup$ – Oleg567 Apr 10 '18 at 9:55
  • $\begingroup$ to find $s_1, s_2$ such that $e_1s_1+e_2s_2=1$, we can apply Extended Euclidean Algorithm. To be accurate, one of $s_1,s_2$ is negative, so we should apply calculation by modulo $\phi(n)$, i.e. to know this value too. $\endgroup$ – Oleg567 Apr 10 '18 at 9:58
  • $\begingroup$ @Oleg567 Thank you. Can I be certain that $gcd(e_1, e_2) = 1$ given this information? $\endgroup$ – Pieter Verschaffelt Apr 10 '18 at 10:40
  • $\begingroup$ If $gcd(e_1,e_2)=1$, then we able to retrieve the message (see answer); but it can occur with low probability that $gcd(e_1,e_2)>1$, then described algorithm wouldn't work. $\endgroup$ – Oleg567 Apr 10 '18 at 11:03
5
$\begingroup$

Let we know $e_1, e_2$ and $n$.

And we know both ciphertexts $C_1 = M^{e_1}(\bmod n)$ an $C_2=M^{e_2} (\bmod n)$.

Then, assuming that $GCD(e_1,e_2)=1$, applying Extended Euclidean Algorithm, it is easy to find $s_1,s_2$ such that $$e_1s_1+e_2s_2=1.$$ And therefore $$C_1^{s_1}\cdot C_2^{s_2} \equiv M^{e_1s_1} \cdot M^{e_2s_2} \equiv M(\bmod n).\tag{1}$$

Note 1: one of the numbers $s_1, s_2$ is negative, so it would be comfortable to know the value $$D\equiv C^{-1} (\bmod n)\tag{2}$$ previously for certain of ciphertexts. We can easily derive this value from EEA too: $$C\cdot D \equiv 1 (\bmod n),$$ $$C\cdot D - n \cdot L = 1,\tag{3}$$ i.e. for given pair $(C,n)$ (if $GCD(C,n)=1$) find coefficients $D,L$ for which $(3)$ holds.

Note 2: in the case when $GCD(e_1,e_2)\ne 1$ or $GCD(C,n)=1$ (which can occur theoretically, but with very small probability), this algorithm wouldn't work.

Note 3: if $GCD(C,n)\ne 1$, then this GCD coincides with one of factors of the number $n$: very lucky example, since we'll able to derive factors of $n$, and $\phi(n)$ instantly then.

Example:
$n = 101\cdot103$.
$e_1 = 5$, $e_2 = 13$.
$M = 64$ (unknown for us yet).
Then
$C_1 = 64^5 \equiv 6582(\bmod 10403)$,
$C_2 = 64^{13} \equiv 2445(\bmod 10403)$;

having $e_1=5,e_2=13$, we easily find $s_1 = -5,s_2=2$: $$5\cdot (-5)+13\cdot 2 = 1, $$

hence $$ M \equiv 6582^{-5} \cdot 2445^{2} (\bmod 10403). $$ Find now value $D\equiv 6582^{-1} (\bmod 10403)$: for given pair $(6582, 10403)$ find $D,L$ such that $(3)$ holds: $$ 6582\cdot(- 3327) + 10403\cdot 2105 = 1; $$ we focus on the number $$D \equiv -3327 \equiv 7076 (\bmod 10403).$$

Then $$ M \equiv 6582^{-5} \cdot 2445^{2} \equiv \\ 7076^5 \cdot 2445^{2} \equiv \\ 4746 \cdot 6703 \equiv \\ 31812438 \equiv 64 (\bmod10403). $$ Message $M$ is recovered.

Example 2:
$n = 101\cdot103$.
$e_1 = 7$, $e_2 = 14$.
$\phi(n)=100\cdot 102 = 10200$;
$GCD(e_1,\phi(n))=1$, $GCD(e_2,\phi(n))=1$,
but we have $GCD(e_1,e_2)=7$, so this algorithm wouldn't work in this case.

$\endgroup$
  • 1
    $\begingroup$ Thank you very much! :) I completely understand now $\endgroup$ – Pieter Verschaffelt Apr 10 '18 at 11:07
  • $\begingroup$ You're welcome. That's nice. $\endgroup$ – Oleg567 Apr 10 '18 at 11:17

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.