Asymmetrische Kryptografie (Verschlüsselung)

In der asymmetrischen Kryptografie arbeitet man nicht mit einem einzigen Schlüssel, sondern mit einem Schlüsselpaar. Bestehend aus einem öffentlichen und einem privaten Schlüssel. Man bezeichnet diese Verfahren als asymmetrische Verfahren oder Public-Key-Verfahren. Üblich sind auch die Bezeichnungen Public-Key-Kryptografie und Public-Key-Verschlüsselung.

Ein fundamentales Problem der Kryptografie ist, dass sich die Kommunikationspartner auf einen gemeinsamen Schlüssel verständigen müssen. Man bezeichnet das als Schlüsselaustauschproblem.

Während ein manueller Schlüsselaustausch durch ein persönliches Treffen oder per Telefon bei einer handvoll Kommunikationspartner sicherlich kein Problem wäre. Wird es bei vielen Schlüsseln oder vielen Kommunikationspartnern schnell unübersichtlich und aufwendig. Hier kommt das Thema Schlüsselverwaltung und -verteilung zum Tragen. Alternativ bestünde die Möglichkeit einen Authentifizierungsserver einzusetzen. Beispielsweise Kerberos. Alternativ bietet sich die asymmetrische Kryptografie an.

Asymmetrische Verschlüsselungsverfahren arbeiten mit Schlüsselpaaren. Ein Schlüssel ist der öffentliche Schlüssel (Public Key), der andere ist der private Schlüssel (Private Key). Dieses Schlüsselpaar hängt über einen mathematischen Algorithmus eng zusammen. Daten, die mit dem öffentlichen Schlüssel verschlüsselt werden, können nur mit dem privaten Schlüssel entschlüsselt werden. Deshalb muss der private Schlüssel vom Besitzer des Schlüsselpaares geheim gehalten werden.

Der konkrete Anwendungsfall sieht so aus: Will der Sender Daten verschlüsselt an den Empfänger senden, benötigt er den öffentlichen Schlüssel des Empfängers. Mit dem öffentlichen Schlüssel können die Daten verschlüsselt, aber nicht mehr entschlüsselt werden (Einwegfunktion). Nur noch der Besitzer des privaten Schlüssels, also der richtige Empfänger kann die Daten entschlüsseln. Wichtig bei diesem Verfahren ist, dass der private Schlüssel vom Schlüsselbesitzer absolut geheim gehalten wird. Kommt eine fremde Person an den privaten Schlüssel muss sich der Schlüsselbesitzer ein neues Schlüsselpaar besorgen.

Das Problem bei der asymmetrischen Kryptografie ist die Verteilung der öffentlichen Schlüssel. Typischerweise erfolgt die Übergabe des öffentlichen Schlüssels beim Erstkontakt. Doch hierbei stellt sich die Frage, ob dieser Schlüssel tatsächlich der echte Schlüssel des Kommunikationspartner ist.

Hinweis: Asymmetrische Verfahren benötigen viel mehr Rechenleistung als symmetrische Verfahren. Wenn man RSA und AES miteinander vergleicht, dann ist RSA ungefähr um den Faktor 1.000 langsamer als AES.

Ich verteile Sparschweine, zu deren Schloss nur ich den Schlüssel habe. Wenn mir jemand die Nachricht „135“ senden möchte, nimmt er eines dieser Sparschweine, steckt einen Zettel mit „135“ hinein und schickt es mir per Post. Ich öffne mit meinem Schlüssel das Sparschwein und kann den Zettel lesen.

Wenn mehrere Personen verschlüsselte Nachrichten austauschen wollen, dann reicht es, wenn jede Person ein Schlüsselpaar aus öffentlichem und privatem Schlüssel besitzt.

Bei 4 Personen A(lice), B(ob), C(lara) und D(avid), die alle miteinander kommunizieren wollen, werden somit 4 Schlüsselpaare benötigt. Bei n Personen benötigt man entsprechend genau n Schlüsselpaare. Es werden also viel weniger Schlüssel benötigt als bei symmetrischen Chiffriersystemen.

Damit so ein Verfahren funktioniert, muss Folgendes gelten:

• Mithilfe der öffentlich verfügbaren Informationen (insbesondere dem öffentlichen Schlüssel) muss es in sinnvoller Zeit möglich sein, den Klartext zum Geheimtext zu verschlüsseln. Außerdem muss es mit dem privaten Schlüssel in sinnvoller Zeit möglich sein, den Geheimtext zu entschlüsseln. Ansonsten könnte man das Verfahren nie anwenden.
• Mithilfe der öffentlich verfügbaren Informationen darf es – ohne den privaten Schlüssel – nicht in sinnvoller Zeit möglich sein, den Geheimtext zu knacken, also den Klartext zu rekonstruieren. Daraus folgt, dass auch der private Schlüssel nicht mithilfe der öffentlichen Informationen in sinnvoller Zeit berechnet werden kann.

Asymmetrische Chiffriersysteme nutzen Funktionen mit den oben dargestellten Eigenschaften – sogenannte Einwegfunktionen. In eine Richtung lassen sie sich in sinnvoller Zeit berechnen, aber die Umkehrung ist – ohne den privaten Schlüssel als Hilfsmittel – kaum möglich.

Auf den ersten Blick klingt es verwunderlich, dass hier immer von „in sinnvoller Zeit“ die Rede ist. Das liegt daran, dass man ja z.B. alle möglichen privaten Schlüssel durchprobieren könnte. Es ist also nicht möglich, das Knacken ganz auszuschließen. Aber, wenn es mit aller Rechenleistung der Welt viele Hundert Millionen Jahre dauern würde, gilt das als ausreichend sicher.

Bei der asymmetrischen Verschlüsselung geht es darum, eine Funktion zu wählen, die sehr einfach zu rechnen ist, aber deren Umkehrung dagegen sehr aufwendig. Realisiert wird das mit Modulo-Rechenarten.

Einige davon sind tatsächlich sehr einfach zu rechnen, während die Umkehrung sehr aufwendig ist. Sie entsprechen also einer Einwegfunktion.

Es gibt allerdings auch Funktionen, bei denen sich mit einer zusätzlichen Information die Umkehrung abkürzen lässt. In so einem Fall spricht man von einer Falltürfunktion.

Bei der Modulo Operation wird der Rest einer Division berechnet. Der Rückschluss vom Ergebnis (Rest) auf die Ausgangszahl ist nicht möglich.

Beispiel:

17 % 5 = 2
6 % 2 = 0
18 % 6 = 0

Potenzieren im Bereich natürlicher, ganzer, reeller oder sogar komplexer Zahlen ist eine grundlegende Operation der Mathematik:

g^e = y

Beispiel:

10^2 = 100

Die Umkehrfunktion zum Potenzieren in Bezug auf das Auffinden der Exponenten ist das Logarithmieren.

log_gy = e

Beispiel: log₁₀ 100 = 2

Hierbei ist es nicht unüblich, dass dieser Exponent außerhalb des Definitionsbereichs liegt (z.B. log₁₀ 8 ≈ 0, 9).

Nichtsdestotrotz lässt sich dieser Exponent mit Hilfe von Computern in sehr schneller Zeit (näherungsweise) errechnen. Beispielhaft wäre da die Berechnung über die Potenzreihenentwicklung.

Ist bei der Addition das Ergebnis größer oder gleich n, dann zieht man n davon ab. Ist analog dazu, das Ergebnis bei der Subtraktion kleiner null, dann zählt man n dazu.

Beispiel:

(3+5) % 7 = 1 
(2+2) % 13 = 4 
(3-6) % 9 = 6 
(3+6) % 9 = 0 

Beispiel:

(4*5) % 7 = 20 -7 -7 = 6 

Fragestellung: gibt es zu jeder Zahl a eine Zahl b mit der Eigenschaft a*b=a (mod n)

Gibt es eine solche Zahl, dann nennt man sie das zu a inverse Element und schreibt dafür a-1.

Es gibt auch eine Modulo-Division, weil b*a^-1 (mod n) gleich ist wie b/a (mod n).

Beispiel:

3^4 % 7 = 3*3*3*3 % 7 = 4 

In der Kryptografie spielt vor allem die Umkehrung dieser Rechenart eine Rolle!

Das Problem des diskreten Logarithmus beschreibt ein mathematisches Problem. Eine der beiden Umkehrungen der Potenzierung mit Modulo ist der Modulo-Logarithmus, der auch als diskreter Logarithmus bezeichnet wird. Sind g, x und p gegeben, dann ist der diskrete Logarithmus die Zahl x, für die gilt:

g^x (mod p) = S

g … Generator p … Primzahl

{g,p,S} ∈ ℕ

{x} ∈ ℕ₀

x ⇒ geheimer Schlüssel
S ⇒ öffentlicher Schlüssel

Ein Angreifer, der diese Gleichung nach dem geheimen Schlüssel nach x auflösen könnte, wäre in der Lage die geheime Nachricht zu entschlüsseln.

Bei kleinen Zahlen kann man durch systematisches Ausprobieren dieses Problem lösen.

g=8, p=29 und S=21 ⇒ 8^x mod 29 = 21

Der diskrete Logarithmus von b zur Basis x, kurz log_x b, ist die kleinste natürliche Zahl g:

g=log_x b (mod n)

Die Frage, wann zu gegebenen Zahlen g, S und n der diskreter Logarithmus existiert, ist kein triviales Problem, in der Kryptografie hat man jedoch nur mit solchen Problemstellungen zu tun, in denen der diskrete Logarithmus existiert.

Sind die Zahlen groß genug, so schaffen es auch nicht die leistungsfähigsten Computer durch systematisches Ausprobieren zu einem Ergebnis zu kommen. Bis jetzt ist kein Algorithmus bekannt, der dieses Problem für große Zahlen lösen kann.

Der diskrete Logarithmus fällt hier als Einwegfunktion besonders auf, weil man diesen sehr leicht berechnen kann. Umgekehrt ist es schlichtweg nicht möglich eine große Zahl in praktikabler Zeit zurückzurechnen. Man bezeichnet das als Diskreter-Logarithmus-Problem. Viele asymmetrische Verfahren basieren darauf. Allerdings bedeutet das nicht, dass nicht doch irgendwann ein Weg gefunden wird, den diskreten Logarithmus zu lösen.

Eine weitere Einwegfunktion ist das Multiplizieren von Primzahlen. Während die Multiplikation für einen Computer kein Problem darstellt, ist der umgekehrte Weg, beim dem das Primzahlprodukt in seine Faktoren zerlegt werden soll, nicht in akzeptabler Zeit machbar. Man spricht von Faktorisierung und in dem Zusammenhang vom Faktorisierungsproblem.

Beispiel:

n = p * q

p=17
q=19

n = p*q = 17*19 = 323

Wenn man 17 x 19 berechnet (beides Primzahlen), dann kommt 323 heraus. Und jetzt soll man die beiden unbekannten Faktoren (17 und 19) daraus zurückberechnen. Es gibt im Prinzip nur einen Weg. Man muss alle Möglichkeiten durchprobieren. Bei hinreichend großen Primzahlen dauert das ewig. Damit ist das Faktorisierungsproblem gemeint.

Alle gängigen asymmetrische Verfahren basieren auf komplexen mathematischen Berechnungen, die gemeinsam haben, dass es für sie noch keine Vereinfachung gibt. Schlüssel, Klartext und Geheimtext stellen große Zahlen bzw. Zahlenpaare dar. Die Verfahren sind aber nur so lange sicher sind, bis jemand eine Vereinfachung gefunden hat.

Weil es nur begrenzt geeignete mathematische Berechnungen mit Einwegfunktion gibt, lassen sich nicht beliebig viele asymmetrische Verfahren entwickeln.

Zurück zum Schlüsseltauschproblem: Alice und Bob können Einweg- und Falltürfunktionen zur Lösung des Schlüsseltauschproblems verwenden.

Ein Verfahren, das den diskreten Logarithmus zur Lösung des Schlüsseltauschproblems verwendet, wurde von den Kryptografen Whitfield Diffie und Martin Hellman erfunden.

Die Mathematik hinter dem Algorithmus ist leider nicht ganz einfach zu verstehen. Dafür gibt es aber eine schöne Analogie mit Farben, die man zum Verständnis nutzen kann.

Der Ablauf:

1. Alice und Bob einigen sich auf eine gemeinsame (öffentliche) Farbe.
2. Jeder wählt sich zudem eine geheime weitere Farbe.
3. Alice und Bob mischen sich aus ihrer geheimen und der öffentlichen Farbe eine weitere Farbe.
4. Sie schicken jeweils die neu gemischte Farbe zu ihrem Kommunikationspartner.
5. Am Ende mischt jeder seine geheime Farbe in die zuvor ausgetauschten Mischfarbe.

Die gemeinsame Farbe (der gemeinsame Cocktail) am Ende des Prozesses besteht also aus drei gemischten Farben. Und Eve in der Mitte? Sie hat nur die öffentliche Farbe und zwei gemischte Farben. Und wie du vielleicht aus dem Kunstunterricht weißt, ist es ziemlich schwierig, aus einer Mischfarbe zu erkennen, welche Ausgangsfarben genau darin stecken.

Exkurs Diffie-Hellmann von INF-Schule

In der folgenden Beschreibung ist von Alice und Bob die Rede. Beide stehen beispielhaft für zwei Kommunikationspartner, die ihre Kommunikation verschlüsseln wollen und den dazu notwendigen geheimen Sitzungsschlüssel zum Ver- und Entschlüsseln vorab austauschen müssen. Um den Sitzungsschlüssel vor einem Angreifer zu schützen, der eventuell die Kommunikation abhört oder aufzeichnet, in der Hoffnung den Sitzungsschlüssel abgreifen zu können, vereinbaren sie den Schlüsselaustausch nach Diffie-Hellman-Merkle.

Das mathematische Verfahren beruht auf dem sog. „modularen Potenzieren“. Auch wenn der mathematische Hintergrund nicht so einfach zu verstehen ist, kannst du das Verfahren aber sicherlich einmal hier nachvollziehen. Die wesentlichen Schritte sind (ganz analog zu den Farben oben) die Folgenden.

Zuerst müssen sich Alice und Bob auf eine große Primzahl p und eine natürliche Zahl g, die ein Generator aus Gruppe Z(p) sein sollte, einigen. Die Zahl g kann aber auch einen Wert kleiner p annehmen. Weil Alice die Kommunikation zu Bob aufbaut, legt typischerweise Alice die Zahlen p und g fest. Diese Vorgehensweise kann in der Praxis auch anders erfolgen. Für dieses Beispiel wählt Alice p = 11 und g = 7.

Beide Werte dürfen bekannt sein und können deshalb über einen unsicheren Kanal übertragen werden.

Alice erzeugt nun zusätzlich eine Zufallszahl a, die kleiner als die gewählte Primzahl p sein muss (1 … p - 1). Für dieses Beispiel wählen wir a = 3.

Bob erzeugt nun zusätzlich eine Zufallszahl b, die kleiner als die gewählte Primzahl p sein muss (1 … p - 1). Für dieses Beispiel wählen wir b = 6.

A = g^a mod p
A = 7³ mod 11 = 2

Übertragung der Zahl A = 2 über den unsicheren Kanal zu Bob.

B = g^a mod p
B = 7⁶ mod 11 = 4

Übertragung der Zahl B = 4 über den unsicheren Kanal zu Alice.

K1 = B^a mod p
K1 = 4³ mod 11 = 9

K2 = A^b mod p
K2 = 2⁶ mod 11 = 9

Beide kommen auf das gleiche Ergebnis und haben so einen gemeinsamen geheimen Schlüssel. Dieser Schlüssel kann zum Beispiel in einem symmetrischen Verfahren als temporärer Sitzungsschlüssel genutzt werden.

K1 = K2

Der Angreifer kennt nur p und g. Außerdem A und B, da beide Werte übertragen werden. Allerdings kann er den Schlüssel K nur berechnen, wenn er a und b hat. Da diese Werte nicht übertragen werden, muss der Angreifer sich den Schlüssel anders berechnen, was bei einer ausreichend großen Primzahl fast unmöglich ist. Dieses Verfahren beruht darauf, dass es mit wenig Rechenleistung möglich ist, die Potenz g^x mod p zu errechnen. Aber der umgekehrte Weg von g^x auf x zu schließen ist sehr schwierig (diskreter Logarithmus).