Sia x un valore arbitrario a 256-bit. L'output di H (x) è inferiore a 2 ^ 215. Quante funzioni hash devo calcolare per trovare una soluzione?
Ho provato a risolvere questo problema con un attacco pre-immagine. E il risultato è che se l'output dell'hash è inferiore a 2 ^ 215, allora dobbiamo calcolare l'hash 2 ^ 215 volte. È corretto?
Una buona funzione di hash che prova nuovi input distinti campionerà in modo uniforme lo spazio di output con 2 256 possibili output. Ora che l'output è inferiore a 2 215 ci sono esattamente 2 215 valori di uscita potenziali (da 0 a 2 215 -1) che soddisfano esso. Quindi la probabilità di ottenere un risultato in questo intervallo provando un hash è p₁ = 2 215 / 2 256 = 2 -41 .
Ora, se provi due volte (ad esempio, hash due input casuali distinti), la possibilità che almeno un output sia nell'intervallo è p₂ = 1 - (1-p₁)*(1-p₁) , in quanto (1-p₁) è la probabilità che il primo hash non sia inferiore a 2 215 , (1-p₁)(1-p₁) è la probabilità che il primo e il secondo hash non siano inferiori a 2 215 , e quindi prendiamo il complemento di tale probabilità (per garantire che o il primo hash o il secondo hash è nell'intervallo). Allo stesso modo, se hai eseguito l'hashing di tre input casuali, la possibilità che almeno un output sia nell'intervallo è p₃ = 1 - (1-p₁)*(1-p₁)*(1-p₁) ; cioè a meno che tutti e tre non siano contemporaneamente nell'intervallo, quindi almeno uno di loro è nel raggio d'azione. Come puoi vedere, questo generalizza per l'hashing N hash separati da p(N) = 1 - (1-p₁)^N .
Se vuoi dire una probabilità del 99% di una soluzione, imposta p(N) = .99 = 1 - (1-p₁)^N e risolvi per N, che riorganizza diventa (1-p₁)^N = .01 , quindi diventa il log naturale di entrambi i lati e usa le proprietà dei log:
N = (ln .01)/(ln [1 - p₁]) = 10126876334760.2 ~ 1.01 x 10^13
Nota, puoi usare l'approssimazione della serie Taylor che ln (1 - x) ~ -x quando x è piccolo (ad esempio, nel nostro esempio quando è 2^-41 ) nell'equazione precedente per semplificarlo a N = ln (1/100) / (-p₁) = 2<sup>41</sup> ln 100 se vuoi valutarlo analiticamente.
Leggi altre domande sui tag hash