On Tuesday 22 April 2008 10:33:05 pm José Angel Rodríguez Leyva wrote: > No iba a hacer comentario alguno pues estos temas no son de "los míos". > Si me llaman mucho la atención por lo interesante y por eso los reviso > como "lectura ligera" (i.e. superficial, solo por la manera de como lo > leo, no pretendo una actitud arrogante de una genialidad que no poseo, > pues quien puede decir ligero en esto que es lo complejo de lo complejo > en la ciencia de la computación de hoy).
Don't worry. No es arrogante tratar de entender (y corregirme si estoy equivocado). Arrogante sería que yo me molestara :D. Gracias! > No estoy seguro de entender cuando dices que toda función es siempre > reversible (supongo que equivale a inversible). Es cierto, como comentas > que restringiendo el dominio de la función se puede crear una inversa > para una función no reversible (como el coseno), pero no veo que esto > sea siempre posible. No siempre se puede dar una expresión analítica para la inversa de todas las funciones biyectivas (pensar en integrales/derivadas), pero la inversa existe. Usé la terminología 'reversible' en lugar de inversible sólo para ser coherente con la que se estaba usando. En el caso del md5 y los hashes tradicionales ni siquiera se habla de este tipo de funciones (que tienen inversa pero que está demostrado que no tienen expresión analítica), sino de funciones que 'tienen "inversa" pero es costoso computarlas'. > Si el dominio es contínuo, se necesita una restriccion contínua (perdón > si no estoy usando los términos correctamente), o sea cuando para la > curva de la función, se pueden definir un conjunto finito de rangos de x > donde cualquier línea paralela a la absisa solo cortará una vez la curva > para esos. De igual si el dominio es discreto como las funciones HASH. > Pero cómo restringes el dominio si necesitas, para definir el > subconjunto del dominio, una cantidad infinita de rangos de valores? Para invertir una función hash realmente no interesa que la restricción del dominio tenga buenas características (continuidad, etc). Sólo hace falta poder encontrar una preimagen (X tal que F(X) sea un Y dado). De hecho, dado que 'valores similares corresponden a hashes muy distintos', probablemente ese dominio no sea muy consecutivo. > Digo no estoy seguro pues supongo que aún se puede acotar el dominio de > la función de tal manera que la cantidad de valores sea finito. Luego se > puede hallar la inversa aún cuando no fuera expresable algorítmica o > sentido general, matemáticamente. Mas o menos quedaría como una relación > "enormemente gigantesca" de pares de valores. Esa es la idea? Acabas de definir formalmente la palabra "función". Una función (muy formalmente!) es una relación en la que no se repite el primer elemento, y una relación es un conjunto "enormemente gigantesco" pares de valores :D. Así que sí, tienes la idea. > Mi picazón en esto es por lo que dices después. Si luego se hallara una > solución al problema NP-completitud de la función de pares de valores, > se resolvería el insomnio de los hackers? Puede que sí. Comenté que no sé de ninguna demostración de 'resolver este hash es NP-Completo'. Hay problemas más duros que los NP-Completos, pero tampoco he visto demostraciones de que un hash esté en esa categoría. De hecho, me parece que son más simples... Me parece que del RSA está demostrado que no es NP-duro (pero aquí si estoy tirando piedras). Pero, si resulta que P=NP: * Muchos problemas complicados se resuelven inmediatamente * Habrá que replantearse muchos conceptos de seguridad (lo que no sé cuales) > Y me pica otra pregunta. > > Existe soluciones *aproximadas* al problema NP-completitud. Por ejemplo, > los algoritmos genéticos (he estado aprendiendo algo de esto con el > problema del agente viajero unas semanas atrás). Crees que tendría algún > exito en esta empresa? Si has leido algo de eso, sería realmente > interesante de conocer. Hay dos problemas para aplicar una solución aproximada a un problema criptográfico. Una, es que si no se tiene la solución exacta, es como si no se tuviera nada. La otra, es que todas las heurísticas usadas para aproximar (colonia de hormigas, recocido simulado, genéticos, genéticos probabilísticos, blah blah blah) se basan en que la función es "buena" (si la imagen está cerca del punto óptimo, entonces la pre-imagen también, así que altero un poquito la preimagen para ver si me acerco al óptimo). En un hash, como pequeñas modificaciones en la imagen provocan cambios radicalmente distintos, el hecho de tener un hash similar no da suficiente información para elegir otro candidato a solución. > saludos > > jar Cheers! K. -- Luis Zarrabeitia (aka Kyrie) Fac. de Matemática y Computación, UH. http://profesores.matcom.uh.cu/~kyrie _______________________________________________ Cancelar suscripción https://listas.softwarelibre.cu/mailman/listinfo/linux-l Buscar en el archivo http://listas.softwarelibre.cu/buscar/linux-l
