Desencriptar un mensaje RSA cuando está encriptado por el mismo módulo

Question

Supongamos que 2 entidades tienen un par de claves RSA diferentes, pero tienen el mismo módulo n. Supongamos también que un mensaje M ha sido cifrado por ambos pares. ¿Cómo se puede recuperar M con una probabilidad razonable?

Conocemos las claves públicas $e_1$ y $e_2$ de ambas entidades, y sabemos que $n$ . Por el algoritmo RSA, también sabemos que $gcd(e_1, \phi(n)) = 1$ y $gcd(e_2, \phi(n)) = 1$ . ¿Es posible ahora recuperar $phi(n)$ de estas ecuaciones, o una de las claves privadas $d_1$ o $d_2$ ¿O debería buscar un enfoque completamente diferente para resolver este problema?

Answer 1

Que sepamos $e_1, e_2$ y $n$ .

Y sabemos que ambos textos cifrados $C_1 = M^{e_1}(\bmod n)$ un $C_2=M^{e_2} (\bmod n)$ .

Entonces, suponiendo que $GCD(e_1,e_2)=1$ , aplicando Algoritmo euclidiano ampliado es fácil de encontrar $s_1,s_2$ tal que $$e_1s_1+e_2s_2=1.$$ Y por lo tanto $$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}$$

Nota 1: uno de los números $s_1, s_2$ es negativo, por lo que sería cómodo conocer el valor $$D\equiv C^{-1} (\bmod n)\tag{2}$$ previamente para algunos de los textos cifrados. Podemos derivar fácilmente este valor de EEE también: $$C\cdot D \equiv 1 (\bmod n),$$ $$C\cdot D - n \cdot L = 1,\tag{3}$$ es decir, para un par dado $(C,n)$ (si $GCD(C,n)=1$ ) encontrar los coeficientes $D,L$ para lo cual $(3)$ se mantiene.

Nota 2: en el caso de que $GCD(e_1,e_2)\ne 1$ o $GCD(C,n)=1$ (que puede ocurrir teóricamente, pero con muy poca probabilidad), este algoritmo no funcionaría.

Nota 3: si $GCD(C,n)\ne 1$ entonces este GCD coincide con uno de los factores del número $n$ : ejemplo muy afortunado, ya que podremos derivar factores de $n$ y $\phi(n)$ instantáneamente entonces.

Ejemplo:
$n = 101\cdot103$ .
$e_1 = 5$ , $e_2 = 13$ .
$M = 64$ (desconocido para nosotros todavía).
Entonces
$C_1 = 64^5 \equiv 6582(\bmod 10403)$ ,
$C_2 = 64^{13} \equiv 2445(\bmod 10403)$ ;

teniendo $e_1=5,e_2=13$ , encontramos fácilmente $s_1 = -5,s_2=2$ : $$5\cdot (-5)+13\cdot 2 = 1, $$

por lo que $$ M \equiv 6582^{-5} \cdot 2445^{2} (\bmod 10403). $$ Encuentre ahora el valor $D\equiv 6582^{-1} (\bmod 10403)$ : para un par dado $(6582, 10403)$ encontrar $D,L$ tal que $(3)$ se mantiene: $$ 6582\cdot(- 3327) + 10403\cdot 2105 = 1; $$ nos centramos en el número $$D \equiv -3327 \equiv 7076 (\bmod 10403).$$

Entonces $$ M \equiv 6582^{-5} \cdot 2445^{2} \equiv \\ 7076^5 \cdot 2445^{2} \equiv \\ 4746 \cdot 6703 \equiv \\ 31812438 \equiv 64 (\bmod10403). $$ Mensaje $M$ se recupera.

Ejemplo 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$ ,
pero tenemos $GCD(e_1,e_2)=7$ , por lo que este algoritmo no funcionaría en este caso.