RSA
El sistema RSA
El primer algoritmo de cifrado de clave pública (cifrado asimétrico) fue desarrollado por R. Merckley M. Hellman en 1977. Gracias al trabajo de los famosos analistas criptográficos Shamir, Zippel yHerlestman, se quedó obsoleto rápidamente.
En 1978 apareció el algoritmo de clave pública creado por Rivest, Shamir y Adelman (de aquí el nombre RSA). Este algoritmo todavía se usaba en 2002 para proteger los códigos de las armas nucleares de Estados Unidos y Rusia.
Cómo funciona RSA
El funcionamiento del criptosistema RSA se basa en la dificultad para factorizar grandes números enteros.
Digamos que p y q son dos números primos, y d un número entero tal que d se factoriza en (p-1)*(q-1)). De esta manera, el terceto (p,q,d) representa la clave privada.
Así, la clave pública es un doblete (n, e) creado con la clave privada a través de las siguientes transformaciones:
n = p * q e = 1/d mod((p-1)(q-1))
Digamos que M es el mensaje a enviar. El mensaje M necesita factorizarse en la clave n. El descifrado se basa en el teorema de Euler, que estipula que si M y n se factorizan, entonces:
Mphi(n) = 1 mod(n)
Phi(n) será la función totient y, en este ejemplo, tendría un valor de (p-1)*(q-1).
Por lo tanto, es necesario que M no sea un múltiplo de p, q o n. Una solución sería dividir el mensaje M en bits Mi de manera que la cantidad de números en cada Mi sea estrictamente inferior a la de p y q. Esto supone entonces que p y q son grandes, que es lo que sucede en la práctica ya que el principio de RSA yace en la dificultad de encontrar p y q en un período de tiempo razonable cuando se conoce n; esto asume que p y q son grandes.
En la práctica...
Supongamos que un usuario (llamado Bob) quiere enviar un mensaje M a una persona (llamémosla Alice). Simplemente necesita obtener la clave pública de Alice (n,e) y luego calcular el mensaje cifrado c:
c = Me mod(n)
Luego, Bob envía el mensaje c a Alice, quien es capaz de descifrarlo con su clave privada (p,q,d):
M = Me*d mod(n) = cd mod(n)
SHA-1
SHA-1 ha sido examinado muy de cerca por la comunidad criptográfica pública, y no se ha encontrado ningún ataque efectivo. No obstante, en el año 2004, un número de ataques significativos fueron divulgados sobre funciones criptográficas de hash con una estructura similar a SHA-1; lo que ha planteado dudas sobre la seguridad a largo plazo de SHA-1.
SHA-0 y SHA-1 producen una salida resumen de 160 bits (20 bytes) de un mensaje que puede tener un tamaño máximo de 264 bits, y se basa en principios similares a los usados por el profesor Ronald L. Rivest del MIT en el diseño de los algoritmos de resumen de mensaje MD4 y MD5.
La codificación hash vacía para SHA-1 corresponde a:
SHA1("") = da39a3ee5e6b4b0d3255bfef95601890afd80709
Ataques contra SHA-1
La resistencia del algoritmo SHA-1 se ha visto comprometida a lo largo del año 2005. Después de que MD5, entre otros, quedaría seriamente comprometido en el 2004 por parte de un equipo de investigadores chinos, el tiempo de vida de SHA-1 quedó visto para sentencia.
El mismo equipo de investigadores chinos, compuesto por Xiaoyun Wang, Yiqun Lisa Yin y Hongbo Yu (principalmente de la Shandong University en China), ha demostrado que son capaces de romper el SHA-1 en al menos 269 operaciones, unas 2000 veces más rápido que un ataque de fuerza bruta (que requeriría 280 operaciones). Los últimos ataques contra SHA-1 han logrado debilitarlo hasta 263.
«Este ataque es de particular importancia para las aplicaciones que usan firmas digitales tales como marcas de tiempo y notarías. Sin embargo, muchas aplicaciones que usan firmas digitales incluyen información sobre el contexto que hacen este ataque difícil de llevar a cabo en la práctica.»
A pesar de que 263 suponen aún un número alto de operaciones, se encuentra dentro de los límites de las capacidades actuales de cálculos, y es previsible que con el paso del tiempo romper esta función sea trivial, al aumentar las capacidades de cálculo y al ser más serios los ataques contra SHA-1.
La importancia de la rotura de una función hash se debe interpretar en el siguiente sentido: Un hash permite crear una huella digital, teóricamente única, de un archivo. Una colisión entre hashes supondría la posibilidad de la existencia de dos documentos con la misma huella. La inicial similitud propuesta con la equivalencia a que hubiese personas que compartieran las mismas huellas digitales, o peor aún, el mismo ADN no es adecuada pues, aunque fuera trivial encontrar dos ficheros con el mismo resumen criptográfico ello no implicaría que los ficheros fueran congruentes en el contexto adecuado. Siguiendo con la hipótesis de la similitud biométrica de dos personas, sería el equivalente a necesitar modificar el número de brazos en una persona para que su impresión dactilar fuera igual a la de otra.
A pesar de que el NIST contempla funciones de SHA de mayor tamaño (por ejemplo, el SHA-512, de 512 bits de longitud), expertos de la talla de Bruce Schneier abogan por, sin llamar a alarmismos, buscar una nueva función hash estandarizada que permita sustituir a SHA-1. Los nombres que se mencionan al respecto son Tiger, de los creadores de Serpent, y WHIRLPOOL, de los creadores de AES.
MD5
Historia
MD5 es uno de los algoritmos de reducción criptográficos diseñados por el profesor Ronald Rivest del MIT (Massachusetts Institute of Technology, Instituto Tecnológico de Massachusetts). Fue desarrollado en 1991 como reemplazo del algoritmo MD4 después de que Hans Dobbertin descubriese su debilidad.
A pesar de su amplia difusión actual, la sucesión de problemas de seguridad detectados desde que, en 1996, Hans Dobbertin anunciase una colisión de hash, plantea una serie de dudas acerca de su uso futuro.
Codificación
La codificación del MD5 de 128 bits es representada típicamente como un número de 32 dígitos hexadecimal. El siguiente código de 28 bytes ASCII será tratado con MD5 y veremos su correspondiente hash de salida:
MD5("Generando un MD5 de un texto") = 5df9f63916ebf8528697b629022993e8
Un pequeño cambio en el texto (cambiar '5' por 'S') produce una salida completamente diferente.
MD5("Generando un MDS de un texto") = e14a3ff5b5e67ede599cac94358e1028
Otro ejemplo sería la codificación de un campo vacío:
MD5("") = d41d8cd98f00b204e9800998ecf8427e
Algoritmo
- Terminologías y notaciones
En este documento "palabra" es una entidad de 4 bytes y un byte es una entidad de 8 bits. Una secuencia de bytes puede ser interpretada de manera natural como una secuencia de bits, donde cada grupo consecutivo de ocho bits se interpreta como un byte con el bit más significativo al principio. Similarmente, una secuencia de bytes puede ser interpretada como una secuencia de 32 bits (palabra), donde cada grupo consecutivo de cuatro bytes se interpreta como una palabra en la que el byte menos significativo está al principio (de este modo trabajan plataformas como Intel, esta propiedad se conoce como endianness).
El símbolo "+" significa suma de palabras.
X <<< s se interpreta por una rotación de bits a la izquierda sobre 'X', 's' posiciones
not(x) se entiende como el complemento de x
X <<< s se interpreta por una rotación de bits a la izquierda sobre 'X', 's' posiciones
not(x) se entiende como el complemento de x
- Descripción del algoritmo md5
Empezamos suponiendo que tenemos un mensaje de 'b' bits de entrada, y que nos gustaría encontrar su resumen. Aquí 'b' es un valor arbitrario entero no negativo, pero puede ser cero, no tiene por qué ser múltiplo de ocho, y puede ser muy largo. Imaginemos los bits del mensaje escritos así:
m0 m1 ... m{b-1}
Los siguientes cinco pasos son efectuados para calcular el resumen del mensaje.
No hay comentarios :
Publicar un comentario