________________________________________________________________________________
Inhalt....: ElGamal-Algorithmus
Kategorie.: Arbeitsblatt
Mathematik: Kryptographie, Zahlentheorie
MuPAD.....: 3.0.0
Datum.....: 2003-06-23
Autoren...: Julia Faflek <faflek@mupad.de>
Funktionen: ithprime, nextprime, igcd, random, powermod,
Funktionen: numlib::toAscii, numlib::fromAscii
________________________________________________________________________________
Der ElGamal-Algorithmus zur Nachrichten-
verschlüsselung und zur Erstellung digitaler
Unterschriften
Der ElGamal-Algorithmus zur Verschlüsselung ist eine Variation des Diffie-Hellman-
Algorithmus. Dieser wird eingehend in dem Notebook "DiffieHellman.mnb", welches
unter www.schule.mupad.de/material zum Download zur Verfügung steht, untersucht.
Die Mathematik, die dem Verfahren unterliegt, ist die im wesentlichen die gleiche wie
beim Diffie-Hellman-Algorithmus. Daher wird auf weitere zahlentheoretische Hinter-
gründe im Rahmen dieses Arbeitsblattes nicht eingegangen.
Wie bei dem Diffie-Hellman-Algorithmus benötigen wir zunächst wieder
eine möglichst große Primzahl p und eine Basis g aller Elemente aus Z_p,
die ungleich 0 sind. Zur Erzeugung dieser Basis benutzen wir die Prozedur
aus dem Notebook "Diffie-Hellman.mnb". Zunächst die Prozedur, die das
Produkt der ersten n Primzahlen berechnet.
kleinePrim := proc(n)
begin
_mult(ithprime(i) $ i = 1..n)
end_proc:
Dann die Berechnung des Produkts der entfernten Primfaktoren und des
übrig gebliebenen großen Teilers:
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:
Abschließend die Erzeugung einer Basis g:
Basis := proc(p, n)
local Ergebnis, x, g, test;
begin
Ergebnis := entferneFaktoren(p, n):
x := random(1..p)():
g := powermod(x, Ergebnis[2], p):
test := powermod(g, Ergebnis[1], p):
while (test > 1) do
Ergebnis := entferneFaktoren(p,n):
x := random(1..p)():
g := powermod(x, Ergebnis[2], p):
test := powermod(g, Ergebnis[1], p):
end_while:
return(g)
end_proc:
Wir wählen also eine zufällige große Primzahl:
p := nextprime(2^300)
und erzeugen die Basis:
g := Basis(p, 300)
Nun können wir mit der Verschlüsselung beginnen. Dazu muss jeder Teil-
nehmer seinen öffentlichen Schlüssel veröffentlichen. Als erstes wählt jede
Partei eine zufällige Zahl zwischen 1 und p-1. Dies ist der geheime
Schlüssel:
geheim1 := random(1..p-1)()
Mittels der diskreten Exponentialfunktion wird nun der öffentliche Schlüssel
berechnet:
oeff1 := powermod(g, geheim1, p)
Wir veröffentlichen unseren öffentlichen Schlüssel, damit jeder, der uns
eine Nachricht schicken möchte, weiß, mit welchen Parametern er ver-
schlüsseln muss.
Die Partei mit der wir kommunizieren wollen erzeugt ihre Schlüssel auf
gleiche Weise:
geheim2 := random(1..p-1)()
oeff2 := powermod(g, geheim2, p)
Nun können wir mit dem Ver- und Entschlüsseln beginnen. Stellen wir uns
vor, die andere Partei möchte uns folgende Nachricht zu kommen lassen:
Nachricht := "Hallo! Bist du auch ein MuPAD-Nutzer?".
"Kryptografie macht wirklich Spass.".
"Bin ja mal gespannt, ob du das entschluesseln kannst."
Nun muss der andere erst einmal aus dem Text Zahlen machen. Dazu wird
der Textstring einfach in das ASCII-Format umgewandelt:
Umwandlung := numlib::toAscii(Nachricht)
Er sucht sich unseren öffentlichen Schlüssel heraus und benutzt zusätzlich
seinen geheimen Schlüssel, um die nun vorliegende Liste von Zahlen zu
verschlüsseln. Dabei wird jede Zahl der Liste einzeln in folgender Weise
verschlüsselt:
Verschluesselung := [(Umwandlung[i] *
powermod(oeff1, geheim2, p) mod p)
$ i = 1..nops(Umwandlung)]:
Diese Verschlüsselung bekommen wir nun zugeschickt. Aber wie kommen
wir nun an den Klartext heran? Dazu müssen wir die Zahlenliste erst einmal
entschlüsseln. Wir benutzen unseren geheimen und den öffentlichen Schlüs-
sel der anderen Partei und machen die Verschlüsselung folgenderweise rück-
gängig:
Entschluesselung := [(Verschluesselung[i] *
powermod(oeff2, p-1-geheim1, p) mod p)
$ i = 1..nops(Verschluesselung)]
Das sieht doch schon aus wie eine Liste im ASCII-Format! Wir müssen sie
lediglich noch in einen Textstring zurückwandeln:
numlib::fromAscii(Entschluesselung)
Toll! Es hat alles geklappt! Aber warum? Sei N die Klartext Nachricht, V die
Verschlüsselung und E die Entschlüsselung. Wir müssen zeigen, dass
E = N gilt. Im Weiteren gelten alle Gleichungen modulo p. Erinnern wir uns
an die Entschlüsselung:
Nun ersetzen wir V durch die entsprechende Verschlüsselungsvorschrift:
und ersetzen die öffentlichen Schlüssel durch ihre Erzeugung. Durch einige
Umformungen ergibt sich:
Durch Wegkürzen folgt:
und das ist:
Der kleine Fermatsche Satz besagt:
Für eine Primzahl p und alle x ungleich 0 aus Z_p gilt:
Damit folgt sofort:
Damit ist bewiesen, dass das Protokoll korrekt arbeitet.
Wir haben nun schon gesehen, wie der ElGamal-Algorithmus zum Ver-
schlüsseln benutzt wird. Als nächstes setzen wir die Methode von ElGamal
als Signaturverfahren ein.
Zunächst einiges über digitale Unterschriften:
Ziel der Signaturverfahren ist es, sowohl den Absender einer Nachricht ein-
deutig zu identifizieren als auch Veränderungen an einer Nachricht belegen
zu können. Denken wir nur einmal an die üblichen E-Mails. Dort kann z.B.
vor Weiterleiten einer Mail der Inhalt unbemerkt verändert werden. Ebenso
können Absenderadressen gefälscht werden. Digitale Unterschriften verhin-
dern diesen Missbrauch.
Die Funktionsweise einer digitalen Signatur lässt sich mit einem durchsichtigem
Safe vergleichen. Durch das Signieren wird das Dokument in den Tresor gelegt,
der dann verschlossen wird. Nur der Besitzer kann den Safe öffnen. Aber jeder
Teilnehmer kann durch den Glastresor das Dokument einsehen und verifizieren,
dass es dem Besitzer gehört.
Wir überlegen nun, wie wir dies mit der ElGamal-Methode umsetzen können.
Stellen wir uns vor, wir wollen die Nachricht von oben signieren. Wir behalten
alle Parameter und Schlüssel bei. Zunächst müssen wir eine zu p-1 teiler-
fremde Zahl r wählen, damit r invertierbar modulo p-1 ist:
r := random(1..p-1)();
while (igcd(r, p-1) > 1) do
r := random(1..p-1)()
end_while:
r
Wir berechnen eine Zahl k mittels der diskreten Exponentialfunktion:
k := powermod(g, r, p)
Jetzt müssen wir folgende Kongruenz lösen:
Wir formen nach s um:
Nun wird klar, warum r invertierbar sein musste. Wir berechnen also zunächst
das Inverse von r:
invr := powermod(r, -1, p-1)
und berechnen s für jede Zahl in der Liste der umgewandelten Nachricht:
s := [0 $ nops(Umwandlung)]:
for i from 1 to nops(Umwandlung) do
s[i] := (Umwandlung[i] - geheim1*k) * invr mod p-1
end_for:
s:
Die digitale Unterschrift ist das Paar (k, s). Wir schicken nun die umge-
wandelte Nachricht und die Unterschrift an die andere Partei.
Diese muss nun durch einige Rechnungen die Echtheit der Unterschrift
verifizieren. Dazu muss überprüft werden, ob folgende Gleichheit gilt:
Wenn dies zutrifft, kann der Andere sicher sein, dass die Unterschrift von
uns stammt. Also berechnet er:
Erg1 := [powermod(g, Umwandlung[i], p)
$ i = 1..nops(Umwandlung)]:
Erg2 := [(powermod(oeff1, k, p) * powermod(k, s[i], p)
mod p) $ i = 1..nops(s)]:
Nun überprüft er jeden Eintrag der Liste folgenderweise:
if(nops(Erg1) - nops(Erg2)=0) then
Pruefe := [0 $ nops(Erg1)]:
for i from 1 to nops(Erg1) do
Pruefe[i] := is(Erg1[i] = Erg2[i])
end_for:
else
error("Listen nicht gleich lang")
end_if:
Pruefe
Da alle Einträge TRUE lauten, weiß die andere Partei genau, dass auch
wirklich wir es waren, die diese Nachricht geschickt haben. Wir überlegen
noch kurz, warum das ganze funktioniert. Auch hier gelten alle Gleichungen
modulo p. Für oeff1 und k setzen wir deren Erzeugungen ein:
Nun folgt:
Wir erinnern uns an die Kongruenz:
Damit ergibt sich doch für eine natürliche Zahl x:
Jetzt können wir einsetzen
und mit dem kleinen Fermatschen Satz folgt die gewünschte Gleichheit:
_____________________________________________________________________________________
Übungen:
1. Machen Sie sich mit den Funktionen numlib::toAscii und numlib::fromAscii vertraut. Besuchen
ssSie dazu die Hilfeseiten ?numlib::toAscii und ?numlib::fromAscii.
2. Erzeugen Sie eine größere Primzahl, berechnen Sie die Basis und verschlüsseln Sie beliebige Textnachrichten.
_____________________________________________________________________________________
Anmerkungen:
1. Weitere Anregungen finden Sie unter: http://schule.mupad.de bzw. http://studium.mupad.de
_____________________________________________________________________________________