El blog de García Larragan y Cía

En este post continúo con el  pequeño repaso a los métodos de factorización más conocidos : en esta ocasión me referiré al método p - 1 de Pollard . Al igual que los otros dos métodos de los que he hablado en posts anteriores ( Fermat y rho de Pollard ), se trata también de un método de factorización de propósito específico , es decir, el tiempo necesario para descomponer el módulo ( n ) en sus dos factores primos ( p y q ) depende de las características de estos últimos, en contraposición con los métodos de factorización de propósito general, en el que el tiempo de ejecución depende únicamente del tamaño del módulo. Por lo que he entendido, el algoritmo podría ser el siguiente (como siempre, si estoy equivocado agradecería las oportunas correcciones a modo de comentario en esta entrada): En nuestro caso (con el ejemplo que vengo utilizando en esta serie de posts): En posteriores posts continuaré con este pequeño repaso a los métodos de factorización más conocidos....

Continúo con el pequeño repaso a algunos de los métodos de factorización más conocidos que inicié en el post anterior  y que, en teoría, podrían emplearse para atacar al algoritmo de cifrado RSA . Digo en teoría porque, como ya he venido insistiendo en esta serie de post, los métodos conocidos y que es posible implementar hasta la fecha no resuelven la factorización del módulo ( n ) en sus dos factores primos ( p y q ) en tiempo polinomial y, por tanto, son ineficientes para abordar este problema en un tiempo razonable cuando se trata de números lo suficientemente grandes (ya dije en el post anterior que actualmente se emplea un tamaño para el módulo de 2.048 bits). En esta ocasión le toca el turno al método de factorización rho de Pollard . Como siempre utilizaré el ejemplo que vengo usando en esta serie de posts ( n = pq = 53 x 997 = 52.841 ). En nuestro caso : Como vemos,  en tan sólo 6 iteraciones hemos conseguido factorizar el módulo ( 52.841 ) en sus...

Ya he dicho en posts anteriores que la fortaleza del cifrado RSA reside en el elevadísimo coste computacional al que tendrían que enfrentarse quienes pretendan atacar este algoritmo ; y referido al caso concreto de la factorización del módulo ( n ) para hallar sus dos factores primos ( p y q ), en la enorme cantidad de cálculos a realizar para ello cuando se trata de números lo suficientemente grandes (actualmente se emplea para el módulo un tamaño de 2.048 bits). Por tanto, se trata de un problema  perfectamente resoluble desde un punto de vista matemático, pero inabordable actualmente por la ingente cantidad de tiempo y recursos necesarios . Comienzo con este post un pequeño repaso a  algunos de los métodos de factorización más conocidos  para hacernos una idea del esfuerzo que esto conlleva . Para ello, intentaré factorizar mediante estos métodos el módulo del ejemplo que vengo utilizando en esta serie de posts ( n = pq = 53 x 997 = 52.841 ). - Método de factori...

En anteriores posts de esta serie he hablado de algunos ataques teóricamente posibles al algoritmo de cifrado RSA  ( cifrado cíclico  y  paradoja del cumpleaños ),  pero que tal y como comenté son ineficientes  cuando se utilizan números primos lo suficientemente grandes para generar el par de claves (pública y privada). Además de los ya mencionados  existen otros ataques posibles ; y en este post trataré sobre uno de ellos: el ataque a RSA mediante módulo común . La idea de este ataque consiste en explotar el hecho de que  se utilice el mismo módulo (n)  a la hora de generar pares de claves para diferentes usuarios  (cada uno de ellos con su exponente publico y privado propios). En principio, esto no compromete la seguridad del algoritmo, pero deja la "puerta abierta" a que   si se cifra el mismo mensaje para más de un usuario  un criptoanalista que intercepte los criptogramas pueda hacerse con el mensaje en claro. Veamos un ...

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 veng...

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 (...

Decía en el primer post sobre RSA  q ue 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 ...