Sea x un valor arbitrario de 256 bits. La salida de H (x) es menor que 2 ^ 215. ¿Cuántas funciones hash tengo que calcular para encontrar una solución?
He intentado resolver este problema con un ataque de pre-imagen. Y el resultado fue que si la salida del hash es menor que 2 ^ 215, debemos calcular el hash 2 ^ 215 veces. ¿Es eso correcto?
Una buena función de hash que pruebe distintas entradas nuevas muestreará uniformemente el espacio de salida con 2 256 salidas posibles. Ahora, para que la salida sea menor que 2 215 , hay exactamente 2 215 valores de salida potenciales (de 0 a 2 215 -1) que satisfacen eso. Entonces, la probabilidad de obtener una salida en este rango al probar un hash es p₁ = 2 215 / 2 256 = 2 -41 .
Ahora, si lo intentas dos veces (por ejemplo, hash dos entradas aleatorias distintas), la probabilidad de que al menos una salida esté en el rango es p₂ = 1 - (1-p₁)*(1-p₁) , ya que (1-p₁) es la probabilidad de que el primer hash no esté en menos de 2 215 , (1-p₁)(1-p₁) es la probabilidad de que tanto el primer hash como el del segundo hash no sean menores que 2 215 , y luego tomamos el complemento de esa probabilidad (para garantizar que ya sea el primer hash o el segundo hash está en el rango). De manera similar, si hizo tres entradas aleatorias, la probabilidad de que al menos una salida esté en el rango es p₃ = 1 - (1-p₁)*(1-p₁)*(1-p₁) ; es decir, a menos que los tres no estén simultáneamente en el rango, entonces al menos uno de ellos está dentro del rango. Como puede ver, esto se generaliza para que los hash de hash separados sean p(N) = 1 - (1-p₁)^N .
Si quiere tener una probabilidad del 99% de encontrar una solución, establezca p(N) = .99 = 1 - (1-p₁)^N y resuelva en N, la reorganización se convierte en (1-p₁)^N = .01 , luego se toma el registro natural de ambos lados y se usan las propiedades de los registros:
N = (ln .01)/(ln [1 - p₁]) = 10126876334760.2 ~ 1.01 x 10^13
Tenga en cuenta que puede usar la aproximación de la serie de Taylor de que ln (1 - x) ~ -x cuando x es pequeña (por ejemplo, en nuestro ejemplo cuando es 2^-41 ) en la ecuación anterior para simplificarla a N = ln (1/100) / (-p₁) = 2<sup>41</sup> ln 100 si desea evaluarla. analíticamente.
Lea otras preguntas en las etiquetas hash