El pasado 3 de diciembre se celebró el II Día Internacional de la Seguridad en la Información (DISI 2007). En el, Hugo Scolnik presentó un nuevo algoritmo de factorización, que aunque está por terminar, no tiene mala pinta.
A continuación dejo los enlaces (Criptored) a la presentación y el vídeo de la conferencia:
- Vídeo principal.
- Vídeo parte 1.
- Vídeo parte 2.
- Vídeo parte 3.
- Vídeo parte 4.
- Vídeo parte 5.
- Vídeo parte 6.
$ cat *.z* > video.zip && unzip video.zip
En el foro de Kriptopolis, alguien que firmaba como "Hugo Scolnik" ponía un ejemplo sencillo de factorización:
Enviado por anónimo el 4. Enero 2008 - 8:42.Pues ahi va un ejemplo pequeño para ilustrar el tema
Sea n = 507527
Los targets únicos son (23 en total):
(1,0,3) , (1,0,4), (4,1,5),....,(649,576,720)
Esto significa que x^2 = 1+3t(1) = 1+4t(2)=...= 649+720t(23)
con t(23) = 88 se consigue la soluciòn
Con respecto a y^2 tenemos que puede escribirse como 576+720u(23) con u(23) = 793
Obviamente con n grande es impracticable buscar los valores de t o de u.
Ahora, (n + 649 -576)/720 = 705 y algunos targets ùnicos de 705 son
(0,1,4) , (0,1,8), (0,1,16)Llamaremos (a1,b1,c1) al target ùnico elegido del primer nivel, o sea (649,576,720) y
(a2,b2,c2) al del segundo nivelSi usamos el primero con la fòrmula x^2 =a1+c1a2+c1c2t = 649+2880t correcto con t = 22
Si usamos el segundo obtenemos x^2 = 649+5760t correcto con t = 11
Pero el tercero da x^2= 649+11520t que es FALSO (deberìa dar x^2 = 6409+11520t)¿Còmo corregir 649 ? Habrìa que sumarle deltax2 = 5760 = 8c1 (siempre es un mùltiplo de c1)
Para y^2 obtenemos y^2= b1+c1b2+c1c2u
En el primer caso y^2 = 1296+2880u correcto con u = 198
En el segundo caso y^2 = 1296+5760u correcto con u = 99
El tercero falla pues da y^2 = 1296+11520u y deberìa ser 7056+11520uLa correcciòn es deltay2 = 5760 que es igual a deltax2
Varios de los teoremas que mostrè ràpidamente tienen que ver con las correcciones, su relaciòn con las ecuaciones
diofánticas, etc. Casos muy interesantes son los simètricos, donde aparecen en el nivel k > 1 targets ùnicos
idènticos a los del primer nivel (al parecer siempre existen pero todavìa no nos dedicamos a demostrarlo porque
hay otras prioridades). Para ellos se pueden demostrar varios resultados muy interesantes, y ahora los estoy
usando para la exploraciòn de las ramas provenientes de las posibles elecciones de targets.Cordialmente
Hugo Scolnik
Entradas
4 comentarios:
¿Me podría explicar alguién cuál es la aberración a las matemáticas que hago aquí?;
Sea "n" un entero largo a factorizar se escoje alguna función que determine la cantidad de primos por debajo de una magnitud dada, después se resuelve un sistema de ecuaciones que encuentre la cantidad de primos por debajo del primer factor, del segundo y también de n"
Ej; Supongamos que hemos seleccionado la función descubierta por Gauss, que establece que la cantidad de primos por debajo de un número es aproximadaemente n/In(n) para n muy grande, lo que tendríamos que hacer es resolver;
x * y = n
x/In(x) + [((y)/In(y)) - (x/In(x))]
+ [(n/In(n)) - (y/In(y))] = n/In(n)
Una vez despejada la incógnita que queramos x o y, probaremos a realizar unas cuantas divisiones de números terminados en 1,3,7 ó 9 por encima y por debajo de la misma.
¿Esto sirve para algo? Podría reducir la cantidad de operaciones o hay algún fallo muy grande que se me ha pasado.
Ya vi el fallo en la pregunta anterior así que no hace falta respuesta.
¿O sea que si alguién ha visto el método de Hugo Scolnik o simplemente los alumnos que lo han ayudado a programar ya hacen que el RSA sea inseguro? Cuando se va a avisar de esto a más gente, como alguién encuentre un forma de romper las curvas elípticas la que se va liar, jajaja... ¿Cuál sería la segunda alternativa después de las curvas elípticas como forma de encriptación?
Tranquilo, aún no está claro que Hugo y su equipo lo vayan a conseguir.
En cualquier caso hay muchos problemas NP-completos con los que crear algoritmos de clave pública.
La única forma real de acabar con este tipo de criptografía vendría de la demostración de P=NP encontrando un algoritmo de tiempo polinómico para el problema SAT.
Publicar un comentario