Explicación incompleta en RSA

[Hawkings]

En la solución al problema RSA no se explica cómo obtener el valor e. Hay decenas de miles de valores posibles de e y para cada uno de ellos hay un d y por tanto un posible "descifrado" que da lugar a cuatro letras diferentes, y no veo claro cómo distinguir la buena de entre decenas de miles de posibilidades teniendo en cuenta que está prohibido probar muchas opciones por fuerza bruta en la plataforma del CTF.

Por otro lado, si no me equivoco la forma de codificar los datos en bloques de cuatro letras no es válida. Por ejemplo, si quisiéramos codificar ZZZZ obtendríamos 25*26^3+25*26^2+25*26+25 = 456 975, pero nos encontramos con el problema que φ(n) = 86 016 < 456 975. Por este motivo creo que para codificar las cadenas se deben usar bloques de una, dos o tres letras como máximo, y no cuatro.

PD: enhorabuena a todo el staff de CodeCamp17, ha sido un evento muy entretenido :)

[gabilm]

Hola,

El 20 feb 2017, a las 18:07, Hawkings ***@***.***> escribió: En la solución al problema RSA no se explica cómo obtener el valor e. Hay decenas de miles de valores posibles de e y para cada uno de ellos hay un d y por tanto un posible "descifrado" que da lugar a cuatro letras diferentes, y no veo claro cómo distinguir la buena de entre decenas de miles de posibilidades teniendo en cuenta que está prohibido probar muchas opciones por fuerza bruta en la plataforma del CTF.

Gracias por el comentario. En la descripción de la solución se plantea un valor de e tal que mcd(e/x)=1, siendo x=(p-1)*(q-1). En este caso el valor de e es 17. Creo recordar que con el software de ayuda se podía calcular (no tengo ahora mismo un windows para comprobarlo :) ) Es cierto que dando el valor de e el reto hubiera sido más accesible :)

Por otro lado, si no me equivoco la forma de codificar los datos en bloques de cuatro letras no es válida. Por ejemplo, si quisiéramos codificar ZZZZ obtendríamos 25*26^3+25*26^2+25*26+25 = 456 975, pero nos encontramos con el problema que φ(n) = 86 016 < 456 975. Por este motivo creo que para codificar las cadenas se deben usar bloques de una, dos o tres letras como máximo, y no cuatro.

Bueno, puse un ejemplo que pueda resolverse para una cadena de 4 caracteres, por dar algo más de juego en la solución, hay muchas variantes que se pueden utilizar. Si no me he equivocado en la descripción de la solución que hay en el git la solución esperada es “CAMP”. Gracias por el esfuerzo y por el interés mostrado :) Un saludo, Gabi.

…

PD: enhorabuena a todo el staff de CodeCamp17, ha sido un evento muy entretenido :) — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#4>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AL8qZGqzpHQujVAeX4q5TZIdkTtUw7y9ks5rechIgaJpZM4MGbTE>.

----------------------------------------------------------- Gabriel López Millán Departamento de Ingeniería de la Información y las Comunicaciones University of Murcia Spain Tel: +34 868888504 Fax: +34 868884151 email: gabilm@um.es <mailto:gabilm@um.es>

[Hawkings]

Hola Gabi, muchas gracias por contestar. En efecto para e=17 se cumple que mcd(e,x)=1, pero también se cumple para e=3, e=5, e=7, ..., e=65537, ...

La idea es que hay miles y miles de posibilidades, todas ellas válidas y todas ellas dando una posible descodificación que habría que probar en la plataforma para comprobar si es correcta, pero hacerlo sería incumplir las normas.

Por otro lado, si bien es cierto que la solución del problema en este caso sí se puede codificar, creo que es razonable esperar que cualquier otra solución posible se pueda codificar, ya que es lo que se da a entender en el problema (donde aparecen las 26 letras de la A a la Z). Utilizando bloques de 4 letras como mensajes, la solución nunca podría empezar por F ni por ninguna letra posterior, por lo que más de la mitad de las combinaciones de letras no son representables usando este método.

Un saludo.

[gabilm]

Hola Hawkings, Vale, ya recuerdo de donde saqué el ejemplo, de aquí: http://www.cs.virginia.edu/~kam6zx/rsa/a-worked-example/ Aquí viene mejor detallada la explicación. Un saludo, Gabi.

…

El 20 feb 2017, a las 23:52, Hawkings ***@***.***> escribió: Hola Gabi, muchas gracias por contestar. En efecto para e=17 se cumple que mcd(e,x)=1, pero también se cumple para e=3, e=5, e=7, ..., e=65537, ... La idea es que hay miles y miles de posibilidades, todas ellas válidas y todas ellas dando una posible descodificación que habría que probar en la plataforma para comprobar si es correcta, pero hacerlo sería incumplir las normas. Por otro lado, si bien es cierto que la solución del problema en este caso sí se puede codificar, creo que es razonable esperar que cualquier otra solución posible se pueda codificar, ya que es lo que se da a entender en el problema (donde aparecen las 26 letras de la A a la Z). Utilizando bloques de 4 letras como mensajes, la solución nunca podría empezar por F ni por ninguna letra posterior, por lo que más de la mitad de las combinaciones de letras no son representables usando este método. Un saludo. — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#4 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AL8qZOR0UR0RqmpzWv9rtkOOCKkNBcPSks5rehkRgaJpZM4MGbTE>.

----------------------------------------------------------- Gabriel López Millán Departamento de Ingeniería de la Información y las Comunicaciones University of Murcia Spain Tel: +34 868888504 Fax: +34 868884151 email: gabilm@um.es <mailto:gabilm@um.es>

[lilezek]

@gabilm Creo que @Hawkings dice que escogiendo un e se puede cifrar, pero la información p,q y el mensaje sin conocer e es insuficiente para obtener el mensaje original. Para descifrar se necesita el valor d, que sin conocer e, y el valor (p-1)*(q-1) puede ser cualquiera de una lista muy larga. Si bien cualquiera de esos valores (que no son muchos) pueden ser la solución, es ilegal bajo las bases del CTF hacer fuerza bruta y probar todas esas posibilidades.

Conocidos p,q, y el valor del mensaje cifrado, el sistema es `seguro'.

[gabilm]

Hola, Efectivamente si no se da la e, la única manera de tratarlo es por fuerza bruta. Mi intención no era esa, y tampoco sabía que era ilegal, lo tendré en cuenta para la siguiente. Supongo que habrá que marcar este reto como no válido. Gracias por los comentarios, aunque yo propondría dar los puntos a los que llegaron a tal deducción :) Un saludo, Gabi.

…

El 21 feb 2017, a las 17:16, lilezek ***@***.***> escribió: @gabilm <https://github.com/gabilm> Creo que @Hawkings <https://github.com/Hawkings> dice que escogiendo un e se puede cifrar, pero la información p,q y el mensaje sin conocer e es insuficiente para obtener el mensaje original. Para descifrar se necesita el valor d, que sin conocer e, y el valor (p-1)*(q-1) puede ser cualquiera de una lista muy larga. Si bien cualquiera de esos valores (que no son muchos) pueden ser la solución, es ilegal bajo las bases del CTF hacer fuerza bruta y probar todas esas posibilidades. Conocidos p,q, y el valor del mensaje cifrado, el sistema es `seguro'. — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#4 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AL8qZHMohlQgYO_iEeIL1a2btQ_tG9DZks5rew3PgaJpZM4MGbTE>.

----------------------------------------------------------- Gabriel López Millán Departamento de Ingeniería de la Información y las Comunicaciones University of Murcia Spain Tel: +34 868888504 Fax: +34 868884151 email: gabilm@um.es <mailto:gabilm@um.es>