Mal was für die ganz Harten

Über IT-Sicherheit in Form von Verschlüsselung macht man sich keinen Kopf. Es sei denn, der  BND oder die NSA hören einen ab. Aber auch dann regt man sich allenfalls auf, dass doch tatsächlich jemand den 3 Stunden unbeaufsichtigt auf die Mauer gelegten 500 €-Schein mitgenommen hat, macht sich aber immer noch keinen Kopf. Verschlüsselung von Emails, das würde mindesten 2 zusätzliche Mausklickes erfodern, wenn überhaupt! Wo kommen wir denn da hin, wenn das einreißen würde?

Wenn man trotzdem mal auf solche Möglichkeiten hinweist, kommt in der Regel ein kecker 1-Semester-Studi, der noch Reste der Eischale auf dem Kopf hat und belehrt den Vortragenden „RSA? Da hole ich mir einen Quantencomputer, und das war’s dann! Also warum sich mit solcher Technik beschäftigen?“ So so, Söhnchen! Dann reden wir mal Klartext:

Asymmetrische Verschlüsselungssysteme, die Grundlage der heutigen Verschlüsselungs- und Signaturprotokolle, basieren auf der technischen Nichtlösbarkeit bestimmter algebraischer Operationen auf endlichen Körpern mit konventionellen Computern (die Details – Ringe und Körper über ganzen Zahlen, Polynomen über Körpern oder erweitert rationalen Polynomkörpern, Körpern auf elliptischen Kurven oder, wem das nicht genügt, hyperelliptischen Kurven, usw – lasse ich mal weg, um niemanden zu verwirren). Für bestimmte Operationen sind nur Lösungen bekannt, die einen exponentiell mit der Anzahl der verwendeten Bits steigenden Aufwand erfordern, andere Operationen sind ohne Kenntnis bestimmter Nebenbedingungen mit dem gleichen Problem behaftet.

1994 entwickelte Peter Shor einen Algorithmus für (nur in der Theorie existierende) Quantencomputer, der das Problem beseitigt, da der Aufwand „nur“ polynomial und nicht mehr exponentiell mit der Bitanzahl steigt. 2001 konnte das Prinzip experimentell verifiziert werden – für die Faktorisierung der Zahl 15. Seitdem nimmt das Thema „Quantencomputer“ und Sicherheit der Verschlüsselung besonders in populärwisschenschaftlichen Medien einen breiten Raum ein. Neben den Bemühungen, einen Quantencomputer zu konstruieren, laufen Bestrebungen, Algorithmen zu konstruieren, die nicht angreifbar sind. Immer wieder wird gemutmaßt, Geheimdienste wie die NSA (oder gewisse 1-Semester-Studis) verfügten bereits über Quantencomputer und könnten die gebräuchliche Verschlüsselung angreifen (bei der Klausur war er nicht so gut, also hat er ihn wohl noch nicht, denn sonst hätte er ja meine Mails mit den Klausuren gelesen).

Technisch wären dazu Quantencomputer notwendig, die bei heute gebräuchlichen Schlüsseln von 2.048 Bit über ca. 6.150 Qbits verfügen müssen. Da bei dieser Größenordnung eine Quantenkontrolle und/oder Korrektur notwendig ist, weil das System durch Wechselwirkung mit der Umgebung oder einfach aus statistischen Gründen gewissermaßen auseinander fällt (man nennt das Dekohärenz), erhöht sich die Zahl etwa auf 20.000 – 332.100 Qbit, je nach Ansatz und Qualitätsvorstellungen. Das ist übringens die Registerbreite der Quanten-CPU, weil Quantencomputer nur über CPU-Register, aber keinen RAM verfügen.

Der Quantencomputer liefert nicht etwa die gesuchten Schlüssel in einer Rechnung, sondern nur mit einer Wahrscheinlichkeit, die in etwa proprotional zu Anzahl der Bits ist,  eine Lösung (vorausgesetzt, die Rechnung kann bis zu Ende durchgeführt werden, ohne dass das System dekohärent wird), die in einem aufwändigen Zusatzschritt mittels eines herkömmlichen Computers ausgewertet werden muss und sich Kettenbrüchen bedient, was vermutlich die meisten erst einmal nachschlagen müssen, um herauszubekommen, was das wohl ist. Der Rechenaufwand auf dem klassischen Computer ist etwa kubisch in der Zahl der Bits, d.h. die Rechenzeit steigt mit der dritten Potenz, wenn die Anzahl der Bits erhöht wird. Benötigt man für 1.024 Bits beispielsweise 1 h Rechenzeit, sind das bei 2.048 Bits bereits 8 h und bei 4.096 Bits 64 h. Das ist zwar nicht mehr exponentiell, sondern polynomial, aber immer noch Aufwand.

Auch der Rechenaufwand für den Quantencomputer zur Erzeugung eines Ergebnisses ist nicht exponentiell, sondern ebenfalls kubisch in der Zahl der zu verarbeitenden Bits (merkwürdig: die Energieausbeute bei Windkraftwerken ist auch kubisch in der Windgeschwindigkeit. Ob das der Grund ist, weshalb Windenergie ebenfalls nicht funktioniert?). Für den Quantenalgorithmus alleine sind im Standardmodell somit O(20483) d.h. ca 100 Mrd.  Operationen notwendig (ohne Kontrollbits!), was zu Ausführungszeiten führt, die nahe an der maximalen statistischen Lebensdauer der Quantenzustände liegen. Die Zeiten kann in Abhängigkeit vom Quantensystem mit Hilfe der Heisenbergschen Unschärferelation berechnet werden, und an den Werten gibt es nichts zu diskutieren, da Heisenberg schon tot ist und die Diskussion über längere Lebensdauern verweigert. Das wiederum führt dazu, dass viele Rechnungen aufgrund vorzeitiger Dekohärenz keine Lösungen liefern. Zumindest kann man das erkennen und muss den Schwachfug nicht auch noch klassisch auswerten.

Erschwerend kommt hinzu, dass jedes der Qbits im Laufe der Operationen mit jedem anderen Qbit mehrfach direkt wechselwirken muss, was mehr oder weniger bedeutet, dass die Qbits in direkten Kontakt gebracht werden müssen (wer will, kann ja mal bei Spin-Spin-Wechselwirkung nachschauen, denn das ist so das Standardmodell). Egal wie man die anordnet, ein Teil der 20.000 – 331.200 Qbits ist weit weg von dem, um das es gerade geht, und muss erst irgendwie herangekarrt werden, wozu es zwar Modellvorstellungen beim Design eines Quantencomputers gibt, was aber auf jeden Fall wieder Zeit kostet. Der Aufwand ist also enorm, die Erfolgsaussichten schwinden mit zunehmender Bitanzahl in Richtung Null – zumindest nach dem derzeitigen Stand der Kenntnisse.

Nun zum Quantencomputer unseres 1-Semesters: technisch verifiziert sind bislang Systeme mit 14 Qbits. IBM hat 2015 einen Chip vorgestellt, der auf 4 Qbits operiert (also mit denen offensichtlich alle notwendigen Sachen machen kann). Auf einem Wafer ließe sich prinzipiell die benötigte Anzahl an Qbits darstellen, jedoch scheint nach dem, was bekannt ist, eine Qbit-Qbit-Wechselwirkung im erforderlichen Umfang nicht möglich zu sein, wenn man sich die Geometrie der Schaltung anschaut (wobei ich zugeben muss, dass ich nicht alle Berechnungen der IBM-Ingenieure kenne). Ein vor einigen Jahren vorgestelltes System mit (angeblich) 512 Qbit konnte bislang wissenschaftlich nicht verifiziert werden, da die Details geheim gehalten werden (nicht wenige vermuten eine Ente, um Geldgeber zu locken, quasi eine Kaffeefahrt für zu reiche Firmen), und basiert auf einem Prinzip (Cooper-Paaren in Ultraleitern), das von der Theorie als weniger aussichtsreich eingestuft wird. Technisch ist man von einem funktionierenden Quantencomputer, der heutige Verschlüsselungssystem angreifen könnte, somit noch weit entfernt.

Da die Lebensdauer der Quantenzustände nicht zuletzt über die Heisenbergsche Unschärferelation begrenzt ist (wir sagten das ja schon), sind Quantencomputer wie herkömmliche Computer ebenfalls nicht beliebig skalierbar, weil sie vor Lieferung der Lösung auseinanderfallen und die klassischen Verfahren wie RSA & Co. durch genügend hohen Aufwand auch dem 1-Semester-Studi, der sich einfach einen funktionierenden Quantenrechner besorgt, davon laufen können. In diese Richtung scheinen auch die Überlegungen der NSA zu laufen, die von Zeit zu Zeit mit Richtlinien über zukunftssichere Verschlüsselung aufwartet und hauptsächlich größere Schlüsselbreiten, die die Zeiten über die Grenzen der bekannten Quantenmechanik pushen, sich allerdings in einem noch recht moderatem Umfang bewegen, empfiehlt.

Wer sich für weitere Details aller angesprochenen Verfahren intersiert, kann sich auf meiner Bücherseite schlau machen.

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht.