jueves, 29 de diciembre de 2016

Criptografía (XL): ataque a RSA mediante la paradoja del cumpleaños

Decía en un post anterior de esta serie que existen algunos métodos para intentar "romper" el cifrado RSA sin necesidad de factorizar el módulo para hallar sus dos factores primos.

Como comenté en ese post, el ataque utilizando el cifrado cíclico nos podría permitir "romper" el secreto que se pretende guardar (en teoría se puede obtener el mensaje en claro), aunque no obtendríamos la clave privada del receptor.

Pero, ¿existen otros métodos de criptoanálisis al cifrado RSA que teniendo en cuenta sólo información pública del destinatario (la clave pública con la que se cifran los mensajes en claro: el exponente y el módulo) podrían revelarnos su clave privada?. La respuesta es, otra vez y en teoría, sí, y, además, ni siquiera haría falta interceptar un criptograma, como sí que es necesario en el caso del ataque mediante cifrado cíclico. Éste es el caso de un ataque basado en la paradoja del cumpleaños.

Veamos un ataque de este tipo con el ejemplo que vengo utilizando en esta serie de posts:

Clave pública del receptor (e, n): (7, 52.841)
Clave privada del receptor (d, n): (7.399, 52.841)
mensaje (m) = 17.225

Cifrado (el emisor utiliza la clave pública del receptor): c = me mod n = 17.2257 mod 52.841 = 1.855.
Descifrado (el receptor utiliza su clave privada): m = cd mod n = 1.8557.399 mod 52.841 = 17.225.


Tal y como he comentado, para realizar el ataque partimos únicamente de la clave pública del receptor (e, n), que como su propio nombre indica es información pública.

Conocido el módulo 'n' (52.841) dividimos el espacio del cuerpo de cifra en dos mitades, de la siguiente manera:
Escogemos un número cualquiera (m). Por ejemplo: 4.683.

Y ahora vamos realizando simultáneamente las dos siguientes operaciones:

ci = mi mod n; cj = mj mod n

hasta encontrar una colisión, es decir, que uno de los valores obtenidos en la primera mitad del espacio del cuerpo de cifra coincida con uno de los obtenidos en la segunda mitad, o viceversa. Si esto ocurre el ataque puede haber prosperado de forma que a partir de los valores de i y j sea posible obtener la clave privada del destinatario (d, n) o una clave que siendo diferente a ésta nos permita descifrar los criptogramas (ver este post).

En nuestro ejemplo:
Como se observa, para i = 524 y j = 26.420 se produce una colisión, por lo que el ataque podría haber prosperado en tan sólo 524 iteraciones (2 cifrados en cada una de ellas) en un cuerpo de cifra de tamaño 52.841. Comprobémoslo:

- Calculamos: x = |i - j| / mcd(e, |i - j|) = |524 - 26.420| / mcd(7, |524 - 26.420|) = 25.896 / mcd(7, 25.896) = 25.896.

- El exponente de la clave podría ser: inv(e, x) = inv(7, 25.896) = 7.399, y, tal y como se puede ver al inicio de este ejemplo, efectivamente hemos obtenido el exponente (d) de la clave privada del receptor, por lo que esta última es (7.399, 52.841).

¿Hemos tenido mucha suerte?. Parece que sí, ya que a simple vista no parece muy probable que se produzca una colisión en la iteración 524 (2 cifrados en cada una de ellas) en un cuerpo de cifra de tamaño mucho mayor. Sin embargo, conforme a la paradoja del cumpleaños (ver este post donde la explico), hacen falta muchas menos iteraciones de las que intuitivamente puede parecer para que la probabilidad de que se produzca una colisión sea muy alta.

De nuevo, como en el caso de ataque mediante cifrado cíclico (ver este post), aunque en teoría es posible, este tipo de ataque se convierte en una tarea inabordable en un tiempo razonable, por mucha potencia de cálculo de la que se disponga con los ordenadores actuales, cuando se utilizan números lo suficientemente grandes para generar las claves

miércoles, 28 de diciembre de 2016

Gimnasia mental (XXIX): probabilidad de que me toque el Gordo del Niño

Como complemento a este post, en el que me preguntaba: ¿Cuál es la probabilidad de que me toque el Gordo de Navidad?, en éste me pregunto:


"¿Qué probabilidad hay de que me toque el Gordo de la lotería del Niño: menor, mayor o igual que en la lotería de Navidad?".

Si no estoy equivocado, según tengo entendido (por favor, si no es así que alguien me corrija):

- En la lotería de Navidad hay un bombo con 100.000 bolas con los números (del 0 al 99.999) y en otro están las bolas con los premios; de tal forma que se van extrayendo del primero las bolas con los números agraciados y del segundo las bolas con el premio que corresponde a cada uno de los anteriores.

- En la lotería de Niño se utiliza el sistema de bombos múltiples, es decir, hay cinco bombos con 10 bolas cada uno (del 0 al 9), un bombo para cada uno de los cinco dígitos posibles (decena de millar, unidad de millar, centena, decena y unidad, respectivamente) que podrían formar los 100.000 números posibles (del 0 al 99.999); de manera que tras la extracción de una bola de cada uno de los cinco bombos se obtiene el número agraciado con el premio programado (los premios van saliendo de forma ordenada ascendente por cuantía) y después se reponen las bolas extraídas en sus respectivos bombos.

También, tal y como tengo entendido, en el sorteo de Navidad resultan premiados menos números que en el del Niño.

La pregunta en concreto es, suponiendo que juego un único décimo en cada sorteo:

¿Qué probabilidad existe de que me toque el Gordo en cada uno de ambos sorteos?:

a) Mayor en la Lotería de Navidad que en la del Niño.
b) Mayor en la del Niño que en la de Navidad.
c) La misma en ambos sorteos.

jueves, 22 de diciembre de 2016

Criptografía (XXXIX): RSA o por qué los números aleatorios son demasiado importantes para dejarlos en manos del azar

Decía en el primer post sobre RSA que utilizando este algoritmo el emisor cifra el mensaje con la clave pública del receptor y que el criptograma resultante sólo puede descifrarse utilizando la clave privada de este último. Esto es una de las primeras cosas que uno aprende al estudiar cómo funciona el cifrado y descifrado usando este algoritmo, pero: ¿es cierto?.

Prescindiendo del ataque a RSA mediante cifrado cíclico, que, como vimos en este post, en teoría nos permitiría descifrar un mensaje concreto cifrándolo sucesivas veces con la clave pública del destinatario hasta volver a obtener el criptograma: ¿sería posible descifrar el criptograma utilizando una clave distinta de la clave privada correspondiente a la clave pública con la que se cifró?. Pues he aprendido que sí, aunque esto parezca ir en contra de la seguridad de este algoritmo.

Veamos un ejemplo:

En el primer post al que he hecho referencia realicé el cifrado de un mensaje (m) con una clave pública (e, n) y su posterior descifrado con la clave privada correspondiente (d, n), de la siguiente manera:

m = 17.225

Clave pública (e, n): (7, 52.841) 
Cifrado: c = me mod n = 17.2257 mod 52.841 = 1.855

Clave privada (d, n): (7.399, 52.841)
Descifrado: m = cd mod n = 1.8557.399 mod 52.841 = 17.225

Vamos ahora a utilizar otras 3 claves diferentes a la clave privada en el cuerpo de cifra (n) para intentar descifrar el criptograma (c):

k1: (20.347, 52.841)
Descifrado: m = 1.85520.347 mod 52.841 = 17.225

k2: (33.295, 52.841) 
m = 1.85533.295 mod 52.841 = 17.225

k3: (46.243, 52.841) 
m = 1.85546.243 mod 52.841 = 17.225

Como se observa, en los tres casos conseguimos descifrar el criptograma sin utilizar la clave privada del destinatario.

- ¿Por qué ocurre esto?. Hay que tener en cuenta que, tal y como comentaba en el primer post, al generarse un par de claves, la clave privada se calcula como el inverso del exponente de la clave pública (e) en el cuerpo j(n) = (p - 1)(q - 1), siendo 'p' y 'q' los dos números primos aleatorios a partir de los cuales se genera el par de claves, y 'n' su producto. Como 'e' y j(n) son coprimos o primos relativos, es decir, mcd(e, j(n)) = 1, esto asegura que el exponente de la clave privada (d) existe, es decir, que 'e' tiene inverso módulo j(n) y, además, que éste (d) es el único inverso de 'e' en el cuerpo j(n).

Lo que ocurre es que como el cuerpo de cifra no es j(n) sino 'n' existirá al menos otro inverso de 'e' en el cuerpo de cifra 'n' con el que también se podrán descifrar los mensajes cifrados con la clave pública (e, n).

- ¿Puedo saber cuántas claves de este tipo existen al generar un par de claves?. Esto depende de los dos números primos aleatorios ('p' y 'q') empleados para generar el par de claves, y puede calcularse de la siguiente forma:
En nuestro caso:
- ¿Puedo saber cuáles son estas claves al generar un par de ellas?:

Calculamos: d1 = inv(e, mcm(p-1, q-1)

Los exponentes de estas claves, incluido el de la clave privada (d), serán:

di = d1 + (i-1) x mcm(p-1, q-1)

Donde: 1 < di < n

Por lo que las claves, incluida la clave privada, serán:

ki: (di, n)

En nuestro caso:

d1 = inv(7, mcm(52, 996)) = inv(7, 12.984) = 7.399

Por lo que los exponentes de estas claves. incluido el de la clave privada (d), serán:

d1 = d1 + (i-1) x mcm(p-1, q-1) = 7.399 + 0 x 12.948= 7.399
d2 = d1 + (i-1) x mcm(p-1, q-1) = 7.399 + 1 x 12.948 = 20.347
d3 = d1 + (i-1) x mcm(p-1, q-1) = 7.399 + 2 x 12.948 = 33.295
d4 = d1 + (i-1) x mcm(p-1, q-1) = 7.399 + 3 x 12.948 = 46.243

Por tanto, incluida la clave privada, las claves serán:

k1: (7.399, 52.841)
k2: (20.347, 52.841)
k3: (33.295, 52.841)
k4: (46.243, 52.841)

Es decir, además de la clave privada (7.399, 52.841), existen otras tres claves con las que se pueden descifrar los criptogramas cifrados con la clave pública (7, 52.841).

- ¿Al generarse un par de claves podrían existir muchas claves de este tipo que hagan vulnerables los criptogramas a una ataque de fuerza bruta?. Pues, en teoría, sí. Ya he dicho que el número de ellas depende de los número primos aleatorios que se empleen para generarlas.

Veamos que ocurre variando los números primos empleados para generar el par de claves de nuestro ejemplo, que eran p = 53 y q = 997 (en este caso, eligiendo '7' como exponente de la clave pública existen 3 claves de este tipo. En los casos que se indican a continuación también elegimos '7' como exponente de la clave pública):

1.- p = 53; q = 53

n = 2.809; clave pública: (7, 2.809); clave privada: (1.159, 2.809)

Aplicando las fórmulas indicadas anteriormente, calculamos que existen 53 claves de este tipo. La primera (15, 2.809), y todas ellas, cuyos exponentes se encuentran separados a lo largo del cuerpo de cifra por 52 (mcm(p-1, q-1)), serán: (15, 2.809), (67, 2.809), (119, 2.809), (171,2.809), (223,2.809),...   

2.- p = 997; q = 997

n = 994.009; clave pública: (7, 994.009); clave privada: (708.583, 994.009)

Existen 997 claves de este tipo: (427, 994.009), (1.423, 994.009), (2.419, 994.009),...

3.- p = 53 ; q = 1.171

n = 62.063; clave pública: (7, 62.063); clave privada: (17.383, 62.063)

Existen 26 claves de este tipo: (1.003, 62.063), (3.343, 62.063), (5.683, 62.063),...

4.- p = 53; q = 983

n = 52.099; clave pública: (7, 52.099); clave privada: (7.295, 52.099)

Existe sólo 1 clave de este tipo: (32.827, 52.099).

Como se ve, al menos yo, saco inicialmente las siguientes conclusiones:

1.- No parece una buena idea utilizar el mismo número primo para 'p' y 'q'.

2.- El número de claves de este tipo, tal y como comentaba, tiene una fuerte dependencia directa de la elección de los dos números primos aleatorios a partir de los cuales se genera el par de claves

- ¿Cómo puede evitarse que al generar un par de claves existan muchas claves de este tipo?.

Parece ser, por lo que voy aprendiendo, que utilizando números primos fuertes o primos seguros en la generación del par de claves. Pero esto es algo que tengo que estudiar e intentar comprender antes de contarlo :). Si lo consigo escribiré otra entrada para compartirlo.

Por tanto, entiendo que es muy importante que los números primos 'p' y 'q' a partir de los cuales se genera el par de claves no sean predecibles, ya que en ellos descansa el secreto de las comunicaciones entre el emisor y el receptor, y la idea de seleccionarlos de forma aleatoria parece la mejor opciónNo obstante, visto lo visto y por otros efectos no deseados que podrían producirse si se realiza una elección no adecuada de los mismos, la frase que oí en su día y que me hizo mucha gracia empieza a tener sentido para mí:

"Los números aleatorios son demasiado importantes para dejarlos en manos del azar"

jueves, 15 de diciembre de 2016

Gimnasia mental (XXVIII): probabilidad de que me toque el Gordo de Navidad

El otro día, tras mi jornada laboral y como casi siempre, entro en mi bar de referencia en Algorta (Getxo), el pueblo más bonito del mundo :).

En él me encuentro con un ilustre parroquiano que me interroga inmediatamente, antes de pedir ninguna consumición: Mikel,

¿Qué probabilidad hay de que te toque el Gordo de Navidad?.

Por la cara que puso, me miraba fijamente y arqueando una ceja, enseguida pensé que la pregunta podía tener trampa y, además, sospeché que no me iba a poder escaquear de responder; me había visto comprar un décimo en ese mismo bar el día anterior, por lo que alguna probabilidad tendré y, peor aún y como digo, él lo sabía (no podía contestar eso de: "Ninguna, porque no juego").

Tras unos segundos meditando, acordándome de un tal Laplace, le contesté que como yo sólo he comprado un décimo de un número, como creo que hay 100.000 números (del 0 al 99.999) y que pienso que todos ellos tienen la misma probabilidad de salir premiados con el Gordo, entonces la probabilidad de que a mí me toque el Gordo de Navidad es de 1/100.000 = 0,00001 (casos favorables/casos posibles, es decir, un ridículo 0,001%).

En ese momento, su expresión inquisidora se tornó en una de absoluta satisfacción (¡otro que no tiene ni idea!. Vaya usted a saber a cuantos les había hecho esa misma pregunta), y me dijo: "En el sorteo de Navidad hay dos bombos, el primero de ellos con los 100.000 números posibles y el segundo con el premio que le corresponde al número que sale en el primero, por lo que la probabilidad de que que te toque el Gordo es mucho menor que el 0,001%" (supongo que con ese argumento se refería a probabilidad condicionada, pero vaya usted a saber).

¿Quién crees que tiene razón?.

miércoles, 14 de diciembre de 2016

Zorionak eta urte berri on 2017!

Como siempre, llegadas estas fechas, no puedo dejar (¡hombre!, por poder si podría, pero no me da gana :) ) de desearos:

¡Lo mejor para este año que termina, para el siguiente y para siempre!.

Como tampoco podía ser de otra forma, este año he escrito muchas entradas en este blog sobre criptografía, en la felicitación se encuentra mi nombre cifrado ;).

Criptografía (XXXVIII): ataque a RSA mediante cifrado cíclico

En un post anterior sobre el algoritmo RSA comentaba que se considera que éste será seguro hasta que no se conozca una forma eficiente de hallar los dos factores primos de un número muy grande resultado del producto de éstos, ya que con los ordenadores actuales la potencia de cálculo que se requiere para ello hace que esta tarea sea inabordable en un tiempo razonable.

Pero, ¿existen otros métodos para intentar "romper" el cifrado RSA sin necesidad de realizar esa factorización?. Además, ¿podría "romperse" este cifrado sin conocerse la clave privada del receptor del mensaje?. La respuesta a ambas preguntas es afirmativa, al menos, en teoría.

Pongo un ejemplo de ataque a un cifrado RSA utilizando el método de cifrado cíclico.

En el ejemplo de cifrado RSA que puse en el post anterior al que he hecho referencia realizaba una operación de cifrado y descifrado sobre un mensaje (m) considerando lo siguiente:

Clave pública del receptor (7, 52.841)
Clave privada del receptor (7.399, 52.841)
m = 17.225

Cifrado (el emisor utiliza la clave pública del receptor): c = me mod n = 17.2257 mod 52.841 = 1.855
Descifrado (el receptor utiliza su clave privada): m = cd mod n = 1.8557.399 mod 52.841 = 17.225

Supongamos ahora que interceptamos este mensaje cifrado o criptograma (1.855): ¿podríamos obtener el mensaje en claro a partir de éste y de la clave pública del receptor?. Pues, también en teoría, sí.

El ataque empleando el cifrado cíclico consiste en cifrar repetidas veces el criptograma interceptado con la clave pública del destinatario hasta volver a obtener el criptograma, cosa que tarde o temprano ocurrirá y que nos revelará el mensaje en claro, de la siguiente manera:
Es decir, la operación de cifrado anterior a aquella en la que se obtiene nuevamente el criptograma (c) nos revela el mensaje en claro (m).

Curioso, ¿no?. Nótese que con este método no se obtiene la clave privada del receptor, pero se "rompe" el secreto que se pretendía guardar (el mensaje en claro). Lástima que este método con la potencia de cálculo disponible actualmente resulte incluso más ineficiente que el de la factorización cuando se utilizan números lo suficientemente grandes para generar las claves :). 

viernes, 9 de diciembre de 2016

Gimnasia mental (XXVII): la paradoja del cumpleaños

Supongamos que un autobús empieza su recorrido sólo con el conductor y va realizando sucesivas paradas.

En cada una de ellas se sube al autobús un nuevo viajero. Suponiendo años de 365 días, es decir, sin considerar años bisiestos:


¿Cuántas paradas debe realizar para que la probabilidad de que al menos dos personas que viajen en el autobús (conductor incluido) celebren su cumpleaños el mismo día sea superior al:
a) 50%?.
b) 99%?.

Un problema (no el mismo, pero muy similar) que recuerdo que nos plantearon en clase en mis tiempos de universidad y, además, que junto con el teorema chino de resto (ver este post de esta misma serie) tiene curiosas aplicaciones en criptología, pero esto ya es otra historia de la que, si es el caso, trataré en entradas posteriores de este blog.

Solución:

1.- La probabilidad de que cuando el autobús empieza su recorrido ninguna de las personas que se encuentran en él celebre su cumpleaños el mismo día que otra es evidentemente (sólo está el conductor) de 365/365 = 1 (100%).

Cuando en la primera parada se sube el primer viajero la probabilidad de que ninguna de las personas que se encuentran en él celebre su cumpleaños el mismo día que otra es de 365/365 x 364/365 = 0,9973 (99,73%).

Cuando en la segunda parada se sube el segundo viajero la probabilidad de que ninguna de las personas que se encuentran en él celebre su cumpleaños el mismo día que otra es de 365/365 x 364/365 x 363/365 = 0,9918 (99,18%).
...
Cuando en la enésima parada se sube el enésimo viajero la probabilidad de que ninguna de las personas que se encuentran en él celebre su cumpleaños el mismo día que otra es de 365/365 x 364/365 x 363/365 x ... x (365-n)/365, lo que se puede generalizar como: 365 x 364 x 363 x ... x (365-n) / 365n+1, siendo n el número de paradas. Nótese que en el autobús hay una persona más (el conductor) que el número de paradas que realice.

Por tanto, la probabilidad de que tras la enésima parada ninguna de las personas que viajan en el autobús (n+1, conductor incluido) celebre su cumpleaños el mismo día que otra es:
2.- Y, por tanto, la probabilidad de que tras la enésima parada al menos dos personas que viajan en el autobús (n+1, conductor incluido) celebren su cumpleaños el mismo día es: 1 - 365 x 364 x 363 x ... x (365-n) / 365n+1, siendo n el número de paradas, es decir:
Por tanto y aunque intuitivamente pudiera parecer que hacen falta muchas más personas en el autobús, con tan sólo 23 personas (22 paradas) la probabilidad de que al menos 2 personas celebren su cumpleaños el mismo día es superior al 50% y tan sólo hacen falta 57 personas (56 paradas) para que esta probabilidad supere el 99%.