elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.


 


Tema destacado: Introducción a la Factorización De Semiprimos (RSA)


+  Foro de elhacker.net
|-+  Seguridad Informática
| |-+  Seguridad
| | |-+  Criptografía (Moderador: kub0x)
| | | |-+  Problema de RSA
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Problema de RSA  (Leído 4,975 veces)
ferry91

Desconectado Desconectado

Mensajes: 18


Ver Perfil
Problema de RSA
« en: 31 Octubre 2010, 20:59 »

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 Desconectado

Mensajes: 3.871


Toys in the attic.


Ver Perfil
Re: Problema de RSA
« Respuesta #1 en: 1 Noviembre 2010, 12:51 »

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 Desconectado

Mensajes: 18


Ver Perfil
Re: Problema de RSA
« Respuesta #2 en: 1 Noviembre 2010, 14:24 »

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 Desconectado

Mensajes: 3.871


Toys in the attic.


Ver Perfil
Re: Problema de RSA
« Respuesta #3 en: 1 Noviembre 2010, 16:50 »

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 Desconectado

Mensajes: 18


Ver Perfil
Re: Problema de RSA
« Respuesta #4 en: 2 Noviembre 2010, 10:50 »

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 Desconectado

Mensajes: 3.871


Toys in the attic.


Ver Perfil
Re: Problema de RSA
« Respuesta #5 en: 2 Noviembre 2010, 13:57 »

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 Desconectado

Mensajes: 76


Viking Metal


Ver Perfil
Re: Problema de RSA
« Respuesta #6 en: 7 Noviembre 2010, 08:25 »

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 Desconectado

Mensajes: 76


Viking Metal


Ver Perfil
Re: Problema de RSA
« Respuesta #7 en: 7 Noviembre 2010, 08:35 »

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

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  
Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines