4

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?

Pieter Verschaffelt
  • 481
  • here one of ways is described: https://crypto.stackexchange.com/questions/16283/how-to-use-common-modulus-attack . – Oleg567 Apr 10 '18 at 09:55
  • 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. – Oleg567 Apr 10 '18 at 09:58
  • @Oleg567 Thank you. Can I be certain that $gcd(e_1, e_2) = 1$ given this information? – Pieter Verschaffelt Apr 10 '18 at 10:40
  • 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. – Oleg567 Apr 10 '18 at 11:03

1 Answers1

6

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.

Oleg567
  • 17,295