Resistencia a la colision
- jllinares
- PreparaTIC XXII
- Mensajes: 149
- Registrado: 07 Oct 2009, 23:47
- Agradecido: 0
- Agradecimiento recibido: 0
Resistencia a la colision
Hola, me ha salido esta pregunta:
16. Para evaluar la calidad de un algoritmo de 'hash' o de resúmen se suele emplear la
'resistencia a la colisión'. Ésta se puede definir como...
a) La resistencia a obtener al texto original a partir de la huella digital
b) La resistencia a localizar un texto alternativo cuya huella digital sea igual a una dada
c) Dado el texto original, es la resistencia a encontrar otra huella digital válida
d) Dadas dos huellas digitales diferentes, es la probabilidad de que procedan del mismo texto
original
La respuesta es la B y yo pensaba que era la C. La cuestión es que por más que busco no consigo aclararme sobre la diferencia entre la resistencia a la colisión, a la primera preimagen y a la segunda preimagen. Alguién me podría decir donde puedo ver una explicación que sea buena, fácil y concisa.
Un saludo y muchas gracias,
16. Para evaluar la calidad de un algoritmo de 'hash' o de resúmen se suele emplear la
'resistencia a la colisión'. Ésta se puede definir como...
a) La resistencia a obtener al texto original a partir de la huella digital
b) La resistencia a localizar un texto alternativo cuya huella digital sea igual a una dada
c) Dado el texto original, es la resistencia a encontrar otra huella digital válida
d) Dadas dos huellas digitales diferentes, es la probabilidad de que procedan del mismo texto
original
La respuesta es la B y yo pensaba que era la C. La cuestión es que por más que busco no consigo aclararme sobre la diferencia entre la resistencia a la colisión, a la primera preimagen y a la segunda preimagen. Alguién me podría decir donde puedo ver una explicación que sea buena, fácil y concisa.
Un saludo y muchas gracias,
Un saludo y muchas gracias,
-
- Usuario registrado
- Mensajes: 38
- Registrado: 19 Ago 2013, 11:24
- Agradecido: 0
- Agradecimiento recibido: 0
Re: Resistencia a la colision
dados los siguientes datos:
X-mensaje en claro
H-funcion hash
Y-resultado de hash
1. resistencia a la primera preimagen es:
teniendo un resumen hash Y es computacionalmnete intratable obtener el mensaje en claro X
2. resistencia a la segunda preimagen es:
teniendo un mensaje en claro X1 cuyo resumen después de aplicar la función hash es Y es computacionalmente intratable encontrar otro mensaje en claro X2 cuyo resumen después de aplicar la misma función hash también sea Y.
3. resistencia a colisiones CRHF
una función hash tendría resistencia a colisiones si es computacionalmente intratable encontrar dos mensajes en claro que tengan el mismo resumen. Este tipo de resistencia incluye a la resistencia a la segunda preimagen y se refiere a resistencia a preimagen para funciones hash con salida aleatoria. Las llaman también funciones hash de un solo sentido
tienen la resistencia a la primera preimagen y a la segunda preimagen. Es deicr es dificil encontrar un mensaje en claro que tenga un resumen hash preespecificado.
Podemos decir que la diferencia entre 2 y 3 es que en dos se tiene el mensaje en claro, se tiene el resumen de este mensaje y se intenta buscar otro mensaje en claro con el mismo resumen, es decir no es aleatoria la imagen sobre la que se busca la coincidencia. Mientras que en el punto 3 se habla de que la función es resistente o mejor dicho existe muy poco probabilidad de que dos mensajes cualesquiera generen el mismo resumen. La diferencia es muy sutil.
Espero que te sirva.
X-mensaje en claro
H-funcion hash
Y-resultado de hash
1. resistencia a la primera preimagen es:
teniendo un resumen hash Y es computacionalmnete intratable obtener el mensaje en claro X
2. resistencia a la segunda preimagen es:
teniendo un mensaje en claro X1 cuyo resumen después de aplicar la función hash es Y es computacionalmente intratable encontrar otro mensaje en claro X2 cuyo resumen después de aplicar la misma función hash también sea Y.
3. resistencia a colisiones CRHF
una función hash tendría resistencia a colisiones si es computacionalmente intratable encontrar dos mensajes en claro que tengan el mismo resumen. Este tipo de resistencia incluye a la resistencia a la segunda preimagen y se refiere a resistencia a preimagen para funciones hash con salida aleatoria. Las llaman también funciones hash de un solo sentido
tienen la resistencia a la primera preimagen y a la segunda preimagen. Es deicr es dificil encontrar un mensaje en claro que tenga un resumen hash preespecificado.
Podemos decir que la diferencia entre 2 y 3 es que en dos se tiene el mensaje en claro, se tiene el resumen de este mensaje y se intenta buscar otro mensaje en claro con el mismo resumen, es decir no es aleatoria la imagen sobre la que se busca la coincidencia. Mientras que en el punto 3 se habla de que la función es resistente o mejor dicho existe muy poco probabilidad de que dos mensajes cualesquiera generen el mismo resumen. La diferencia es muy sutil.
Espero que te sirva.
- vfrades
- PreparaTIC XXI
- Mensajes: 631
- Registrado: 16 Jun 2008, 15:40
- Agradecido: 0
- Agradecimiento recibido: 0
Re: Resistencia a la colision
La resistencia a la colisión puede ser débil o fuerte. Véase la Wikipedia:
http://es.wikipedia.org/wiki/Colisi%C3%B3n_(hash)
La pregunta no especifica el tipo de resistencia, así que deberíamos entender la menos restrictiva (la débil)
http://es.wikipedia.org/wiki/Colisi%C3%B3n_(hash)
La pregunta no especifica el tipo de resistencia, así que deberíamos entender la menos restrictiva (la débil)
- vfrades
- PreparaTIC XXI
- Mensajes: 631
- Registrado: 16 Jun 2008, 15:40
- Agradecido: 0
- Agradecimiento recibido: 0
Re: Resistencia a la colision
La respuesta b) es la definición de resistencia a la colisión débil: dado un texto en claro x, es la imposibilidad (o enorme dificultad) de encontrar otro texto diferente y, tal que H(x)=H(y) (H es la función hash)
La respuesta c) no tiene sentido. No puede haber dos huellas válidas para un mismo texto claro. Lo mismo ocurre para la respuesta d).
Por su parte, la respuesta a) no tiene nada que ver con la resistencia a la colisión; es la definición de resistencia a la primera preimagen.
La respuesta c) no tiene sentido. No puede haber dos huellas válidas para un mismo texto claro. Lo mismo ocurre para la respuesta d).
Por su parte, la respuesta a) no tiene nada que ver con la resistencia a la colisión; es la definición de resistencia a la primera preimagen.
-
- PreparaTIC XXII
- Mensajes: 152
- Registrado: 19 Oct 2010, 08:26
- Agradecido: 0
- Agradecimiento recibido: 0
Re: Resistencia a la colision
Opino como vfrades.
Las opciones c) y d) no tienen sentido. Un texto solo puede tener un hash (ya que la aplicación del mismo algoritmo sobre los mismos datos, siempre va a dar lo mismo).
La correcta es la b)
Las opciones c) y d) no tienen sentido. Un texto solo puede tener un hash (ya que la aplicación del mismo algoritmo sobre los mismos datos, siempre va a dar lo mismo).
La correcta es la b)
- jllinares
- PreparaTIC XXII
- Mensajes: 149
- Registrado: 07 Oct 2009, 23:47
- Agradecido: 0
- Agradecimiento recibido: 0
Re: Resistencia a la colision
Es que, para mi, y después de haber leído la wiki, la B se parece más a la segunda preimagen que la resistencia a la colisión. De todos modos por descarte, efectivamente, se puede sacar...
Un saludo y muchas gracias,
- vfrades
- PreparaTIC XXI
- Mensajes: 631
- Registrado: 16 Jun 2008, 15:40
- Agradecido: 0
- Agradecimiento recibido: 0
Re: Resistencia a la colision
Resistencia a la segunda preimagen sería:
Dado x, encontrar un y tal que H(x) = H(y)
Por su parte, resistencia a la colisión (débil) sería:
Dado H(x), encontrar un y tal que H(x) = H(y)
Y resistencia a la colisión fuerte sería:
Encontrar un par x,y tal que H(x) = H(y)
La respuesta b) dice "...cuya huella sea igual a una dada" que es una diferencia sutil respecto a "...cuya huella sea igual a la de un texto original dado". Como ves, la diferencia entre resistencia a la segunda preimagen y resistencia a la colisión es el dato conocido.
Dado x, encontrar un y tal que H(x) = H(y)
Por su parte, resistencia a la colisión (débil) sería:
Dado H(x), encontrar un y tal que H(x) = H(y)
Y resistencia a la colisión fuerte sería:
Encontrar un par x,y tal que H(x) = H(y)
La respuesta b) dice "...cuya huella sea igual a una dada" que es una diferencia sutil respecto a "...cuya huella sea igual a la de un texto original dado". Como ves, la diferencia entre resistencia a la segunda preimagen y resistencia a la colisión es el dato conocido.