Post-Quanten-Kryptographie


Unter dem Begriff der Post-Quanten-Kryptographie (englisch post-quantum cryptography, PQC) fallen kryptographische Bausteine und Verfahren, die selbst beim Einsatz von Quantencomputern nicht zu entschlüsseln sind. Der Begriff post-quantum cryptography geht auf Daniel J. Bernstein zurück1 und wird immer relevanter, das sich im Bereich der Quantencomputer von Jahr zu Jahr mehr tut. Angeblich kauften im Mai 2013 die Raumfahrtagentur NASA und der Suchmaschinenbetreiber Google den angeblich ersten funktionierenden Quantencomputer der Firma D-Wave Systems.2 Erst im März 2018 stellt dann Google mit Bristlecone, den neusten Quanten-Prozessor vor. 3 Warum das alles für die Kryptographie relevant ist? Experten gehen davon aus, dass solche Quantencomputer eine ersten Gefahr für die weitverbreiteten Public-Key-Verfahren sind. Damit wären Schlüsselaustausch und digitale Signaturen anfällig für Angriffe.


Der sogenannte Shor-Algorithmus erlaubt es in Kombination mit leistungsfähigen Quantencomputern asymmetrischen Kryptosysteme zu brechen. Die aktuelle Stärke, das Beruhen auf der Schwierigkeit der Primfaktorzerlegung(z.B. RSA) und der Berechnung diskreter Logarithmen (z.B. Diffie-Hellmann-Schlüsseltausch, den IPSec oder TLS verwendet), könnte dann ihre Schwäche werden.


Gegenüber der Computerzeitschrift c‘t äußerte sich der Quanteninformatiker und Mitbegründer des Institute for Quantum Computing an der Universtät Waterloo, Michele Mosca, dahingehend, dass mit einer Wahrscheinlichkeit von 1:7 im Jahr 2026 Quantencomputer soweit entwickelt sind, dass sie heutige kryptografische Verfahren brechen können. Bis zum Jahr 2031 soll sich die Wahrscheinlichkeit sogar auf 1:2 erhöhen.4



Die Post-Quanten-Kryptographie beschäftigt sich mit kryptografischen Ansätzen, die sich den neuen Herausforderungen, die durch die Quantencomputer entstehen, annehmen sollen. Diese lassen sich unter anderem in die folgenden Gruppen einteilen:

  • Code-basierte Verfahren (z.B. McEliece-Kryptosystem)
  • Hash-basierte Verfahren (z.B. XMSS,Merkle-Signaturverfahren oder SPHINCS)
  • Lattice-basierte Verfahren (z.B. New Hope-Algorithmus)
  • Multivariat-basierte Verfahren
  • Isogenie-basierte Verfahren

Standardisiert ist aber bisher kein quantencomputerresistente kryptographische Verfahren, so ist es auch kein Wunder, dass in der technischen Richtlinie „BSI TR-02102 Kryptographische Verfahren: Empfehlungen und Schlüssellängen“ vom Bundesamt für Sicherheit in der Informationstechnik (BSI) auch nur heißt:


„Quantencomputerresistente kryptographische Verfahren werden in der vorliegenden Technischen Richtlinie mit Ausnahme von Merkle-Signaturen nicht behandelt, weil diese Verfahren derzeit erst die Phase der Standardisierung erreichen. Da die Entwicklung von Quantencomputern ein aktives Forschungsgebiet ist, müssen die weiteren Fortschritte beobachtet werden.“5

Quantencomputer gefährden asymmetrische Verfahren

Quantencomputer sind dabei nicht unbedingt schneller als heutige Computer, sie funktionieren nur grundsätzlich anders und entfalten damit bei bestimmten Aufgabenstellungen ihr ganzes Potential. So kann ein heutiges Bit in einem Computer nur zwei Zustände annehmen, entweder 0 oder 1. Ein Qubit eines Quantencomputers kann hingegen unendlich viele Zustände zwischen 0 und 1 annehmen (Superposition). Darüber hinaus können sich diese Qubits auch miteinander verbinden, wodurch ein Quantencomputer einen riesigen Zustandsraum abdecken kann. Bei Problemen, wie der Faktorisierung großer Zahlen (z.B. via Shor-Algorithmus) oder bei Suchalgorithmen (z.B. via Grover‘s Algorithmus – je größer die Datenbank die durchsucht werden muss, desto größer der Zeitvorteil zu normalen Computern) arbeiten Quantencomputer damit deutlich schneller als normale Computer.


Eine Erhöhung der Schlüssellänge würde bei den heutigen asymmetrischen Verfahren übrigens nicht viel bringen. Die Zahl der erforderlichen Qubits würden für einen Angreifer nur linear steigen und auch der Zeitbedarf nur unwesentlich erhöhen. Die Verfahren wären hingegen bei einer benötigten erhöhten Schlüssellänge schlichtweg nicht mehr praktikabel. Es müssen also neue Verfahren her.

Symmetrische Verfahren nicht so stark betroffen

Im Gegensatz zu asymmetrischen Verfahren stellen Quantencomputer für symmetrische Verschlüsselungsverfahren,wie beispielsweise AES, nicht eine ganz so große Bedrohung dar. Hier reicht es, wenn man die Schlüssellänge entsprechend verlängert, da sich deren Schutzwirkung nur um die Hälfte reduziert. Eine AES-Verschlüsselung mit 256 Bit (AES-256) hätte damit nur noch eine Schutzwirkung wie AES 128 hat, also die Version, die mit 128-Bit-Keys arbeitet.


Nun kann man aber nicht einfach die gefährdeten asymmetrischen Verfahren durch die symmetrischen Verfahren austauschen, da man damit wieder das Problem des Schlüsselaustauschs hätte. Da der Schlüssel bei symmetrischen Verfahren von Sender und Empfänger gleich sind, muss dieser sicher über einen öffentlichen Kanal übertragen werden. Genau hier haben asymmetrische Verfahren mit ihrer Public-Key-Verschlüsselung unterstützt. Fällt diese weg, wären auch symmetrische Verfahren in vielen Fällen nicht mehr praktikabel umsetzbar.

Leistungesfähige Quantencomputer bisher nur in der Theorie

Bisher ist es nur in der Theorie möglich einen leistungsfähigen Quantencomputer zu bauen. Aktuelle Systeme sind noch sehr anfällig, kaum leistungsfähig und funktionieren nur unter extremen Bedingungen. So benötigen sie aktuell beispielsweise noch extreme Kälte, wenige Grad über dem absoluten Nullpunkt, um überhaupt lauffähig zu sein.

Schon jetzt ein Thema

Warum man sich, obwohl es noch keine leistungsfähige Quantencomputer gibt, dennoch schon mit der Post-Quantenkryptographie auseinandersetzen sollte, ist die Tatsache, dass Quantencomputer auf jeden Fall kommen werden. Und bis zu diesem Zeitpunkt können alle von Geheimdiensten und anderen Organisationen gesammelten, verschlüsselten Informationen und Dokumente rückwirkend entschlüsselt werden. Wer also heute geheime Daten verschicken möchte, die auch in einigen Jahren nicht entschlüsselt werden soll, der sollte sich lieber zwei Mal Gedanken machen, über welchen Weg er die Daten austauscht.

Video: (Post-Quantum) Isogeny Cryptography von 36c3

Anbei noch ein etwas aktuelleres Video vom 27.12.2019. Im Vortrag erfährt man mehr zu Isogenie-basierte Verfahren in der Post-Quantum Kryptographie.

Quellen und Verweise



Artikel zuletzt aktualisiert am 28.12.2019.

Das könnte dich auch interessieren: