algoritmi di hashing

[prip]

Qualcuno mi può spiegare in parole semplici come funziona un algoritmo di hashing,
e magari farmi qualche piccolo esempio in codice bellobello?

Non riesco a pensare come sia possibile che una funzione,
dato un input, ritorni sempre lo stesso valore; e non possa essere reversibile.

Se poi qualcuno volesse spiegarmi come funziona md5, facendo un bel discorso completo, sarei enormemente soddisfatto :D... ma ovviamente chiederei troppo :)

Grazie

[end.is.forever]

La più semplice funzione di hash che mi viene in mente è il calcolo di un bit di parità: sommi modulo due tutti i bit di una stringa, il risultato è l'impronta della tua stringa.
I valori possibili dell'impronta quindi sono due: 0 ed 1; se uno legge 0, non può capire quale stringa l'ha generato perche di numeri che danno 0 come bit di parità sono infiniti.
In questo senso questa funzione è unidirezionale.

In generale questo vale per qualsiasi funzione che associ ad ogni possibile valore dello spazio delle uscite sempre più di un valore dello spazio degli ingressi.
Per questo motivo tutte le funzioni che riassumono in questo modo strighe di lunghezza arbitraria in stringhe di lunghezza fissa sono unidirezionali.

Piuttosto la sicurezza delle funzioni hash sta nel fatto di rendere computazionalmente molto difficile trovare collisioni (cioè due stringhe x e y tali che H(x) = H(y)), questo perchè molto spesso le funzioni hash sono usate per verificare l'integrità di un testo.

Nel dettaglio md5 non lo conosco, però ti so dire che tutti gli algoritmi di hash fanno le seguenti cose:
1)Dividono il testo in blocchi di lunghezza k fissa (t(0),...,t(l))
2)Pongono y(0) = x (valore iniziale fisso)
3)Ad ogni passo i-esimo calcolano y(i) = f(y(i-1), t(i)). Quindi in pratica comprimono insieme attraverso una qualche funzione due ingressi lunghi k in un unica uscita di lunghezza k (mescolando insieme il riassunto calcolato finora e il blocco di testo i-esimo)
4)Alla fine restituiscono y(l) che riassume tutti i blocchi precedenti.

Più la funzione usata è complicata (nel senso che è difficile capire quali variazioni dell'ingresso facciano variare quali bit dell'uscita, e soprattutto quanti) più si dice sicura, perchè è difficile analizzarla e trovare delle collisioni.

Spero di esserti stato di aiuto ciao.

[prip]

Originariamente inviato da end.is.forever
La più semplice funzione di hash che mi viene in mente è il calcolo di un bit di parità: sommi modulo due tutti i bit di una stringa, il risultato è l'impronta della tua stringa.
I valori possibili dell'impronta quindi sono due: 0 ed 1; se uno legge 0, non può capire quale stringa l'ha generato perche di numeri che danno 0 come bit di parità sono infiniti.
In questo senso questa funzione è unidirezionale.

In generale questo vale per qualsiasi funzione che associ ad ogni possibile valore dello spazio delle uscite sempre più di un valore dello spazio degli ingressi.
Per questo motivo tutte le funzioni che riassumono in questo modo strighe di lunghezza arbitraria in stringhe di lunghezza fissa sono unidirezionali.


In effetti a questo non avevo pensato.
Basterebbe anche solo contare i caratteri di una stringa!
Solo che chissà quante altre stringhe potrebbero avere lo stesso numero di caratteri...
Quindi:

Piuttosto la sicurezza delle funzioni hash sta nel fatto di rendere computazionalmente molto difficile trovare collisioni (cioè due stringhe x e y tali che H(x) = H(y)), questo perchè molto spesso le funzioni hash sono usate per verificare l'integrità di un testo.


ho già imparato qualcosa. :D



Nel dettaglio md5 non lo conosco, però ti so dire che tutti gli algoritmi di hash fanno le seguenti cose:
1)Dividono il testo in blocchi di lunghezza k fissa (t(0),...,t(l))
2)Pongono y(0) = x (valore iniziale fisso)
3)Ad ogni passo i-esimo calcolano y(i) = f(y(i-1), t(i)). Quindi in pratica comprimono insieme attraverso una qualche funzione due ingressi lunghi k in un unica uscita di lunghezza k (mescolando insieme il riassunto calcolato finora e il blocco di testo i-esimo)
4)Alla fine restituiscono y(l) che riassume tutti i blocchi precedenti.

Più la funzione usata è complicata (nel senso che è difficile capire quali variazioni dell'ingresso facciano variare quali bit dell'uscita, e soprattutto quanti) più si dice sicura, perchè è difficile analizzarla e trovare delle collisioni.

Spero di esserti stato di aiuto ciao.

Grazie, ti ringrazio tantissimo :D