• Viernes 22 de Octubre de 2021, 13:51

Autor Tema:  Sha-1 Y Colisiones  (Leído 2306 veces)

mjesun

  • Miembro activo
  • **
  • Mensajes: 56
    • Ver Perfil
Sha-1 Y Colisiones
« en: Jueves 13 de Septiembre de 2007, 02:38 »
0
hola a todoss!!

tengo una duda existente acerca del algoritmo SHA-1, y en general con todos los algoritmos que generan una clave o hash o... (no encuentro el termino exacto) a partir de una cadena de bytes:

1º SHA-1 genera hashes o claves de 20 bytes... esto quiere decir que como mucho puede producir 256^20 claves diferentes, sin ningun tipo de colisión.

2º si construimos cadenas (o arrays, mal usada la palabra cadenas) de 20 bytes exactos, realizando todas las combinaciones posibles, ocuparemos exactamente todas las claves generadas de SHA-1, ya que estas son también 256^20...

3º si no se ha producido colisión, cosa bastante curiosa, pero que demostraría una gran pericia, obviamente se producirá con cadenas de 21 caracteres... es mas... si no hay colisión con 20 bytes, hay colisión al menos entre una cadena de 20 y una cadena de 21...

¿entonces porqué se pone siempre en juicio el hecho de que no haya colisiones en un algoritmo? en arrays de bytes cuya longitud sea superior a la del hash siempre habra colision... no?

un saludo a todos y gracias por aclararmelo!

Nebire

  • Miembro HIPER activo
  • ****
  • Mensajes: 670
    • Ver Perfil
Re: Sha-1 Y Colisiones
« Respuesta #1 en: Domingo 23 de Septiembre de 2007, 19:49 »
0
Cita de: "mjesun"

 
Citar
1º SHA-1 genera hashes o claves de 20 bytes... esto quiere decir que como mucho puede producir 256^20 claves diferentes, sin ningun tipo de colisión.

Ahora mismo no estoy seguro que sea exactamente así, pero para lo que preguntas es trivial.

Citar
2º si construimos cadenas (o arrays, mal usada la palabra cadenas) de 20 bytes exactos, realizando todas las combinaciones posibles, ocuparemos exactamente todas las claves generadas de SHA-1, ya que estas son también 256^20..

Si tomas la calculadora y hechas cuentas, verás que arroja un resultado de 48 cifras, esto significa que computacionalmente hablando una rutina que tarde 1 msg. tardaría 1*10^45 segundos... es decir 1*10^41 horas * 4, es decir 1'69 * 1*10^40 días, es decir: 4'63 *1*10^37 años, es decir: 463439129036942833017403866284,97 millones de siglos. incluso aunque redujeras esa rutina de 1 milisegundo a una millonésima de segundos no tendría apensa sconsecuencias..

Citar
3º si no se ha producido colisión, cosa bastante curiosa, pero que demostraría una gran pericia, obviamente se producirá con cadenas de 21 caracteres... es mas... si no hay colisión con 20 bytes, hay colisión al menos entre una cadena de 20 y una cadena de 21...
si yo tomo cadenas de 256 caracteres, y tu me envías cadenas de de 264 caracteres una de 2 o arroja error de tipo de datos o en el mejor de los casos, tomando los datos secuencialmente, sólo tomo los enésimos 256 caracteres , de modo que si tu has enviado cadenas de 264 caracteres, se va truncando en cadenas de 256...

Citar
¿entonces porqué se pone siempre en juicio el hecho de que no haya colisiones en un algoritmo? en arrays de bytes cuya longitud sea superior a la del hash siempre habra colision... no?
Sólo si yo no aprovechara el rango completo del tipo de datos que estoy utilizando pero al momento de comparar truncara el exceso. Me explico si el número mayor de mi tipo de datos que utilizo en x función fuera 4096.... pero mi rango máximo fuera 999, parece razonable suponer que tanto 999 como 1999, como 2999 y 3999 dieran positivo pero cuando yo establezca una igualdad se pierde y sólo valida con 999, a excepción de que validadra con  'x mod 1000' en cuyo caso entrarían los anteriormente descritos. Por eso siempre se aprovecha el rango completo del tipo de datos que manejas, porque para eso tiene su límite.

nota: puedes aplicar los mismos razonamientos con los números negativos caso de ser numérico y no de cadenas el valor...

saludos...
«Ma non troppo»
----> ModoVacaciones = False<----