Sveučilište u Zagrebu
Fakultet Elektrotehnike i Računarstva
ZEMRIS

Seminarski rad iz predmeta "Operacijski sustavi 2"
Hash algoritam

CRC-32

(Cyclic Redundancy Code)

Robert Đurin

crc32.exe - Izvršna datoteka

0160010184

CRC-32 izvorni kod u C-u

Sadržaj

  1. Uvod
  2. Opis algoritma CRC-32
  3. Literatura

1. Uvod

CRC-32 je skraćenica od cyclic redundancy code, dok broj 32 označava da je izlaz iz hash algoritma veličine 32 bita. Algoritam CRC-32 se rijetko koristi u računalnoj sigurnosti zbog male veličine izračunatog sažetka. Međutim CRC-32 je naišao na veliku primjenu u detektiranju pogrešaka kod prijenosa podataka gdje odašiljatelj računa sažetak poruke i pridodaje ga poruci, te ih zajedno šalje primatelju koji također računa sažetak i uspoređuje ga sa primljenim sažetkom, te se na temelju podudaranja ili nepodudaranja sažetaka može utvrditi ispravnost dobivene poruke. Prednost ovog algoritma prema klasičnim načinima detektiranja pogrešaka (npr. paritet, Hammingov kod) je u tome što ti algoritmi u nekim slučajevima ne mogu otkriti pogrešku (npr. ako kod provjere pariteta dva bita promijene vrijednost), dok CRC-32 otkriva grešku jer i za male promjene poruka sažeci se jako razlikuju.
CRC-32 također se koristi kod alata za arhiviranje podataka, te kod medija za pohranu podataka(npr. CD, DVD). Tu se također CRC-32 koristi za detekciju pogreške u podacima.
Dakle možemo zaključiti da CRC-32 nije hash algoritam koji ima neku veliku važnost u računalnoj sigurnosti, međutim on je od velike važnosti u aplikacijama i sredstvima gdje je potreban pouzdan i brz alat za detektiranje pogreške.

2. Opis algoritma CRC-32

2.1 Osnovna ideja algoritma CRC-32

Osnovna ideja koja se krije iza CRC algoritma je pretvoriti poruku u vrlo veliki binarni broj koji se tada dijeli s nekim definiranim brojem koji se naziva ključ(key). Dijeljenjem tih brojeva dobivamo kvocijent i ostatak. Ostatak dijeljenja nam predstavlja sažetak(hash) poruke.
Kod CRC algoritma binarni broj koji dobijemo iz poruke te definirani broj ključ ne predstavljaju se kao cijeli brojevi već kao polinomi sa binarnim koeficijentima.
Prije opisa rada algoritma opisat će se binarni polinomi tj. polinomi sa binarnim koeficijentima i aritmetika nad binarnim poljem(modulo-2 aritmetika).

2.2 Aritmetika nad binarnim poljem

Binarno polje,označimo ga sa BF, kao što i sam naziv govori ima dva elementa i možemo ga prikazati kao:

BF={0,1}

Nad tim poljem provodimo aritmetiku modulo-2, to ustvari znači da radimo operacije kao i inače samo što rezultat uzimamo kao cjelobrojni ostatak dijeljenja sa brojem 2 koji može biti 0 ili 1, a pošto su to elementi BF-a tada i rezultat operacija pripada BF-u.
Tablica operacija u modulo-2 aritmetici:
			Zbrajanje:
				0 + 0 = 0
				0 + 1 = 1 + 0 = 1
				1 + 1 = 0 (2 mod 2 = 0)

			Oduzimanje:
				0 - 0 = 0
				1 - 0 = 1
				1 - 1 = 0

			Množenje:
				0 * 0 = 0
				0 * 1 = 0
				1 * 1 = 1

			Dijeljenje:
				0 / 1 = 0
				1 / 1 = 0
Iz ovoga se može vidjeti da su ustvari operacije zbrajanja i oduzimanja jednake te da se mogu zamijeniti binarnom operacijom XOR(exkluzivni-ili), a da se operacija množenja može zamijeniti binarnom operacijom &(I, AND).

2.3 Polinomi s binarnim koeficijentima ili binarni polinomi

Binarni polinomi imaju koeficijente iz binarnog polja BF. Primjer binarnog polinoma:

1x4+0x3+0x2+1x1+1x0

Ovaj polinom se može prikazati kao binarni broj:
10011

Da je ovaj prikaz dobar može nam poslužiti primjer zbrajanja i množenja dva binarna polinoma:

(1x2+1x1+0x0) + (0x2+1x1+1x0) = 1x2+0x1+1x0

(1x2+1x1+0x0) * (0x2+1x1+1x0) = 0x2+1x1+0x0

Prikažimo sada te polinome kao binarne brojeve i izvršimo nad njima operaciju XOR kao zamjena za zbrajanje i operaciju &(I,AND) kao zamjena za množenje:

110 Å 011 = 101

110 & 011 = 010

Vidimo da su koeficijenti u oba načina prikazivanja jednaki te da se binarni polinom može prikazati kao binarni broj.
Polinomi se inače prikazuju bez koeficijanata 1 i 0 tako da su u zapisu polinoma imamo samo one potencije x-a koje kao koeficijent imaju 1, dok se koeficijenti sa 0 ne prikazuju. Takav zapis bio bi prikazan na sljedeći način:

x8+x5+x4+x2+x0

Taj zapis jednak je:

100110101

Iz ovih razmatranja slijedi da se svaki binarni podatak može prikazati kao polinom sa binarnim koeficijentima ili binarni polinom.

2.4 Opis rada algoritma

Algoritam CRC-32 uzima podatak iz kojeg računa sažetak te ga pretvara u binarni polinom(MP(x)) te dijeli taj polinom sa definiranim binarnim polinom zvanim ključ(KP(x)). Ostatak dijeljenja tih polinoma (MP(x) i KP(x)) daje kvocijent(Q(x)) i ostatak(R(x)). Ostatak tog dijeljenja je sažetak(H) dobiven algoritmom CRC-32. Može se pisati:

MP(x) / KP(x) = Q(x) + R(x)
R(x)=H

Pošto CRC-32 ima 32-bitni sažetak(H) iz toga slijedi da ostatak(R) mora biti 32-bitni broj. Ako želimo da imamo ostatak stupnja d tada djeljitelj mora biti stupnja d+1.
Sažetak kod CRC-32 ima stupanj 31 i iz toga slijedi da ključ(KP) mora imati stupanj 32.
Ključ koji se najčešće koristi kod CRC-32 možemo u hexadecimalnom zapisu prikazati kao:

KP=0x4C11DB7

Kao binarni polinom ključ ima sljedeći oblik:

KP(x) = x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x1 + x0

Dakle CRC-32 zahtijeva dijeljenje binarnog polinoma poruke MP(x) i ključa KP(x). Ova dva polinoma ne možemo direktno podijeliti jer u registre procesora stane najviše 32 bita dok poruka može biti duljine milijuna bitova, a čak i ključ ne stane u registar jer je on duljine 33 bita. Vidi se da treba neki algoritam kojim će se podijeliti ova dva broja. Kod dijeljenja nam nije važan kvocijent dijeljenja već samo ostatak koji čini sažetak(hash), te se kvocijent neće računati.

Opis algoritma za dijeljenje:
Krećemo sa krajnje lijevim koeficijentom binarnog polinoma MP(x)(poruka), koeficijent sa najvećom potencijom. Ako je taj koeficijent nula idemo na sljedeći koeficijent, pomaknemo se u desno. Ako je taj koeficijent jedan uzmemo sljedećih n bitova gdje je n duljina djeljitelja ili ključa i oduzmemo ih po modulo-2 aritmetici. Oduzimanje je jednako XOR operaciji u modulo-2 aritmetici. Sada se opet pomaknemo za jedno mjesto u desno provodimo isti postupak do kraja poruke.
Za primjer rada algoritma podijelit ćemo dva binarna polinoma:

P1(x) = x5 + x2 + x1

P2(x) = x2 + x0

Ta dva polinoma u binarnom zapisu su:

P1 = 100110

P2 = 101

Dobivanje ostatka iz ova dva binarna broja:

				10011000 / 101
				101|||||
				---|||||
				  111|||
				  101|||
				  ---|||
				   100||
				   101||
				   ---||
				     100
				     101
				     ---
				      01
Ostatak u ovom slučaju je 01. Iz ovoga primjera vidimo da se krajnje lijevi bit polinoma P2(x) ne mora zapisivati jer je on uvijek jedan. Tako se ni krajnje desni bit ključa ne zapisuje pa tako pamtimo samo 32 bita, a ne 33 koja ne stanu u registar.
Sada će opet biti prikazano gornje dijeljenje, ali tako da će biti podebljani bitovi polinoma P1 koji su u registru tijekom dobivanja ostatka, a podcrtani će biti oni bitovi polinoma P2 koji su također u registru. 
				      	0010011000 / 101
					001|||||||
					 010||||||
					  100|||||
					  101|||||
					  ---|||||
					  001|||||
					   011||||
					    111|||
					    101|||
					    ---|||
					    010|||
					     100||
					     101||
					     ---||
					     001||
					      010|
					       100
					       101
					       ---
					       001

Ovaj način dobivanja sažetka poruke je dosta spor jer se radi bit po bit. Iz tog razloga napravljena je optimizirana verzija CRC-32 algoritma. Ta verzija ne radi sa bitovima već sa byteovima. Za ovu verziju moramo već imati izračunatu tablicu za sve kombinacije 8-bitnog broja tj. tablicu sa 256 elemenata. Nakon što imamo tablicu možemo računati sažetak.
Sažetak računamo tako da izvadimo posljednji byte(najmanje značajni byte) iz registra i XOR-amo ga sa ulaznim sljedećim byteom poruke. Tu vrijednost koristimo kao index elementa u tablici iz koje dobavljamo pospremljenu vrijednost operacije te tu vrijednost XOR-amo sa prijašnjom vrijednošću registra pomaknutom za jedan byte(8 bitova) u desno.

Algoritam za računanje CRC-32 preko tablice:

					crc32(ulaz[], duljina_poruke){
						hash = 0
						za( i = 0; i < duljina_poruke; i++){
							izlazni_byte = hash & 0xff
							hash = crc32_tablica[ulaz[i] XOR izlazni_byte] XOR (hash >> 8)
						}
						vrati hash;
					}
Tablica za ključ 0x4C11DB7:

 					00h   00000000 77073096 EE0E612C 990951BA
					04h   076DC419 706AF48F E963A535 9E6495A3
 					08h   0EDB8832 79DCB8A4 E0D5E91E 97D2D988
					0Ch   09B64C2B 7EB17CBD E7B82D07 90BF1D91

					10h   1DB71064 6AB020F2 F3B97148 84BE41DE
					14h   1ADAD47D 6DDDE4EB F4D4B551 83D385C7
 					18h   136C9856 646BA8C0 FD62F97A 8A65C9EC
					1Ch   14015C4F 63066CD9 FA0F3D63 8D080DF5

  					20h   3B6E20C8 4C69105E D56041E4 A2677172
  					24h   3C03E4D1 4B04D447 D20D85FD A50AB56B
 					28h   35B5A8FA 42B2986C DBBBC9D6 ACBCF940
					2Ch   32D86CE3 45DF5C75 DCD60DCF ABD13D59

 					30h   26D930AC 51DE003A C8D75180 BFD06116
  					34h   21B4F4B5 56B3C423 CFBA9599 B8BDA50F
  					38h   2802B89E 5F058808 C60CD9B2 B10BE924
					3Ch   2F6F7C87 58684C11 C1611DAB B6662D3D

  					40h   76DC4190 01DB7106 98D220BC EFD5102A
  					44h   71B18589 06B6B51F 9FBFE4A5 E8B8D433
  					48h   7807C9A2 0F00F934 9609A88E E10E9818
					4Ch   7F6A0DBB 086D3D2D 91646C97 E6635C01
	
  					50h   6B6B51F4 1C6C6162 856530D8 F262004E
 					54h   6C0695ED 1B01A57B 8208F4C1 F50FC457
  					58h   65B0D9C6 12B7E950 8BBEB8EA FCB9887C
					5Ch   62DD1DDF 15DA2D49 8CD37CF3 FBD44C65

  					60h   4DB26158 3AB551CE A3BC0074 D4BB30E2
  					64h   4ADFA541 3DD895D7 A4D1C46D D3D6F4FB
 					68h   4369E96A 346ED9FC AD678846 DA60B8D0
					6Ch   44042D73 33031DE5 AA0A4C5F DD0D7CC9

					70h   5005713C 270241AA BE0B1010 C90C2086
  					74h   5768B525 206F85B3 B966D409 CE61E49F
  					78h   5EDEF90E 29D9C998 B0D09822 C7D7A8B4
					7Ch   59B33D17 2EB40D81 B7BD5C3B C0BA6CAD

  					80h   EDB88320 9ABFB3B6 03B6E20C 74B1D29A
  					84h   EAD54739 9DD277AF 04DB2615 73DC1683
  					88h   E3630B12 94643B84 0D6D6A3E 7A6A5AA8
					8Ch   E40ECF0B 9309FF9D 0A00AE27 7D079EB1

  					90h   F00F9344 8708A3D2 1E01F268 6906C2FE
  					94h   F762575D 806567CB 196C3671 6E6B06E7
  					98h   FED41B76 89D32BE0 10DA7A5A 67DD4ACC
					9Ch   F9B9DF6F 8EBEEFF9 17B7BE43 60B08ED5

  					A0h   D6D6A3E8 A1D1937E 38D8C2C4 4FDFF252
  					A4h   D1BB67F1 A6BC5767 3FB506DD 48B2364B
  					A8h   D80D2BDA AF0A1B4C 36034AF6 41047A60
					ACh   DF60EFC3 A867DF55 316E8EEF 4669BE79

  					B0h   CB61B38C BC66831A 256FD2A0 5268E236
  					B4h   CC0C7795 BB0B4703 220216B9 5505262F
  					B8h   C5BA3BBE B2BD0B28 2BB45A92 5CB36A04
					BCh   C2D7FFA7 B5D0CF31 2CD99E8B 5BDEAE1D

					C0h   9B64C2B0 EC63F226 756AA39C 026D930A
  					C4h   9C0906A9 EB0E363F 72076785 05005713
  					C8h   95BF4A82 E2B87A14 7BB12BAE 0CB61B38
					CCh   92D28E9B E5D5BE0D 7CDCEFB7 0BDBDF21
					
 					D0h   86D3D2D4 F1D4E242 68DDB3F8 1FDA836E
  					D4h   81BE16CD F6B9265B 6FB077E1 18B74777
  					D8h   88085AE6 FF0F6A70 66063BCA 11010B5C
					DCh   8F659EFF F862AE69 616BFFD3 166CCF45

 					E0h   A00AE278 D70DD2EE 4E048354 3903B3C2
  					E4h   A7672661 D06016F7 4969474D 3E6E77DB
 					E8h   AED16A4A D9D65ADC 40DF0B66 37D83BF0
					ECh   A9BCAE53 DEBB9EC5 47B2CF7F 30B5FFE9

  					F0h   BDBDF21C CABAC28A 53B39330 24B4A3A6
  					F4h   BAD03605 CDD70693 54DE5729 23D967BF
					F8h   B3667A2E C4614AB8 5D681B02 2A6F2B94
  					FCh   B40BBE37 C30C8EA1 5A05DF1B 2D02EF8D

3. Literatura

WEB LINKOVI:

www.thecodeproject.com/csharp/crc32_dotnet.asp

www.vbaccelerator.com/home/NET/Code/Libraries/CRC32/article.asp

www.relisoft.com/Science/CrcMath.html

www2.rad.com/networks/1994/err_con/crc_how.htm

biw.rult.at/tuts/crctut1.htm?PHPSESSID=8b57624320d1292d1a10813ad8d2b7b8

www.nsrl.nist.gov/documents/hash-selection.doc

POČETAK