Si te interesa, google me guió hasta esto que como introducción está bueno:
http://www.unixwiz.net/techtips/iguide-crypto-hashes.html Te voy a dar una explicación yo. Considera las funciones F que van del conjunto de todas las cadenas (un conjunto numerable pero infinito) al conjunto de todas las cadenas de una longitud fija (que tendrá unos 256^longitud elementos). Es imposible que esa función sea biyectiva (que para todo x exista un único y y que para todo y exista un único x) porque uno de los conjuntos es más grande. Pero, ojo, que aquí la gente se confunde mucho y he visto confusión en este hilo, no es a eso a lo que se refiere la frase de "función irreversible". Esta función F no tiene inversa, pero si se restringe adecuadamente su dominio, tendría (es decir, aunque en el concepto puro pueda no tener inversa, toda función matemática es reversible. Ejemplo: función seno, no tiene inversa, pero si la restringes a 0<=x<=2*pi, tiene su arcoseno). Un ejemplo de función F puede ser "la función que para cualquier entrada, devuelve la cadena 'AAA'". Esta función no nos es muy interesante. Son interesantes las funciones "F" que cumplen que: 1) Son conocidas. 2) Dados dos valores similares X1 y X2, los resultados F(X1) y F(X2) sean extremadamente distintos. 3) Dado un valor Y, sea muy difícil desde el punto de vista computacional calcular un X tal que F(X) = Y [Hallar una "colisión"] 4) Dado un valor X1, sea muy difícil desde el punto de vista computacional calcular un X2 tal que F(X1) = F(X2) (Este problema es más sencillo que el anterior) 5) Que sea muy difícil hallar dos valores X1 y X2 tal que F(X1) = F(X2) (y este es muchísimo más sencillo que el anterior, ver "paradoja del cumpleaños") Una función que cumpla más o menos bien todos esos puntos, se llama función de Hash. Un ejemplo de una buena función Hash era el MD5. En el 2005 se logró romper el punto 4, no estoy seguro de si el 3. Es al punto 3 al que se refieren cuando se dice "función no reversible", realmente sería "función no reversible en la práctica" (toda función es reversible en teoría, así que decir 'en la práctica', aunque más correcto, es casi redundante y nadie lo dice). Sería genial una función cuya inversa esté probada NP-Completo (ese es el problema teórico de la computación que es considerado el más fuerte actualmente y que posiblemente se mantenga así este siglo), pero no sé de ninguna demostración de NP-Completitud para ninguno de los hash actuales. Las funciones hash se usan en criptografía (especialmente firmas digitales), pero el caso del que hablan ahora es el almacenamiento de passwords. Si el password es "abcd", almaceno F("abcd") que posiblemente luzca así: "e2fc714c4727ee9395f324cd2e7f331f". Para verificar el password, si el usuario introduce "cde", computo F("cde") y obtengo 'a256e6b336afdc38c564789c399b516c', como no es la misma cadena, deduzco que no es el mismo password. PERO, si introduzco la cadena "m1P4$$w0rDN4d13L0Adivin4" y da el mismo resultado "e2fc714c4727ee9395f324cd2e7f331f", podré entrar al sistema (y viceversa). Ahora, debido al punto 2, si uno de los passwords tiene algún sentido, es muy poco probable que exista una colisión que tenga sentido. Como medida de seguridad adicional, algunos sistemas almacenan no F(Password), sino "cadenaAleatoria"+F("la misma cadena aleatoria"+Password). Así, no basta con encontrar una colisión, sino que hay que encontrar una colisión que *empiece* con "esa misma cadena aleatoria". Paradoja del cumpleaños a la inversa, el problema ahora es *mucho* más complicado que el original. A esa "cadenaAleatoria" se le llama "sal" (ver mensaje mío anterior acerca de los passwords salados). Eso es casi todo lo que necesitas tener para un básico de 'funciones hash'. No se trata de si se conoce o no el algoritmo que computa a la función F, ni siquiera se trata de si se conoce un algoritmo que compute la función inversa de F: el problema radica en que no se conozca (o esté demostrado que no exista, o que sea muy improbable que exista) un algoritmo que permita computar la función inversa en un tiempo aceptablemente corto. Espero haber sido útil con mi explicación, y que no esté demasiado formal. K. On Monday 21 April 2008 10:50:37 pm Carlos Cesar Caballero Diaz wrote: > a ver si puedo entender, pk con eso del md5 me han dejado confundido, dicen > que es irreversible, y ahora me dicen, que una palabra puede generar > códigos distintos(o al menos eso fue lo que entendí, rectifiquenme si no es > así), pero según tenia entendido para comprobar si la password(en md5) es > cierta lo que se escribe se lleva a md5 y se compara, pero si una palabra > no genera siempre el mismo código como quedamos?? lo otro es que, si una > palabra si genera siempre el mismo código, es pk existe un algoritmo de > codificación determinado, y no pone caracteres aleatoriamente, por tanto, > si se descubre el algoritmo, hasta ahí llegó la seguridad. > > lo que he dicho, no es una afirmación, es mas bien una pregunta, para que > me saquen de la duda........... > > Saludos Cesar. -- 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
