MD5 hash algoritam

Izradio:

Ognjen Fabris (mbr. 0036369511)

u sklopu seminara iz predmeta Operacijski sustavi 2

Fakultet elektrotehnike i računarstva

1. Uvod

MD5 je hash algoritam koji se koristi za računanje sažetka poruke. Razvijen je 1993. godine od Ronald L. Rivest-a, a distribuiran od RSA Data Security, Inc.

Stvara 128 bitni sažetak ulaznog podatka proizvoljne duljine. MD5 je dizajniran da bude brz na 32-bitnim računalima. Također, ne koristi velike supstitucijske tablice kako bi implementacija bila što kompaktnija. Kod njegovih prethodnih inačica, algoritama MD2 i MD4, uočeni su nedostaci te ih se više ne koristi. MD5 je nešto sporiji od MD4 algoritma, ali je dobio na sigurnosti. Često je upotrebljavan, no 1996. godine je ukazano na neke njegove slabosti pa se ne smatra da predstavlja vrhunac sigurnosti. Može se koristiti slobodno, bez kupnje licence.

2. Opis algoritma

Produljivanje poruke

U prvom koraku se poruka (niz bitova) produljuje tako da se na kraj doda jedinica pa niz nula tako da duljina poruke pri dijeljenju sa 512 daje ostatak 448. Na poruku se dodaje produžetak čak i ako je već duljine n*512+448 bitova, gdje je n cijeli broj. Znači, na poruku se dodaje najmanje jedan, a najviše 512 bitova.

Zatim se na proširenu poruku dodaje 64 bitna reprezentacija duljine originalne poruke. Ako je duljina originalne poruke veća od 2⁶⁴ bita, uzima se samo donjih 64 bita. Ti bitovi se dodaju kao dvije 32 bitne riječi, i to prvo manje značajna riječ (donjih 32 bita) a onda značajnija (gornjih 32 bita) riječ. Svaka riječ se dodaje po sistemu little-endian, tj. prvo najmanje značajan oktet a onda značajniji. Sada bi duljina u bitovima ovako proširene poruke trebala biti višekratnik broja 512.

Pomoćne strukture i funkcije

Sažetak poruke je predstavljen sa četiri 32 bitna spremnika (A, B, C i D). Njihove inicijalne vrijednosti su (little-endian: prvo niži pa viši okteti):

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

Koriste se 4 pomoćne funkcije. Svaka od njih prima tri 32 bitna parametra, a kao rezultat vraća jednu 32 bitnu riječ. Definicije funkcija su:

F(x, y, z) = (x AND y) OR ((NOT x) AND z)

G(x, y, z) = (x AND z) OR (y AND (NOT z))

H(x, y, z) = x XOR y XOR z

I(x, y, z) = y XOR (x OR (NOT z))

Koristi se tablica T koja ima 64 elementa (T[1..64]) a generira se pomoću matematičke funkcije sinus:

T[i] = cijeli dio od 2³² * abs(sin(i)), gdje je i kut u radijanima.

Npr. T[1]

sin(1) = 0,841470984807896506652502321630...

abs(sin(1)) = 0,841470984807896506652502321630...

2³² * abs(sin(1)) = 3614090360,282828338625143907966...

trunc(2³² * abs(sin(1))) = 3614090360₍₁₀₎ = D76AA478₍₁₆₎

T[1] = D76AA478₍₁₆₎

Procesiranje blokova

Poruka se sada dijeli na 32 bitne podblokove M[0], M[1], ..., M[N-1], gdje je N višekratnik od 16.

Kako se poruka procesira u 512 bitnim blokovima, i-ti blok čine 16 podblokova: M[i*16], M[i*16+1], ..., M[i*16+15].

Pseudokod algoritma:

MD5 (M, N, H)

// postavi početne vrijednosti

A = 67452301

B = efcdab89

C = 98badcfe

D = 10325476

 
 za i = 0 do N/16-1 //procesiramo svaki blok
 
 // kopiraj i-ti blok u X
 za j = 0 do 15
 X[j] = M[i*16+j]
 
 // spremi kopije, trebat ce kasnije
 AA = A
 BB = B
 CC = C
 DD = D
 
 // 1. runda – funkcija F
 // neka [abcd k s i] predstavlja naredbu:
 // a = b + ((a + F(b,c,d) + X[k] + T[i]) << s)
 // 16 naredbi:
 [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. runda – funkcija G
 // neka [abcd k s i] predstavlja naredbu:
 // a = b + ((a + G(b,c,d) + X[k] + T[i]) << s)
 // 16 naredbi:
 [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. runda – funkcija H
 // neka [abcd k s i] predstavlja naredbu:
 // a = b + ((a + H(b,c,d) + X[k] + T[i]) << s)
 // 16 naredbi:
 [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. runda – funkcija I
 // neka [abcd k s i] predstavlja naredbu:
 // a = b + ((a + I(b,c,d) + X[k] + T[i]) << s)
 // 16 naredbi:
 [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]
 
 // povećaj svaki spremnik za vrijednost koju je imao prije obrade bloka
 A = A + AA
 B = B + BB
 C = C + CC
 D = D + DD
 
 // svi blokovi su obrađeni, spoji spremnike A, B, C i D u sazetak (hash)
 // tako sazetak pocinje sa najnizim oktetom spremnika A, a zavrsava sa
  // najvisim oktetom spremnika D
 H = A:B:C:D
KRAJ
 
3. Zadatak
 
Napisati program za računanje sažetka poruke algoritmom MD5.
Vrijednosti elemenata T tablice nalaze se u datoteci md5.h.
Primjeri poruka i njihovih pripadajućih sažetaka nalaze se u datoteci primjeri.txt.
 
4. Rješenje
 
Source kod (C): md5.c, md5.h
Izvršna verzija (za pinus): md5.exe
Primjer: message.text (tekstualna datoteka sa porukom kao nizom znakova), message.md5 (tekstualna datoteka sa heksadekadskom reprezentacijom sažetka).
 
5. Literatura
 
RFC1321 - The MD5 Message-Digest Algorithm

Vladimir Semenčić: Portal - seminari iz kolegija Operacijski Sustavi

Digitalni potpisi laboratorijska vježba iz predmeta Operacijski sustavi 2