Hashfunktion

En hashfunktion er en særlig funktion, som bruges til at omdanne data fra normalt en stor definitionsmængde til en mindre billedmængde, for eksempel en vilkårlig tekst til et heltal mellem 0 og en bestemt maksimal værdi. Hashfunktioner bruges bl.a. i hashtabeller og inden for kryptologi. En god hashfunktion vil fordele sine resultater så ligeligt som muligt inden for billedmængden, og dermed have så få kollisioner som muligt. Det kaldes en kollision når to forskellige inddata giver den samme funktionsværdi.

Dataintegritet

Hashfunktioner kan bruges i forbindelse med og lagermedier til at kontrollere om data er blevet forvansket (enten ved fejl i transmissionen eller en tredieparts mellemkomst) ved foruden de originale data også at sende/gemme resultatet af en hashfunktion. Til dette formål er det vigtigt at bruge en hashfunktion som ikke giver kollisioner ved små ændringer af inddata, idet det vil nedsætte sandsynligheden for at opdage forvanskninger af data.

En af de simpleste hashfunktioner til dette er en checksum, hvor man lægger f.eks. ASCII-værdierne for de enkelte bytes sammen modulo 256. Det ses umiddelbart at det er meget let at lave en kollision for denne hashfunktion, idet to bytes blot skal ændres med lige meget i hver sin retning for at opnå den samme checksum. Man kan gange tegnværdierne med forskellige tal, så det ikke er nok, at bytte om på to tilfældige tegn.

En mere avanceret, og meget udbredt hashfunktion til dette er CRC (cyclic redundancy check). CRC-32 anvendes (bl.a.) af Ethernet, , Zip-formatet og PNG-formatet. CRC er god til at opdage tilfældige ændringer i data, men da det er nemt bevidst at konstruere kollisioner, er den ikke velegnet til at sikre mod bevidste ændringer af data. Til dette anvendes i stedet kryptografiske hashfunktioner.

Kryptografi

Kryptografiske hashfunktioner har til formål at danne et "fingeraftryk" af en bid information (), f.eks. en tekst eller en datafil. Resultatet kaldes en hash eller et digitalt fingeraftryk (eng. message digest eller fingerprint). Hashen kan være af vilkårlig længde, men er typisk på mellem 32 og 256 bits. Hashfunktioner kan bl.a. bruges til digitale signaturer samt at verificere integriteten af information.

En af de vigtigste egenskaber for en kryptografisk hashfunktion er at den kollisionsfri, dvs. at det er "svært" (dvs. meget beregningstungt) at finde en anden klartekst med samme hash. Ideelt set skal det eneste angreb være et brute force-angreb, dvs. et hvor man prøver sig frem indtil man finder en kollision. Hvis hash'en består af ${\displaystyle n}$ bits, er der ${\displaystyle 2^{n}}$ mulige fingeraftryk, og et brute force angreb vil i gennemsnit kræve ${\displaystyle {\sqrt {2^{n}}}=2^{n/2}}$ beregninger af hashfunktionen.

Populære kryptografiske hashfunktioner er MD4 (der bl.a. anvendes af EDonkey fildelingssystemet), MD5 og SHA (SHA-0, SHA-1, SHA-2). Der er publiceret angreb på alle disse algoritmer pånær SHA-2.

Hashtabeller

Der bruges en hashfunktion i hashtabeller. En hashtabel er en datastruktur, hvor man hurtigt kan finde data ud fra en nøgle. Nøglen behandles med en hashfunktion, og resultatet bruges som indeks til selve opslaget.

En meget udbredt hashfunktion er i denne sammenhæng h(nøgle) = nøgle modulo N, hvor N er antallet af rækker i tabellen. En anden type hashfunktioner 'folder' nøglen. Foldning går ud på, at man deler nøglen op i bidder og derefter lægger de nye tal sammen. Hvad der er mest effektivt er meget afhængigt af de aktuelle data.

Det kan ske, at to eller flere nøgler giver den samme hashværdi. Data skal så placeres et andet sted, som regel i nærmeste efterfølgende ledige position. Rutinen, der skal finde en nøgle, skal derfor kunne søge fremefter, hvis dette er tilfældet. Hashtabellen skal også have en del ledige positioner, for at dette kan fungere.

Se også

• Digitalt fingeraftryk
• Kryptosystem
• Kryptologi