Problema de RSA

[ferry91]

El enunciado dice lo siguiente:

Alicia y Bob utilizan una clave RSA con el mismo módulo, pero diferentes exponentes para cifrar. Es decir, las claves públicas de Alicia y Bob son respectivamente, pka = (N,ea) y pkb = (N,eb). Un adversario pasivo se apropia de dos cifrados, uno de Alicia Ca y otro de Bob Cb. Los dos cifrados corresponden a un mismo mensaje m. ¿Qué ha de hacer la adversaria Eva para obtener información del mensaje m?

No se ni por donde empezarlo, si pudieran hecharme una mano estaría muy agradecido.

Un saludo.

[APOKLIPTICO]

Donde conseguis estos problemas? Realmente estarían muy buenos para el taller...

En cuanto a tu problema:
Acordate que:
n = p * q
phi(n) = (p - 1) * (q - 1).
e < phi(n) y coprimo con phi(n).
e * d mod phi(n) = 1 ("e" es el público y "d" el privado).
Ahora miremos a los cifrados:
m^e1 mod n = m^e2 mod n (siendo e1 y e2 los dos exponentes públicos).

Ahí te lo plantee, hoy a la tarde voy a ver si te puedo dar una mano, pero ahora mismo me tengo que ir a la facu!
Nos vemos luego!
Un abrazo
APOKLIPTICO

[ferry91]

Bueno el problema me lo han puesto en clase.

En el paso:

m^e1 mod n = m^e2 mod n

¿Es esto realmente cierto? Puesto que tenemos dos cifrados (c1 y c2) de un mismo mensaje (m), como los exponentes son diferentes los dos cifrados pueden ser diferentes. Es más sería una casualidad enorme que fuesen iguales.

Es por eso que me atasco en la resolución.

[APOKLIPTICO]

En clase? Estudiás criptografía?? Que buena onda...
Perdón! me equivoqué... Lo hice rápido a la mañana y medio dormido...
Lo que quise decir es:
c^d1 mod n = c^d2 mod n. (siendo d1 y d2 los exponentes privados).

Esto quiere decir que d1 = d2 + n * x o bien d2 = d1  + n * x.
El exponente mayor, va a ser igual al exponente menor más x veces el módulo.

[ferry91]

Bueno, estudio Ingenieria en telecomunicaciones, y tengo una asignatura de Sistemas de Comunicación, en la que tocamos la seguridad informática.

Entonces, la información que Eva puede sacar del mensaje, ¿Cuál es? Es que no me ha quedado claro este punto.

Gracias.

[APOKLIPTICO]

Yo lo que pude ver es que hay una relación entre los dos exponentes:
d2 = d1 + n * x.
Osea que el exponente más grande, es el más chico sumado al módulo "x" veces.

[dakomt]

Hola, el problema que planteas es uno de los ataques típicos contra RSA, denominado "ataque del módulo común" (Common modulus attack).

Si buscas en google encontrás rápidamente la solución... Pero si no quieres hacer trampas e intentarlo por tu cuenta te dejo algunas pistas que tal vez te sirvan...

La idea está en considerar que tanto ea como eb son coprimos entre sí (es muy probable que sea así), por lo tanto, resulta fácil calcular dos números enteros, r y s , tales que r * ea  + s * eb = 1. (Mediante algoritmo extendido de euclides)

Sabiendo r y s y algunas propiedades elementales de la aritmetica modular no es muy complicado demostrar que se puede calcular M a partir de ca , cb , r y s.

[dakomt]

Y un añadido... además de Eva... Alicia y Bob también podrían hacer fechorías jeje.. como comparten el mismo módulo N y cada uno sabe su factorización, tanto Alicia como Bob podrían calcular fácilmente la clave privada de cada uno con tan sólo recibir un mensaje cifrado.