Post-Quanten-Kryptografie

Quantencomputer sind in aller Munde – sie sollen das Tempo von Berechnungen massiv steigern. Doch kaum jemand weiß, was sich hinter diesem Begriff verbirgt.

Was sind Quantencomputer eigentlich?

Ein gewöhnlicher Computer arbeitet nach dem binären Zahlensystem. Register und Speicherelemente können immer nur genau einen der Zustände „0“ oder „1“ annehmen. Mithilfe der booleschen Algebra lassen sich daraus Verfahren entwickeln, nach denen Computer Programme abarbeiten.

Quantencomputer haben ebenfalls Speicherelemente – Qubits genannt –, die die Zustände „0“ und „1“ annehmen können. Das kann beispielsweise der Drehimpuls eines einzelnen Elektrons sein („Spin“).

Im Unterschied zu klassischen Computern können die Qubits nicht nur entweder „0“ oder „1“ sein, sondern auch beide Zustände gleichzeitig oder sogar noch ganz andere Zustände annehmen.

Durch diese Gleichzeitigkeit vieler Zustände lassen sich Rechenoperationen mit sehr vielen unterschiedlichen Eingabegrößen parallel ausführen.

Ein konkretes Beispiel macht den Unterschied deutlich: Soll etwa ein hochauf­lösendes Bild Pixel für Pixel von einem Zustand in einen anderen umgerechnet werden – z.B. um Helligkeit und Kontrast zu ändern –, würden konventionelle Computer das Bild Pixel für Pixel umrechnen.

Eine Parallelität in der Berechnung und damit eine Steigerung der Geschwindigkeit ist nur durch die Aufteilung auf mehrere Prozessoren möglich. Bei Quantencomputern könnte ein einzelner Quantenprozessor viele Pixel gleichzeitig umrechnen, je nachdem, wie viele Zustände die Qubits annehmen können.

Damit lässt sich eine aus heutiger Sicht unglaubliche Parallelität und damit Steigerung der Rechengeschwindigkeit erreichen.

Folgen für bestehende Verschlüsselungsverfahren

Was hat das für Auswirkungen auf die Sicherheit von Verschlüsselungsverfahren?

Verschlüsselungsverfahren gelten als sicher, wenn es keinen anderen Weg zum Knacken eines Schlüssels gibt, als stur alle Möglichkeiten auszuprobieren – was auch Brute-Force genannt wird.

Dieses sture Ausprobieren ist aber genau ein Fall für Quantencomputer mit ihrer extrem hohen Parallelität. Brute-Force-Angriffe dauern dann nicht mehr Millionen von Jahren, sondern nur noch Stunden oder Tage.

Allerdings sind die Auswirkungen von Quantencomputern auf die Verschlüsselungsverfahren, die aktuell im Einsatz sind, sehr unterschiedlich.

PKI am Ende

Besonders hart treffen Quantencomputer die Verschlüsselungsverfahren, die mit zwei Schlüsseln arbeiten, also die Public-Key-Infrastruktur (PKI) mit einem privaten und einem öffentlichen Schlüssel.

Die aktuellen Verfahren verfolgen einen Grundsatz, der bisher immer funktioniert hat, nun aber fraglich geworden ist: Man nehme eine mathematische Funktion und ihre Umkehrfunktion (also z.B. Addition und Subtraktion).

Mathematische Funktionen sind für Verschlüsselung geeignet, wenn die Funktion leicht zu berechnen ist, die Umkehrfunktion aber extrem schwer. Addition und Subtraktion sind also für Verschlüsselung eher ungeeignet.

Eine Funktion, die dagegen für die Verschlüsselung geeignet ist, ist beispielsweise die Multiplikation sehr großer Primzahlen, wie sie das RSA-Verfahren nutzt.

Soll ein Schlüsselpaar erzeugt werden, multipliziert das RSA-Verfahren sehr große Primzahlen miteinander. Daraus ergeben sich nach einigen weiteren Berechnungen die beiden Schlüssel.

Ein Angreifer, der aus dem öffentlichen Schlüssel eines Benutzers dessen privaten Schlüssel berechnen will, braucht mit herkömmlichen Computern viel Geduld.

Das Zerlegen von riesengroßen Zahlen in ihre Primfaktoren ist zwar ein Standard-Problem der Mathematik, aber nach wie vor sehr rechenintensiv. Quantencomputer würden das Verfahren komplett aushebeln.

Aus auch für Diffie-Hellman-Verfahren und ECC

Ein anderes Verfahren, dem das Aus droht, ist das Diffie-Hellman-Verfahren. Es wird weltweit für den Austausch von Schlüsseln genutzt.

Hier ist das „einfache“ Verfahren, mit dem beide Seiten sich den gemeinsamen Schlüssel berechnen, die Exponenzialfunktion. Ein Angreifer, der aus der mitgehörten Kommunikation der Partner den Schlüssel ermitteln will, muss die Umkehrfunktion, also den Logarithmus berechnen. Das ist sehr rechenintensiv, zumindest so lange, bis die Quantencomputer kommen.

Ein drittes Verfahren, das vor dem Aus steht, ist die Elliptic-Curve-Cryptography (ECC). Von ihr hatte man sich viel versprochen, da ECC mit deutlich geringeren Schlüssellängen auskommt als beispielsweise RSA.

Allerdings hat ECC dasselbe Problem wie RSA oder Diffie-Hellman. Es gibt eine einfache mathematische Operation – in diesem Fall die Multiplikation zweier Zahlen auf einer elliptischen Kurve – und eine schwierige Operation – die Division. Beides lässt sich aber dank Quantencomputern schnell durchführen.

Die Auswirkungen von Quantencomputern auf symmetrische Verschlüsselungsverfahren mit nur einem Schlüssel zur Ver- und Entschlüsselung sind unklar.

Mathematiker schätzen, dass sich die effektive Schlüssellänge in etwa halbiert. Aus einem AES (Advanced Encryption Standard)mit 256 Bit Schlüssellänge werden dann 128 Bit – was für heutige Bedürfnisse ausreicht.

Aber wie es sich genau verhält, lässt sich erst sagen, wenn ein funktionierender Quantencomputer zur Verfügung steht.

Ähnlich verhält es sich mit den Hashverfahren, also den kryptografisch abgesicherten Prüfsummen Sie sind für digitale Signaturen wichtig.

Man rechnet damit, dass ein Angreifer seine Attacken quadratisch beschleunigen kann. SHA-512 würde dann noch ausreichen. Aber: Niemand weiß Genaues.

Verschlüsselungsalgorithmen der Zukunft

Aufgrund der derzeit unklaren und gefährlichen Situation arbeiten Mathematiker und Kryptologen schon seit Jahren daran, Verschlüsselungsverfahren zu entwickeln, die auch im Zeitalter von Quantencomputern noch sicher sind.

Da niemand weiß, wann Quantencomputer aus dem Laborstadium zu fertigen Produkten werden, müsste man schon Algorithmen in der Hinterhand haben, um sie schnell auszurollen und zu aktivieren. Denn wenn in ca. zehn bis 15 Jahren die ersten Quantencomputer verfügbar sind, werden viele Verschlüsselungsverfahren gebrochen.

Wie werden die Verschlüsselungsalgorithmen der Zukunft aussehen? Die Idee mit der schwierigen und der leichten mathematischen Funktion hat sich jedenfalls erledigt.

Eine Möglichkeit wäre, PKI-Verfahren mit symmetrischen Komponenten „anzureichern“, die ja nicht so anfällig sind. Besser ist es aber, ganz neue Verfahren zu entwickeln, die so gestaltet sind, dass Quantencomputer ihre Fähigkeit zur massiven Parallelverarbeitung nicht ausspielen können.

Hier arbeiten Wissenschaftler seit Jahren an möglichen Verfahren. Das Problem ist aber, dass niemand derzeit genau weiß, wie letztlich ein Quantencomputer aussieht und was er für Stärken und Schwächen hat. Trotzdem wird die Entwicklung weitergehen.

WICHTIG: Wer heute vertrauliche Daten länger als 15 Jahre schützen will, müsste eigentlich bereits auf neue Algorithmen umstellen.

Das tut aber niemand, und so freuen sich die Geheimdienste.

Die National Security Agency (NSA) sammelt schon jetzt verschlüsselte Daten, in der Gewissheit, sie in einigen Jahren mit einem Quantencomputer knacken zu können.

Entwarnung bei symmetrischen Verfahren, aber …

Bei den symmetrischen Verfahren mit einem Schlüssel muss man sich keine großen Sorgen machen. Die Schlüssellänge zu verdoppeln, sollte ausreichen, um dieselbe Sicherheit zu gewährleisten.

Bei Hash- und Public-Key-Verfahren gibt es einige Ansätze zu Quanten-resistenten Algorithmen. Sie haben aber den Nachteil, dass die Schlüssel sehr groß sind.

So benötigt etwa das McEliece-Verfahren eine Länge des privaten Schlüssels von etwa 1 MByte. Damit sind Nicht-Quanten-Systeme wie normale PCs, Tablets oder Smartphones überfordert. Wer dann von seinem Smartphone eine digital signierte Mail verschicken will, kann erstmal eine Kaffeepause machen.

Hier ist also noch einiges an theoretischen Vorarbeiten nötig, um Verschlüsselung auch im Zeitalter von Quantencomputern sicherzustellen.

Dr.-Ing. Markus a Campo