- Home
- /
- 02 – Kryptologie
- /
- 02.03 – Kryptographie
- /
- 02.03.02 – asymmetrische Verfahren
Das Manko der symmetrischen Verfahren liegt darin, dass der benötigte Schlüssel geheim bleiben muss, aber der berechtigte Empfänger der Nachricht ihn dennoch haben muss. Dies erfordert einen geheimen Transport des Schlüssels. Ferner ist eine geheime Kommunikation mit jedem einzelnen einer größeren Anzahl von Teilnehmern dadurch erschwert, dass eine Vielzahl von Schlüsseln erforderlich wäre. Bei drei Teilnehmern wären es noch (3*2)/2=3 Schlüssel (A-B, A-C, B-C); bei 10 Teilnehmern aber sind dies schon (10*9)/2=45 Schlüssel.
Dieses Problem umgehen asymmetrische Verfahren, auch Public-Key-Verfahren genannt. Hierbei hat jeder Teilnehmer ein Schlüsselpaar bestehend aus einen geheimen und einen öffentlichen Schlüssel. Letzterer kann und soll frei an alle Kommunikationsteilnehmer verteilt werden, daher öffentlich. Die Verschlüsselung des Klartextes erfolgt mit dem öffentlichen Schlüssel des Empfängers. Die Nachricht kann nur mit dem geheimen Schlüssel entschlüsselt werden.
Die Sicherheit dieser Verfahren basiert im Grunde auf der Tatsache, dass es im Moment als unmöglich gilt, in absehbarer Zeit das Produkt zweier sehr großer Primzahlen ohne Kenntnisse dieser wieder zu zerlegen, zu faktorisieren. In anderen Fällen basiert die Sicherheit darauf, dass es zur Zeit als unmöglich gilt,, in absehbarer Zeit den diskreten Logarithmus einer Zahl zu ermitteln, die aus dem Potenzieren zweier großer Zahlen entstanden ist (ElGamal, Diffie/Hellman). Mit anderen Worten: es ist einfach zwei große Zahlen miteinander zu multiplizieren oder zu potenzieren, aber es ist sehr schwierig, den Weg wieder zurück zu gehen.
Diese Verfahren gelten heute als sicher, aber eine Grundregel der Kryptologie sagt, dass kein Code unbrechbar ist! Bei den asymmetrischen Verfahren steht und fällt die Sicherheit mit den Fortschritten der Mathematik bzw. der Leistungszunahme in der Rechentechnik.
Die nachfolgenden Abschnitte geben einen Überblick über bekannte asymmetrische Verfahren.
Asymmetrische Verfahren: RSA
RSA
wurde 1977 von Ron Rivest, Adi Shamir und Leonard Adleman entwickelt.
Das Verfahren verwendet große Primzahlen; seine Sicherheit basiert auf
der Schwierigkeit, große Zahlen zu faktorisieren. Das Verfahren ist
einfach zu verstehen und ebenso leicht in Applikationen zu
implementieren [Schneier].
RSA wurde intensiv der Kryptanalyse unterzogen, die zwar das Verfahren
nicht brechen konnte, allerdings auch keinen Beweis für die Sicherheit
liefern konnte. Schneier beschreibt in seinem Buch verschiedene
Angriffspunkte, kommt aber mehrfach zu der Auffassung „…Ich würde mir
keine Sorgen machen…“. Diese Aussage gilt unter der Prämisse, dass
seine Schlußfolgerungen aus den Angriffsbetrachtungen bei der
Implementierung berücksichtigt werden.
Die folgenden Zeilen sollen darstellen, wie simpel und doch zugleich
effektiv der RSA-Algorithmus funktioniert, der neben den Algorithmen
ElGamal und Diffie-Hellmann in verschiedenster Software zum Einsatz
kommt. Diese Darstellung basiert auf der Veröffentlichung: The
Mathematical Guts of RSA Encryption und „Angewandte Kryptographie“. Sie
richtet sich nicht an den Mathematiker unter den Lesern, sondern an den
einfachen Anwender von PGP, GnuPG oder S/MIME. Die durchzuführenden
Schritte wurden nur mit einem Minimum an mathematischen Formeln
beschrieben. Für das Beispiel wurden bewusst kleine und einfache Zahlen
verwendet, die natürlich für die Realität keineswegs hinreichend sind.
1. Schritt
Wir
benötigen zwei sehr große Primzahlen; für die reale Verschlüsselung
sollten die Primzahlen 1024 bit groß sein, also 100 oder mehr Ziffern
haben. Wir begnügen uns mit
P=3 und Q=5
In PGP sollen P und Q so gewählt werden, dass das Produkt PQ mehr als 300 Stellen hat.
2. Schritt
Nun sollen wir eine Zahl E finden, die folgende Bedingungen erfüllen muss:
E muss kleiner als der Wert sein, der sich ergibt, wenn man P und Q miteinander multipliziert (Produkt aus P und Q)
E darf keine gemeinsamen Faktoren mit dem Produkt (P-1)(Q-1) haben
E braucht keine Primzahl zu sein, muss aber ungerade sein
Das Produkt (P-1)(Q-1) ist übrigens zwangsläufig gerade. Das Produkt PQ
nennen wir N, den Modulus. Er wird so in einigen Veröffentlichungen
genannt. N sollte etwa doppelt soviele Ziffern wie die Primfaktoren P
und Q haben.
PQ=15 daraus folgt für (P-1)(Q-1)=8
Eine Primfaktorenzerlegung zeigt für 8 die Faktoren 2*2*2. E darf also
keine 2 als Teiler haben, was ja ohnehin gegeben ist, da E ungerade sein
soll. Der für unser Beispiel einfachste Wert wäre die 3; also E=3.
3. Schritt
Der
Algorithmus schreibt nun vor, dass wir noch eine Zahl D bestimmen.
Diese muss die Bedingung erfüllen, dass das um Eins verminderte Produkt
aus D und E, (DE-1), ohne Rest durch (P-1)(Q-1) teilbar ist oder mehr
mathematisch beschrieben:
DE=1 mod ((P-1)(Q-1))
und nicht gleich dem Wert von E sein soll.
Anmerkung: Die Zeile ist wie folgt zu lesen: DE wird durch ((P-1)(Q-1)) so geteilt, dass Rest 1 bleibt.
Wie macht man das? Nun, eigentlich ganz einfach: man muss nur eine
ganzzahlige Zahl X finden, die dafür sorgt, dass die folgende Gleichung
ein ganzzahliges Ergebnis liefert:
D= (X(P-1)(Q-1)+1)/E
Eine derartige Gleichung nennt man diophantische Gleichung, die in
unserem vorliegenden Fall exakt lösbar ist. Im Rahmen dieser
Beschreibung will ich aber aus Gründen der einfachen Darstellung nicht
auf den Lösungsweg eingehen. Zur Vertiefung dient daher folgende Seite:
Diophantische Gleichungen bei den Vordenkern
In unserem einfachen Fall kann X=4 gewählt werden, dann wird D zu
D=(4*2*4+1)/3=33/3=11.
Damit gilt für DE=33. Die Probe ist 33/8=4 Rest 1.
Fassen wir mal unsere einzelnen Zahlen zusammen:
P=3
Q=5
N=15
D=11
E=3
Die Zahlen N (oder PQ) und E bilden den Public Key. Die Zahlen N (oder
PQ) und D bilden den Secret Key. Dies erklärt auch die Zusatzforderung,
dass E und D nicht den gleichen Wert haben sollten, da sonst Public und
Secret Key gleich wären. Sind diese Zahlen einmal berechnet, so müssen
alle Hilfsgrößen wie P, Q, (P-1)(Q-1) und X gelöscht werden.
Verschlüsselung
Die Rechenvorschrift für die Verschlüsselung lautet:
C=K^E mod N
C steht für Ciphertext
K steht für Klartext
E und N sind der Public Key des Empfängers.
Die Zeile sagt lediglich: Potenziere den Klartext mit E, teile das durch
N und gib den Rest als Ciphertext aus. Nehmen wir mal an, wir wollen
folgende Zahlenreihe verschlüsseln:
12130508.
Die einzelnen zu verschlüsselnden Elemente müssen in Stücke zerlegt werden, die kleiner als N sind:
12 13 05 08
Die Ciphertexte wären demnach:
123= 1728 | 1728/15 = 115 Rest 03 |
133= 2197 | 2197/15 = 146 Rest 07 |
053= 125 | 125/15 = 8 Rest 05 |
083= 512 | 512/15 = 34 Rest 02 |
Das Ergebnis ist dann:
03 07 05 02
Entschlüsselung
Die Rechenvorschrift für die Entschlüsselung lautet:
K=C^D mod PQ
C steht für Ciphertext
K steht für Klartext
D und N sind der Secret Key des Empfängers
Die Mathematik ist exakt die gleiche wie bei der Verschlüsselung. Rechnen wir mal den Ciphertext zurück:
03 07 05 02
0311= 177147 | 177147/15= 11809 Rest 12 |
0711= 1977326743 | 1977326743/15= 131821782 Rest 13 |
0511= 48828125 | 48828125/15= 3255208 Rest 05 |
0211=2048 | 2048/15=136 Rest 08 |
Das
sehr einfach gewählte Beispiel führt zu sehr kleinen zu
verschlüsselnden Textelementen. Der entstandene Code ließe sich
vermutlich schnell brechen. Es ist allerdings nicht Aufgabe dieses
Beispiels gewesen, die Unbrechbarkeit des Codes zu beweisen, sondern
vielmehr die Vorgehensweise und den Algorithmus verständlich zu
erläutern.
Anmerkung: In einigen Veröffentlichungen wird beschrieben, die Stärke
des RSA-Algorithmus basiere auf der Tatsache, dass es schwierig sei,
große Primzahlen zu faktorisieren. Dies ist ein Schreibfehler, denn
Primzahlen allgemein, groß oder klein, haben nur zwei Faktoren 😉
Gemeint ist, dass es schwierig ist, große Zahlen zu faktorisieren und
der Modulus (PQ) ist eine solche große Zahl.
Asymmetrische Verfahren: Diffie/Hellmann
In der Tat eignet sich das 1976 beschriebene Verfahren nicht zur Ver- und Entschlüsselung, sondern vielmehr zum Austausch von Schlüsseln über „unsichere“ Kanäle. Seine Sicherheit basiert wie ElGamal auf der Problematik, dass es keine eindeutigen, sicheren mathematischen Verfahren gibt, den diskreten Logarithmus zu berechnen, es aber umgekehrt sehr einfach ist, eine Zahl zu potenzieren.
Die Darstellung ist wie üblich möglichst kurz und einfach gehalten und richtet sich nicht an Mathematiker oder Krypto-Experten.
1. Schritt
Alice
und Bob möchten miteinander verschlüsselt kommunizieren. Dazu möchten
sie gern die Schlüssel für den Verschlüsselungsvorgang miteinander
austauschen. Leider besteht keine gesicherte Verbindung zwischen beiden
und ein persönliches Treffen als sicherste Alternative ist nicht
möglich. Also wählen sie folgende Vorgehensweise:
Zunächst denkt sich einer von beiden eine möglichst große Primzahl P
sowie eine Zahl z aus. Für diese muss gelten, dass sie kleiner als P
ist. (Tatsächlich gibt es noch eine weitere Einschränkung, die wir aber
hier vernachlässigen; bei weiterem Interesse sei auf die oben genannte
Literatur verwiesen).
Diese Daten werden offen an den anderen Partner gesendet.
2. Schritt
Nun denkt sich jeder der beiden eine geheime Zahl aus; Alice nimmt a und Bob nimmt b.
Nun berechnet jeder:
Alice | Bob |
X=za mod P | Y=zb mod P |
Die Werte X und Y werden wie auch z und P miteinander ausgetauscht. Die Werte a und b dagegen sind die geheimen Schlüssel.
Jeder der beiden berechnet daraus den Schlüssel:
Alice | Bob |
KA=Ya mod P | KB=Xb mod P |
Damit erhalten beide den gleichen Wert, denn es gilt:
(zb mod P)a mod P = (za mod P)b mod P = z(ab) mod P
Beispiel
Alice denkt sich für P=11 und für z=4 aus. Dieses teilt sie Bob mit. Außerdem hat sie sich für a den Wert 3 ausgedacht, während Bob seinen geheimen Schlüssel auf den Wert 5 gesetzt hat.
Alice | Bob | ||
X | = 43 mod 11 | Y | = 45 mod 11 |
= 64 mod 11 | = 1024 mod 11 | ||
= 5 Rest 9 | = 93 Rest 1 |
Alice teilt Bob noch den Wert für X mit (9) und Bob den Wert für Y (1).
Nun kann jeder seinen Schlüssel berechnen:
Alice | Bob | ||
KA | = 13 mod 11 | KB | = 95 mod 11 |
= 1 mod 11 | = 59049 mod 11 | ||
= 0 Rest 1 | = 5368 Rest 1 |
Dieses Beispiel ist natürlich sehr vereinfacht und trivial gehalten. Es soll lediglich die Vorgehensweise und die Funktion von Diffie-Hellmann beschreiben. Aus diesem Zweck wurden unrealistisch kleine Werte eingesetzt und ggf. vorgegebene Restriktionen (s. weiter oben) nicht beachtet.
Anmerkung
Diffie
und Hellmann gelten zusammen mit Merkle aufgrund ihrer
Veröffentlichungen in 1976 als Entdecker der Public-Key-Verfahren. In
jüngerer Zeit wurde aber bekannt, dass nur wenige Zeit zuvor drei andere
Wissenschaftler ein nahezu identisches Verfahren entdeckt hatten, es
aber nicht veröffentlichen durften.
Aufgrund sehr hoher Kosten bei der Schlüsselverteilung hatte das
britische Militär dem Government Communication Headquarter (GCHQ) schon
in den 60er Jahren den Auftrag erteilt, andere Wege zu finden. Die von
James Ellis und Clifford Cocks geäußerten Ideen ähnelten denen von
Diffie und Hellmann, nur etwa sechs Jahre früher. Diese Ideen wurden
zusammen mit Williamson 1975 vervollständigt und entsprachen dem nur ein
Jahr später vorgestellten Diffie/Hellmann/Merkle-Verfahren. Das GCHQ
hat einerseits aus Gründen der Geheimhaltung und andererseits wegen des
für die Briten aus Sicht der frühen 70er Jahre fraglichen Nutzens nie
ein Patent beantragt. Im Dezember 1997 wurde dieser Sachverhalt bekannt.
James Ellis starb einen Monat zuvor und reiht sich in die Liste
britischer Kryptologen wie Babbage und Turing ein, denen öffentlicher
Ruhm zu Lebzeiten aus Gründen der Geheimhaltung vorenthalten blieb.
Asymmetrische Verfahren: ElGamal
In PGP, GnuPG und in S/MIME wird für die Verschlüsselung des Sitzungsschlüssels ein asymmetrisches Verfahren gewählt. Neben RSA ist hier Diffie-Hellmann und ElGamal vorgesehen .
In diesem Kapitel soll die grundlegende Funktionsweise und der Vorgang für das Verfahren nach ElGamal beschrieben werden. Die Darstellung richtet sich nicht an Mathematiker und Kryptospezialisten, sondern an einfache, interessierte Anwender von Krypto-Software.
Das Verfahren wurde 1985 von ElGamal veröffentlicht. Es eignet sich sowohl zur Verschlüsselung als auch für digitale Signaturen. Seine Sicherheit beruht auf der Schwierigkeit, diskrete Logarithmen zu bestimmen. Das heißt, es ist einfach eine Zahl mit einer anderen zu potenzieren (y=ab), aber zur Zeit ist kein mathematisches Verfahren bekannt, diesen Prozess ohne Kenntnis von b korrekt umzukehren, ohne raten zu müssen.
1. Schritt
Zunächst benötigen wir eine große Primzahl Z. Sicherheitshalber sollte diese Zahl um Eins verringert und dann halbiert (Z-1)/2 ebenfalls prim sein. Je nach Schlüssellänge ist diese Zahl viele Bit lang, in unserem Falle soll ihr Wert aber nur 11 betragen.
2. Schritt
Wir benötigen zwei weitere beliebige Zahlen y und g, die größer als Eins, aber kleiner als die Zahl Z sein müssen. Nehmen wir für unser Beispiel y=2 und g=3. Aus diesen Werten, zusammen mit Z, bilden wir:
p=yg mod Z
Also y wird mit g potenziert, durch Z geteilt und der Rest wird als p weiterverwertet. p, y und Z sind öffentlich und werden auch im öffentlichen Schlüssel verwendet. g dagegen ist geheim und darf nie veröffentlicht werden.
Betrachten wir das Ergebnis in unserem Beispiel:
p | = 23 mod 11 |
= 8/11 | |
= 0 Rest 8 | |
p | = 8 |
Damit hätten wir bis jetzt: Z = 11 p = 8 y = 2 g = 3
Verschlüsselung
Die Klartextnachricht soll lauten: 05070810
Die zu verschlüsselnde
Nachricht muss einen Wert aufweisen, der kleiner als Z ist, sonst muss
er in Teile zerlegt werden. Für unser Beispiel gilt daher für die
Nachricht:
05 07 08 10
Der Absender benötigt noch eine zufällige Zahl x, die größer Eins, aber kleiner Z-1 sein muss und keinen gemeinsamen Teiler mit Z haben soll. Wir nehmen den Wert x=5 an. Der Absender erzeugt zunächst mal die Hilfsgröße c1:
c1= yx mod Z
und außerdem für jeden zu verschlüsselnden Klartextteil
c2=(k px) mod Z mit k= Klartextteil.
In unserem Beispiel wäre c1 damit
c1 | = 25 mod 11 |
= 32/11 | |
= 2 Rest 10 | |
c1 | = 10 |
und für c2 ergäbe sich mit k=05
c2 | = (5*85) mod 11 |
= 163840/11 | |
= 14894 Rest 6 | |
usw. |
k | c2 |
05 | 06 |
07 | 04 |
08 | 03 |
10 | 01 |
Die chiffrierte Nachricht lautet 06 04 03 01
Zusätzlich wird der Wert c1=10 übermittelt.
Entschlüsselung
Der Empfänger weiß nichts von der Hilfszahl x, benötigt diese aber für die Rückrechnung auch nicht. Für die Entschlüsselung gilt
k= (c2 c1(Z-1-g)) mod Z
Im ersten Teil der Nachricht 06 ergibt dies:
k | = (6*10(11-1-3)) mod 11 |
= (6*107) mod 11 | |
= 6*10000000/11 | |
= 5454545 Rest 5 |
c2 | k |
06 | 05 |
04 | 07 |
03 | 08 |
01 | 10 |
Die Darstellung zeigt, dass ähnlich wie bei RSA der Vorgang sehr simpel
und die Mathematik nicht schwierig ist (sieht man mal vom Umgang mit
sehr großen Zahlen ab). Sie ist bewusst sehr einfach gewählt und hat,
dem besseren Verständnis dienend, unrealistisch kleine Werte verwendet.