 Autor
|
Tema: Problema de RSA (Leído 6,596 veces)
|
ferry91
 Desconectado
Mensajes: 18
|
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.
|
|
|
|
|
En línea
|
|
|
|
APOKLIPTICO
Desconectado
Mensajes: 3.871
Toys in the attic.
|
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
|
|
|
|
|
En línea
|
AMD Phenom II 1075T X6 @ 290 Mhz x 11 (HT 2036 Mhz NB Link 2616 Mhz) 1.23 Vcore
ASUS M4A89GTD-PRO/USB3
2x2gb G-Skill RipjawsX DDR3 1600 Mhz CL7 (7-8-7-24-25-1T)
Seagate 500 Gb
XFX HD4850 512Mb GDDR3. 650 Mhz/995 Mhz 1.1 Tflops.
|
|
|
ferry91
Desconectado
Mensajes: 18
|
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.
|
|
|
|
|
En línea
|
|
|
|
APOKLIPTICO
Desconectado
Mensajes: 3.871
Toys in the attic.
|
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.
|
|
|
|
|
En línea
|
AMD Phenom II 1075T X6 @ 290 Mhz x 11 (HT 2036 Mhz NB Link 2616 Mhz) 1.23 Vcore
ASUS M4A89GTD-PRO/USB3
2x2gb G-Skill RipjawsX DDR3 1600 Mhz CL7 (7-8-7-24-25-1T)
Seagate 500 Gb
XFX HD4850 512Mb GDDR3. 650 Mhz/995 Mhz 1.1 Tflops.
|
|
|
ferry91
Desconectado
Mensajes: 18
|
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.
|
|
|
|
|
En línea
|
|
|
|
APOKLIPTICO
Desconectado
Mensajes: 3.871
Toys in the attic.
|
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.
|
|
|
|
|
En línea
|
AMD Phenom II 1075T X6 @ 290 Mhz x 11 (HT 2036 Mhz NB Link 2616 Mhz) 1.23 Vcore
ASUS M4A89GTD-PRO/USB3
2x2gb G-Skill RipjawsX DDR3 1600 Mhz CL7 (7-8-7-24-25-1T)
Seagate 500 Gb
XFX HD4850 512Mb GDDR3. 650 Mhz/995 Mhz 1.1 Tflops.
|
|
|
dakomt
Desconectado
Mensajes: 76
Viking Metal
|
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.
|
|
|
|
|
En línea
|
|
|
|
dakomt
Desconectado
Mensajes: 76
Viking Metal
|
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.
|
|
|
|
|
En línea
|
|
|
|
|
 |
