Teil 4: Asymmetrische Verschlüsselung

Kryptografie für Anfänger: Asymmetrisch wird’s sicherer
Keine Kommentare

Die bisher vorgestellten Ansätze zur symmetrischen Verschlüsselung haben einige gravierende Nachteile. Können asymmetrische Verfahren die Probleme lösen?

Alle bisher vorgestellten Verschlüsselungsverfahren fallen in die Kategorie der sogenannten symmetrischen Verschlüsselung. Die heißt so, weil zum Ver- und Entschlüsseln stets ein- und derselbe Schlüssel verwendet wird. Das erscheint auf den ersten Blick nicht nur naheliegend, sondern auch alternativlos. Schließlich benötigt man auch in der Realität zum Aufschließen und Öffnen einer Tür eben jenen Schlüssel, mit dem sie verschlossen und zugesperrt wurde. Insofern haben sich die bisherigen Verfahren nur in ihrer Komplexität, die eigentliche Verschlüsselung durchzuführen, unterschieden – nicht jedoch in ihrem grundlegenden, konzeptionellen Ansatz.

Das war bislang auch in Ordnung. Dennoch haben die bisherigen Verfahren alle ein paar Probleme gemeinsam. Dabei ist es kein Zufall, dass diese Probleme bei jedem Verfahren aufgetreten sind, da sie konzeptioneller Natur und damit in allen vorgestellten Verfahren prinzipbedingt enthalten sind. Am gravierendsten sind dabei die folgenden beiden Probleme:

  • Zum einen weisen alle bisher vorgestellten Verfahren das Problem des effizienten und sicheren Schlüsselaustauschs auf. Wenn es einen solchen Weg für den Austausch des Schlüssels gibt, könnte man diesen auch gleich für den eigentlichen Nachrichtenaustausch verwenden. Wenn es einen solchen Weg nicht gibt, kann der ausgetauschte Schlüssel nicht guten Gewissens als sicher angesehen werden.
  • Zum anderen wächst die Anzahl der benötigten Schlüssel enorm schnell. Unter der Annahme, dass jeder mit jedem kommunizieren können möchte, braucht der n-te Teilnehmer für jeden der übrigen n-1 Teilnehmer einen eigenen, individuellen Schlüssel – was das zuvor beschriebene Problem des Schlüsselaustauschs sehr schnell verschärft.

Artikelserie

Willkommen, asymmetrische Verschlüsselung

Glücklicherweise gibt es einen Ausweg: Als Alternative zur symmetrischen gibt es nämlich die asymmetrische Verschlüsselung. Sie arbeitet anders als die symmetrische Verschlüsselung nicht mit einem, sondern mit zwei Schlüsseln. Einer davon dient zum Ver-, der andere zum Entschlüsseln. Das Prinzip ähnelt damit dem eines Vorhängeschlosses, bei dem sich die Wege zum Schließen und Öffnen des Schlosses ebenfalls deutlich voneinander unterscheiden. Das besondere an diesen beiden Schlüsseln ist nun, dass einer davon geheim bleibt, der andere hingegen veröffentlicht wird, sodass jedermann ihn einsehen kann. Daher bezeichnet man den ersten Schlüssel auch als Private Key, den zweiten als Public Key. Jeder Teilnehmer braucht nun nur diese beiden Schlüssel: Den geheimen und den öffentlichen.

Die Schlüssel bedingen sich dabei gegenseitig. Das bedeutet, dass eine mit dem einen Schlüssel verschlüsselte Nachricht nur mit dem anderen Schlüssel wieder entschlüsselt werden kann, und umgekehrt. Das heißt, rein technisch und mathematisch gesehen ist es also zumindest im Hinblick auf die Berechnungen egal, welcher der beiden Schlüssel privat bleibt, und welcher veröffentlicht wird. Da sich aber der eine Schlüssel aus dem anderen herleiten lässt, sind die Rollen in der Praxis keineswegs gleichgültig.

Mathematisch gesehen basieren alle asymmetrischen Verfahren auf sogenannten Falltürfunktionen. Das sind mathematische Funktionen, die sehr einfach zu berechnen sind – deren Umkehrung aber enorm schwierig beziehungsweise aufwendig ist. Ein einfaches Beispiel dafür stellt die Multiplikation von zwei Primzahlen dar: 47 * 97 = 4559.

Diese Rechnung lässt sich selbst von Hand in wenigen Minuten ausführen. Die umgekehrte Frage, aus welchen beiden Primzahlen sich das Produkt 4559 ergibt, kann jedoch nicht direkt beantwortet werden: Es gibt schlichtweg keinen effizienten Algorithmus, der eine Zahl in ihre Primfaktoren zerlegen kann. Im dümmsten Fall bleibt einem nur, so lange Zahlen auszuprobieren, bis man einen passenden Teiler gefunden hat. Wählt man die initialen Primzahlen groß genug, dauert das entsprechend lange.

Der diskrete Logarithmus

Gesucht sind also mathematische Probleme, die sehr einfach zu berechnen sind, sich jedoch nur sehr aufwendig umkehren lassen. Bei der Suche nach solchen Problemen ist man auf den diskreten Logarithmus gestoßen. Der normale Logarithmus stellt die Umkehrung der Potenzfunktion dar. So lässt sich beispielsweise zu 28 = 256 mit Hilfe des Logarithmus leicht die Lösung 8 berechnen: log2(256) = 8.

Der diskrete Logarithmus ist prinzipiell die gleiche Funktion, allerdings nicht in Bezug auf ganze Zahlen, sondern auf Restklassen. Das hört sich deutlich schwieriger an als es ist. Eine Restklasse ist die Menge der Zahlen, die sich ergibt, wenn man die ganzen Zahlen mit Hilfe der Modulodivision und einer anderen Zahl verrechnet. Beispielsweise enthält die Restklasse Z/12 alle Zahlen zwischen 0 und 11, denn das sind genau die Reste, die bei der Modulodivision durch 12 entstehen können: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11.

Berechnet man nun die Potenzfunktion in der Restklasse Z/12, muss man das Ergebnis lediglich durch 12 teilen und den Rest als Ergebnis übernehmen 28 mod 12 = 256 mod 12 = 4.

Das bedeutet, dass die Aufgabe 28 in der Restklasse Z/12 das Ergebnis 4 hat. Der diskrete Logarithmus ist nun die Umkehrfunktion davon. Gefragt ist also, welche Zahl man für x einsetzen muss: log2(4) = x mod 12.

Das lässt sich nun, anders als die diskrete Potenzfunktion, nur sehr schwer berechnen – letztlich bleibt nicht viel übrig, als es einfach auszuprobieren. Wie schon bei der Primfaktorzerlegung gilt auch hier: Wählt man die Zahlen groß genug, wird diese Aufgabe so aufwendig, dass man sie praktisch als unlösbar ansehen kann.

Ein öffentliches Geheimnis

Damit lassen sich nun einige nette Sachen anstellen. Beispielsweise kann man die schwere Berechenbarkeit des diskreten Logarithmus nutzen, um in der Öffentlichkeit ein Geheimnis auszutauschen. Bevor das mathematisch gezeigt wird, soll zunächst ein anschauliches Beispiel das grundlegende Prinzip erklären. Das praktische Pendant zum diskreten Logarithmus ist dabei das Problem, aus einer im Baumarkt individuell gemischten Farbe wieder die exakten Bestandteile zu ermitteln. Anders gefragt: Ist es möglich, einen individuell gemischten Farbton exakt zu reproduzieren, ohne die Bestandteile und deren genaue Mischverhältnisse zu kennen?

Als anschauliches Beispiel treffen sich nun Alice und Bob, die ein gemeinsames Geheimnis etablieren möchten, dazu allerdings keinen Ort finden, an dem es Eve nicht möglich wäre, sie zu belauschen. Sie beschließen daraufhin, Eve wie folgt auszutricksen: Zunächst überlegen sich Alice und Bob jeweils eine Farbe, die sie geheim halten. Nehmen wir an, Alice entscheidet sich für Rot, und Bob für Blau. Diese beiden Farben entsprechen dem jeweiligen Private Key. Anschließend überlegen sie sich öffentlich eine gemeinsame Farbe, beispielsweise Gelb. Diese Farbe entspricht dem Public Key. Eve kennt zu diesem Zeitpunkt nur diese gemeinsame öffentliche Farbe.

Nun mischt Alice ihre geheime mit der öffentlichen Farbe und erhält aus Rot und Gelb Orange. Bob geht ebenso vor und erhält aus Blau und Gelb entsprechend Grün. Nun tauschen Alice und Bob diese Farben aus. Eve kennt nun die beiden Mischfarben und weiß, dass ein Bestandteil gelb ist. Diese Information genügt aber nicht, um auf die jeweils andere Komponente zu schließen. Nun mischt Alice in die Mischfarbe, die sie von Bob erhalten hat, ihre geheime Farbe hinein. Aus Grün und Rot wird nun Braun. Bob macht das gleiche mit der Mischfarbe, die er von Alice erhalten hat, und seiner geheimen Farbe, und erhält aus Orange und Blau ebenfalls Braun. Nun haben Alice und Bob den exakt gleichen Farbton als gemeinsames Geheimnis, das allerdings zu keinem Zeitpunkt öffentlich gemacht wurde.

Der entscheidende Punkt an diesem Beispiel ist, dass Eve zu keinem Zeitpunkt die beiden privaten Schlüssel kennt, und weder in der Lage ist, diese aus den öffentlich ausgetauschten Farben zu rekonstruieren, noch die Mischung, die Alice und Bob am Ende jeweils durchführen, nachzuvollziehen. Natürlich kann Eve die beiden ausgetauschten Mischfarben zusammengießen. Darin ist jedoch zu viel gelb enthalten, da die Mischfarben von Alice und Bob beide gelb enthalten – das jeweils gemischte braun aber nur einen Teil davon.

Das gleiche lässt sich nun auch mathematisch durchführen. Das Prinzip ist exakt das Gleiche, und die Sicherheit basiert dieses Mal nicht auf der Unmöglichkeit, gemischte Farben in ihre Bestandteile zu zerlegen, sondern auf der Unmöglichkeit, den diskreten Logarithmus effizient zu berechnen.

Alice und Bob überlegen sich zunächst jeweils eine Zahl als Private Key, die im Folgenden mit a und b bezeichnet werden. Alice entscheidet sich beispielsweise für 2, und Bob für 3. Außerdem tauschen sie öffentlich eine Primzahl p und eine weitere Zahl g aus, wobei gilt, dass g kleiner als p sein muss. Sie könnten beispielsweise p als 7 und g als 4 festlegen:

Öffentlich: p = 7, g = 4 (mit g < p)
Alice:      a = 2
Bob:        b = 3

Nun können sowohl Alice als auch Bob jeweils A und B berechnen:

Öffentlich: p = 7, g = 4 (mit g < p)
Alice:      a = 2
            A = g ^ a mod p
            = 4 ^ 2 mod 7
            = 16 mod 7
            = 2
Bob:        b = 3
            B = g ^ b mod p
            = 4 ^ 3 mod 7
            = 64 mod 7
            = 1

Als nächstes tauschen Alice und Bob die Werte A und B aus. Eve erfährt diese zwar und kennt von Anfang an p und g, kann aber auf a und b nicht zurück schließen, da sie dazu den diskreten Logarithmus für eine der beiden folgenden Aufgaben lösen müsste, was wie zuvor erklärt praktisch nicht möglich ist:

log4(2) mod 7 = a
log4(1) mod 7 = b

Alice und Bob verwenden nun den vom jeweils anderen erhaltenen Wert B beziehungsweise A und setzen ihn wiederum in folgende Formel ein:

Öffentlich: p = 7, g = 4 (mit g < p), A = 2, B = 1
Alice:      a = 2
            X = B ^ a mod p
            = 1 ^ 2 mod 7
            = 1 mod 7
            = 1
Bob:        b = 3
            X = A ^ b mod p
            = 2 ^ 3 mod 7
            = 8 mod 7
            = 1

Wie man sieht, erhalten Alice und Bob beide das gleiche Ergebnis für X, und haben somit nun ein gemeinsames Geheimnis. Setzt man noch einmal die Formeln für A und B ein, erklärt sich auch, warum das so ist:

X = (g ^ b mod p) ^ a mod p
X = (g ^ a mod p) ^ b mod p

Wie man sieht, berechnen beide exakt das Gleiche – nur in anderer Reihenfolge. Dass das funktioniert, liegt daran, dass die Potenzfunktion auch bei Restklassen kommutativ ist, also in der Reihenfolge vertauschbar.

Dieses Vorgehen heißt Diffie-Hellman Key Exchange, benannt nach den beiden Erfindern, und kann zum Beispiel dafür genutzt werden, ad hoc einen Schlüssel für die symmetrische Verschlüsselung zu generieren, obwohl kein sicherer Kanal zur Verfügung steht. Das heißt, dass – sofern sie eine Verbindung zueinander aufbauen können – die beiden Teilnehmer durchaus in der Lage sind, das Schlüsselaustauschproblem zu lösen beziehungsweise zu umgehen. Allerdings ist es auch mit diesem Verfahren nicht möglich, eine Nachricht im Vorfeld, das heißt, ohne bestehende Verbindung, zu verschlüsseln, da dann der Schlüsselaustausch ad hoc selbstverständlich nicht möglich ist.

RSA

Das gleiche Vorgehen lässt sich jedoch nicht nur auf den Schlüsselaustausch, sondern auf die gesamte Verschlüsselung anwenden. Ein Algorithmus (wenn nicht sogar schlechthin der bekannteste Algorithmus) dafür ist RSA. Auch seine Sicherheit basiert auf dem diskreten Logarithmus, und auch er arbeitet mit einem privaten und einem öffentlichen Schlüssel. Allerdings werden die beiden Schlüssel in diesem Fall nicht ad hoc ausgehandelt, sondern von einem Teilnehmer bereits im Vorfeld generiert. Das heißt, Alice besitzt ebenso wie Bob ein Schlüsselpaar, bestehend aus einem privaten und einem öffentlichen Schlüssel. Die erste Frage lautet also, wie ein solches Schlüsselpaar generiert werden kann.

Dazu muss Alice zunächst zwei Primzahlen wählen, die im Folgenden als p und q bezeichnet werden, beispielsweise 11 und 13. Diese beiden multipliziert sie miteinander, und erhält so den sogenannten Modul N:

p = 11
q = 13
N = 11 * 13 = 143

Als nächstes berechnet sie die Eulersche Phi-Funktion von N, was sehr einfach ist, wenn man p und q kennt: phi(N) = (p – 1) * (q – 1).

Die Phi-Funktion von 143 ist also 120:

phi(120) = (p - 1) * (q - 1)
         = 10 * 12
         = 120

Nun wählt Alice eine weitere Zahl e, die zwischen 1 und phi(N) liegen und teilerfremd zu phi(N) sein muss. Die Zahl 20 beispielsweise würde zwar das erste, nicht aber das zweite Kriterium erfüllen. Daher wählt Alice die Zahl 23. Die beiden Zahlen N und e bilden nun gemeinsam den Public Key: (N, e) = (143, 23).

Nun muss Alice noch den Private Key passend zum Public Key bestimmen. Dazu muss sie das multiplikative Inverse von e bezüglich phi(N) bestimmen. Auch das klingt wieder sehr schwierig, ist aber mit dem erweiterten euklidischen Algorithmus zum Berechnen von größten gemeinsamen Teilern sehr einfach zu bewerkstelligen. Letztlich muss sie die folgende Gleichung lösen, wobei d den private Key darstellt: e * d = 1 mod phi(N).

Das ergibt für d den Wert 47. Die Werte pq und phi(N) sind nun nicht mehr relevant. Tatsächlich wird e in der Praxis aus Effizienzgründen relativ klein gewählt, gängig ist zum Beispiel der Wert 65537. Um nun mit RSA tatsächlich zu verschlüsseln, führt man mit der Nachricht m folgende Berechnung durch, wobei m kleiner als N sein muss (im folgenden Beispiel wird m als 7 gewählt):

c = m ^ e mod N
  = 7 ^ 23 mod 143
  = 2

Das Entschlüsseln des Geheimtextes c erfolgt prinzipiell auf dem exakt gleichen Weg, nur dass an Stelle des öffentlichen der private Schlüssel verwendet wird:

m = c ^ d mod N
  = 2 ^ 47 mod 143
  = 7

Wie man sieht, ist es nun also möglich, ohne einen vorherigen Schlüsselaustausch eine verschlüsselte Nachricht an Alice zu senden: Alles, was man dazu benötigt, ist ihr öffentlicher Schlüssel. Da aber nur sie den passenden privaten Schlüssel dazu kennt, ist es nur ihr möglich, die Verschlüsselung wieder aufzuheben.

Bist Du’s?

Besonders praktisch an RSA ist, dass sich die Reihenfolge der Berechnungen auch umkehren lässt: Vertauscht man die Rolle von e und d, kann man auch zuerst mit dem privaten Schlüssel von Alice ver- und mit ihrem öffentlichen Schlüssel entschlüsseln. Natürlich stellt sich dabei die Frage nach dem Sinn, denn warum sollte man eine Nachricht verschlüsseln, die anschließend von jedermann entschlüsselt werden kann?

Tatsächlich gibt es hierfür einen sehr praktischen und gängigen Anwendungsfall: Der Punkt beim Vertauschen der Rollen der Schlüssel ist nämlich gar nicht so sehr, dass es jedem möglich ist, den Geheimtext zu entschlüsseln, sondern dass es ausschließlich Alice möglich gewesen sein kann, den ursprünglichen Text so zu verschlüsseln, dass er mit ihrem öffentlichen Schlüssel wieder entschlüsselt werden kann.

Damit ist RSA also der bislang einzige Algorithmus, der nicht nur zum Verschlüsseln, sondern auch zum Erzeugen einer digitalen Signatur verwendet werden kann. In der Praxis nutzt man in der Regel beide Schritte hintereinander: Zunächst wird eine Nachricht vom Absender signiert, anschließend mit dem öffentlichen Schlüssel des Empfängers verschlüsselt. Das stellt sicher, dass nur er die Nachricht wieder entschlüsseln und in einem zweiten Schritt überprüfen kann, dass die Nachricht tatsächlich von dem Absender kommt, von dem sie angeblich stammt.

Wichtig dabei ist allerdings zu berücksichtigen, dass auch RSA nicht vor Manipulation der Nachricht schützt, weshalb auch dieser Algorithmus stets mit wenigstens einem Hash oder einem HMAC kombiniert werden sollte.

Warum nicht alles asymmetrisch verschlüsseln?

Es drängt sich die Frage auf, warum man überhaupt noch auf symmetrische Verschlüsselung setzen sollte. Immerhin löst die asymmetrische Verschlüsselung sämtliche Probleme der symmetrischen Verfahren, und ermöglicht darüber hinaus sogar noch den Einsatz zum Erzeugen von digitalen Signaturen. Warum also nicht einfach alles immer asymmetrisch verschlüsseln?

Wie so oft gibt es dort, wo viel Licht ist, auch entsprechende Schatten. Konkret bedeutet das, dass auch RSA (beziehungsweise die asymmetrische Verschlüsselung allgemein) mit einigen Problemen zu kämpfen hat, die ihren Einsatz als Universallösung leider verbieten. Als erstes ist dabei die Geschwindigkeit zu nennen: RSA arbeitet im Vergleich zu AES deutlich langsamer, tatsächlich liegt die Geschwindigkeit von RSA gut um den Faktor 1 000 bis 10 000 unter der von AES. Das macht das Verschlüsseln längerer Nachrichten unerträglich langsam.

Es kommt jedoch noch schlimmer: Es ist mit RSA noch nicht einmal möglich, längere Nachrichten überhaupt zu verschlüsseln, da die Nachrichtengröße durch die Länge des Schlüssels begrenzt wird. Es lassen sich also nur sehr kurze Nachrichten mit RSA verschlüsseln. Im Hinblick auf die Performance ist das in gewissem Sinne eine gute Nachricht, im Hinblick auf die Praktikabilität des Verfahrens jedoch überhaupt nicht.

Die Lösung für beide Probleme liegt darin, sich das Beste beider Welten zu Nutze zu machen: Will man eine Nachricht verschlüsseln, erzeugt man zunächst einen zufälligen Schlüssel und verschlüsselt die Nachricht anschließend mit AES. Das geht schnell und funktioniert für beliebig große Nachrichten. Den zufälligen Schlüssel betrachtet man im Anschluss als eine weitere Nachricht, die nun aber asymmetrisch verschlüsselt und signiert wird. Da ein symmetrischer Schlüssel für AES sehr kurz ist, treten hierbei keine Probleme mit RSA auf. Zu guter Letzt überträgt man beides — die eigentliche Nachricht sowie den Schlüssel — an den Empfänger, der dann zunächst den Schlüssel wieder mit RSA entschlüsseln muss, um mit ihm anschließend die Nachricht mit AES zu entschlüsseln.

Das klingt aufwendig, ist aber eine gängige Option, um effektiv und effizient beliebig große Nachrichten zu verschlüsseln, ohne dass man vorher einen gemeinsamen Schlüssel generieren und austauschen müsste.

Fazit

Die Verfügbarkeit der asymmetrischen Verschlüsselung ist ein weiterer hilfreicher Baustein in der Palette der Verfahren zum Verschlüsseln, Signieren und Absichern von Nachrichten. Insbesondere die Kombination der symmetrischen mit den asymmetrischen Verfahren ist sehr praktisch, um die Vorteile beider Welten gleichzeitig nutzen zu können.

Ein Problem bleibt aber: Woher weiß man, dass ein öffentlicher Schlüssel wirklich zur behaupteten Person gehört? Anders formuliert: Wer hindert Eve daran, ein asymmetrisches Schlüsselpaar zu erzeugen, und sich als Alice auszugeben? Für Bob wäre das nicht überprüfbar, außer er trifft sich mit Alice, um persönlich zu verifizieren, dass Nachrichten, die mit ihrem privaten Schlüssel signiert wurden, tatsächlich von ihr stammen. Umgekehrt gilt das Gleiche: Auch bei Bob kann Alice sich nicht sicher sein. Eve könnte sich also durchaus zwischen Alice und Bob positionieren und sich beiden gegenüber als der jeweils andere ausgeben. Sie müsste also gar nicht die Verschlüsselung an sich angreifen, sondern würde das System an anderer Stelle kompromittieren.

Ein Lösungsansatz dafür sind Zertifikate, die die Identität einer Person bestätigen sollen. Um diese wird es im nächsten und letzten Teil der Serie gehen.

Unsere Redaktion empfiehlt:

Relevante Beiträge

Hinterlasse einen Kommentar

Hinterlasse den ersten Kommentar!

avatar
400
  Subscribe  
Benachrichtige mich zu:
X
- Gib Deinen Standort ein -
- or -