________________________________________________________________________________
Inhalt....: Diffie-Hellman-Algorithmus
Kategorie.: Arbeitsblatt
Mathematik: Kryptographie, Zahlentheorie
MuPAD.....: 3.0.0
Datum.....: 2003-06-23
Autoren...: Julia Faflek <faflek@mupad.de>
Funktionen: nextprime, ithprime, factor, numlib::primroot, numlib::order,
Funktionen: powermod, igcd, random, plot::Point2d
________________________________________________________________________________
Schlüsselerzeugung mittels des Diffie-Hellman-
Algorithmus
Zum Ver- und Entschlüsseln von Daten braucht man Schlüssel. Mit dem hier vorgestellten
Algorithmus werden Schlüssel auf sicherem Wege generiert, um später z.B. ein sym-
metrisches Kryptosystem zu verwenden.
Wir wollen einen gemeinsamen Schlüssel mit einer anderen Person ver-
einbaren. Dazu legen wir zunächst eine Primzahl p fest und eine Basis g
aller Elemente aus Z_p, die ungleich 0 sind. Die Ordnung dieser Gruppe
ist p-1 und ein Element erzeugt die Gruppe, wenn dessen Ordnung p-1 ist.
p := nextprime(10)
Das Problem, dass sich nun stellt ist: Wie finden wir einen Erzeuger dieser
Gruppe? Falls p klein genug ist, findet man das gewünschte Element x fol-
genderweise:
Man wählt ein zufälliges x und überprüft, ob die Ordnung von x nicht (p-1)/q
teilt für jeden Primfaktor q von p-1, indem man x mit (p-1)/q potenziert. Das
Ergebnis muss immer ungleich 1 sein.
factor(p-1)
Wir versuchen es mit der 3:
powermod(3, (p-1)/2, p);
powermod(3, (p-1)/5, p)
3 ist also kein erzeugendes Element. Zur Veranschaulichung lassen wir
alle Potenzen von 3 ausgeben:
powermod(3, i, p) $ i = 1..p
Die Ordnung von 3 modulo p ist also 5. Man überprüft:
numlib::order(3, p)
Es ist also nicht so einfach ein erzeugendes Element zu finden. MuPAD
bietet mit der Funktion numlib::primroot ein Hilfsmittel an:
numlib::primroot(p)
Dieser Befehl liefert uns das kleinste Element mit Ordnung p-1:
numlib::order(2, p)
Wir können aber auch ein anderes Element wählen, eins das größer ist
als 2:
numlib::primroot(3, p)
numlib::order(6, p)
Es gibt also meistens mehrere Kandidaten für den Erzeuger.
Wenn aber p zu groß ist, dann versagt unsere bisherige Vorgehensweise.
Denn in der Praxis ist p-1 so groß, dass das Faktorisieren von p-1 schwer
ist. In diesem Fall muss man sich damit zufrieden geben, ein Element mit
großer Ordnung zu bekommen. Wir sammeln also zunächst alle kleinen
Primfaktoren von p-1 und dividieren p-1 durch diese. Übrig bleibt ein großer
Faktor von p-1. Nun wird jedes Element x ^(Produkt entfernter Primfaktoren)
mit großer Wahrscheinlichkeit eine Ordnung haben, die den großen Faktor
teilt. Als erstes bilden wir das Produkt der ersten n Primzahlen:
kleinePrim := proc(n)
begin
_mult(ithprime(i) $ i = 1..n)
end_proc:
kleinePrim(10) = factor(kleinePrim(10))
Mittels des ggT entfernen wir nun alle kleinen Primfaktoren von p-1 und
lassen uns den übrig gebliebenen großen Faktor sowie das Produkt der
entfernten Primfaktoren zurückgeben:
entferneFaktoren := proc(p, n)
local grFaktor, gemFaktor, ProdFaktoren;
begin
grFaktor := p-1:
gemFaktor := igcd(kleinePrim(n), grFaktor):
while (gemFaktor > 1) do
grFaktor := grFaktor/gemFaktor:
gemFaktor := igcd(kleinePrim(n), grFaktor):
end_while:
ProdFaktoren := (p-1)/grFaktor:
return(grFaktor, ProdFaktoren):
end_proc:
Wir erzeugen eine große Primzahl:
p := nextprime(random(2^500..2^550)());
Nun wenden wir die obige Prozedur an und berechnen einen Erzeuger von der
Form x^(Produkt entfernter Faktoren), wobei x beliebig gewählt wird:
Ergebnis := entferneFaktoren(p,100)
x := random(1..p)();
g := powermod(x, Ergebnis[2], p)
Wir überprüfen, ob g die gewünschte Ordnung hat:
powermod(g, Ergebnis[1], p)
Nun haben wir alles zur Hand um mit dem eigentlichen Protokoll zu beginnen:
1) p und g sind jeder Partei bekannt
2) Wir wählen einen geheimen Schlüssel a < p-1
a := random(1..p-1)()
3) Wir berechnen Alpha und schicken dies an die andere Partei
Alpha := powermod(g, a, p)
4) Von der anderen Partei erhalten wir ein Beta, das auf die gleiche Weise
sserzeugt wurde
b := random(1..p-1)()
Beta := powermod(g, b, p)
5) Nun berechnen wir mit der Exponentialfunktion einen gemeinsamen Schlüssel
ssk wie folgt:
k1 := powermod(Beta, a, p)
6) Die andere Partei geht wie folgt vor:
k2 := powermod(Alpha, b, p)
Schon hier sehen wir, dass beide Parteien wirklich gleiche Schlüssel erzeugt
haben. Warum ist das so? Wir erinnern uns daran wie Beta erzeugt wurde:
Mit einfachen Rechenregeln folgt:
Nun wissen wir:
Die Frage ist, wie geheim ist denn der geheime Schlüssel? Kann ein Angreifer
den geheimen Schlüssel berechnen? Kann dieser bei Kenntnis von Alpha bzw.
Beta den Wert von a bzw. b herausfinden? Dazu müsste der Angreifer den
diskreten Logarithmus von Alpha bzw. Beta zur Basis g berechnen. Dies ist
glücklicherweise nicht leicht möglich bei großen Zahlen. Die Sicherheit dieses
Protokolls basiert also auf der Eigenschaft, dass die diskrete Exponentialfunkt-
ion eine Einwegfunktion ist, d.h. leicht zu berechnen, aber schwer zu invertieren.
Um dies zu verdeutlichen schauen wir uns die Funktionswerte von g^x mod p an.
Dazu wählen wir ein nicht zu großes p und einen Erzeuger g:
p := nextprime(random(1000..2000)());
g := numlib::primroot(p)
Nun wollen wir das ganze visualisieren:
plot(plot::Point2d(i, powermod(g, i, p)) $ i = 1..p)
In dieser Grafik können wir keinerlei Muster erkennen. Es scheint als würde
sich die diskrete Exponentialfunktion zufällig verhalten. Dies macht es be-
sonders schwer auf das Urbild zurück zu schließen.
_____________________________________________________________________________________
Übungen:
1. Machen Sie sich mit den Funktionen numlib::order und numlib::primroot vertraut. Besuchen Sie
ssdazu die Hilfeseiten ?numlib::order und ?numlib::primroot.
_____________________________________________________________________________________
Anmerkungen:
1. Weitere Anregungen finden Sie unter: http://schule.mupad.de bzw. http://studium.mupad.de
_____________________________________________________________________________________