MD5 Algoritam

MD5 Algoritam

Pripremio:

Dario Hofman

4 god. RAČ

8.12.2002

Autor algoritma: Ronald L. Rivest (inače redoviti profesor na MIT-u odio elektotehnike i računarstva, osnivač RSA Data Security koja se je spojila sa Security Dynamics u RSA Security). Algoritam se još može naći pod nazivom Riv92c po autoru i verziji algoritma.

Datum algoritma: 1991 godina

UKRATKO O ALGORITMU:

· Jednostavan za implementirati

· Duljina ulaznog teksta je proizvoljne veličine

· Kodiraju se riječi po 32 bita

· Dobiveni sažetak poruke je 128 bitni

· U svakom od 4 koraka se vrši po jedna funkcija (transformacija) nad grupom od 16 podataka

MALO VIŠE O ALGORITMU:

MD5 algoritam uzima ulaznu poruka proizvoljne duljine i proizvodi (iz nje) 128bitni «fingerprint» («otisak prsta») ili «message digest» («sažetak poruke»). Samo nagađanjem se može dobiti dvije poruke koje imaju isti sažetak poruke ili proizvesti poruku sa zadanim sažetkom poruke*. MD5 je namijenjen za digitalno potpisivanje programa, kod kojih velika datoteka mora biti «komprimirana» sigurnim postupkom prije nego ih se kriptira sa (tajnim) privatnim ključem koristeći kriptoalgoritam poput RSA.

Ukratko, MD5 služi verificiranju integriteta podataka i puno je sigurniji nego checksum ili neke druge metode.

* Vjerojatnost da se dobiju 2 ista sažetka poruke ovisi o 2^64 operacija, a da se dobije željeni sažetak poruke ovisi o 2^128 operacija.

JOŠ MALO O ALGORITMU:

MD5 algoritam (u daljnjem tekstu samo MD5) je dizajniran da bi bio relativno brz na 32bitnim procesorima. Također MD5 ne zahtjeva velike tablice. MD5 je nastavak MD4 algoritma. Malo je sporiji od njega, ali je više konzervativan u dizajnu. MD5 je nešto sporiji od MD4 algoritma, ali donosi bolju sigurnost. U MD5 su implementirane neki savjeti raznih korisnika (revizora) algoritma. Npr. za ulaznu poruku «abc» dobiti će se slijedeći sažetak «900150983cd24fb0d6963f7d28e17f72».

5 KORAKA ALGORITMA:

(1) Proširenje poruke

Duljina poruke mora (u bitovima) biti jednaka 448 ako se nad njome izvrši operacija modulo 512. To znači da je duljina poruke višekratnik broja 512 umanjen za 64. Proširenje poruke se izvodi uvijek, pa čak i kada je duljina poruke modulo 512 iznosi 448.

Proširenje se izvodi ovako: bit «1» se nadodaje na kraj poruke, a onda se nadodaju bitovi «0» tako da poruka zadovoljava gornji uvjet. U svakom slučaju najmanje jedan, a najviše 512 bitova se nadodaje na kraj poruke.

(2) Nadodavanje duljine

Duljinu «b» originalne (znači prije 1. koraka) poruke prikazati u 64 bita i nadodati na poruku dobivenu prethodnim korakom. Ako je poruka dulja od 2^64 bita onda se dopisuje samo doljnih 64 bita duljine poruke. Bitovi se dopisuju od najmanje bitnog prema najviše bitnom. Sada je znači duljina poruke djeljiva sa 512. Znači poruku možemo zapisati kao višekratnik od 32 (= riječ). Neka to zapisujemo kao M(0,1,2,...,N-1) gdje je N sigurno višekratnik broja 16, a 0 predstavlja 32bitnu riječ, 1 predstavlja 32bitnu riječ itd.

(3) Inicijalizacija MD spremnika

Četiri 32 bitna spremnika (A,B,C,D) se koriste za izračunavanje sažetka poruke. Njihove inicijalne vrijednosti u heksadecimalnom zapisu su:

A 01 23 45 67

B 89 ab cd ef

C fe dc ba 98

D 76 54 32 10

Napomena!!! Najmanje značajan bit je napisan najlijevije (prvi po redu)

(4) Obrada poruke po 16 32bitna bloka

Prvo definiramo 4 izlazne funkcije:

F(X,Y,Z) = X*Y v not(X)*Z

G(X,Y,Z) = X*Z v Y*not(Z)

H(X,Y,Z) = X xor Y xor Z

I(X,Y,Z) = Y xor (X v not(Z))

Za svaki bit funkcija F se ponaša kao uvjet: «Ako X onda Y inače Z». Funkcije G, H i I su slične funkciji F (zgodno je za primijetiti da je funkcija H ustvari paritetna funkcija ulaznih bitova).

Sljedeći korak koristi 64 elementnu tablicu T[1 ... 64] konstruiranu iz sinusne funkcije. T[i] je jednako cjelobrojnom dijelu od 4294967296 * abs(sin(i)), gdje je i u radijanima.

Treba napraviti sljedeće:

/* Za svaki od 16-riječnih blokova */

For i = 0 to N/16-1 do

{

/* Kopiraj blok i u X. */

For j = 0 to 15 do

{Set X[j] to M[i*16+j]}

/* Spremi A kao AA, B kao BB, C kao CC, i D kao DD. */

AA = A

BB = B

CC = C

DD = D

/* 1. korak */

/* Neka [abcd k s i] obavi operaciju

a = b + ((a + F(b,c,d) + X[k] + T[i]) <<< s). */

/* Napravi sljedećih 16 operacija */

[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]

/* 2. korak */

/* Neka [abcd k s i] obavi operaciju

a = b + ((a + G(b,c,d) + X[k] + T[i]) <<< s). */

/* Napravi sljedećih 16 operacija */

[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]

/* 3. korak */

/* Neka [abcd k s t] obavi operaciju

a = b + ((a + H(b,c,d) + X[k] + T[i]) <<< s). */

/* Napravi sljedećih 16 operacija */

[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]

/* 4. korak */

/* Neka [abcd k s t] obavi operaciju

a = b + ((a + I(b,c,d) + X[k] + T[i]) <<< s). */

/* Napravi sljedećih 16 operacija */

[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]

/* Nakon toga napravi sljedeća zbrajanja. (To je povećanje svakog od 4 registra za vrijednost prije nego je ovaj blok počeo) */

A = A + AA

B = B + BB

C = C + CC

D = D + DD

}

(5) Izlazni sažetak poruke

Izlazni sažetak poruke je A, B, C, D s time da se počinje sa (najlijevije je) najniži bit od A, a završava sa najvišim bitom od D. To je cijeli opis implementacije MD5 algoritma po rfc 1321 dokumentu (za detalje pogledajte navedeni dokument).

MD5 demonstacija

Prava na korištenje MD5 algoritma:

RSA's MD5 disclaimer

License to copy and use this software is granted provided that it is identified as the "RSA Data Security, Inc. MD5 Message-Digest Algorithm" in all material mentioning or referencing this software or this function.

License is also granted to make and use derivative works provided that such works are identified as "derived from the RSA Data Security, Inc. MD5 Message-Digest Algorithm" in all material mentioning or referencing the derived work.

RSA Data Security, Inc. makes no representations concerning either the merchantability of this software or the suitability of this software for any particular purpose. It is provided "as is" without express or implied warranty of any kind.

These notices must be retained in any copies of any part of this documentation and/or software.