Kryptographie URL
haftendorn.uni-lueneburg.de/mathe-lehramt/krypto/krypto.htm
[Kryptographie]  [Algebra]  [MuPAD]   © Prof. Dr. Dörte Haftendorn
Download des MuPAD-Notebooks     Save Link Taget As..., Verküpfung speichern unter...
Kryptographie, Hash-Funktion
Mathematik mit MuPAD 2, Prof. Dr. Dörte Haftendorn 1.12.02 Version vom 1.12.02
#################################################################################
Eine Hash-Funktion ist ein Einweg-Funktion, die die Nachricht komprimiert. Sie wird im Zusammenhang mit der digitalen Signatur gebraucht.
Foderungen an eine Hashfunktion:
Sie soll möglichst kollisionsresistent sein.
Schwache Kollisionsresistenz liegt vor, wenn das Verändern einer Nachricht so gut wie immer zu einem veränderten Hashwert führt.
Starke Kollisionsresistenz liegt vor, wenn das Konstruieren einer Nachricht mit gleichem Hashwert mindestens so schwierig ist, wie den diskreten Logarithmus modolo p zu bestimmen. #################################################################################

Unten erst das Von - Hand- Beispiel durchführen !!!!!!!!!!!!!!!!!!!!!!!!!!!!!! Zunächst muss ein Paar von Primzahlen p und q bestimmt werden,
die p=2 q+1 erfüllen.
   

   
   

Eine Primitivwurzel a von p ist zu bestimmen.
d. h. <a>=zstern(p). Bei der oben erzeugten Konstellation hat zstern die Ordnung p-1=2q.
Damit kommt als Ordnung der Elemente von zstern(p) nur 2 oder q oder p-1 infrage
Wenn also modulo p weder a^2=1 noch a^q=1 gilt, dann erzeugt a zstern(p), ist also Primitivwurzel.
Der Sinn ist, dass die hash-Funktion, die ja a^x enthält, alle Werte aus zstern(p) annehmen kann.
   

   

   

   

Schon die Änderung nur einer Ziffer ergibt einen völlig anderen Hashwert. Von Hand- Hashfunktion
   

   
   

Wenn hier eine 1 steht, Neuwahl von a < p. Nun erzeugt a wirklich zstern(p), Probe dazu:
   

   

Wahl von b aus zstern(p) beliebig Nachricht, aufgeteilt in zwei Blöcke
   
   
   

Die letzte Zahl ist der Hashwert der Nachricht. Überlegungen zur Kollisionsfreiheit
Will man den 1. Teil der Nachrricht manipulieren, also auch 3 als hashwert erhalten,
so sieht man an der folgenden Zeile, dass es keinen anderen Wert für x gibt, der auch 8 erzeugt.
Das liegt daran dass a Primitivwurzel ist.
   

   

Ändert man den ersten und den zweiten Teil der Nachrricht, so kann man 8 erzeugen, in jeder Zeile
kommt 8 genau einmal vor. Z.B. x=4, y=7. Eine solche Kombination ist aber bei großem p nicht zu finden.
   

[Kryptographie]  [Algebra]  [MuPAD]   
Inhalt und Webbetreuung ©Prof. Dr. Dörte Haftendorn 2001, hier neu 2005, update 17. September 2005
Direkte Internetadressen [www.doerte-haftendorn.de]
[haftendorn.uni-lueneburg.de/mathe-lehramt]    [haftendorn.uni-lueneburg.de/ing-math]