www.jammni.de

Gepostet:
17.07.2006 16:56

Haskell Hash-Funktionen

In dieser Aufgabe sollen Sie Analysefunktionen für Hash-Funktionen implementieren, die wünschenswerte Eigenschaften
einer Hash-Funktion überprüfen. Die Schlüssel der Hashfunktion sollen vom Datentyp Integer sein. Als Bild soll
eine endliche Integer-Teilmenge dienen.

a) Besonders wichtig im Fall von kryptographischen Hashfunktionen ist das Avalanche-Kriterium: Es besagt, dass
durch Kippen eines Bits in der Eingabe im Mittel die Hälfte der Ausgabe-Bits verändert wird. Implementieren
Sie eine Funktion avalanche, die eine Statistik über die gekippten Ausgabe-Bits ausgibt.

b) Interessant ist auch die Verteilung der Kollisionen. Diese sollten möglichst gleichverteilt über der Zielmenge sein.
Schreiben Sie eine Funktion collusion, die eine Statistik über die Positionen der Kollisionen ausgibt.

c) Überlegen Sie sich eine Hash-Funktion h, die sich möglichst vorteilhaft gemäß der beiden Kriterien verhält.

d) Das wichtigste Kriterium für eine kryptographische Hash-Funktion ist, dass sich Kollisionen nur schwer berechnen
lassen. Wie ist das bei Ihrer Funktion?

Kann mir wer helfen? wie fange ich da am besten an?

Zum Seitenanfang

Jacke

Gepostet:
17.07.2006 21:25

also als erstes würde ich mir ne hashfunktion schreiben

z.b. auch ein sehr einfaches beispiel ...;-)


myhash x= x `mod` 10

und hier mal ne ganz einfachvariante von collision die alle mit myhash errechneten werte in eine liste wirft


liste=[1..100]
collision []=[]
collision (x:xs) =  (myhash x):(collision xs)

eine möglichkeit wäre hier einfach einen zähler zu erhöhen wenn das element bereits einmal vorkam

z.b.
if (myhash x) `elem` list then (count+1)

oder einfach die ergebnisliste von collision durchlaufen und alle doppelten zählen

für die sache mit den kippen von bits hatte ich dir ja schonmal einige binärfunktionen geschrieben du weißt schon inttobin und bintoint...erinnerst du dich?
das könnte dir ja eigentlich schon helfen...
und d ist ja nur ne textaufgabe...
gruß jacke

Zum Seitenanfang

blizz

Gepostet:
18.07.2006 22:34

also ich steh aufm schlauch, ich bekomm nichts hin :(

Zum Seitenanfang

Jacke

Gepostet:
18.07.2006 23:27

habt ihr ein paar tipps bekommen? wenn ja erzähl mal...für diese beiden funktionen(avalance und colliosion) müßte es formeln geben oder?

Zum Seitenanfang

blizz

Gepostet:
20.07.2006 13:52

keine ahnung, ich hab nichts im script oder so gefunden
wir bekommen für haskell allgemein sehr sehr wenige informationen

Zum Seitenanfang

Jacke

Gepostet:
21.07.2006 15:33

myhash x= x `mod` 10

liste=[1..100]
collision []=[]
collision (x:xs) =  (myhash x):(collision xs)

toBinary 0 = [0]
toBinary x = toBinary t ++ [x `mod` 2]
	     where t = x `div` 2

toint [] = 0
toint (x:xs)
                |(x==1)  =( 2^( length (xs) ) )   +(toint xs)
                | otherwise = 0+ (toint xs)


avalance zahl= diff (toBinary(myhash(toint((((head(toBinary zahl))+1)`mod`2) : (tail(toBinary zahl)))))) (toBinary(myhash zahl))

diff [] [] = []
diff  s [] = s++[]
diff [] s  = s++[]
diff (z1:z1s) (z2:z2s) = ((z1+z2)`mod` 2): (diff z1s z2s)

so also noch ein wenig erklärung dazu ...
avalance ruft die funktion diff auf...
diff gibt die differenz zwischen zwei Binärzahlen zurück...deshalb die tobinary funktion
diff wir mit der dem um eins geänderten bit aufgerufen:
also das hier:
(toBinary(myhash(toint((((head(toBinary zahl))+1)`mod`2) : (tail(toBinary zahl))))))(toint((((head(toBinary zahl))+1)`mod`2) : (tail(toBinary zahl))))
myhash ist wird hier nochmal aufgerufen weil die ausgabewerte der hashfunktion verglichen werden sollen

der zweite wert der der diff-funktion übergeben wurde ist der normale wert den die hashfunktion zurrückgibt...also ohne verschobenes bit

avalance 3
[0,0,0,1]<---nur eine 1 also 1 bit
besagt das sich nur ein bit geändert hat...das zeigt wie schlecht meine hashfunktion ist...

gruß jacke

Zum Seitenanfang

Haskell-Forum