Vielleicht hast du schon mal gehört, dass Quantencomputer moderne Kryptographie knacken können, indem sie anderweitig unlösbare mathematische Probleme plötzlich lösen können. Aber wusstest du, dass der eigentliche Deal-Breaker – Shors Algorithmn – erst 1994 entwickelt wurde, lange nach dem Auftauchen der ersten quanten-kryptographischen Algorithmen?

Das Hauptproblem der Kryptographie ist, dass sie auf einem einzigen Prinzip basiert: Sie ist nur sicher, solange niemand über ausreichend Rechenleistung verfügt oder gar einen besseren Algorithmus findet. Kurz gesagt: sie beruht auf mathematischer Schwierigkeit. Zum Beispiel ist die Faktorisierung großer Zahlen mit zunehmender Größe immer schwieriger und kann daher nicht so einfach mit "Brute-Force" geknackt werden. Aber wie Peter Shor später zeigen konnte, ist dies mit einem Quantencomputer erstaunlich einfach hinzubekommen.

Forscher stellten sich schon früh eine viel tiefgründigere Frage:

Können wir einen kryptographischen Algorithmus finden, dessen Sicherheit nicht allein auf rechnerischer Schwierigkeit basiert, sondern in der Natur selbst verankert ist?

Im Jahr 1984 kamen Charles Bennett und Gilles Brassard auf einen solchen Algorithmus, der heute einfach „BB84" genannt wird. Ich möchte erklären, wie er funktioniert, aber dazu muss ich zunächst darauf eingehen, wie Quantencomputer eigentlich arbeiten. Konkret: Was ist ein Qubit? Wie verhält er sich?

Qubits

Die Quantenphysik ist seltsam. Qubits umso seltsamer für jemanden, der von klassischen Computern kommt, die hauptsächlich mit Nullen und Einsen arbeiten. Aber im Wesentlichen funktioniert ein Quantencomputer ähnlich wie ein klassischer Computer. Er wendet "Quantum-Gates" auf die sog. Quantenbits (Qubits) an und erhält dadurch ein Ergebnis. Der Unterschied ist nur, dass sowohl Qubits als auch Quantum-Gates komplett anders funktionieren, als wir das gewohnt sind.

Ich kann mein Argument nur bringen, wenn du bereit bist, ein paar seltsame Fakten über Qubits zu akzeptieren. Falls du Schwierigkeiten haben solltest, die Fakten zu glauben, hilft es bestimmt zu wissen, dass die meisten Physiker sich auch nicht sicher, warum sie wahr sind. Die Natur ist nunmal so.

Vergleichen wir Qubits mit klassischen Bits und führen gleich ein paar neue Konzepte ein:

2. Wahrscheinlichkeiten

Wenn du jetzt deinen Qubit misst, liest du den Pfeil nicht direkt aus. Stattdessen erhälst du entweder 0 oder 1, genau wie bei klassischen Computern! Aber: Je mehr der Pfeil in eine Richtung zeigt, desto wahrscheinlicher ist das Ergebnis. Im ersten Bild wäre es also sehr wahrscheinlich, eine 1 zu messen, und sehr unwahrscheinlich, eine 0 zu messen. Im zweiten Bild misst man immer eine 0. Und im dritten Bild ist die Chance 50:50. Man nennt das auch eine Superposition von 0 und 1.

4. Freiheit der Messung

Falls das noch nicht verwirrend genug war: 1 muss nicht oben und 0 muss nicht unten sein. Du entscheidest, in welche Richtung du misst. Sie könnten einfach definieren, dass deine 0 rechts und deine 1 links ist. Dann würde das Bild oben sich anders lesen: „ziemlich 0, aber auch ein bisschen 1", „1 und 0 gleichzeitig" und „genau 1". Du hast also die Freiheit, deinen Qubit in jede beliebige Richtung zu messen. Das bedeutet auch, dass ein Qubit in einer Superposition (0 und 1 gleichzeitig) in einem anderen Koordinatensystem wie eine 0 aussehen kann. Es ist ein bisschen wie bei der Zeichenkodierung, bei der Sender und Empfänger sich auf eine Richtung einigen müssen, da sonst Fehler auftreten würden.

Bist du verrückt genug zu akzeptieren, dass es tatsächlich ein physikalisches System gibt, das sich genau wie beschrieben verhält und dabei diese seltsame Unschärfe mit Wahrscheinlichkeiten aufweist, dann lässt sich zeigen, wie sich das ausnutzen lässt, um einen quantenkryptographischen Algorithmus zu erstellen.

Das Messproblem

Vielleicht hast du es schon bemerkt: Wenn du den Qubit durch Messen veränderst, kann man das doch nutzen, um herauszufinden ob ein geheimer Angreifer bei einer Kommunikation in der Mitte mitgehört hat.

Die Idee ist also, dass man einen Angreifer irgendwie dazu zwingen muss, in einer anderen Richtung als man selbst zu messen. Aber wie macht man das?

Man kann sich ja nicht einfach mit der anderen Partei auf eine Richtung einigen. Die Einigung müsste öffentlich erfolgen, und der Angreifer wäre klug genug, mitzuhören und dieselbe Richtung zu verwenden.

Aber was, wenn man sich nicht nur auf eine Richtung einigt? Was, wenn man vereinbart, zwei Richtungen zu verwenden. Komplett zufällig für jeden einzelnen Qubit. Der Angreifer kann unmöglich vorhersagen, welche Richtungen gewählt wurden! (Da wir bereits im Quantenbereich sind, können wir auch von "echter Zufälligkeit" ausgehen)

Natürlich stößt man jetzt auf das Problem, dass etwa die Hälfte der gesendeten Daten zu völligem Kauderwelsch wird, weil etwa die Hälfte der Zeit die falsche Richtung beim Empfänger gewählt wird. Aber vielleicht ist das genau das, was man will!

Verwirrt? Lasst uns den BB84-Algorithmus mal Step-by-step durchgehen.

BB84

(A)lice und (B)ob wollen einen geheimen Schlüssel über einen evtl. unsicheren Kanal auszutauschen. Sie gehen so vor:

Schritt 2

Alice schickt Bob eine lange Sequenz von Qubits. Für jeden Qubit wählt sie zufällig eine 0 oder 1, kodiert in einer zufälligen Richtung (blau/lila).

Schritt 3

Bob empfängt diese zufällige Qubit-Sequenz und misst jeden Qubit mit einer zufälligen Richtung (blau/lila). Sollte er zufällig dieselbe Richtung gewählt haben, sollte er dasselbe Ergebnis erhalten. Andernfalls ergibt sich etwas völlig anderes. Auf diese Weise erhält er seine eigene Sequenz, die beispielsweise so aussieht:

Schritt 4

Nachdem alles abgeschlossen ist, vergleichen beide ihre Ergebnisse, indem sie einen Teil ihrer Sequenz öffentlich bekannt geben. Es gibt nun zwei mögliche Szenarien, was passieren kann:

Szenario 1: Geheimer Angreifer

Wenn beide Parteien dieselbe Richtung verwendet haben, würden sie bei diesen Qubits eine 100%ige Übereinstimmung erwarten. Aber wenn ein Angreifer die Qubits in der Mitte abhört, kann es vorkommen, dass beide Parteien trotz identischer Messrichtung nicht übereinstimmen. Da der Angreifer Alices und Bobs Messrichtung nicht im Voraus kennt, kann er auch nur zufällig raten, was zwangsläufig einige der Ergebnisse verändert und sofort Verdacht erregt.

Es ist immer noch möglich, dass rein zufällig beide Parteien trotzdem auf ein gleiches Ergebnis kommen, aber je länger die Sequenz, desto unwahrscheinlicher wird das. Alice und Bob wählen einfach eine Sequenzlänge, die lang genug ist.

Mit anderen Worten: „Alle Ergebnisse stimmen exakt überein" ist exponentiell unwahrscheinlicher als „mindestens eines der Ergebnisse stimmt nicht überein", wenn ein Angreifer heimlich mitliest. Ist die Sequenz nur lang genug, ist es praktisch unmöglich mitzulesen, ohne dabei unausweichlich Fehler zu machen.

Szenario 2: Kein geheimer Angreifer

Da beide ihre Richtungen zufällig gewählt haben, gibt es wieder Qubits, bei denen beide dieselbe Richtung gewählt haben. Wenn kein geheimer Angreifer vorhanden ist, besteht wieder eine 100%ige Chance, dass beide Parteien bei diesen Qubits übereinstimmen. Sie können einfach die Qubits überprüfen, die in derselben Richtung gemessen wurden, eins nach dem anderen:

Stimmen alle überein, ist die Kommunikation sehr wahrscheinlich sicher gewesen. Der Trick ist jetzt, dass sie nicht die gesamte Sequenz veröffentlicht haben, sondern nur einen Teil. Damit können sie die übereinstimmenden Qubits der restlichen Sequenz als kryptographischen Schlüssel verwenden, der dann für symmetrische Verschlüsselung genutzt werden kann.

Was das für die Zukunft bedeutet

Wenn Alice und Bob herausfinden, dass ein geheimer Angreifer ihre Daten beobachtet, können sie eigentlich nichts dagegen tun. Das Beste, was sie tun können, ist es erneut zu versuchen oder einen anderen Kanal zu verwenden. Die Idee hier ist eher, dass man es erkennen kann.

Ein weiteres Problem mit BB84 ist seine Anfälligkeit für Man-in-the-Middle-Angriffe. Es könnte eine dritte Partei E zwei Kanäle mit A und B aufbauen und dabei so tun, als wäre sie B und A. Aber das ist ein Problem, das alle kryptographischen Algorithmen haben, ob quantenbasiert oder nicht. Es wird durch die Einführung von Certificate-Authorities gelöst.

Darüber hinaus gibt es viele Probleme im Zusammenhang mit Qunatum-Noise, was die praktische Implementierung solcher Algorithmen erschwert. Je mehr Qubits benötigt, desto mehr Qubits braucht man für die Fehlerkorrektur. Und aktuell gibt es eine Grenze, bei der das Hinzufügen von weiteren Qubits noch mehr Qubits für die Fehlerkorrektur erfordern würde, sodass man durch das Hinzufügen weiterer Qubits nichts erreicht.

Wir haben die kritische Qubit-Grenze noch nicht erreicht, bei der ein Teil der klassischen Kryptographie kaputt geht. Und selbst dann gibt es bereits viele neuere und bessere klassische Algorithmen, die von Quantencomputern nicht knackbar sein sollen.

Aber einige Systeme verwenden immer noch alte Kryptographie, weil es oft nicht trivial ist, große laufende Systeme schnell mal zu aktualisieren. Außerdem beginnen viele bereits damit, verschlüsselte Daten zu sammeln, nur für den Fall, dass sie in Zukunft entschlüsselt werden können.

Es bleibt spannend, was passieren wird, wenn die ersten Quantencomputer die kritische Grenze erreichen.