© ikorch / 123RF.com

Die Ursprünge der Kryptografie lassen sich bis ins 19. Jahrhundert vor Christus zurückverfolgen. Doch auch vier Jahrtausende später stehen Kryptografen noch vor spannenden Herausforderungen.

Die Anfänge der Kryptografie hatten etwas Mystisches, ging es doch zunächst um eine Kunst, deren Ziel es war, Informationen vor Unbefugten zu verbergen. Ein einfaches Verfahren zur Verschlüsselung von Nachrichten entwickelte zum Beispiel Gaius Iulius Caesar ungefähr im Jahr 100 vor Christus. Die grundlegende Idee des Verfahrens war es, jeden Buchstaben einer Nachricht um einen festen Betrag im Alphabet zu verschieben. Diese Position diente dann als geheimer Schlüssel. Verschlüsselte Caesar zum Beispiel den Text “Veni, vidi, vici” mit dem geheimen Schlüssel 3, erhielt er den Chiffretext “Yhql, ylgl, ylfl”.

Das Verfahren wurde allerdings bald durchschaut, daraufhin verbessert, wieder geknackt und so weiter. Auf diese Weise entwickelte sich mit der Zeit eine Art Katz-und-Maus-Spiel zwischen den Designern von Verschlüsselungsverfahren und den Angreifern, die die Verfahren brechen, um an die geheime Information zu gelangen. Das zog sich bis zur Entdeckung der beweisbaren Sicherheit in den 1980er-Jahren hin. Dies war zugleich die Zeit, während der sich die Kryptografie von einer Kunstform zu einer Wissenschaft entwickelte.

Heute beschäftigt sich die moderne Kryptografie nicht mehr nur mit der Geheimhaltung, sondern allgemein mit dem Schutz digitaler Informationen. Dazu zählt zum Beispiel der Schutz von Daten gegen Manipulation, Berechnungen auf verschlüsselten Daten, verifizierbare Berechnungen, Authentifikation, Identifikation, sichere Mehrparteienberechnung, verteilte Berechnungen und vieles mehr.

Im Folgenden stellen wir das Konzept der beweisbaren Sicherheit am Beispiel sicherer E-Mail-Kommunikation vor. Des Weiteren kommen typische Fehler bei der Verwendung kryptografischer Verfahren sowie die Stärken und Grenzen der beweisbaren Sicherheit zur Sprache. Zu guter Letzt veranschaulicht der Artikel anhand praktischer Beispiele aktuelle Themen der Forschung aus dem Bereich der modernen Kryptografie.

Beweisbar sicher

Sichere Software nach dem Security-by-Design-Prinzip beruht auf sechs Schritten, die Abbildung 1 zeigt. Am Beginn jeder Entwicklung steht als erster Schritt die Beschreibung der Funktionalität, häufig in Form eines Lastenhefts. Im zweiten Schritt gilt es, die Sicherheitseigenschaften zu definiert, in der Regel in einem zweistufigen Prozess: Zuerst beschreibt man die Sicherheitsziele in einer für jeden verständlichen Form. Danach geht es darum, das Ganze präzise zu formalisieren, um mehrdeutige Interpretationen zu vermeiden.

Abbildung 1: Sechs Schritte, die zu beweisbarer Sicherheit führen.

Darüber hinaus gilt der formale Sicherheitsnachweis nur für die formale Beschreibung. Darum muss diese Formalisierung die realen Schutzziele so genau wie möglich aufschlüsseln. In der Regel deckt sie folgende Aspekte ab: Welche Sicherheitseigenschaft soll das System erreichen? Um welche(s) System(e) mit welchem Setup handelt es sich? Welche Klasse von Angreifern gilt es abzuwehren? Wie sehen deren Fähigkeiten aus? Wann ist der Angreifer erfolgreich?

Das Identifizieren und Formalisieren der Sicherheitseigenschaften erweist sich als anspruchsvolle Aufgabe, und für viele kryptografische Schemata wurde noch kein passendes Sicherheitsmodell gefunden. Zum Beispiel hat sich die Forschungsgemeinschaft immer noch nicht auf eine Definition für authentifizierte Verschlüsselung geeinigt [1]. Außerdem gibt es immer eine natürliche Spannung zwischen Effizienz und Sicherheit. Idealerweise möchte man sich gegen alle Arten von Gegnern schützen und optimale Sicherheitsgarantien in Anspruch nehmen. Sicherheit ist jedoch nicht kostenlos, und stärkere Sicherheitsgarantien sind oft weniger effizient. Ineffiziente Systeme aber werden in der Regel in der Praxis nicht angenommen.

Nach dem Festlegen der Funktionalität und der Sicherheitseigenschaften besteht der dritte Schritt darin, die Funktionen mittels generischer Verfahren zu realisieren. Darunter versteht man die grundlegenden kryptografischen Bausteine wie Verschlüsselung mit privatem Schlüssel, Nachrichtenauthentifizierungscodes, Hash-Funktionen oder Signaturschemata. Dieser Schritt hilft zu verstehen, welche Sicherheitseigenschaft des zugrunde liegenden Bausteins zum Einsatz kommt, um damit eine bestimmte Sicherheitseigenschaft des neuen Systems zu erzielen.

Die Konstruktion muss dabei unabhängig von bestimmten Verfahren funktionieren, da es immer passieren kann, dass einzelne Verfahren gebrochen werden. Zum Beispiel fanden Forscher kürzlich die ersten Angriffe auf die Hash-Funktion SHA-1. Ein vollständig neues System zu entwickeln, weil einzelne Komponenten gebrochen wurden, ist schlicht zu kostenintensiv. Zudem ändert die Unsicherheit einzelner Instanzen nichts daran, dass das Konzept als solches sicher war. Um dies zu verdeutlichen, sei an dieser Stelle kurz an das Beispiel des Brandschutzkonzepts erinnert. Nur weil das Material einer einzelnen Tür sich nicht als feuerfest erwies, bedeutet das nicht, dass das ganze Konzept falsch war, das eine feuerfeste Tür an einer bestimmten Stelle vorschrieb.

Nach der formalen Spezifikation der Sicherheitseigenschaften und der Konstruktion folgt im vierten Schritt ein formaler mathematischer Sicherheitsbeweis. Er dient als Bestätigung, dass die Konstruktion die gewünschten Sicherheitseigenschaften erfüllt. Der formale Beweis liefert eine Eins-zu-eins-Zuordnung zwischen den Sicherheitseigenschaften der zugrunde liegenden kryptografischen Bausteine und den Sicherheitseigenschaften, die das System erreichen soll. Der Sicherheitsnachweis deckt Designfehler auf: Kommen die Sicherheitseigenschaften des zugrunde liegenden kryptografischen Gebäudes nicht zum Zug, liegt ein Fehler im Design vor, und es gibt höchstwahrscheinlich eine effizientere Lösung.

Sobald die formale Sicherheit des Systems feststeht, gilt es, die generischen kryptografischen Bausteine mit spezifischen kryptografischen Verfahren zu instanziieren. Zum Beispiel kommt ein Verschlüsselungsschema mit privatem Schlüssel (generisch) zur Anwendung, und dieser Baustein wird in der Praxis mit AES realisiert. Da generische Bausteine mit abstrakten Objekten arbeiten (wie “ein privater Schlüssel” oder “ein Chiffretext”), muss man diese Objekte in konkrete Instanzen übersetzen. Zum Beispiel wird das Objekt “Public-Key-Verschlüsselungsschema” mit einem El-Gamal-Verschlüsselungsschema instanziiert.

Der sechste und letzte Schritt besteht in der Sicherheitsbewertung der konkreten Instanziierung. Er ist notwendig, weil der Übergang von einer abstrakten Beschreibung in eine konkrete Realisierung viele Fallstricke birgt. Zum Beispiel handelt es sich bei dem kryptografischen Grundelement “Verschlüsseln-dann-MAC” um ein schwach sicheres authentifiziertes Verschlüsselungsschema. Es gilt als CPA-sicher und fälschungssicher unter der Annahme, dass das Verschlüsselungsschema CPA-sicher ist und der Message Authentication Code (MAC) sich nicht fälschen lässt. Die konkrete Instanziierung, die etwa in IPsec verwendet wurde, erwies sich jedoch als unsicher. Die Sicherheit der Implementierung lässt sich auch durch sogenannte Penetrationstest nachweisen. Sie decken Schwachstellen in der Umsetzung des Sicherheitskonzepts auf, die es einem Angreifer unter Umständen erlauben, in das System einzudringen.

Beispiel: Sichere E-Mail

Das Prinzip der beweisbar sicheren Softwareentwicklung wollen wir nun am Beispiel einer verschlüsselten E-Mail verdeutlichen (Abbildung 2). In diesem Fall möchte Alice eine verschlüsselte Nachricht an Bob schicken. Bob soll die E-Mail entschlüsseln und die Signatur überprüfen können.

Abbildung 2: Sichere E-Mail-Kommunikation von Alice zu Bob.

Alice besitzt den öffentlichen Schlüssel von Bob pkB. Zur Vereinfachung nehmen wir an, dass Alice den Schlüssel überprüft und sichergestellt hat, dass er von Bob stammt. Des Weiteren besitzt Alice ihren eigenen privaten Schlüssel skA. Analog kennt Bob den öffentlichen Schlüssel von Alice pkA und hat seinen eigenen privaten Schlüssel skA. Auch in diesem Fall gehen wir davon aus, dass Bob die Authentizität des Schlüssels pkA überprüft hat.

Im ersten Schritt spezifiziert man nun die Funktionalität. In diesem Fall handelt es sich um eine authentifizierte E-Mail, folglich geht es um zwei Aufgaben: Erstens gilt es, eine verschlüsselte und authentifizierte E-Mail zu berechnen. Diese Schnittstelle bezeichnen wir mit Enc+Auth. Zweitens muss – sofern die Authentifikation gilt – die verschlüsselte E-Mail entschlüsselt werden. Analog nennen wir diese Schnittstelle Vrfy+Dec.

Im zweiten Schritt erfolgt das Ermitteln der (recht einfachen) Sicherheitseigenschaften. Der Angreifer kennt die öffentlichen Schlüssel von Alice und Bob sowie alle verwendeten Verfahren. Er darf dennoch nicht in der Lage sein, Informationen aus der E-Mail zu erlangen. Des Weiteren soll der Angreifer keine E-Mails im Namen von Alice – also unter dem öffentlichen Schlüssel pkA verifizierte Nachrichten – an Bob senden können.

Obwohl diese Eigenschaften auf der intuitiven Ebene sinnvoll erscheinen, lassen sie noch zu viel Raum für Interpretation: Kann der Angreifer mit Bob interagieren? Gibt es eine Lernphase, in der der Angreifer Alice als Schnittstelle benutzen darf, um die verschlüsselten und authentifizierten E-Mails von Alice an Bob weiterzuleiten? Darf der Angreifer sich als Bob ausgeben und eine Zeit lang verschlüsselte E-Mails lesen? Wie werden die Nachrichten an Bob generiert? In einer formalen Beschreibung der Sicherheitseigenschaften gilt es, diese Doppeldeutigkeiten zu eliminieren, sodass eine präzise und eindeutige Beschreibung entsteht.

Nach der Formalisierung der Schnittstellen und der Sicherheitseigenschaften folgt nun im dritten Schritt das Instanziieren der einzelnen Komponenten mit kryptografischen Verfahren. Es gilt, die zwei Schnittstellen Enc+Auth und Vrfy+Dec mit kryptografischen Verfahren so zu konstruieren, dass sie genau die gewünschten Funktionen bereitstellen. Im Falle einer sicheren E-Mail gestaltet sich das relativ einfach (Abbildung 3).

Abbildung 3: Schema einer sicheren E-Mail-Kommunikation.

Um die Schnittstelle Enc+Auth zu implementieren, verschlüsselt man die Nachricht zunächst mit einem Public-Key-Verfahren und signiert das Chiffrat im Anschluss mit einem digitalen Signaturverfahren. Mit c bezeichnen wir den Chiffretext und mit dem griechischen Kleinbuchstaben Sigma die Signatur. Passend dazu realisiert man die Schnittstelle Vrfy+Dec mit den folgenden Operationen: Zunächst wird der Verifikationsalgorithmus des Signaturverfahrens verwendet, um die Gültigkeit der Signatur auf dem Chiffretext c zu überprüfen. Ist diese Signatur gültig, so entschlüsselt der Entschlüsselungsalgorithmus des Public-Key-Verfahrens den Chiffretext c und gibt die resultierende Nachricht m aus.

Im Sicherheitsbeweis nimmt man nun im vierten Schritt an, dass sowohl das Verschlüsselungsverfahren als auch das Signaturverfahren gemäß formaler Definitionen sicher sind. Danach führt man den formalen Beweis, dass ein Angriff, der die Sicherheit von Enc+Auth sowie Vrfy+Dec bricht (nach dem formalen Modell), sich dazu verwenden lässt, die Sicherheit des Public-Key- und des Signaturverfahrens zu brechen. Da im ersten Schritt jedoch beide Verfahren als sicher angenommen wurden, entsteht hier ein Widerspruch, aus dem folgt, dass es einen solchen Angreifer nicht geben kann.

In den letzten beiden Schritten setzt man nun konkrete Verfahren ein, beispielsweise eine RSA-basierte Verschlüsselung, implementiert sie und weist die Sicherheit der Implementierung durch Penetrationstests nach.

Stärken und Grenzen

Seit der Entdeckung dieser Verfahrensweise wurden beweisbar sichere kryptografische Verfahren wie zum Beispiel die El-Gamal-Verschlüsselung praktisch nicht mehr gebrochen. Die Beweise dieser Verfahren führen die Sicherheit auf ein einfaches Berechnungsproblem zurück, etwa das sehr bekannte Faktorisierungsproblem.

Bei diesem Problem erhält der Angreifer eine Zahl N=p*q, die aus dem Produkt zweier Primzahlen gleicher Länge p und q berechnet wurde. Die Aufgabe des Angreifers besteht nun in der Berechnung der beiden Primfaktoren p und q. Für dieses seit Langem bekannte Berechnungsproblem wurde bis heute kein effizienter Lösungsalgorithmus entdeckt. Beruht die Sicherheit eines Verschlüsselungsverfahrens nun auf dem Faktorisierungsproblem, dann zeigt der formale Beweis Folgendes: Falls es einen effizienten Angreifer gibt, der das Verschlüsselungsverfahren bricht, dann gibt es auch einen effizienten Angreifer, der das Faktorisierungsproblem löst. Mit anderen Worten: Das Problem, die Verschlüsselung zu brechen, ist genauso schwierig zu lösen wie das Problem der Faktorisierung.

Auf den ersten Blick suggeriert die Bezeichnung “beweisbar sicher”, dass es auch beweisbar keine Angriffe mehr gibt. Das stimmt so jedoch nicht, es finden immer wieder Angriffe auf vermeintlich beweisbar sichere Systeme statt. Woher kommt der Widerspruch, und wie lässt er sich auflösen? Zunächst gilt es festzuhalten, dass die Sicherheit des Beweises sich immer auf ein formales Modell bezieht. Entspricht das Modell jedoch nicht der Realität, dann schließt es mögliche Angriffe nicht aus, weil sie darin schlicht nicht vorkommen. Folglich stellt das präzise Modellieren der Realität eine der größten Herausforderungen in diesem Bereich dar, und schon kleinste Fehler dabei können zu einer unsicheren Lösung führen.

Ein perfektes Beispiel für eine unvollständige Modellierung liefert die Sicherheit des SSL-Protokolls (Secure Sockets Layer). Es konnte in der realen Ausführung passieren, dass die Nachricht nicht entschlüsselt wurde und stattdessen die Fehlermeldung »Padding Error« erschien. Auf den ersten Blick erscheint sie harmlos, da sie keine direkte Information über den Klartext preiszugeben scheint. Daher wurde sie nicht in das formale Modell aufgenommen. Auf den zweiten Blick konnten Forscher jedoch zeigen, dass es möglich war, diese Fehlermeldung auszunutzen, um die vollständige Nachricht zu entschlüsseln – und zwar ohne die eigentliche Sicherheit des Verschlüsselungsverfahrens zu brechen.

Typische Fehler

Ein weitverbreitetes Mantra aus dem Bereich der IT-Sicherheit besagt, dass man niemals ein eigenes kryptografisches Verfahren entwickeln soll. Doch ab welchem Zeitpunkt konstruiere ich mein eigenes Verfahren? In der Tat greift dieses Mantra an vielen Stellen zu kurz und sollte vielmehr lauten: Setze niemals kryptografische Verfahren ein, wenn du nicht nachweisen kannst, was du tust. Das folgende Beispiel demonstriert, dass diese Darstellung keineswegs überzogen ist und selbst die einfache Verwendung zweier kryptografischer Verfahren zu einer vollständig unsicheren Konstruktion führen kann.

In diesem Beispiel nehmen wir an, dass Alice eine Datei m verschlüsselt in der Cloud speichern möchte. Dazu verwendet sie die Nachricht zusammen mit einem öffentlichen Schlüssel. Der Cloud-Betreiber möchte aus Effizienzgründen keine Duplikate derselben Nachricht speichern. Da die Datei jedoch verschlüsselt wurde, kann er nicht ohne Weiteres feststellen, ob die Nachricht bereits verschlüsselt in der Cloud liegt.

Aus diesem Grund wird der Chiffretext um den Hash-Wert der Nachricht erweitert: c = (Enc(pk,m), H(m)). Bei einer Hash-Funktion handelt es sich um eine deterministische Funktion, die die Eingabe in der Regel komprimiert. Die Sicherheit dieser Funktion basiert auf der Kollisionsresistenz. Diese Eigenschaft bedeutet, dass es (effizient) unmöglich ist, zwei unterschiedliche Nachrichten m1 und m2 zu finden, die dieselbe Ausgabe erzeugen (H(m1) = H(m2)).

Intuitiv könnte man erwarten, dass dank der Kompressionseigenschaften der Hash-Wert keine Informationen über die Nachricht m preisgibt. Es gibt jedoch keine Sicherheitseigenschaft, die diese Annahme deckt. Eine Analyse der Konstruktion zeigt sogar, dass sie vollständig unsicher ist. Insbesondere lässt sich die Ausgabe der Hash-Funktion nutzen, um die Sicherheitseigenschaften der Verschlüsselung vollständig außer Kraft zu setzen.

Dieses einfache Beispiel verdeutlicht, dass selbst die Kombination zweier sicherer kryptografischer Verfahren zu einer unsicheren Konstruktion führen kann. Kryptografische Verfahren sollte man nur dann miteinander einsetzen, wenn man die Sicherheitseigenschaften der einzelnen Verfahren auch tatsächlich benötigt. Genau dieser Zusammenhang zwischen den unterliegenden Eigenschaften und denen, die man gern erreichen möchte, weist ein formaler Beweis nach.

Aktuelle Forschungsthemen

Auf dem Forschungsgebiet der Kryptografie gibt es noch zahllose offene Probleme. Thematisch bewegt sich das Ganze zwischen theoretischer Grundlagenforschung und angewandter praktischer Forschung. Der folgende Abschnitt stellt zwei Gebiete aus der aktuellen Forschung vor.

Bei dem einen handelt es sich um die passwortbasierte Kryptografie. Passwörter sind die Achillesferse von vielen modernen Systemen, da sie alles vereinen, was ein Kryptograf in der Regel nicht schätzt: Sie sind kurz und haben wenig Entropie, was bedeutet, dass ein Angreifer die meisten Passwörter durch einfaches Durchprobieren brechen kann. Diese Art der Angriffe nennt man Offline-Brute-Force-Angriffe. Nach der Erfindung der Public-Key-Kryptografie mutmaßten viele, dass Passwörter aussterben und jeder nur noch einen privaten Schlüssel zur Authentifikation verwenden würde. Das ist bis heute nicht eingetreten, und es hat den Anschein, als würden Passwörter auch langfristig die verbreitetste Technik zur Authentifikation im Internet bleiben. Das führt in der Forschung zu folgender Frage: Wie lässt sich die Sicherheit eines Systems garantieren, auch wenn es schwache Geheimnisse wie Passwörter verwendet?

In diesem Zusammenhang wurden Passwort Hardening und Passwort Hardened Encryption (PHE) entwickelt, also eine passwortgehärtete Verschlüsselung (Abbildung 4). Die Idee beruht im Wesentlichen auf folgenden Überlegungen: Zum einen darf sich die Schnittstelle des Users nicht ändern, er verwendet also weiter Benutzernamen und Passwort zur Authentifikation. Zum anderen müssen die Daten des Benutzers gegen Offline-Brute-Force-Attacken resistent sein – auch dann, wenn die Datenbank gestohlen wurde. Und drittens: Um das zu erreichen, benötigt man einen externen Crypto-Service, der keinen direkten Zugriff auf die Daten erhält, sondern nur bei Operationen zur Ver- und Entschlüsselung hilft.

Abbildung 4: Ablauf bei der passwortgehärteten Verschlüsselung.

Die passwortgehärtete Verschlüsselung erreicht ein Sicherheitsniveau, das vorher nicht denkbar war. Erstmals lassen sich die Daten eines Benutzers gegen Offline-Brute-Force-Angriffe gesichert speichern, und zwar ohne dass der Benutzer komplizierte Public-Key-Techniken verwenden muss.

Ein zweiter Forschungsschwerpunkt beschäftigt sich mit Berechnungen auf verschlüsselten Daten, wofür wir im Folgenden verschiedene Techniken vorstellen. Zum besseren Verständnis, wie sich Berechnungen auf verschlüsselten Daten vornehmen lassen, sehen wir uns zunächst die Funktionsweise einer herkömmlichen Verschlüsselung an.

Unabhängig von der Art des Verschlüsselungsverfahrens stellt jedes im Wesentlichen die Schlüsselerzeugung, Verschlüsselung und Entschlüsselung zur Verfügung. Da die Schlüsselerzeugung bei den folgenden Betrachtungen keine Rolle spielt, gehen wir auf diese Operation nicht weiter ein.

Als Verschlüsselungsverfahren bezeichnet man in der Kryptografie ein Verfahren, das einen lesbaren Text – den Klartext – in eine Form überführt, die keine Informationen mehr über den Klartext preisgibt – das sogenannte Chiffrat. Abbildung 5 visualisiert die Ver- und Entschlüsselungsoperation. Der Verschlüsselungsalgorithmus Enc erhält als Eingabe eine Nachricht m und einen öffentlichen Schlüssel pk. Das Ergebnis der Berechnung ist ein Chiffrat c. Der Entschlüsselungsalgorithmus Dec dient dazu, es wieder zu entschlüsseln. Er benötigt als Eingabe den geheimen Schlüssel sk und das Chiffrat c.

Abbildung 5: Berechnungen auf verschlüsselten Daten.

Zur Beschreibung eines homomorphen Verschlüsselungsverfahrens gilt es, zunächst den Begriff des Homomorphismus zu verstehen. Er stammt aus der Mathematik und meint eine strukturerhaltende Abbildung. Vereinfacht gesagt bedeutet das, dass man das Ausführen einer Berechnung in einer Struktur auf eine Berechnung in einer anderen Struktur abbilden kann. Dabei bleibt die Struktur an sich erhalten.

Der Begriff des Homomorphismus wird nun auf Verschlüsselungsverfahren übertragen. Dabei nimmt man auf dem Chiffrat eine Berechnung vor, ohne das Chiffrat zu entschlüsseln. Das Besondere an dieser Operation: Die Berechnung auf den Klartext wirkt sich innerhalb des Chiffrats aus, obwohl der Klartext bei der Berechnung nicht zur Verfügung steht. Je nach Art der Verschlüsselung wirkt sich die Verknüpfung der Chiffrate als Addition oder Multiplikation auf die Klartexte aus. Im ersten Fall spricht man von einer additiven homomorphen, im zweiten Fall von einer multiplikativen homomorphen Verschlüsselung.

Abbildung 5 stellt das in der rechten Hälfte dar. Dort sehen Sie links zwei Chiffrate C1 und C2. Sie wurden auf herkömmliche Art und Weise berechnet: C1 ist also das Ergebnis der Verschlüsselung einer Nachricht m1 mit dem öffentlichen Schlüssel pk, C2 das Ergebnis der Verschlüsselung einer Nachricht m2 mit dem öffentlichen Schlüssel pk. Diese beiden Chiffrate verknüpft man nun durch eine Berechnung × miteinander.

Ein Beispiel: Zunächst verschlüsselt man die Zahl 2 mit dem öffentlichen Schlüssel pk: C1 := Enc(pk,2). Das resultierende Chiffrat heißt C1. Im zweiten Schritt verfährt man analog mit der Zahl 3: C2 := Enc(pk,3) und erzeugt so das Chiffrat C2. Der dritte Schritt verknüpft nun die beiden Chiffrate durch die Operation × miteinander: C3 := C1 × C2. Handelt es sich bei dem Verschlüsselungsverfahren um ein additives homomorphes Verfahren, dann enthält das Chiffrat C3 := C1×C2 := Enc(pk,2) × Enc(pk,3) = Enc(pk,2+3) = Enc(pk,5) den Wert 5. Ist das Verfahren multiplikativ homomorph, dann enthält C3 := C1 × C2 := Enc(pk,2) × Enc(pk,3) = Enc(pk,2*3) = Enc(pk,6), also den Wert 6.

In beiden Fällen hat nur der Besitzer des geheimen Schlüssels sk Zugriff auf das Ergebnis der Berechnung, da nur er das Chiffrat C3 entschlüsseln kann. Ein Beispiel für additive homomorphe Verschlüsselung bietet das El-Gamal-Verfahren, das Paillier-Verfahren ist multiplikativ homomorph.

Im Gegensatz zu den vorherigen Verfahren lassen sich bei der vollhomomorphen Verschlüsselung beliebige Berechnungen auf dem Chiffrat ausführen. Zum besseren Verständnis der Funktionsweise zeigt Abbildung 6 die einzelnen Schritte. Zunächst wird ein Klartext m mit dem öffentlichen Schlüssel pk verschlüsselt (a), woraus das Chriffrat C resultiert. Nun geht es an die Berechnung (b), in die neben dem Chiffrat C und dem öffentlichen Schlüssel pk die Beschreibung des Programms P einfließt. Als Ergebnis der Berechnung entsteht ein Chiffrat CP mit dem Ergebnis der Berechnung: Eval(pk,C,P) = CP = Enc(pk,P(m)).

Abbildung 6: Vollhomomorphe Verschlüsselung.

Genau wie in den vorherigen Beispielen kann jedermann die Berechnung auf dem Chiffrat C vornehmen, da man dafür keine geheimen Informationen benötigt. Das Ergebnis kann jedoch nur der Besitzer des zugehörigen geheimen Schlüssels sk berechnen. Vollhomomorphe Verschlüsselung ist ein unglaublich mächtiges Werkzeug, da es keine Beschränkungen für das Programm P gibt. Es lassen sich also beliebige Berechnung auf der Verschlüsselung vornehmen.

Fazit

Die moderne Kryptografie ist eine sehr spannende und aktuelle Wissenschaft, die wegen der zahllosen Cyberangriffe immer mehr an Bedeutung gewinnt. Trotz der beeindruckenden Erfolge der Forschung in den letzten Jahrzehnten gibt es nach wie vor mehr offene als gelöste Probleme.

Dieser Artikel hat Ihnen ein paar Eckpfeiler der modernen Kryptografie vorgestellt, wie die Erfindung der beweisbaren Sicherheit, und aktuelle Techniken gezeigt, die noch nach purer Magie klingen. Wer hätte etwa gedacht, dass heute bereits eine Berechnung auf verschlüsselten (genetischen) Daten gelingt? Doch die Kryptografie steckt auch nach vier Jahrtausenden Entwicklung noch immer in den Kinderschuhen, und die Kryptotechnologien der Zukunft werden uns weiter überraschen. (jcb/jlu)