_________________________________________________________________________________
Inhalt....: Einführung in das RSA-Krypto-Verfahren
Kategorie.: Unterrichtsmaterial
Mathematik: Kryptographie, Zahlentheorie
MuPAD.....: 3.0.0
Datum.....: 2002-06-10
Autoren...: Annamaria Pelles <pellesa@freemail.hu>
Autoren...: Kai Gehrs <acrowley@mupad.de>
Funktionen: random, isprime, float, igcd, igcdex, mod, powermod, factor,
Funktionen: nextprime, time
_________________________________________________________________________________
Einführung in das RSA-Krypto-Verfahren
RSA ist derzeit quasi der weltweite Standard für public-key-Verfahren.
Wir werden sehen wie RSA für die zwei wesentlichen Aufgaben der Kryptographie benutzt werden
kann. Hierbei handelt es sich um die
1. Verschlüsselung von Nachrichten
2. Entschlüsselung von Nachrichten
Dieses Notebook präsentiert stellenweise mathematische Sachverhalte, die über den Rahmen
dessen, was man in der Schule behandelt hinausgehen. Diese komplizierteren Sachverhalte
kann man jedoch getrost überlesen, wenn man sich nur dafür interessiert, wie mit Hilfe des
RSA-Verfahrens Botschaften ver- oder entschlüsselt werden. Darüber hinaus kann dieses
Notebook eventuell als Anreiz für eine eventuelle Facharbeit verwendet werden.
Wozu dient das RSA-Krypto-Verfahren?
Wir erklären das Verfahren an einem Beispiel: Bob möchte an Alice eine
Nachricht M senden, ohne dass eine dritte Person, wir nennen sie Eve, diese
Nachricht lesen kann, obwohl Eve unbeschränkten Zugang zum Kommunikations-
kanal zwischen Alice und Bob hat.
Die Lösung besteht darin die Nachricht M zu verschlüsseln. Das Verfahren kann
man sich grafisch wie folgt vorstellen:
Kanal
Bob -----> Verschlüsselung --------------> Entschlüsselung -----> Alice
Wie funktioniert dieses Verfahren im Detail?
Bob möchte also an Alice eine Nachricht senden, so dass nur Alice diese
Nachricht lesen kann, und niemand anderes.
Aus diesem Grund erzeugt Alice einen sogenannten private key S (privater
Schlüssel) und einen public key K (öffentlicher Schlüssel). Jeder kann K lesen,
aber S ist ein Geheimnis.
Auch Bob kennt nur K. Wenn nun Bob eine Nachricht an Alice schickt, muß er zur
Verschlüsselung K verwenden: Bei Empfang der Nachricht kann Alice mit ihrem
privaten Schlüssel die Nachricht entschlüsseln.
Die Nachricht kann aus Texten, Bildern, Dateien oder Programfiles etc. bestehen;
die Nachricht soll aber immer in der oben genannten Form verschlüsselt werden.
Im folgenden werden wir Schritt für Schritt das Verfahren der Verschlüsselung
(damit niemand anderer die Nachricht lesen kann) und der Entschlüsselung
an einem Beispiel verstehen lernen.
Schritt (1): Alice wählt zufällig zwei Primzahlen p und q.
Zur Erinnerung: Eine Primzahl ist eine positive ganze Zahl, die nur durch 1 und sich
selbst (ganzzahlig) teilbar ist.
Zum Beispiel ist 25 keine Primzahl, denn 5 * 5 ist 25 und damit 5 ein Teiler von 25.
Dagegen ist 7 eine Primzahl, denn 2,3,4,5 und 6 sind keine Teiler von 7.
Mit MuPAD können wir Zufallszahlen mit Hilfe der Funktion random() erzeugen.
Zufall:= random(1..500)
Eine Zufallszahl wird nun immer aus der Menge {1,2,3,...,499,500} gewählt:
p:= Zufall()
Wie können wir nun schnell herausfinden, ob die erzeugte Zufallszahl eine Primzahl
ist?
Die MuPAD Funktion isprime testet, ob p eine Primzahl ist oder nicht, d.h.
isprime(p) liefert true, wenn p eine Primzahl ist, und false, wenn p eine
zusammengesetzte Zahl ist.
Wenn p keine Primzahl ist, dann müssen wir das obige Verfahren nochmals
wiederholen, bis wir mit p eine Primzahl gefunden haben.
isprime(p)
Eine Möglichkeit besteht nun darin, die obige Befehlszeile p:= Zufall()
so lange auszuführen, bis p eine Primzahl eine Primzahl ist.
Wir verfahren also wie folgt:
p:= Zufall():
while isprime(p) = FALSE do
p:= Zufall();
end_while:
p;
Dieses Verfahren scheint nicht sehr elegant zu sein, aber es führt nach kurzer
Zeit zum Ziel, denn der sogenannte Primzahlsatz der Zahlentheorie besagt,
dass in einem vorgegebenen Intervall stets hinreichend "viele" Primzahlen
vorhanden sind.
Primzahlsatz. Ist x eine positive Zahl und bezeichnet p(x) die Anzahl der
Primzahlen, die kleiner oder gleich x sind, so gilt:
Was bedeutet dies nun in unserem Beispiel? In unserer Situation gilt x = 500.
Also gilt:
hold(PI(x)) = float(500/ln(500))
Es gibt also näherungsweise 80 Primzahlen in der Menge {1,2,3,...,499,500},
d.h. wiederum, dass die Wahrscheinlichkeit, dass eine gewählte Zufallszahl eine
Primzahl ist, beträgt näherungsweise
float(80/500)
d.h. 16%. Dies bedeutet, dass wir innerhalb von 10 Versuchen in der Regel
mindestens eine Primzahl finden werden.
Nun zurück zu Bob und Alice: Jetzt muss Alice nach der gleichen Methode die
zweite Primzahl q wählen.
q:= Zufall():
while isprime(q) = FALSE do
q:= Zufall();
end_while:
q;
Schon haben wir p und q gefunden, nämlich
p,q
Schritt (2): Alice muss N und Phi(N) berechnen, wobei N = p*q und Phi(N) wie
folgt erklärt ist:
Für eine natürliche Zahl k ist Phi(k) definiert als die Anzahl der zu k
teilerfremden Zahlen (dazu gehört auch die 1), die kleiner sind als k.
Zum Beispiel ist Phi(6) = 2, denn nur 1 und 5 sind kleiner als 6 und teilerfremd
zu 6. Andererseits ist Phi(7) = 6, denn alle Zahlen 1,2,3,4,5 und 6 sind teilerfremd
zu 7.
Allgemein gelten die folgenden Rechenregeln für die Eulersche Phi-Funktion.
Rechenregeln für die Eulersche Phi Funktion:
Phi(1) = 1
Phi(p) = p-1, wenn p eine Primzahl ist.
Phi(p*q) = (p - 1) * (q - 1), wenn p und q Primzahlen sind.
Wir werden im folgenden nur die dritte Regel benutzen. Wer die Eulersche
Phi-Funktion nicht kennt, kann sich daher für alles folgende merken:
Phi(N) ist stets das Produkt (p - 1) * (q - 1).
N:=p*q; Phi_N:= (p-1)*(q-1)
Schritt(3): Alice berechnet ihren öffentlichen Exponenten e auf folgende
Weise: Sie wählt e zufällig und teilerfremd zu Phi(N).
Zufall:= random(2..Phi_N-2)
e:= Zufall()
In MuPAD berechnet igcd (integer greatest common divisor) den größten
gemeinsamen Teiler zweier Zahlen.
Um zu prüfen, ob e und Phi(N) tatsächlich teilerfremd sind, berechnen wir
einfach ihren größten gemeinsamen Teiler. Ist dieser 1, so haben wir
ein passendes e gefunden. Ist dieser größer oder gleich 2, so wählen wir
ein neues e. Auch dieses Verfahren liefert beweisbar innerhalb kurzer Zeit
einen passenden Wert für e.
igcd(e,Phi_N)
Schritt(4): Alice berechnet ihren privaten Exponenten d als Inverses von e
modulo Phi(N).
Das modulare Inverse berechnet man mit Hilfe des Euklidischen Algorithmus.
Für zwei Zahlen a und m liefert der Euklidische Algorithmus nicht nur den
größten gemeinsamen Teiler g, sondern auch Zahlen k und l, so dass gilt:
g = k * a + l * m
Reduziert man diese Gleichung modulo m (d.h. man rechnet auf beiden
Seiten modulo m - man nimmt also einfach den Rest, der bei ganzzahliger
Division der Zahlen durch m verbleibt), so ergibt sich wegen m modulo m = 0:
g modulo m = (k * a) modulo m
Ist nun g = 1, also der größte gemeinsame Teiler von a und m ist 1, so folgt:
1 modulo m = (k * a) modulo m
d.h. k ist das modulare Inverse zu a (denn k * a ist 1 modulo m).
In unserer Situation setzen wir für m die Zahl Phi(N) ein und für a die Zahl e.
Die Zahl k wird dann Alices privater Exponent, d.h. k = d.
Mit der MuPAD Funktion igcdex kann man die Werte g, k und l des Euklidischen
Algorithmus berechnen.
igcdex(e,Phi_N)
dd:= igcdex(e,Phi_N)[2]
Da Alices privater Schlüssel d eine positive Zahl sein muss, müssen wir zu dem
Wert dd einmal Phi(N) addieren, falls dd negativ ist. Andernfalls können wir
dd als Wert für d wählen. Dies hört sich jetzt unglaublich kompliziert an, aber
wir müssen alle Fälle berücksichtigen, denn wir haben e ja als zufälligen Wert
gewählt.
if dd < 0 then
d:= dd + Phi_N;
else
d:= dd;
end_if:
print(Unquoted, "d = ".d);
d = 60227
d.h. es gilt
1 = (d * e) modulo Phi(N)
Wir können das Ergebnis überprüfen:
(d * e) mod Phi_N
Schritt(5): Alice veröffentlicht das Paar (N,e) (öffentlicher Schlüssel) und behält
(N,d) als Geheimnis (geheimer Schlüssel). Schauen wir uns die bisher
berechneten Werte einmal an:
N,e
N,d
Schritt (6): Alice löscht p, q und Phi(N) vom Computer - sie benötigt diese Zahlen
nicht mehr. Sie sollte sie auch löschen, damit diese Eve nicht auf ihrem Computer
finden kann.
Jetzt möchte Bob an Alice eine Nachricht senden; was muß er jetzt tun?
Schritt(7): Bob möchte Alice zum Beispiel eine Zahl x senden, x soll zwischen
1 und N sein, also z.B. x = 13
Bob soll x zu einem y verschlüsseln. y ist x^e mod N. Bob berechnet also die
Zahl y und sendet sie an Alice. Auf diese Weise hat er x zu y verschlüsselt.
Die folgenden Rechnungen benötigen durchaus etwas mehr Zeit. Man
möge sich gedulden. Wir werden uns später damit beschäftigen, warum
diese Rechnung so zeitintensiv ist und wie wir sie effizienter durchführen
können.
x:= 13
y:=(x^e) mod N
Schritt(8): Alice berechnet den Wert xx mit Hilfe ihres eigenen geheimen
Exponenten d. Dazu bestimmt sie y^d modulo N (dass dieses Verfahren
bei korrekter Anwendung immer funktioniert und wieder den ursprünglichen
Wert von x liefert, kann man mit Mitteln aus der Zahlentheorie beweisen,
die allerdings den Rahmen dieses Notebooks sprengen).
xx:= (y^d) mod N
Probe: Ist x gleich xx?
x = xx
Das Verfahren hat also funktioniert: Bob konnte seine Nachricht an Alice
schicken, Alice konnte mit Hilfe ihres eigenen Geheimschlüssels die
Nachricht entschlüsseln.
Folgende Fragen sind nun offensichtlich:
(1) Warum sollte Eve das Geheimnis nicht entschüsseln können,
wo sie doch N kennt?
(2) Warum benötigen die letzten Rechnungen so viel Zeit?
(3) Kann man das Suchen von Primzahlen mit MuPAD nicht
noch geschickter machen?
Zu Frage (1): Eve könnte bei Kenntnis von N versuchen, die Zahl in ihre Faktoren
p und q zerlegen. Mit Hilfe von p und q könnte Eve Phi(N) = (p-1) * (q-1) berechnen.
Da sie auch e kennt (e wurde von Alice veröffentlicht) könnte sie genau wie Alice
den Wert von d bestimmen (über den Euklidischen Algorithmus, wie wir es oben
für Alice getan haben). Wenn Eve d kennt, so kann Eve die Nachricht von Bob
auch genauso leicht entschlüsseln wie Alice.
Wo könnte es Probleme für Eve geben? Eves großes Problem ist es, N zu
faktorieren, d.h. die Zahlen p und q zu finden. In der Realität wird man N als
Produkt zweier riesig großer Primzahlen wählen, so dass die Faktorisierung
von N viel zu lange dauert.
Man kann zeigen, dass alle anderen Operationen auch bei sehr großem N
immer noch schnell genug durchgeführt werden können (z.B. der Euklidische
Algorithmus zur Berechnung des modularen Inversen funktioniert auch bei
großen Zahlen sehr schnell).
leicht Kanal leicht
Bob -------> Verschlüsselung -------> Entschlüsselung -------> Alice
Ein Beispiel:
NN:= 112589990654654760673 * 112589990654654760791;
Die Zahl N kann man in MuPAD mit dem Befehl factor in ihre Faktoren zerlegen:
Wir kennen das Ergebnis bereits, denn oben stehen die beiden Primfaktoren von
N. Wie lange benötigt MuPAD nun ungefähr für die Faktorisierung? Wir testen dies...
(man kann die Faktorisierung per Mausklick auf das Abbruchsymbol - roter Kreis
mit weißem Kreuz in der obigen Befehlsleiste - vorzeitig abbrechen)
time( factor(NN) )
time(igcdex(NN, 112589990654654760673))
Wie man sieht: Die Berechnung des Euklidischen Algorithmus geht schnell,
die Faktorisierung dagegen nicht.
Fazit: Wenn Eve p und q nicht kennt, so hat sie für große N keine Chance, die
Werte von p und q in angemessener Zeit zu berechnen. Dies zeigt die Sicherheit
des Verfahrens für hinreichend große Werte von p, q und N.
Zu Frage (2): Das Potenzieren x^d ist nicht kostengünstig und ungeschickt,
weil erst potenziert und danach erst modulo N gerechnet wird.
Besser ist es, nach jeder berechneten Potenz zunächst wieder modulo N
zu reduzieren, da dann die Zahlen viel kleiner sind. Wie wir unten sehen,
dauern die Berechnungen von oben, die mehrere Sekunden in Anspruch
genommen hatten, nur noch Sekundenbruchteile:
xx:= powermod(y, d, N)
Dabei berechnet powermod(y, d, N) nichts anderes als y^d modulo N.
Diesmal allerdings auf die etwas geschicktere, oben angedeutete Weise.
Auch das modulare Inverse läßt sich leichter berechnen. Wir wissen,
dass d das modulare Inverse zu e modulo Phi(N) ist. Mit MuPAD können
wir dies auch unter Verzicht auf die Funktion igcd
direkt berechnen:
d:= e^-1 mod Phi_N
Die Probe zeigt auch dieses Mail wie oben, dass das Ergebnis korrekt ist:
d * e mod Phi_N
Zu Frage (3): Das Finden von Primzahlen kann mit Hilfe der Funktion
nextprime verbessert werden. Diese Funktion liefert zu einer gegebenen
Zahl die nächst größere Primzahl. Damit ist das Auffinden einer
zufälligen Primzahl aus der Menge {1,2,...,999,1000} ganz einfach:
Zuerst wählen wir eine Zufallszahl a
a:= Zufall()
Dann setzen wir p auf den Wert
pp:= nextprime(a)
Dann ist pp sicherlich eine Primzahl und wir sind fertig.
In der Praxis, wo man mit riesig großen Zahlen rechnet, wird man aber
dennoch nicht nextprime benutzen, sondern eher, wie oben, Zufalls-
zahlen erzeugen und testen, ob diese Primzahlen sind. Dieses Verfahren
ist, so unglaublich es klingen mag, schneller.
Eine weitere Anwendung: Natürlich möchten Alice und Bob nicht nur
Zahlen aneinander verschicken. Man kann z.B. folgende Vereinbarung treffen:
- Die Buchstaben des Alphabets werden mit 1 bis 26 durchnumeriert.
- Wörter werden durch 27 getrennt oder separat verschickt.
Eine Codierung des Worter "Hallo" wäre also gegeben durch
8 01 12 12 15
Stellen wir uns vor, wir wären Alice und Bob hätte uns die folgende
Nachricht geschickt:
Unser privater Schlüssel ist:
d:=155731;
p:=271; q:=977;
N:=p*q;
Wir entschüsseln die Nachricht sukzessiv wie oben:
x1:= powermod(143723, d, N);
x2:= powermod(28057, d, N);
x3:= powermod(165879, d, N);
x4:= powermod(34978, d, N);
x5:= powermod(169363, d, N);
x6:= powermod(152576, d, N);
x7:= powermod(22350, d, N);
x8:= powermod(169363, d, N);
x9:= powermod(164850, d, N);
Die übersandten Werte sind also
Dabei ist die Zahl 27 als Trennung zwischen zwei Wörtern zu lesen.
Die Zahlen 13 und 25 entsprechen den Buchstaben M und Y. Die Zahlen
19, 5, 3, 18, 5 und 20 entsprechen den Buchstaben S, E, C, R, E und T.
Damit lautet die entschlüsselte Botschaft "My Secret" (mein Geheimnis).
_______________________________________________________________________________
Anmerkungen:
1. Weitere Anregungen finden Sie in der Buchreihe Mathematik 1 x anders. In dieser Reihe
wird eine Vielzahl unterschiedlichster mathematischer Probleme mit MuPAD gelöst. Die
Bücher können unter www.schule.mupad.de/literatur kostenfrei kopiert werden.
_______________________________________________________________________________