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=a^b), 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=y^g 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 c₁:

c₁= y^x mod Z

und außerdem für jeden zu verschlüsselnden Klartextteil

c₂=(k p^x) mod Z mit k= Klartextteil.

In unserem Beispiel wäre c₁ damit

c1	= 25 mod 11
	= 32/11
	= 2 Rest 10
c1	= 10

und für c₂ 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 c₁=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= (c₂ c₁^(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.

weiter zur Kryptanalyse