Neue Algorithmen gegen Quantencomputer

Verschlüsselung in Zeiten der Post-Quantum-Kryptographie

| Autor / Redakteur: Dr. Bernd Schöne / Peter Schmitz

Quantencomputer können durch die speziellen Qubits in kurzer Zeit Aufgaben erledigen, für die herkömmliche Rechner Jahrtausende benötigen würden.
Quantencomputer können durch die speziellen Qubits in kurzer Zeit Aufgaben erledigen, für die herkömmliche Rechner Jahrtausende benötigen würden. (© sakkmesterke - Fotolia)

Ohne zuverlässige Verschlüsselung ist die digitale Welt unvorstellbar. Nach zahllosen Tests gelten die etablierten Verfahren heute als äußerst sicher. Doch das könnte sich bald ändern, wenn Codebrecher über Quantencomputer verfügen. Mit Hochdruck arbeiten Mathematiker an neuen Verfahren. Läuft alles glatt, sollen sie in 10 Jahren einsatzfähig sein, die Frage ist aber, ob das schnell genug ist.

Kommt er, oder kommt er nicht? Jahrzehntelang wurde spekuliert, ob es jemals möglich sein wird, die Gesetze der Quantenmechanik zur Lösung von mathematischen Probleme zu nutzen. Inzwischen gilt als sicher, das dies theoretisch möglich ist, und das ein Quantencomputer konstruierbar sein dürfte. In einem solchen Rechner werden subatomare Teilchen in definierte Quantenzustände versetzt, und anschließend angeregt. Um einen funktionierenden Rechner bauen zu können, müssen sehr viele dieser Teilchen in exakte definierte und stabile Zustände überführt werden. Bislang ist dies nur teilweise gelungen. Doch die Einschläge kommen näher.

Im Mai 2013 kauften die Raumfahrtagentur NASA und die Firma Google den angeblich ersten funktionierenden Quantencomputer der Firma D-Wave Systems. Der Rechner ist speziell für die Lösung von Optimierungsproblemen entwickelt worden, und soll 100 Millionen mal schneller rechnen als klassische Computer Er erreicht dies durch einen supraleitenden Prozessor mit mehr als 1.000 Qubits. Über die Funktionsfähigkeit des Gerätes gibt es keine unabhängigen Berichte. Weltweit arbeiten Forschungseinrichtungen, aber auch Konzerne wie IBM mit Hochdruck an einem Quantenrechner. Im Mai stellte die Firma ein Quantenregister mit 16 Qubits vor. Aus solchen Registern setzen sich Quantenrechner zusammen.

Quantencomputer werden auf Grund ihrer Rechenkraft die heute verwendeten asymmetrischen Public-Key Verfahren brechen, und die Schlüssellänge der symmetrischen Verfahren halbieren. Das weiß die Fachwelt seit 1994 bzw. 1996 durch die Arbeiten der Mathematiker Shor und Grover.

Damit wären alle Public-Key-Algorithmen wie RSA, Diffie Hellman wertlos, ebenso elliptische Kurven. Zahlreiche Internetstandards wie Transport Layer Security (TLS), S/MIME, PGP, und GPG nutzen dies Verfahren für den gesicherten Austausch von Schlüsseln, ebenso das Onlinebanking auf „https“-Seiten oder die Verschlüsselung von Textnachrichtendiensten („Instant Messaging“). Auch symmetrische Verschlüsselungsverfahren wie AES würden durch Quantenrechner an Sicherheit einbüßen. Ihre Sicherheit entspräche nur mehr der halben Schlüssellänge. Das bedeutet schon heute, dass alle Verantwortlichen die Schlüssellängen ihrer Verschlüsselungsverfahren mindestens verdoppeln sollten, auch wenn dies zu Lasten der Schnelligkeit und der Leistungsfähigkeit geht.

Die Suche nach neuen Verschlüsselungsverfahren

Auf der diesjährigen Sicherheitstagung des BSI in Bonn stand daher die Suche nach neuen Verschlüsselungsverfahren für die Quantencomputerzeit in Zentrum des Interesses. Die PQK (Post-Quantum-Kryptographie) Verfahren sollen gegen die Entschlüsselungsversuche von Quantenrechnern ebenso gefeit sein, wie gegen Attacken von klassischen Rechnern. Mathematiker suchen daher quantenschwere Verfahren, die auch von klassischen Rechnern nicht geknackt werden können. Quantencomputer werden auf lange Zeit den klassischen Rechner bestenfalls ergänzen, ihn aber nicht ersetzen. Darum müssen alle neuen kryptographischen Verfahren zwingend auch gegen Angriffe von klassischen Rechner gewappnet sein.

Wie weit die Entwicklung eines universellen Quantenrechners exakt fortgeschritten ist, weiß niemand genau, aber immer mehr Komponenten werden veröffentlicht und sind teilweise bereits kommerziell verfügbar. „Ich habe eine Wette mit meinem Chef laufen, dass es noch vor meiner Pensionierung einen funktionsfähigen Quantencomputer geben wird“, umreißt Dr. Manfred Lochter, Verschlüsselungsexperte beim BSI seine Einschätzung der Lage. Das wäre 2030 und deckt sich fast mit den Vorstellungen der EU Kommission, welche davon ausgeht, dass es 2035 soweit sein könnte.

Die amerikanische Standardisierungsbehörde NIST sieht dringenden Handlungsbedarf und sucht seit 2016 nach PQK-Kandidaten. Auch deutsche Forscher beteiligen sich an dem Wettbewerb. 2018 soll entschieden werden. Danach erfolgt die Feinarbeit. Auch das wird Jahre kosten. „Vielleicht sind wir schon zu spät“, befürchtet Donna F. Dodson vom NIST, denn auch die Implementierung der neuen Algorithmen in die bestehende IT-Infrastruktur wird viele Jahre erfordern. Auch halbfertige Quantencomputer können gefährlich werden, darauf wiesen die Experten hin, weil sie Teillösungen liefern, also besonders rechenintensive Probleme beschleunigen und so das Brechen von Siegeln und kodierten Informationen beschleunigen würde. Auch in diesem Falle wären die bisherigen Abschätzungen über die Sicherheit von Verschlüsselungssystemen obsolet.

Heutige Computer nutzen Spannungszustände, um zu rechnen. Physikalische werden die Rechenregistern von Transistoren aufgebaut, die sich auf Chips befinden. Sie sind klein, gehorchen aber immer noch den Gesetzen der Makrophysik, so wie Autos und Schraubenzieher, denn in ihnen arbeiten immer noch große Mengen von Ladungsträgern. Ganz anders funktionieren Quantencomputer. Sie benötigen einzelne, subatomare Teilchen. Diese unterliegen den Gesetzen der Quantenmechanik. Gelingt es ausreichend viele dieser Teilchen, isoliert voneinander, in die gewünschten Quantenzustände zu präparieren und kann man sie anschließend gezielt anregen und das Ergebnis wieder ohne Verfälschung auslesen entsteht ein Quantenrechner. So lauten zumindest die theoretischen Überlegungen. Überprüft werden konnten diese Aussagen noch nicht, denn niemand kann bislang einen universellen Quantencomputer kommerziell fertigen. Die physikalischen Anforderungen sind enorm hoch, denn die Quantenzustände, etwa der Spin eines Elektrons, müssen bei sehr tiefen Temperaturen stabil gehalten werden, erst dann verfügt man über ein Qubit. Ähnlich wie bei einem klassischen Rechner benötigt man sehr viele dieser Qubits, um so etwas wie einen leistungsfähigen Computer bauen zu können. Anders als beim klassischen Computer wird es aber keine physikalischen Gatter geben, um etwa Additionen durchführen zu können. Beim Quantencomputer „rechnet“ die Natur selbst, indem sich nach einer Anregung ein bestimmter Quantenzustand einstellt. Als Anregung kann Laserlicht oder ein Magnetfeld dienen.

Während der Stand der Entwicklung in den Laboratorien der Universitäten recht genau bekannt ist, herrscht über die Situation bei Geheimdiensten wie etwa der NSA große Unsicherheit. Seit den Enthüllungen des Whistleblowers Edward Snowden in der Washington Post vom 2. Januar 2014 ist zumindest allgemein bekannt, dass die National Security Agency (NSA) der USA an der Entwicklung eines „kryptologisch nützlichen“ Quantencomputers arbeitet. Diese Quantenrechner sind auf das Codebrechen spezialisiert.

„Der Bereich der Geheimhaltung“, so Reinhard Posch, CIO der österreichischen Bundesregierung, stehe nun ganz allgemein „vor schwierigen Problemen“. Denn verschlüsselte Informationen, die man nicht lesen kann, die aber von großem Interesse zu sein scheinen, lassen sich eben speichern. Und genau das tut das weltweit größte Rechenzentrum. Es gehört der NSA und steht in Utah. Mit 12 Exabyte Speicherkapazität besitzt es genug Kapazität, um mindestens 1 Terabyte Informationen pro Mensch auf der Erde zu sichern.

"Die NSA kann Chiffriertexte jetzt speichern und in 2017+X entschlüsseln", sagte der Informatiker Johannes Buchmann von der TU Darmstadt. Firmengeheimnisse, die auch in einigen Jahren von Wert sein könnten, müssten schon jetzt mit den neuen Algorithmen geschützt werden, doch die sind noch nicht verfügbar, und werden auch noch eine ganze Weile auf sich warten lassen. Auch staatliche Stellen sind alarmiert. Hoheitliche Daten sind in Deutschland 10 Jahre zu schützen. Geheime Regierungsdokumente, auch „Verschlusssachen“ genannt, 30 Jahre. Andreas Könen vom Bundesinnenministerium wies in der Podiumsdiskussion auf den Chip im neuen Personalausweises hin. Ein Quantenrechner könnte diese Komponente des Ausweises obsolet machen und es müssten neue Verfahren für elektronische Identitäten gefunden werden.

Wettlauf zu einem quantenresistenten Kryptosystem

Die Suche nach neuen mathematischen Verfahren hat bereits begonnen. Aktuell werden sie getestet und von Fehlern befreit. Dann erfolgt der Standardisierungsprozess und erst dann die Vermarktung. Das alles wird mindestens 10 Jahre dauern. Wer nicht so lange warten will, dem steht es natürlich offen, eigene Maßnahmen zu ergreifen, also selbst Verfahren zu entwickeln und diese zu nutzen.

Das BSI und wichtige Deutsche Wissenschaftler setzen auf standardisierte Verfahren. Sie tragen Namen wie TESLA und ring-TESLA und GPV. Diese versprechen ein Höchstmaß an Sicherheit, ihre mathematischen Grundlagen sind aber noch nicht vollständig erforscht. Auf Grund ihres hohen Potentials werden sie aber vermutlich Ende des Jahres bei der amerikanischen Standardisierungsbehörde NIST als PQK-Kandidat eingereicht. Gegenwärtig laufen die letzten Tests mit den Kandidaten, wie die Mathematikerin Nina Bindel von der TU Darmstadt ausführte. Praktiker stören sich vor allem an den beachtlichen Schlüssellängen und der Rechenleistung, die zur Erzeugung und zur Überprüfung der Signaturen benötigte werden. Fast zeitgleich mit dem BSI Kongress teilte der Chipkartenhersteller Infineon mit, eine Variante des Krypto-Systems „New Hope“ zu verwenden, das auch schon Google für eine Demoversion des Chrome Browsers verwendet hat, und als Kandidat eines quantenresistenten Kryptosystems gilt. New Hope basiert auf dem Ring-Learning-With-Errors-Verfahren, gilt als ressorcenschonend und daher auch auf kontaktlosen Smartcard einsetzbar. Dr. Manfred Lochter vom BSI reichen diese Fortschritte nicht, er fordert Krypto- Agilität als Designkriterium.

Andreas Könen, Leiter des Stabes Cybersicherheit im Bundesinnenministerium BMI, stimmt dem zu. „Es ist ein generelles Problem, dass die heute verfügbaren Smartcards nur ein Protokoll und einen Verschlüsselungsalgorithmus beherrschen.“ Um im Falle des Falles schnell reagieren zu können, sollten Alternativen auf der Karte vorhanden sein, damit nach Enttarnung eines Sicherheitsproblems nicht auf einen Schlag Millionen von Ausweisen kurzfristig ausgetauscht werden müssen.

Es ist schwer vorstellbar, das ausschließlich Studenten und Doktoranden die anstehenden Arbeiten bewältigen können. Prof. Tommaso Calarco von der Universität Ulm stellte das mit einer Milliarde Euro dotierte Quantum Technologies Flagship Programm der EU vor. Es fördert alle Arten von Forschung, die Quantentechnologie für industrielle Einsätze nutzbar machen will. Auch PQK-Projekte könnten davon am Rande profitieren, im Zentrum stehen sie nicht. Auch das Bundesinnenminsterium gibt kein zusätzliches Geld aus, man vertraut auf die Kompetenz des BSI, dessen Personal zwischenzeitlich um 180 Stellen aufgestockt wurde. Weitere Impulse erhofft man sich von Startups, die von jungen Wissenschaftlern gegründet werden sollen. Doch was geschieht, wenn sie wirklich die Lösung finden?. Aktuell schützt niemand Deutschland und die EU davor, dass lebenswichtige Technologie einfach aufgekauft wird. Andreas Könen fordert daher eine neue Form des Außenwirtschaftsgesetzes, das wichtige Firmen und ihr Knowhow schützt. Der 2016 von China gekauften Roboter Herstellers Kuka gilt als mahnendes Beispiel. Hier gibt es bislang unüberbrückbare Meinungsverschiedenheiten zwischen Innenministerium und Wirtschaftsministerium, das ein solches Gesetz nicht will. US Konzerne wie Google sehen die Entwicklung gelassen, erläuterte die Firma gegenüber Prof. Tommaso Calarco von der Universität Ulm, „im Gegensatz zu den Europäern sitzen wir auf einem Berg Geld.“

Ein Aspekt fehle bei der Bonner Konferenz. Denn die Gesetze der Quantenmechanik ermöglichen auch eine neue Form der Kommunikation, die so genannte Quantenkommunikation. Die Quanteneigenschaften machen diese Art der Kommunikation abhörsicher. Sollte ein Lauscher sich in die Verbindung einklinken, wird die Nachricht auf Grund der Gesetze der Quantenmechanik zerstört. China nutzt seit wenigen Monaten dieses Verfahren, um via Satellit Codes an seine Botschaften zu funken.

Fazit

Welches PQK-Verfahren sich durchsetzen wird, ist derzeit vollkommen offen. Die quantenresistente Kryptographie ist auf jeden Fall langsamer, als die bislang verwendeten Verfahren. Sie benötigt mehr Rechenleistung und Speicherkapazität. Zumindest beim heutigen Stand der Entwicklung könnten die neuen Verfahren nur schwer auf elektronischen Ausweisen und Smartcards untergebracht werden. Auch sind sie zu langsam für das Internet der Dinge. Es besteht also in allen Richtungen Forschungsbedarf. Techniker werden die Verfahren auch erst dann wirklich optimieren können, wenn ihr Gegner auf dem Labortisch steht. Ein handelsüblicher Quantencomputer, mit dem sich testen lässt, was die neuen Algorithmen wirklich taugen. Wann dieser Zeitpunkt erreicht sein wird, weiß niemand. Im Hase und Igel Spiel zwischen Verschlüsselungs- und Entschlüsselungsexperten scheinen für lange Zeit die Entschlüsseler die Nase vorn zu haben.

Kommentare werden geladen....

Kommentar zu diesem Artikel

Anonym mitdiskutieren oder einloggen Anmelden

Avatar
  1. Avatar
    Avatar
    Bearbeitet von am
    Bearbeitet von am
    1. Avatar
      Avatar
      Bearbeitet von am
      Bearbeitet von am

Kommentare werden geladen....

Kommentar melden

Melden Sie diesen Kommentar, wenn dieser nicht den Richtlinien entspricht.

Kommentar Freigeben

Der untenstehende Text wird an den Kommentator gesendet, falls dieser eine Email-hinterlegt hat.

Freigabe entfernen

Der untenstehende Text wird an den Kommentator gesendet, falls dieser eine Email-hinterlegt hat.

copyright

Dieser Beitrag ist urheberrechtlich geschützt. Sie wollen ihn für Ihre Zwecke verwenden? Infos finden Sie unter www.mycontentfactory.de (ID: 44738162 / Verschlüsselung)