MOOC El algoritmo RSA


Lección 10. Ataque por paradoja del cumpleaños
Dr. Jorge Ramió Aguirre - 4/01/2013 

En la lección 10 Ataque por paradoja del cumpleaños, la última de este curso, veremos otro de los ataques que pueden hacerse al algoritmo RSA. Conocido como ataque basado en la paradoja del cumpleaños, cuando éste prospera habremos encontrado la clave privada d, una clave privada pareja d' o bien, en muy pocos casos, un falso positivo que no tendrá ninguna utilidad. Lo más interesante de todo esto es que para realizar dicho ataque sólo hace falta contar con los valores públicos de la clave de la víctima, nada más. Ni siquiera es necesario capturar un criptograma como en el ataque visto en la lección anterior. Lógicamente, este ataque que nos permite conocer la clave privada o una clave privada pareja sin necesidad de factorizar el módulo n, parece más atractivo que el ataque por cifrado cíclico y mucho más peligroso para esa víctima si llega a prosperar en un tiempo prudente.

Si deseas descargar las diapositivas del curso en formato pptx animado o bien en pdf, puedes hacerlo desde esta dirección.

Este icono y el fondo de color amarillo te indican que entras en una zona de prácticas.

Este icono y el fondo de color azul te indican que entras en una zona de cuestiones para reflexionar e investigar.

El tiempo recomendado para el seguimiento de esta lección, la realización de sus prácticas y ejercicios, así como la búsqueda de información en la red sobre los temas abiertos planteados al final de cada apartado, es de dos semanas.

Temario

Objetivos

  • 1. Comprobar que en RSA es posible encontrar la clave privada sin necesidad de factorizar el módulo n.
  • 1. Analizar las características del algoritmo de ataque propuesto por Merkle y Hellman.
  • 2. Comprobar el comportamiento de este ataque ante cambios de la clave públice e.

Software que vas a utilizar en esta lección


APARTADO 10.1. LA PARADOJA DEL CUMPLEAÑOS

Aunque su nombre es el de paradoja, en realidad no es tal porque no hay nada en este problema que nos indique una contradicción matemática. Se trata, simplemente, de una serie cuyo resultado parece a simple vista asombroso y de ahí el nombre de paradoja.

El desarrollo del problema podría ser el siguiente:

En una aula con decenas de personas, marcamos en la pizarra mediante un recuadro todos los días del año, que supondremos no es bisiesto. Las personas abandonan el aula y entran nuevamente a ella de una manera aleatoria, de uno en uno, marcando con un aspa el recuadro en que aparece el día de su cumpleaños en esa pizarra. El proceso termina cuando hay una colisión, es decir, cuando hay una persona que entra al aula y ve que la fecha de su cumpleaños ya está marcada.

Repetimos este proceso (limpiar la pizarra, todos fuera del aula y entrando de uno en uno) unas cuantas veces.

La pregunta es, ¿cuántas personas deben entrar para que, en media, exista una probabilidad mayor que el 50% (lo que se conoce como confianza) de que ya esté marcado ese cumpleaños?

Aunque el resultado nos pueda sorprender, y de ahí su nombre de paradoja, en media basta que entren 23 personas para que la siguiente persona tenga ya más de un 50% de probabilidad de que su cumpleaños esté marcado.

Y esto tiene sentido porque la primera persona que entra al aula se encuentra con los 365 días del año no marcados, la segunda se encuentra con un día menos libre de los 365, la tercera con dos días menos y así sucesivamente, por lo que va aumentando la probabilidad de que exista una colisión.

Explicación:

Si las personas entran en el aula de uno en uno y van marcando en esa pizarra con 365 días su cumpleaños, el primero tendrá una probabilidad de que su cumpleaños no esté borrado igual a n/n = 1, el segundo de (n-1)/n, el tercero (n-2)/n, etc.

La probabilidad de no coincidencia será pNC = n!/nk(n-k)! siendo k el número de personas. Si lo deseas, mira la explicación detallada y justificación de esta fórmula en este enlace a Birthday Paradox.

Si k = 23, se tiene que pNC = 0,493 y, por tanto, la probabilidad de coincidencia pC o colisión será el complemento a la unidad, (1 - 0,493), es decir, pC = 0,507 que es mayor que el 50%.

Te recomiendo veas una explicación más completa y con gráficas desde esta página Web de Estadísticas para todos, que incluye un programa de simulación en Excel y enlaces a interesantes programas online de la Universidad de Illinois y de la Universidad de Stanford, a los que puedes acceder haciendo clic en las figuras que se muestran más abajo.

Enlace a la página The Birthday Problem de la Universidad de Illinois

Enlace a la página Random Birthday Applet de la Universidad de Stanford

Ejercicio 10.1.1

Entra en la aplicación Random Birthday Applet de la Universidad de Stanford de la figura superior. Marca generar 20 cumpleaños en modo Fast Update y ve pulsando en Start.
Mira cómo comienzan aparecer las colisiones y observa cómo se comportan dichas colisiones a medida que se va repitiendo la generación de fechas de cumpleaños y se comienza a llenar el calendiario de colisiones. ¿Es ese comportamiento lineal?

Solución:

No te entregaré aquí la solución al ejercicio, pero sí en cambio dos capturas de pantalla. La primera figura corresponde a la segunda vez (40 fechas) que he pulsado en Start y la segunda figura a la décima vez (200 fechas) que he pulsado en Start. Comprueba estas capturas y saca tus propias conclusiones.

Generación de 40 fechas de cumpleaños aleatorias y una colisión

Generación de 200 fechas de cumpleaños aleatorias y 38 colisiones

Tal vez te hayas hecho ya la pregunta en el sentido contrario. Esto es, ¿cuántas fechas de cumpleaños aleatorias deberías generar en media para que hubiese al menos una colisión en todos los días del calendario? Como no hay nada mejor que un ejemplo práctico, vas a contestar a esta pregunta en el siguiente ejercicio.

Ejercicio 10.1.2

En la misma aplicación Random Birthday Applet, marca generar 100 cumpleaños en modo Fast Update y ve pulsando en Start hasta que tengas todo el calendario en rojo.
¿Cuántos cumpleaños has tenido que generar? ¿Más de 1.000? ¿Más de 3.000? ¿Tal vez 7.500?

Cuestiones para reflexionar e investigar:
1. ¿Por qué crees que a este problema se le llama paradoja?
2. ¿Qué sucede con la probabilidad de colisión a medida que avanza el ataque?
3. ¿Qué implicaciones tendría en un ataque real el comportamiento que has contestado en el punto anterior?
4. En un concierto al que asisten 10.000 personas, ¿qué posibilidad hay de que todos los asistentes tengan al menos una persona que esté en ese recinto y que cumpla años en el mismo día?


APARTADO 10.2. EL ALGORITMO DE MERKLE Y HELLMAN

En el año 1981 Ralph Merkle y Martin Hellman proponen un método para atacar al algoritmo DES, Data Encryption Standard, en su modalidad de doble cifrado con texto en claro y criptograma conocidos, basado en el problema o paradoja del cumpleaños y que deriva finalmente en lo que conocemos como ataque por encuentro a medio camino, meet in the middle, y no hace aconsejable este tipo de cifrado.

Este mismo principio nos permitirá encontrar colisiones en las cifras realizadas con RSA. El ataque tiene la particularidad de que al prosperar tras observarse una colisión, nos entregará la clave privada de la víctima, una clave privada pareja, y en muy pocos casos un falso positivo. Este concepto de falso positivo se analizará más adelante.

¿Cómo funciona este ataque? Muy simple: se elije un valor o número N de ataque aleatorio cualquiera y, conocido el módulo n de la víctima que es un dato público, dividimos ese módulo en dos mitades; la mitad izquierda o baja del módulo y la mitad derecha o alta del módulo, y con dichos valores que supondremos la clave k a la que se cifra el valor de ataque N se realiza la operación de cifra Nk mod n en la zona baja y alta del módulo hasta que se encuentre un resultado igual o colisión, momento en el cual este algoritmo llega a su fin.

En la siguiente figura se resumen los pasos de este ataque.

Resumen del ataque por paradoja del cumpleaños

Observa que esta colisión podrá producirse en cualquier parte del espacio del módulo n, es decir para cualquier valor de i y cualquier valor de j, como comprobarás en el siguiente ejercicio.

Ejercicio 10.2.1

Para una clave pública RSA con n = 209 (p = 11, q = 19) y e = 7, realiza las operaciones de cifra de este algoritmo, usando como número de ataque N = 25 y los valores iniciales de i = 17 y j = 138. Usa el software Fortaleza de Cifrados.

Solución:

Después de [(31-17)+1]x2 = 30 cifrados, se ha producido una colisión:
El resultado 25152 mod 209 = 130 colisiona con el valor 2517 mod 209 = 130.

No obstante, es recomendable determinar los espacios de los contadores i y j de forma que abarquen todo el módulo, por lo que el espacio óptimo de ataque será:

  1. Espacio del contador i de la clave k en la zona izquierda o baja del módulo: 1 ≤ i < n/2
  2. Espacio del contador j de la clave k en la zona derecha o alta del módulo: n/2 ≤ j < n

Observación: Como n nunca será par al ser el resultado del producto de dos primos, se tomará el valor entero inferior a n/2 para separar las dos zonas. Es decir, si n = 133 (pxq = 7x19), entonces n/2 = 66 y con ese valor comenzarán las cifras del contador j.

Operaciones del ataque:

En la zona baja del módulo con el contador i se realizarán los siguientes cálculos:
N1 mod n = Ci1;   N2 mod n = Ci2;   N3 mod n = Ci3; ...   Nn/2-2 mod n = Ci(n/2-2);   Nn/2-1 mod n = Ci(n/2-1)

Y simultáneamente en la zona alta del módulo con el contador j se realizarán los siguientes cálculos:
Nn/2 mod n = Cj(n/2);   Nn/2+1 mod n = Cj(n/2+1);   Nn/2+2 mod n = Cj(n/2+2); ...   Nn-2 mod n = Cj(n-2);   Nn-1 mod n = Cj(n-1)

Esto es mejor verlo representado en dos columnas, donde el eje del tiempo será el desplazamiento vertical hacia abajo como se aprecia en la siguiente figura.

Operaciones del ataque por paradoja del cumpleaños

Por tanto, se realiza el primer cifrado de la columna i que nos entrega el valor C1 (obviamente el mismo valor de ataque N) y se compara con el primer cifrado de la columna j que entrega el valor Cj(n/2+1). Se aumentan en una unidad los contadores i y j, repitiendo los cifrados en ambas columnas, hasta que un resultado de la columna j colisiona con un resultado previo de la columna i (o viceversa) y cuando esto último ocurre, habrá culminado el ataque.

Para encontrar otras características de este efecto de colisión, vamos a realizar el siguiente ejercicio.

Ejercicio 10.2.2

Para la clave pública RSA con n = 133 (p = 7, q = 19) y e = 5, utiliza como número de ataque N = 31, N = 55 y luego N = 100. Observa cuándo se produce una colisión. Usa el software Fortaleza de Cifrados.

Solución:

Elegimos entonces los siguientes rangos bajo y alto: 1 < i < 66; 65 < j < 132.
Es decir, i = 2, 3, 4, ... 63, 64, 65; j = 66, 67, 68, ... 129, 139, 131. Vamos a suponer que primero realizamos la cifra en la zona baja y luego la cifra en la zona alta.
Procedemos a cifrar con N = 31:

Se ha producido una colisión pues el resultado en j 3167 mod 133 = 31 es igual que el valor en i 311 mod 133 = 31.

Procedemos ahora a cifrar con N = 55:

Se ha producido una colisión pues el resultado en j 5573 mod 133 = 55 es igual que el valor en i 551 mod 133 = 55.

Procedemos ahora a cifrar con N = 100:

Se ha producido una colisión pues el resultado en i 1003 mod 133 = 106 es igual que el valor en j 10066 mod 133 = 106.

Del ejercicio anterior podemos sacar 3 conclusiones importantes:

1. Que la velocidad del ataque va a depender del número N con el que éste comienza pues se observan cantidades diferentes de operaciones de cifrado en función de ese valor.

2. Que las colisiones pueden deberse a una coincidencia de resultados entre un valor de la columna j con uno anterior de la columna i, o viceversa.

3. Y la tercera muy importante: que la colisión se manifiesta por un último valor de la columna j que ha coincidido con el primer valor de la columna i, o viceversa.

Lo interesante de esta última conclusión es que sólo hace falta conocer los dos primeros valores del ataque, esto es C1 y Cn/2, de forma que en los siguientes resultados de cifra de la columna de la derecha del contador j buscaremos una colisión con C1, y en los siguientes resultados de cifra de la columna de la izquierda del contador i buscaremos una colisión con Cn/2. Esto es así porque cuando se produce una colisión, los resultados de las cifras en i y en j se quedan en fase, encadenados, permaneciendo iguales de aquí en adelante como veremos en el siguiente ejercicio.

Ejercicio 10.2.3

Para la clave RSA anterior con n = 133 y e = 5, repite las ecuaciones del algoritmo durante 12 cifrados en i y 12 en j para N = 25. Observa cómo se encadenan los valores de las dos columnas a partir de una colisión. Usa el software Fortaleza de Cifrados.

Procedemos a cifrar con N = 25:

¿Qué conclusiones podríamos sacar de lo que acabamos de ver?

1. Se ha formado un anillo en ambas columnas con estos 9 valores 25 - 93 - 64 - 4 - 100 - 106 - 123 - 16 - 1 que se van repitiendo.

2. Que siempre un resultado de la columna izquierda del contador i colisionará con un resultado de la columna derecha del contador j antes de que se repita el ciclo en la misma columna. En el ejemplo la colisión entre i y j se produce en el octavo cifrado y el ciclo, como ya hemos visto, era de nueve valores.

Ejercicio 10.2.4

Continúa las operaciones de cifra del ejercicio 10.2.1 (n = 209) para la columna del contador i hasta que encuentres un anillo de valores que se repiten.
Comprueba que estos valores son: 130 - 115 - 158 - 188 - 102 - 42 - 5 - 125 - 199 - 168 - 20 - 82 - 169 - 45 - 80 - 119 - 49 - 180 - 111 - 58 - 196 - 93 - 26 - 23 - 157 - 163 - 104 - 92 - 1. Usa el software Fortaleza de Cifrados.
¿Cuántos cifrados han sido necesarios hasta que se repiten los valores y forman un anillo? ¿Cuántos cifrados fueron necesarios en el ejercicio 10.2.1 para encontrar una colisión entre i y j? Saca tus propias conclusiones.

Por las razones que se indican en el próximo apartado 10.3, se dejará como pendiente para una próxima actualización de esta lección algunas conclusiones a las que ha llegado el autor de este MOOC, después de realizar diversas prácticas y ensayos, y que se encuentra estudiando y evaluando junto al Dr. Alfonso Muñoz, editor también de Crypt4you.

Volvamos ahora al algoritmo propuesto por Merkle y Hellman. Una vez encontrada una colisión entre un resultado de la cifra con el contador i y un resultado de la cifra con el contador j, deberemos aplicar los pasos que se indican a continuación.

Puedes encontrar información detallada sobre este tema en el libro "Criptografía Digital: fundamentos y aplicaciones" de los autores José Pastor Franco y Miguel Angel Sarasa López, de la colección Textos Docentes de la Universidad de Zaragoza, 1998, ISBN 84-7733-491-9. Se entregan todos estos datos pues no resulta fácil encontrar actualmente dicho libro en liberías.

Pasos del ataque de Merkle y Hellman en RSA:

  1. Se leen los valores del contador i y del contador j en los que se ha producido la colisión
  2. Como el atacante conoce la clave pública e, calcula: w = (i - j) / mcd (e, |i - j|)
  3. Deberán existir dos valores (s, t) de forma que se cumpla lo siguiente: w*s + e*t = 1 (en mod e y en mod w)
  4. Las posibles soluciones a esta ecuación son: w*s mod e = 1 y e*t mod w = 1
  5. Se calcula s = inv (w, e)
  6. Se calcula t = inv (e, w)
  7. Se comprueba que w*s + e*t = 1
  8. El valor t será la clave privada, una clave privada pareja o bien un falso positivo

Ejercicio 10.2.5

Para los valores de ataque del ejercicio 10.2.3, calcula la clave encontrada para la colisión encontrada entre 251 mod 133 = 25 y 2573 mod 133 = 25. Usa el software Fortaleza de Cifrados.
Solución:
  1. i = 1, j = 73
  2. w = (i - j) / mcd (e, |i - j|) = (1 - 73) / mcd (5, |1 - 73|) = -72 / 1 = -72
  3. Como w*s + e*t = 1, entonces -72*s + 5*t = 1
  4. Posibles soluciones: w*s mod e = -72*s mod 5 =1 y e*t mod w = 5*t mod 72 = 1
  5. Calculamos s = inv (w, e) = inv (72, 5) = inv (3, 5) = 2 (porque 72 mod 5 = 3)
  6. Calculamos t = inv (e, w) = inv (5, 72) = 29
  7. Comprobamos: w*s + e*t = -72*2 + 5*29 = -144 + 145 = 1
  8. El valor t = 29 es una de las claves privadas parejas como lo muestra la figura.

Clave atacada con clave privada pareja 29

Comprobado el funcionamiento del algoritmo de ataque de Merkle y Hellman, vamos a realizar algunas prácticas con el software genRSA en las que obtendremos la clave privada, una clave privada pareja o un falso positivo.

Práctica 10.2.1

Con el programa genRSA genera la clave con p = 239, q = 191, e = 151 y realiza un ataque por paradoja del cumpleaños siendo el valor de ataque N = 100.
Comprueba con el software que el ataque encuentra la clave privada y luego desmuéstralo usando las ecuaciones del algoritmo.

Ataque que encuentra la clave privada d = 5.091

En la práctica anterior has encontrado la clave privada realizando solamente en 212*2 = 424 cifrados en un módulo de cifra cuyo tamaño es 45.649, cien veces mayor. Vas a realizar ahora otra práctica en la que encontrarás una clave privada pareja.

Práctica 10.2.2

Genera nuevamente la clave con p = 239 y q = 191 pero ahora usando e = 149, y repite el ataque con N = 100.
Comprueba con el software que el ataque encuentra una clave privada pareja y luego desmuéstralo usando las ecuaciones del algoritmo.

Ataque que encuentra la clave privada pareja d' = 7.739 en 212*2 = 424 cifrados para n = 45.649

El software genRSA genera un log con el nombre ParadojaLog.html. Los valores iniciales y finales de ambos ataques se muestran a continuación:

Parte de los archivos ParadojaLog.html de los dos ataques de la práctica en que sólo cambia la clave pública e

Como has comprobado, el cambio de la clave pública e ha significado que en vez de encontrar la clave privada d se ha encontrado una clave privada pareja d', siendo el recorrido del ataque exactamente el mismo. De hecho, las ecuaciones del algoritmo que tenías que haber encontrado en la práctica anterior son:

Para e = 151:
  w = (i - j)/mcd (e, |i-j|) = (214 - 22.824)/mcd (151, |22.610|) = -22.610/1 = - 22.610.
  e * t mod w = 1 = 151 * t mod 22.610 = 1, luego t = inv (151, 22.610) = 5.091, que es la clave privada.

Para e = 149:
  w = (i - j)/mcd (e, |i-j|) = (214 - 22.824)/mcd (149, |22.610|) = -22.610/1 = - 22.610.
  e * t mod w = 1 = 149 * t mod 22.610 = 1, luego t = inv (149, 22.610) = 7.739, que es la clave privada pareja.

Destacar finalmente que, como puedes comprobar, una vez que se produce las colisión sólo hace falta realizar dos cálculos:

  1.   w = (i - j)/mcd (e, |i-j|)
  2.   t = inv (e, w)
        donde t es la clave buscada

Observa, además, que el software genRSA comienza el contador con el valor i = 3. Esto no tiene mayor importancia pues como ya se ha comentado, puede elegirse cualquier valor para los contadores, si bien es recomendable usar los valores presentados al comiezo de este apartado.

¿Qué sucedería si en vez de realizar el ataque con el valor N = 100 lo hacemos con 139? Lo verás resolviendo la siguiente práctica.

Práctica 10.2.3

Con el programa genRSA genera la clave con p = 239, q = 191, e = 151 y realiza un ataque por paradoja del cumpleaños siendo el valor de ataque N = 139.
Comprueba con el software que el ataque encuentra un falso positivo.

Falso positivo 303 al realizar el ataque con N = 139

Como se observa en la figura de la práctica anterior, el algoritmo encuentra una colisión entre Mi3 = 37977 y Mj22879 = 37977, pero al resolver las ecuaciones obtiene como resultado una supuesta clave privada de valor 303 que, como es fácil comprobar, no es la clave privada ni tampoco una clave privada pareja.

¿Qué ha sucedido? Lo que ha sucedido es que hemos encontrado un falso positivo que sólo servirá para descifrar ese valor de ataque N = 139 en particular pero ningún otro valor, por lo que no tendrá ninguna utilidad para atacante.

La siguiente figura demuestra que el valor 139 al cifrarse con la clave pública 151 en el módulo de cifra 45.649 puede descifrarse con este valor 303. Lógicamente, también lo podremos descifrar con las claves propias d = 5.091 y d' = 27.701.

Descifrando con una clave privada de un falso positivo el valor N = 139

A algo similar vas a llegar si usas como valor de ataque N alguno de los 33 números no cifrables de esta clave que, a excepción del 0 y del 1, son: 240, 955, 956, 1195, 1911, 2150, 5737, 6692, 7410, 7647, 8365, 9320, 11951, 12906, 13861, 31788, 32743, 33698, 36329, 37284, 38002, 38239, 38957, 39912, 43499, 43738, 44454, 44693, 44694, 45409, 45648.

Compruébalo y saca conclusiones de lo observado.

Cuestiones para reflexionar e investigar:
1. ¿Qué puedes decir sobre los anillos que has encontrado al buscar colisiones a través del algoritmo de Merkle y Hellman? ¿Podría esto considerarse como una vulnerabilidad y de alguna manera aprovecharla?
2. Si la búsqueda de colisiones se hiciese entre los primeros valores del contador i (1, 2, 3, ...) con los últimos valores del contador j (n-1, n-2, n-3, ...), ¿crees que se obtendría algún beneficio o se optimizaría el ataque?
3. ¿A qué conclusión has llegado luego de analizar los falsos positivos que has obtenido con los números no cifrables y otros valores del módulo de cifra n?
4. Aparte de los números no cifrables propios de la clave, ¿hay muchos o pocos valores de ataque N que entreguen falsos positivos? ¿Aproximadamente qué porcentaje?


APARTADO 10.3. LIMITACIONES DEL ATAQUE CON genRSA Y TRABAJO FUTURO

El software genRSA hasta ahora utilizado tiene sus limitaciones porque en la fecha de su creación, febrero de 2004, no se consideró adecuado incluir más prestaciones. En el caso del ataque por la paradoja de cumpleaños, el ataque se realizaba comparando todos los resultados de los cifrados en la columna i con los de la columna j, que como ya hemos comentado en el apartado anterior no es necesario porque la colisión se produce entre un último resultado de la columna j con el primer resultado de la columna i, o bien entre un último resultado de la columna i con el primer resultado de la columna j.

Si no se sigue el algoritmo que se acaba de recordar y, por el contrario, se comparan todos los valores de cifra de la columna i con los correspondientes de la columna j, obviamente el recurso memoria del ordenador se resiente y por ello en el programa genRSA se limitaron estos ataques a claves de hasta de 20 bits como se observa en la siguiente figura, al intentar realizar un ataque a una clave de 22 bits.

Limitación en genRSA del ataque por paradoja del cumpleaños a claves de hasta 20 bits

Al tratarse de un software educacional para prácticas de laboratorio, tampoco tenía mucha importancia esta limitación.

Los creadores de este MOOC Crypt4you, Drs. Alfonso Muñoz y Jorge Ramió, se encuentran en estos momentos (enero de 2013) trabajando en la generación de un documento más amplio y detallado sobre este tipo de ataques a RSA con un software ad-hoc y sin las limitaciones que has observado en genRSA. Por ese motivo, se ha decidido dejar este apartado pendiente hasta tener concluido y publicado dicho trabajo.

En fechas próximas se publicarán los resultados de este estudio, momento en el cual se actualizará esta lección 10 con dos nuevos apartados y se incluirá la correspondiente sección Cuestiones para reflexionar e investigar.


APARTADO 10.4. TEST DE EVALUACION DE LA LECCION RSA10

En las siguientes 5 preguntas, elige la respuesta correcta.

1. Según la paradoja del cumpleaños, para que exista confianza en que se produzca una colisión:

a) Es suficiente realizar 32 operaciones
b) Es suficiente realizar 23 operaciones
c) Es suficiente realizar 365/2 = 183 operaciones

2. A medida que avanza un ataque por paradoja del cumpleaños:

a) Se vuelve más difícil encontrar colisiones
b) Las colisiones se mantienen constantes
c) Se vuelve más fácil encontrar colisiones

3. El ataque por paradoja del cumpleaños propuesto por Merkle y Hellman estaba destinado al algoritmo:

a) DES
b) Doble DES
c) Triple DES

4. Cuando prospera un ataque por paradoja del cumpleaños a RSA, se obtiene:

a) La clave privada d
b) La clave privada d, una clave privada pareja d' o un falso positivo
c) El mensaje en claro

5. El ataque por paradoja del cumpleaños a RSA termina cuando se encuentra una colisión entre:

a) Ci y Cj
b) Ci(n/2-1) y Cj(n/2)
c) Ci(1) y Cj(n-1)


Ir a: [Portada c4y]    [Lección 9] [Índice]