Quantencomputing verständlich erklärt — Episode 11

Kann ein Quantencomputer das Internet entschlüsseln?Quantencomputing verständlich erklärt — Episode 11Über Quantencomputer wird häufig behauptet:

Ein ausreichend großer Quantencomputer kann die Verschlüsselung des gesamten Internets brechen.Diese Aussage ist zu pauschal. Ein Quantencomputer kann weder jede Verschlüsselung brechen noch einfach sämtliche Schlüssel gleichzeitig ausprobieren.

Trotzdem gibt es ein echtes Problem. Um es zu verstehen, müssen wir uns zunächst ansehen, worauf ein Teil der heutigen Verschlüsselung beruht.

Von HTTPS zu zwei PrimzahlenWenn wir eine Website über https:// aufrufen, wird die Verbindung durch Transport Layer Security (TLS) geschützt. TLS sorgt unter anderem dafür, dass Dritte die übertragenen Daten nicht einfach mitlesen oder unbemerkt verändern können.

Dafür verwendet TLS nicht nur ein einziges Verfahren, sondern mehrere. Dazu gehören auch sogenannte asymmetrische Verfahren.

Eines dieser Verfahren ist Rivest–Shamir–Adleman (RSA). Nicht jede TLS-Verbindung verwendet RSA. RSA zeigt aber besonders anschaulich, wo ein Quantencomputer gefährlich werden könnte.

Für RSA werden zunächst zwei sehr große Primzahlen miteinander multipliziert. Das Ergebnis darf öffentlich bekannt sein. Die beiden Primzahlen selbst müssen jedoch geheim bleiben.

Der Weg in die eine Richtung ist einfach:

Primzahl × Primzahl → sehr große ZahlDer Rückweg ist wesentlich schwieriger:

sehr große Zahl → welche beiden Primzahlen?Wer nur das Ergebnis kennt, muss herausfinden, welche beiden Primzahlen miteinander multipliziert wurden. Bei ausreichend großen Zahlen benötigt ein klassischer Computer dafür nach heutigem Wissen unvertretbar viel Zeit.

Auf genau diesem Unterschied beruht die Sicherheit von RSA:

Multiplizieren ist einfach. Aus dem Ergebnis wieder die beiden Primfaktoren zu bestimmen, ist sehr schwer.Könnte ein Angreifer diese Primfaktoren dennoch mit vertretbarem Aufwand finden, könnte er daraus den geheimen RSA-Schlüssel berechnen.

Genau dafür wurde ein Quantenalgorithmus entwickelt: der Shor-Algorithmus.

Ein kleines BeispielNehmen wir die Zahl:

15Ihre Primfaktoren sind:

3 × 5 = 15Bei 15 sehen wir die Lösung sofort. Bei RSA müsste ein Angreifer dagegen eine ganze Zahl mit mehreren hundert Ziffern in ihre beiden Primfaktoren zerlegen. Diese Faktoren lassen sich nicht durch einfaches Ausprobieren in brauchbarer Zeit finden.

Der Unterschied liegt nicht darin, dass eine Zerlegung mathematisch unmöglich wäre. Sie ist nur mit den besten bekannten klassischen Verfahren für ausreichend große Zahlen praktisch nicht durchführbar.

Shor probiert nicht alle Primzahlen gleichzeitig ausEine häufige Erklärung lautet:

Der Quantencomputer testet alle möglichen Primfaktoren parallel.Das wäre wieder dieselbe irreführende Vorstellung, die uns seit Episode 3 begleitet.

Eine Messung könnte aus einer solchen Superposition nur ein einzelnes Ergebnis liefern. Wir könnten nicht alle getesteten Faktoren auslesen und anschließend den passenden auswählen.

Shors Algorithmus verwendet deshalb einen anderen Weg:

Er verwandelt die Faktorisierung in die Suche nach einem periodisch wiederkehrenden Muster.Dieses Muster kann ein Quantencomputer mit einer geeigneten Gatterfolge wesentlich effizienter sichtbar machen.

Aus der Faktorisierung wird eine MustersucheWir wollen weiterhin die Faktoren von 15 bestimmen.

Zunächst wählen wir eine Zahl, die kleiner als 15 ist und keinen gemeinsamen Teiler mit 15 besitzt. Wir nehmen:

2Nun berechnen wir Potenzen von 2. Nach jeder Berechnung teilen wir durch 15 und betrachten nur den Rest:

2⁰ = 1 → Rest 1
2¹ = 2 → Rest 2
2² = 4 → Rest 4
2³ = 8 → Rest 8
2⁴ = 16 → Rest 1
2⁵ = 32 → Rest 2
2⁶ = 64 → Rest 4
2⁷ = 128 → Rest 8Die Folge der Reste wiederholt sich:

1, 2, 4, 8, 1, 2, 4, 8, ...Nach vier Schritten beginnt dasselbe Muster erneut.

Die Periode dieser Folge beträgt deshalb:

r = 4Diese Periode enthält die Information, aus der sich die Faktoren von 15 gewinnen lassen.

Wie wird aus der Periode ein Primfaktor?Wir verwenden die gewählte Zahl 2 und die gefundene Periode 4:

2^(r ÷ 2)
= 2²
= 4Nun betrachten wir:

4 − 1 = 3
4 + 1 = 5Der größte gemeinsame Teiler von 3 und 15 ist 3.

Der größte gemeinsame Teiler von 5 und 15 ist 5.

Damit erhalten wir:

15 = 3 × 5Das funktioniert nicht bei jeder zufälligen Wahl sofort. Manche gewählten Zahlen oder gefundenen Perioden liefern keinen brauchbaren Faktor. Dann wird der Ablauf mit einer anderen Wahl wiederholt.

Entscheidend ist:

Wenn eine geeignete Periode gefunden wurde, lassen sich die Primfaktoren anschließend mit klassischen Rechenschritten bestimmen.Der schwierige Teil ist also nicht mehr die direkte Suche nach den Primfaktoren. Der schwierige Teil ist das Finden der Periode.

Welchen Teil übernimmt der Quantencomputer?Shors Algorithmus ist kein rein quantisches Programm. Klassischer Computer und Quantencomputer teilen sich die Arbeit.

Der klassische Computer:

• wählt eine geeignete Ausgangszahl,
• baut daraus die Quantenschaltung,
• startet die Berechnung,
• wertet das Messergebnis aus,
• berechnet daraus die Periode und mögliche Faktoren,
• wiederholt den Ablauf, wenn kein Faktor entsteht. Der Quantencomputer übernimmt den Teil, für den er einen Vorteil bieten kann:

Er erzeugt aus der periodischen Struktur ein Amplitudenmuster, aus dem sich die Periode mit hoher Wahrscheinlichkeit bestimmen lässt.Wie wird die Periode in den Quantenzustand eingebaut?Wir verwenden vereinfacht zwei Qubit-Register.

Das erste Register stellt mögliche Exponenten dar:

0, 1, 2, 3, 4, 5, 6, 7, ...Das zweite Register nimmt den zugehörigen Rest der Potenzrechnung auf:

Exponent 0 → Rest 1
Exponent 1 → Rest 2
Exponent 2 → Rest 4
Exponent 3 → Rest 8
Exponent 4 → Rest 1
...Zunächst erzeugt die Schaltung im ersten Register eine Superposition der möglichen Exponenten. Danach berechnet eine reversible Quantenschaltung zu jedem Exponenten den zugehörigen Rest.

Der gemeinsame Zustand enthält dadurch Amplituden für zusammengehörige Paare:

Exponent 0 mit Rest 1
Exponent 1 mit Rest 2
Exponent 2 mit Rest 4
Exponent 3 mit Rest 8
Exponent 4 mit Rest 1
...Damit ist das Muster zwar im Quantenzustand enthalten. Wir können die Liste aber nicht einfach auslesen. Eine Messung würde weiterhin nur ein einzelnes Ergebnis liefern.

Die Gatterfolge muss das periodische Muster deshalb vor der Messung in eine messbare Form umwandeln.

Interferenz macht die Periode sichtbarDafür verwendet Shors Algorithmus eine festgelegte Gatterfolge, die Quanten-Fourier-Transformation.

Der Name klingt komplizierter als ihre Aufgabe in unserem Zusammenhang:

Sie verändert die Amplituden so, dass Beiträge, die zur regelmäßigen Wiederholung passen, einander verstärken und andere Beiträge sich abschwächen.Wir kennen das Prinzip bereits:

gleiche Ausrichtung → Amplituden verstärken sich

entgegengesetzte Ausrichtung → Amplituden schwächen sich abDie Quanten-Fourier-Transformation erfindet die Periode nicht und sucht nicht nach einem gewünschten Ergebnis. Ihre Gatter sind so konstruiert, dass eine im Zustand vorhandene regelmäßige Wiederholung bestimmte messbare Spitzen im Amplitudenmuster erzeugt.

Eine Messung liefert anschließend nicht direkt den Satz:

Die Periode ist 4.Sie liefert einen Zahlenwert, aus dem der klassische Teil des Algorithmus einen Kandidaten für die Periode berechnet. Je nach Messergebnis kann die Schaltung mehrfach ausgeführt werden.

Der vollständige Ablauf lautet damit:

Zahl auswählen
→ Superposition möglicher Exponenten erzeugen
→ Potenzreste berechnen
→ periodische Struktur im Quantenzustand erhalten
→ Amplituden mit der Quanten-Fourier-Transformation verändern
→ messen
→ Periode klassisch bestimmen
→ Primfaktoren klassisch berechnenWarum ist das für große Zahlen so bedeutend?Für kleine Zahlen ist Shors Algorithmus nutzlos. Ein klassischer Computer zerlegt 15 ohne Mühe in 3 × 5.

Der Unterschied zeigt sich bei sehr großen Zahlen.

Der Aufwand klassischer Faktorisierungsverfahren wächst so stark, dass ausreichend große RSA-Schlüssel praktisch nicht zerlegt werden können.

Shors Algorithmus verändert nicht nur die Geschwindigkeit um einen festen Faktor. Sein Aufwand wächst grundsätzlich günstiger mit der Größe der Zahl.

Das ist der Unterschied zwischen:

dieselbe Aufgabe etwas schneller lösenund:

für die Aufgabe ein grundsätzlich günstigeres Verfahren besitzenEin ausreichend großer, fehlertoleranter Quantencomputer könnte deshalb Zahlen faktorisieren, die für klassische Computer praktisch unerreichbar sind.

Bedeutet das das Ende von TLS?Nein.

TLS ist kein einzelnes Verschlüsselungsverfahren. Es ist ein Protokoll, das verschiedene Verfahren für Authentifizierung, Schlüsselaustausch und die anschließende geschützte Datenübertragung kombiniert.

RSA ist außerdem nicht das einzige Verfahren mit einem solchen mathematischen Angriffspunkt. Moderne Systeme verwenden häufig Verfahren auf Basis elliptischer Kurven. Sie beruhen auf einer anderen mathematischen Aufgabe als RSA. Auch für diese Aufgabe beschreibt Shors Algorithmus einen günstigeren Rechenweg als die heute bekannten klassischen Verfahren.

Das bedeutet zunächst nur:

Bestimmte Verfahren, die TLS heute verwenden kann, wären mit einem ausreichend leistungsfähigen Quantencomputer angreifbar.Ob daraus ein praktischer Angriff wird, ist eine zweite Frage.

Wie könnte ein wirklicher Angriff aussehen?Ein Quantencomputer würde nicht das gesamte Internet auf einmal entschlüsseln. Er müsste einen bestimmten öffentlichen Schlüssel verarbeiten und die dazugehörige mathematische Aufgabe lösen.

Bei einem länger verwendeten öffentlichen RSA-Schlüssel könnte eine erfolgreiche Faktorisierung genügen, um den zugehörigen geheimen Schlüssel zu berechnen. Die aufwendige Quantenberechnung müsste dann nicht für jede Verbindung erneut ausgeführt werden.

Bei Verfahren, die für jede Verbindung neue Schlüsselwerte erzeugen, sieht es anders aus. Dann müsste der Angreifer die jeweilige mathematische Aufgabe für die betreffende Verbindung lösen. Für eine Manipulation während des Verbindungsaufbaus müsste das rechtzeitig geschehen. Sollen lediglich aufgezeichnete Daten später untersucht werden, darf die Berechnung länger dauern.

Eine Quantenberechnung bearbeitet dabei nicht automatisch Millionen Verbindungen gleichzeitig. Wenn eine Maschine für einen Schlüssel mehrere Tage benötigt, ist sie während dieser Zeit im Wesentlichen mit dieser Aufgabe beschäftigt. Viele gleichzeitige Angriffe würden entsprechend viele Maschinen oder erheblich mehr parallel arbeitende Quantenhardware verlangen.

Wie groß müsste ein solcher Quantencomputer sein?Das weiß heute niemand genau. Die benötigten Ressourcen hängen von der Bauart der Qubits, ihrer Fehlerrate, der Fehlerkorrektur, der Geschwindigkeit der Gatter und vom verwendeten Quantenschaltkreis ab.

Eine Modellrechnung des Quantenforschers Craig Gidney aus dem Jahr 2025 kommt unter bestimmten technischen Annahmen zu folgendem Ergebnis:

Aufgabe: die Zahl eines RSA-2048-Schlüssels faktorisieren
Qubits: weniger als eine Million physische Qubits
Rechenzeit: weniger als eine WocheDas ist keine Beschreibung einer vorhandenen Maschine. Es ist eine Hochrechnung für einen Quantencomputer, der erst noch gebaut werden müsste. Die Annahmen betreffen unter anderem Fehlerraten, Reaktionszeiten und die Geschwindigkeit der Fehlerkorrektur.

Quelle: Craig Gidney: How to factor 2048 bit RSA integers with less than a million noisy qubits

Aus der Zahl der Qubits lassen sich weder die Abmessungen noch der Preis einer solchen Anlage zuverlässig ableiten. Zusätzlich zu den Qubits wären Steuerungselektronik, Kühlung und eine gewaltige Infrastruktur für die Fehlerkorrektur erforderlich. Da diese Maschine nicht existiert, gibt es auch keinen belastbaren Kaufpreis und keine gemessene Zahl gleichzeitig angreifbarer Verbindungen.

Damit ist RSA mathematisch durch Shor bedroht. Daraus folgt aber nicht, dass RSA heute praktisch gebrochen oder jede TLS-Verbindung plötzlich unbrauchbar wäre.

TLS kann zudem auf andere kryptografische Verfahren umgestellt werden.

Warum beginnt die Umstellung schon heute?Ein Quantencomputer, der aktuelle große Schlüssel praktisch angreifen könnte, steht heute nicht zur Verfügung.

Trotzdem wäre es falsch, mit der Umstellung bis zu seinem Bau zu warten.

Verschlüsselte Kommunikation kann heute aufgezeichnet und viele Jahre gespeichert werden:

heute aufzeichnen
→ später leistungsfähigen Quantencomputer besitzen
→ alte Kommunikation nachträglich angreifenDieses Risiko wird Harvest now, decrypt later genannt: jetzt sammeln, später entschlüsseln.

Für Daten, die nur wenige Minuten vertraulich bleiben müssen, ist das möglicherweise unerheblich. Medizinische Daten, staatliche Informationen, Geschäftsgeheimnisse oder langfristig gültige Identitäten können jedoch auch in vielen Jahren noch schützenswert sein.

Post-Quantum-Kryptografie benötigt keinen QuantencomputerAls Ersatz werden Verfahren entwickelt, deren Sicherheit nicht auf den durch Shor angreifbaren Problemen beruht.

Sie werden Post-Quantum-Kryptografie genannt.

Der Name ist leicht missverständlich. Diese Verfahren laufen auf gewöhnlichen Computern:

klassischer Computer
→ post-quanten-sicheres Verfahren
→ Schutz gegen bekannte QuantenangriffeDas US-amerikanische National Institute of Standards and Technology, kurz NIST, hat 2024 die ersten drei entsprechenden Standards veröffentlicht:

• ML-KEM für die Vereinbarung beziehungsweise Kapselung gemeinsamer Schlüssel,
• ML-DSA für digitale Signaturen,
• SLH-DSA als weiteres Signaturverfahren auf einer anderen mathematischen Grundlage. Diese Standards bedeuten nicht, dass jede Verbindung bereits umgestellt ist. Protokolle, Software, Zertifikate, Hardware und organisatorische Abläufe müssen die neuen Verfahren unterstützen.

Die Migration hat jedoch bereits begonnen.

Warum baut man nicht einfach längere RSA-Schlüssel?Ein längerer RSA-Schlüssel erhöht auch für einen Quantencomputer den Aufwand. Er ändert aber nichts daran, dass Shors Algorithmus für die Faktorisierung einen grundsätzlich günstigeren Rechenweg beschreibt als die heute bekannten klassischen Verfahren.

Noch größere RSA-Schlüssel würden außerdem:

• mehr Rechenzeit benötigen,
• größere Schlüssel und Signaturen erzeugen,
• bestehende Systeme stärker belasten,
• das zugrunde liegende Problem nicht beseitigen. Die dauerhafte Lösung besteht deshalb nicht in immer größeren RSA-Schlüsseln, sondern im Wechsel zu anderen mathematischen Verfahren.

Die korrekte AussageDie Behauptung

Quantencomputer können die Verschlüsselung des Internets brechen.ist zu pauschal.

Genauer lautet sie:

Ein ausreichend großer, fehlertoleranter Quantencomputer könnte mit Shors Algorithmus bestimmte heute verwendete asymmetrische Verfahren angreifen. Wie viele Schlüssel er in welcher Zeit berechnen könnte, hinge von seiner tatsächlichen Größe, Bauart und Leistung ab. Eine dafür geeignete Maschine existiert heute nicht.Das ist weniger spektakulär als die Schlagzeile. Es ist aber immer noch eine bedeutende technische und organisatorische Herausforderung.

Mit einem Missverständnis aufräumen*Missverständnis:* Sobald es leistungsfähige Quantencomputer gibt, wird jede verschlüsselte Internetverbindung automatisch lesbar.Ein Quantencomputer entschlüsselt nicht automatisch jede Verbindung. Shors Algorithmus beschreibt einen günstigeren Rechenweg für bestimmte mathematische Aufgaben, auf denen einige asymmetrische Verfahren beruhen.

Andere Verfahren sind anders betroffen. TLS kann neue kryptografische Verfahren verwenden, und die Umstellung auf Post-Quantum-Kryptografie hat bereits begonnen.

Die Gefahr ist deshalb real, aber weder universell noch unvermeidbar.

Was wir jetzt wissen- TLS verwendet mehrere kryptografische Verfahren.

• RSA beruht unter anderem darauf, dass große Zahlen klassisch nur mit gewaltigem Aufwand faktorisiert werden können.
• Shors Algorithmus probiert nicht einfach alle Primfaktoren parallel aus.
• Er verwandelt die Faktorisierung in die Suche nach einer Periode.
• Die periodische Struktur wird in einem gemeinsamen Quantenzustand erzeugt.
• Die Quanten-Fourier-Transformation macht diese Struktur durch Interferenz messbar.
• Aus dem Messergebnis bestimmt ein klassischer Computer die Periode und daraus mögliche Faktoren.
• Shors Algorithmus lässt sich auch auf die mathematische Grundlage verbreiteter Verfahren mit elliptischen Kurven anwenden.
• Ein kryptografisch relevanter Angriff benötigt einen großen, fehlertoleranten Quantencomputer.
• Post-Quantum-Kryptografie läuft auf klassischen Computern.
• Die Umstellung kann erfolgen, bevor ein solcher Quantencomputer existiert. Quantencomputer sind damit weder universelle Supercomputer noch bloße Forschungsspielzeuge. Sie können für einzelne, genau passende mathematische Probleme einen grundlegend anderen Rechenweg ermöglichen. Gerade deshalb muss jede Behauptung über ihre Leistung mit derselben Frage beginnen:

Welcher Algorithmus löst welches Problem — und welche reale Hardware wäre dafür erforderlich?In Episode 12 ziehen wir Bilanz. Wir trennen die tatsächlichen Fähigkeiten von Quantencomputern von den Behauptungen, die daraus gemacht werden. Dabei betrachten wir, welche Voraussetzungen in Meldungen über einen „Quantenvorteil“ häufig fehlen, was heute Forschung, Demonstration oder bereits praktische Anwendung ist — und mit welchen fünf Fragen sich solche Meldungen überprüfen lassen.