Public-Key-Kryptographie einfach erklärt

Einführung

Eigentlich müsste es ein Fach wie „Digitale Aufklärung“ in den öffentlichen Schulen geben und wenn es so etwas geben würde, dann müsste die Public-Key-Kryptographie ein eigener Baustein im Lehrplan dieses Faches sein. Warum? Weil ein grundlegendes Verständnis der Public-Key-Kryptographie nicht mehr aus unserer digitalen Gesellschaft wegzudenken ist. Es ist so etwas wie das kleine digitale Einmaleins und genauso wie beim kleinen Einmaleins, muss man nicht in die Tiefen der Mathematik eintauchen, sondern nur wissen, wie man es im Alltag anwendet.

Mit der Public-Key-Kryptographie ist es genauso. Wir müssen sie nicht verstehen. Daher ist ein Ziel meines Blogs, anhand von einfachen Bespielen das Grundverständnis zur Public-Key-Kryptographie zu vermitteln, ohne (genau wie beim kleinen Einmaleins) in die Tiefen der Mathematik einzutauchen ([4] und [5]).

Das Ziel dieses Blogs

Ein weiteres Ziel meines Blogs ist es als „Fahrplan“ für mathematisch versiertere Leser zu dienen, die sich eingehender mit der Public-Key-Kryptographie beschäftigen wollen. Das Problem beim Einstieg in dieses Feld ist, dass man nicht genau weiß, wie man strukturiert an das Thema rangehen soll. Für diese Leser werde ich im Laufe des Blogs auf Referenzen hinweisen, die ihnen helfen werden, tiefer einzusteigen, ohne den Gesamtfaden zu verlieren. Es ist ein Fahrplan zum Einsteigen.

Konzept

Ich habe lange darüber nachgedacht, ob ich nach der Einführung erst mit dem Konzept oder mit der historischen Entwicklung anfangen soll. Im Fall der Public-Key-Kryptographie habe ich mich entschlossen, mit dem Konzept anzufangen.

Die meisten Leute denken, dass, wenn wir eine Nachricht vertraulich mit jemand anderem austauschen möchten, wir diese mit einem geheim Schlüssel verschlüsseln müssen, die dem anderem auch bekannt ist. Das bedeutet wiederum, dass wird diesen Schlüssel bereits mit der anderen Partei vertraulich ausgetauscht haben. Ebenfalls nutzen wir diesen Schlüssel sowohl zum Ver- als auch zum Entschlüsseln. Deshalb nennen wir diesen auch symmetrischer Schlüssel.

Der symmetrische Schlüsselaustausch

Aber ist das wirklich praktikabel? Angenommen Sie haben sehr viele Personen, die wir mit geheimen Schlüsseln ausstatten müssen. Wie groß wäre der Aufwand? Nehmen wir als Beispiel 10 Personen. Wie viele symmetrische Schlüssel müssen die Personen untereinander austauschen? Nun, im Falle von 10 Personen wären dies alle mögliche Paarbildung außer die mit sich selber (man muss keinen Schlüssel mit sich selber austauschen) und das genauso viele, wie viele Paare es gibt. Das wären 10*(10-1)/2=45 oder n(n-1)/2 Schlüsselpaare, wenn n die Anzahl der Personen ist. Diese müssten wir bereits vorher schon gegenseitig sicher austauschen. Die folgende Abbildung veranschaulicht die Komplexität dieser Art des Schlüsselaustausches.

Der Aufwand steigt quadratisch mit der Anzahl der Teilnehmer. Dies ist ein enorm hoher und teurer Aufwand für die Schlüsselverwaltung und ist zugleich sehr sicherheitskritisch, so dass sich dies damals nur sehr große Organisationen oder Länder leisten konnten (z.B. das Militär oder der Geheimdienst). Heutzutage wo alle Menschen vernetzt sind, wäre es unmöglich den Verwaltungsaufwand handzuhaben. Unsere digitale Gesellschaft wäre so nicht möglich. Übrigens: Um die Beschreibung der Vorgänge zwischen zwei Personen einfacher zu beschreiben, werden in der kryptografischen Fachliteratur diese Personen meistens Alice und Bob (anstatt A und B) genannt.

Ein weiterer Punkt, der zwingend bei digitalem Datenaustausch erforderlich ist, ist die Möglichkeit seine Daten zu signieren und damit die „Integrität“ des Übermittlers der digitalen Daten zu gewährleisten. Auch hier war das Militär Vorreiter, denn wie sonst sollten sich Flugzeuge, Schiffe, Fahrzeuge und Soldaten identifizieren? Auch hier existierten Verfahren, die allerdings auf einem symmetrischen Schlüsselverwaltungssystem aufsetzen.

Der Heilige Gral

Der „Heilige Gral“ der Kryptografie ist es, die Vertraulichkeit und die Integrität von Daten zwischen zwei Personen auch über einen unsicheren Kanal effektiv zu gewährleisten. Lange wurde nach solch einer Lösung gesucht und die Mathematiker glaubte schon, dass es keine Lösung geben würde. Aber dann stellte sich heraus, dass es eine Lösung für das Problem gibt und diese trägt den Namen „Public-Key-Kryptografie“.

Wie funktioniert die Public-Key-Kryptographie? Sie basiert auf dem, was wir asymmetrische Verschlüsselung nennen. Das bedeutet, dass wir zwei Schlüssel besitzen. Einen Schlüssel, um die Nachricht zu verschlüsseln und einen weiteren Schlüssel, um die Nachricht wiederum zu entschlüsseln. „So what?“, könnte man sagen.

Die Funktionsweise

Um das zu erklären kommen wir wieder auf unser Bespiel mit den 10 Personen zurück. Wie hoch ist jetzt der Aufwand, um asymmetrische Schlüssel zu verwalten? Er ist genau 0 (eigentlich 1 aber dazu später). Warum 0? Weil wird die Schlüssel zum Verschlüsseln von Nachrichten veröffentlichen können. Wir müssen ihn nicht einmal mehr geheim gehalten und können diesen sogar in einer Zeitung mit der Überschrift „Das ist Alice öffentlicher Schlüssel“ veröffentlichen. Wenn jetzt Alice Bob eine Nachricht schicken möchte, verschlüsselt sie die Nachricht mit Bobs öffentlichem Schlüssel aus der Zeitung. Da Bob der Einzige ist, der im Besitz des privaten Schlüssels ist, wird er auch der Einzige sein, der in der Lage ist, die Nachricht von Alice zu entschlüsseln. Die folgende Abbildung verdeutlicht diesen Sachverhalt:

In der Realität wird der Text keine vollständige Nachricht, sondern ein symmetrischer Schlüssel sein, mit dem später größere Daten schnell und sicher verschlüsselt werden. Es geht um ein Protokoll um vorher symmetrische Schlüssel auszutauschen.

Und wie ist es mit digitalen Unterschriften?

Kann ich meine Daten digital signieren? Ja, das kann man, und zwar genau so, nur das man das Protokoll quasi „umdreht“. Was bedeutet das? Mit dem privaten Schlüssel kann Bob eine Nachricht verschlüsseln und alle anderen können aus der Zeitung Bobs öffentlichen Schlüssel entnehmen und die Nachricht entschlüsseln. Da nur Bob in der Lage ist die Nachricht durch seinen privaten Schlüssel zu verschlüsseln, muss sie auch von ihm getätigt worden sein und damit hätten wir etwas äquivalentes zu einer Unterschrift.

Doch wie soll solch ein Algorithmus aufgebaut sein? Lange haben Mathematiker nach einem Algorithmus gesucht, um das Problem zu lösen. Das, was einfach klingt und zu erklären gewesen ist, muss auch praktisch implementiert werden. Der abstrakte Grundgedanke, der die Mathematiker antrieb, war eine Funktion zu finden, die man schnell in eine Richtung ausführen kann, die Umkehrung ohne im Besitz einer Zusatzinformation nicht so einfach durchführen ist. Damit ist gemeint, dass es entweder zu lange dauert oder zu teuer ist. Jetzt kennen wir das Konzept des Public-Key-Verfahrens und gehen in die 70er Jahre des 20 Jahrhunderts.

Historische Entwicklung

Anfangs waren sich die Mathematiker nicht sicher, ob es überhaupt möglich ist ein Public-Key-Verfahren zu realisieren. Die beiden Mathematiker Whitfield Diffie und Martin Hellman wollten eben dies beweisen (also, dass es nicht möglich ist) und bewiesen am Ende das genaue Gegenteil.

Wie alles anfing

1976 veröffentlichten die Beiden das Paper „New Directions in Cryptography“ [1]. Darin beschrieben sie eine völlig neuartige Methode, kryptografische Schlüssel mithilfe des Public-Key-Verfahrens zu verteilen, bzw. auszuhandeln. Dieses Protokoll löste das im letzten Abschnitt von mir beschriebene Problem, welches man bei einer symmetrischen Schlüsselverwaltung hat. Die Beiden nannten das Verfahren ax1x2, welches heute „Diffie-Hellman Schlüsselaustausch-Protokoll“ genannt wird. Es bildet das Fundament jeglicher vertrauenswürdigen Kommunikation im Internet (das Rückgrat des Homebankings). Aus Sicht des Internets ist dieses Verfahren das, was die Mondlandung für die Raumfahrt gewesen ist. Aus diesem Grund bekamen Whitfield Diffie und Martin Helman im Jahr 2015 den Turing Award (das was für Mathematiker die Fields-Medalie und für Naturwissenschaftler der Nobelpreis ist, ist der Turing Award für Informatiker).

Was ist mit den Geheimdiensten?

Was die Kryptografie so einzigartig macht, ist das Umfeld, in dem diese eingebettet ist. Der Sinn und Zweck ist es nun mal, Geheimnisse zu verbergen und deshalb haben das Militär und die Geheimdienste ein besonderes Interesse an dieser Technologie. Daher war man auch nicht verwundert, als 1997 herauskam, dass die britische Government Communications Headquarters bereits 1973 ein erstes Konzept für ein Public-Key-Verfahren veröffentlichte, welches 1975 von einem Mathematiker Namens Clifford Cocks implementiert wurde. Da alles geheim war, wurde auch kein Patent beantragt. Wer weiß, was für „kryptografische Schätze“ noch in den Geheimdiensten schlummern. 1977 wird das nach seinen Entwicklern Ronald Rivest, Adi Shamir und Leonard Adleman benannte RSA-Verfahren veröffentlicht. Es ist das erste praktisch einsetzbare Public-Key-Verfahren. Ich werde das RSA-Verfahren in meinem nächsten Blogbeitrag beschreiben.

Fing wirklich mit dem Anfang an?

Es muss jedoch erwähnt werden, dass bereits 1974 Ralph Merkle [2] den ersten Ansatz hierzu machte. Er initiierte seine Idee als Projekt im Rahmen eines Kurses an der UC Berkeley, die jedoch abgelehnt wurde. Sie wurde erst 1978 veröffentlicht. Aus diesem Grund wird manchmal das Protokoll Diffie-Hellmann-Merkle-Schlüsselaustauschprotokoll genannt.

Ist jetzt wirklich alles in Ordnung?

Alle diese „Public-Key-Verfahren“ haben eine Sache gemeinsam: Sie alle beruhen auf der Tatsache, dass es mit „normalen“ Computern nicht möglich scheint, effizient gewisse Funktionen zu berechnen. 1982 hat der Physiker Richard Feynman [3] ein theoretisches Modell eines Quantencomputers erstellt. 1994 veröffentlichte Peter Shor, der damals bei den AT&T Bell Laboratories beschäftigt war, einen Algorithmus, welcher in polynomialer Zeit eine Primfaktorzerlegung und einen diskreten Logarithmus berechnen konnte. Allerdings lässt sich der Algorithmus „nur“ auf einem Quantencomputer durchführen, welchen es noch nicht gibt. Ich werde den Shor-Algorithmus [6] in einem gesonderten Blogartikel beschreiben. Das nächste Unterkapitel beschreibt das Diffie-Hellman-Verfahren.

Diffie-Hellman-Verfahren

Vorgehen

1. Alice und Bob einigen sich auf eine große Primzahl p und eine natürliche Zahl g, die kleiner ist als p. Einigen bedeutet, dass diese öffentlich bekannt sein kann. Z.B. in einer Zeitung, öffentlich sichtbar für jedermann.
2. Alice und Bob erzeugen jeweils für sich selber eine Zufallszahl kleiner als die zuvor vereinbarte Primzahl p. Für Alice sein dies die Zahl a, für Bob die Zahl b. a und b fungieren als private Schlüssel.
3. Alice berechnet jetzt mit ihrem privaten Schlüssel a, ihren dazugehörigen öffentlichen Schlüssel A=g^a mod p und schickt diesen zu Bob. Bob berechnet aus seinem privaten Schlüssel b, seinen dazugehörigen öffentlichen Schlüssel B=g^b mod p und schickt diesen zu Alice.
4. Alice erhält den öffentlichen Schlüssel B von Bob und berechnet K₁=B^a mod p und Bob berechnet aus dem öffentlichen Schlüssel A von Alice K₂=A^b mod p.
5. Nun ist K₁= K₂ und Alice und Bob verwenden diesen als gemeinsamer Schlüssel um Nachrichten auszutauschen.

Warum ist K1= K2?

Weil K₁=B^a mod p = (g^b mod p)^a mod p =(g^b)^a mod p = g^ba mod p = g^ab mod p = K₂.

Warum ist das Verfahren „sicher“?

Damit ein Lauscher (wird „Eve“ genannt, welcher von „Eavesdropper“ abgeleitet ist) K berechnen kann, muss er in der Lage sein den diskreten Logarithmus aus A und B zu berechnen. Das wären nämlich die privaten Schlüssel a und b von Alice und Bob. Aber bis heute ist kein Algorithmus bekannt, welcher dies in polynomialer Zeit bewerkstelligt.

Beispiel

Kommen wir nun zu einem extra einfach gehaltenen Beispiel:

1. Wir wählen die Primzahl p=13 und für q=2. Diese sind öffentlich bekannt.
2. Alice generiert die Zufallszahl a=3 und Bob die Zufallszahl b=7. Diese Zahlen fungieren als Alice und Bobs private Schlüssel.
3. Alice berechnet ihren öffentlichen Schlüssel A=g^a mod p=2³ mod 13=8 und sendet diese zu Bob. Bob berechnet ihren öffentlichen Schlüssel B=g^b mod p=2⁷ mod 13=11 und sendet diese zu Alice.
4. Alice berechnet K₁=B^a mod p=11³ mod 13=5 und Bob K₂=A^b mod p=8⁷ mod 13=5.
5. Sie sehen, dass Alice und Bob jetzt den gleichen Schlüssel „5“ haben.

In der Praxis sind die Zahlen wesentlich größer.

Zusammenfassung

Ich bin in diesem Blogartikel kurz auf die Motivation hinter dem Public-Key-Verfahren eingegangen und habe die wichtigsten Stationen während der Entwicklung durch die Geschichte beschrieben. Das erste Verfahren, welches ich beschrieben habe, war das Diffie-Hellman-Verfahren.

In meinem nächsten Kapitel werde ich auf das RSA-Verfahren eingehen. Das RSA-Verfahren bildet die erste praktische Implementierung für das digitale Signieren von Nachrichten und bildet (zusammen mit den Elyptischen-Kurven) das Rückgrat der modernen Kryptografie.

Zu guter Letzt kann man zu Recht sagen, dass die Public-Key-Kryptographie zu den größten Erfindungen des 20 Jahrhunderts gehört. Eine Entdeckung ohne die unsere digitale Welt so nicht möglich wäre.

Referenzen

[1] Whitfield Diffie, Martin Hellman: New Directions in Cryptography.: IEEE Transactions on Information Theory.22, Nr. 6, 1976, S. 644–654

[2] Ralph Merkle: Secure Communications over Insecure Channels.: Communications of the ACM 21, Nr. 4, April 1978, S. 294–299

[3] Richard P. Feynman: Simulating physics with computers.: International Journal of Theoretical Physics, volume 21, 1982, S467-488

[4] Peter Bundschuh: Einführung in die Zahlentheorie.: Springer, 2008, 6. Auflage, ISBN 978-3-540-76490-8

[5] Jochen Ziegenbalg: Elementare Zahlentheorie – Beispiele, Geschichte, Algorithmen.: Springer, 2015, 2. Auflage, ISBN 978-3-658-07170-7

[6] Peter W. Shor: Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. In: SIAM Journal on Computing, 26/1997, S. 1484–1509