MD5

Programmazione, algoritmica, teoria dell'informazione, ...
Bloccato
Avatar utente
Metal H
Messaggi: 2
Iscritto il: 14 nov 2006, 18:08
Contatta:

MD5

Messaggio da Metal H »

So che si dovrebbe postare problemi o programmi mirati al problem solving... ma in fondo l'algoritmo MD5... se non è qualcosa di matematico...
Ad ogni modo, mi chiedevo se qualcuno di voi poteva spiegarmi nel dettaglio come si procede per trasformare una stringa in un fingerprint MD5, o almeno se qualcuno conosceva qualche risorsa in Internet dove quello che chiedo è spiegato.
Per favore, non postate siti contenenti algoritmi per l'MD5 hashing, quelli li ho già trovati, e idem per spiegazioni in lingue diverse dall'italiano.
Vorrei una spiegazione chiara.
Grazie.

P.S.: Se davvero non potete accettare questo topic in questa sezione spostatelo, ma rispondetemi! Grazie.
Avatar utente
SkZ
Messaggi: 3333
Iscritto il: 03 ago 2006, 21:02
Località: Concepcion, Chile
Contatta:

Messaggio da SkZ »

tratto da "RFC 1321 - The MD5 Message-Digest Algorithm"
http://www.faqs.org/rfcs/rfc1321.html

3. Descrizione dell'algoritmo MD5
Iniziamo supponendo che abbiamo in input un messaggio di $ ~b\in \mathbb{N} $ bit. immaginiamo cge i bit del messaggio siano scritti come $ ~m_0 m_1 ... m_{b-1} $

I seguenti 5 passaggi sono eseguiti per calcolare message digest del messaggio

3.1 Step 1. Appendere Bit di riempimento

Il messaggio e' esteso cosi' che la sua lunghezza in bit sia congruaa 448 modulo 512. Tale aggiunta e' fatta sempre ed e' eseguita aggiungendo un singolo "1" alla fine del messaggio e poi tanti "0" quanti necessari affinche' la sua lunghezza sia congrua 448 modulo 512. In tutto sono aggiunti almeno un bit e al massimo 512 bit


3.2 Step 2. Aggiungere la lunghezza

una rappresentazione a 64-bit di b (la lunghezza del messaggio prima dell'estensione) e' accodata. nell'improbabile caso che b sia piu' grande di $ ~2^64 $, alloar solo i 64 bit di ordine piu' basso sono utilizzati. (Questi bit sono accodati come due parole di 32 bit e prima la parola accodata di ordine basso in accordo con le convenzioni precedenti.

a questo punto il messaggio risultante ha una lunghezza multipla di 512. Ovvero ha una lunghezza pari a quella di un multiplo di 16 parole di 32bit. Chiamiamo $ ~M[0 ... N-1] $ le parole del messaggio risultante,con N multiplo di 16.

3.3 Step 3. Inizializzazione del MD Buffer

un buffer di quattro parole (A,B,C,D) e' usato per calcolare il message digest.
A, B, C, D sono registri a 32bit. Questi sono inizializzati ai seguenti valori esadecimali (byte di basso ordine prima):

word A: 01 23 45 67
word B: 89 ab cd ef
word C: fe dc ba 98
word D: 76 54 32 10

3.4 Step 4. Processare il message in blocchi di 16-Word

Inizialmente definiamo 4 funzioni ausiliari che ognuna prende per input 3 parole da 32bit e produce come output una 32-bit word.

F(X,Y,Z) = XY V not(X) Z
G(X,Y,Z) = XZ V Y not(Z)
H(X,Y,Z) = X xor Y xor Z
I(X,Y,Z) = Y xor (X V not(Z))

Per ogni posizione di bit F agisce come un condizionale: se X allora Y oppure Z. La funzione F puo' essere definita usando + al posto di V dato che XY e not(X)Z non avranno mai degli 1 nella stessa posizione). E' interessante notare che se i bit di X, Y e Z sono indipendenti e unbiased, ogni bit di F(X,Y,Z) sara' indipendente e unbiased.

Le funzioni G, H e I sono simili a F, nel senso che agiscono in "bitwise parallel" per produrre il loro output dai bit di X, Y e Z, in un modo tale che se i corrispondenti bits di X, Y e Z sono indipendenti e unbiased, allora ognuno dei G(X,Y,Z),
H(X,Y,Z) e I(X,Y,Z) sara' indipendente e unbiased. E' da notare che la funzione H e' il bit-wise "xor" o funzione "parita'" del suo input.

questo passaggio usa una tavola di 64 elementi T[1 ... 64] costruita a partire dal seno. Posto T l'i-esimo elemento della tavola, che e' pari alla parte intera di 4294967296 volte abs(sin(i)), dove i e' in radianti. Gli elementi della tavolo sono dati in appendice.

Esegui i segenti:

/* Processa ogni 16-word block. */
For i = 0 to N/16-1 do

/* Copy block i into X. */
For j = 0 to 15 do
Set X[j] to M[i*16+j].
end /* del loop su j */

/* Salva A come AA, B come BB, C come CC e D come DD. */
AA = A
BB = B

CC = C
DD = D

/* Round 1. */
/* Denotiamo con [abcd k s i] l'operazione
a = b + ((a + F(b,c,d) + X[k] + T) <<< s). */
/* fai le seguenti 16 operazioni. */
[ABCD 0 7 1] [DABC 1 12 2] [CDAB 2 17 3] [BCDA 3 22 4]
[ABCD 4 7 5] [DABC 5 12 6] [CDAB 6 17 7] [BCDA 7 22 8]
[ABCD 8 7 9] [DABC 9 12 10] [CDAB 10 17 11] [BCDA 11 22 12]
[ABCD 12 7 13] [DABC 13 12 14] [CDAB 14 17 15] [BCDA 15 22 16]

/* Round 2. */
/* Denotiamo con [abcd k s i]
a = b + ((a + G(b,c,d) + X[k] + T) <<< s). */
/* fai le seguenti 16 operazioni. */
[ABCD 1 5 17] [DABC 6 9 18] [CDAB 11 14 19] [BCDA 0 20 20]
[ABCD 5 5 21] [DABC 10 9 22] [CDAB 15 14 23] [BCDA 4 20 24]
[ABCD 9 5 25] [DABC 14 9 26] [CDAB 3 14 27] [BCDA 8 20 28]
[ABCD 13 5 29] [DABC 2 9 30] [CDAB 7 14 31] [BCDA 12 20 32]

/* Round 3. */
/* Denotiamo con [abcd k s t] l'operazione
a = b + ((a + H(b,c,d) + X[k] + T) <<< s). */
/* fai le seguenti 16 operazioni. */
[ABCD 5 4 33] [DABC 8 11 34] [CDAB 11 16 35] [BCDA 14 23 36]
[ABCD 1 4 37] [DABC 4 11 38] [CDAB 7 16 39] [BCDA 10 23 40]
[ABCD 13 4 41] [DABC 0 11 42] [CDAB 3 16 43] [BCDA 6 23 44]
[ABCD 9 4 45] [DABC 12 11 46] [CDAB 15 16 47] [BCDA 2 23 48]

/* Round 4. */
/* Denotiamo con [abcd k s t] l'operazione
a = b + ((a + I(b,c,d) + X[k] + T) <<< s). */
/* fai le seguenti 16 operazioni.*/
[ABCD 0 6 49] [DABC 7 10 50] [CDAB 14 15 51] [BCDA 5 21 52]
[ABCD 12 6 53] [DABC 3 10 54] [CDAB 10 15 55] [BCDA 1 21 56]
[ABCD 8 6 57] [DABC 15 10 58] [CDAB 6 15 59] [BCDA 13 21 60]
[ABCD 4 6 61] [DABC 11 10 62] [CDAB 2 15 63] [BCDA 9 21 64]

/* Poi esegui le seguenti addizioni. (cioe' incrementa ognuno dei 4 registri del valore che aveva prima che questa serie venisse esguita). */
A = A + AA
B = B + BB
C = C + CC
D = D + DD

end /* del loop su i */

3.5 Step 5. Output

Il message digest prodotto come output e' A, B, C, D. Cioe' iniziamo col byte di basso ordine di A e finiamo con quello di ordine alto di D.
impara il [tex]~\LaTeX[/tex] e mettilo da par[tex]\TeX~[/tex]

Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
MindFlyer

Messaggio da MindFlyer »

Penso che SkZ abbia risposto, quindi chiudo questo thread OT.
Bloccato