Newsportal - Ruhr-Universität Bochum
-
Die Firma D-Wave brachte 2010 nach eigenen Angaben den ersten Quantencomputer auf den Markt. Kritiker bezweifeln allerdings, dass der Rechner wirklich mit Quanteneffekten arbeitet.© Courtesy of D-Wave Systems Inc. -
Langzeitkritische Daten, etwa Bank- oder Gesundheitsdaten, sollten auch in vielen Jahren noch geschützt sein – selbst wenn es Quantencomputer gäbe.© Roberto Schirdewahn -
Kritiker bezweifeln, dass der sogenannte Quantencomputer der Firma D-Wave die enorme Rechenpower erzielt, die mit einem richtigen Quantencomputer möglich wäre.© Courtesy of D-Wave Systems Inc.
Harte Nuss für den Quantencomputer
Auf der Suche nach Verschlüsselungsverfahren, die selbst von einem leistungsstarken Quantencomputer nicht schnell geknackt werden können, befasst sich Prof. Dr. Alexander May mit sogenannten schweren mathematischen Problemen. Es handelt sich um Berechnungen, für die es noch keinen effizienten Algorithmus gibt, das heißt, für die ein Computer bei umfangreichen Daten sehr lange braucht. Eine große Zahl in ihre Primfaktoren zu zerlegen, ist beispielsweise ein solches Problem.
Auf den ersten Blick haben die schweren Probleme nicht unbedingt etwas mit Verschlüsselungsverfahren zu tun. Aber IT-Wissenschaftler nutzen sie als Hilfsmittel: Sie stellen zwischen einer bestimmten Verschlüsselungsmethode und einem Problem einen Zusammenhang her. So können sie herausfinden, wie schwer das Verfahren zu brechen ist.
So können wir etwas darüber herausfinden, wie schwer der Code zu brechen ist.
In der theoretischen Informatik interessieren sich Wissenschaftler dafür, wie viele Schritte ein Algorithmus für eine Berechnung benötigt. Die exakte Zahl können sie in der Regel nicht ermitteln, aber sie können abschätzen, wie viele Schritte von der Größenordnung her höchstens gebraucht werden – gewissermaßen ob es eher 10, 100 oder 1.000 sind.
„Wir verknüpfen nun die Anzahl der Rechenschritte, die ein Algorithmus zum Lösen eines schweren Problems braucht, mit der Anzahl der Rechenschritte, die zum Knacken eines Codes nötig wären“, erklärt Alexander May, Professor für Kryptologie und IT-Sicherheit an der Ruhr-Universität Bochum. „So können wir etwas darüber herausfinden, wie schwer der Code zu brechen ist.“
Seine Kollegen und er nehmen dazu an, es gäbe einen Algorithmus, der eine Verschlüsselung in einer bestimmten Zeit T knackt, zum Beispiel in 280 Schritten – etwas mehr als eine Quadrillion, eine Zahl mit 25 Stellen. Wie genau dieser Algorithmus funktionieren könnte, ist für die Wissenschaftler nicht von Belang; sie nehmen lediglich an, dass er existiert. „Der Algorithmus ist eine Blackbox“, erläutert May. „Wir arbeiten nur mit der Annahme, dass es ihn gibt und dass er die Verschlüsselung in der angenommenen Zeit bricht.“ Mithilfe logischer Argumente leiten er und seine Mitarbeiter dann daraus ab, wie lange das Lösen eines schweren Problems dauert.
„Üblicherweise ist das ein Vielfaches der Zeit T, die zum Brechen der Verschlüsselung benötigt wird, also c·T“, so May. „Wir versuchen bei unserer Arbeit, in der Argumentation einen möglichst kleinen Faktor c zu erreichen, damit die Aussagen über das schwere Problem und über das Brechen der Verschlüsselung nicht allzu weit auseinanderliegen.“
Argumente umdrehen
Ist dies geschafft, haben die Wissenschaftler beispielsweise einen Zusammenhang wie diesen hergestellt: Wenn die Verschlüsselung in T = 280 Schritten gebrochen werden kann, kann das schwere Problem in c·T Schritten gelöst werden. Ist c = 210, also in 290 Schritten. Wohlgemerkt ist die Aussage rein hypothetisch, aber die Wissenschaftler nutzen nun einen üblichen Trick aus der Logik: Sie drehen die Folgerung um. Dabei müssen sie beide Aussagen verneinen.
Zum Beispiel kann die gültige Folgerung „Wenn der Hund gesund ist, hat er vier Beine“ umgedreht werden; damit sie gültig bleibt, müssen die Aussagen aber negiert werden: „Wenn der Hund nicht vier Beine hat, ist er nicht gesund.“ Ebenso dreht Alexander May den gefundenen Zusammenhang zwischen dem Brechen eines Codes und einem schweren Problem um: Wenn das schwere Problem nicht in 290 Schritten gelöst werden kann, kann die Verschlüsselung nicht in 280 Schritten gebrochen werden.
Die umgedrehte Aussage gilt für alle denkbaren Algorithmen.
Da May für seine Argumentation keine einzige Eigenschaft des hypothetischen Code-Brech-Algorithmus genutzt hat – außer der bloßen Existenz –, ist er sich sicher: „Die umgedrehte Aussage gilt für alle denkbaren Algorithmen, auch für die, die erst noch erfunden werden.“ Diese Art, eine Frage auf eine andere zu verlagern, nennt man Reduktion. Alexander May und seine Mitarbeiter haben die Frage, ob ein Code schnell zu brechen ist, nun also auf eine andere Frage zurückgeführt, nämlich wie schnell ein schweres Problem zu lösen ist.
Schwere Probleme nennt man in der theoretischen Informatik Berechnungen, für die ein Computer besonders lange braucht. Allerdings ist nicht der konkrete Zeitbedarf auf einem bestimmten Computer gemeint, sondern die Anzahl der benötigen Rechenschritte, abhängig davon, wie viele Eingaben gemacht wurden. Diese sogenannte Laufzeit ist unabhängig davon, welcher Computer genutzt wird; sie gibt Informatikern Aufschluss darüber, wie kompliziert eine Berechnung ist.
Beispielsweise gilt das Sortieren einer Liste von Zahlen nicht als schwer. Denn sollen n Zahlen sortiert werden, benötigen gängige Sortieralgorithmen dazu nicht mehr als etwa n·n Rechenschritte. Zum Sortieren von zehn Zahlen sind also nicht mehr als 100 Schritte erforderlich, zum Sortieren von 20 Zahlen nicht mehr als 400. Denn die Algorithmen haben eine quadratische Laufzeit oder sind sogar schneller: Verdoppelt sich die Größe der zu sortierenden Liste, dauert die Sortierung im schlimmsten Fall etwa viermal so lang.
Anders ist es beim sogenannten Teilsummenproblem, das folgende Frage stellt: Angenommen, es liegt eine Liste mit Zahlen vor, ist es dann möglich, eine Menge von Zahlen in dieser Liste zu finden, die sich zu null aufsummiert? Enthält die Liste n Zahlen, so benötigt ein übliches Programm maximal etwa n·2n Rechenschritte.
Was für Nichtmathematiker nicht wüster als das n·n vom Sortieren aussieht, ist für Experten ein gewaltiger Unterschied: Verdoppelt sich die Listenlänge, wird die Laufzeit mehr als quadriert. Enthält die Liste beispielsweise fünf Elemente, so weiß man, dass der Algorithmus im Großen und Ganzen nicht mehr als 5·25, also 160 Schritte braucht; bei einer Listengröße von zehn Zahlen sind es jedoch bereits 10·210, also 10.240 Schritte.
Als schwer bezeichnen IT-Wissenschaftler zum Beispiel das Teilsummenproblem: Angenommen, es liegt eine Liste mit Zahlen vor, ist es dann möglich, eine Menge von Zahlen in dieser Liste zu finden, die sich just zu null aufsummiert? Ist die Liste zum Beispiel −9, −3, 1, 4, 5, so lautet die Antwort ja, weil sich −9, 4 und 5 gerade zu null addieren. Dieses Beispiel mag einfach sein. Doch die benötigte Zeit hängt exponentiell von der Länge der Liste ab. Zu überprüfen, ob es in einer Liste eine Menge von Zahlen gibt, die sich zu null aufsummiert, ist somit ein schweres Problem.
So lange braucht es, einen Code zu knacken
Alexander May und seine Kollegen interessieren sich für solche Probleme, weil sie sie als Hilfsmittel nutzen, um etwas über die Sicherheit kryptografischer Verfahren auszusagen. Aus der Zeit, die es braucht, ein schweres Problem zu lösen, schließen sie nur durch logische Argumentation auf die Zeit, die das Knacken eines kryptografischen Verfahrens benötigt. Dabei ist es selten möglich, die Zeit exakt anzugeben. Allerdings können sie Schranken finden. „Wir wissen dann, wie viel Zeit ein Verfahren maximal braucht“, erläutert Alexander May. „Allerdings wissen wir nichts darüber, ob es nicht auch schneller gehen kann.“
Die Herausforderung für die Wissenschaftler besteht darin, möglichst enge Grenzen zu finden, in denen sich die tatsächliche Laufzeit befindet. Für das Teilsummenproblem braucht ein übliches Programm n·2n Rechenschritte. May hat festgestellt, dass es jedoch deutlich schneller erledigt werden kann, nämlich mit etwa 20,3·n Rechenschritten, eine enorme Verringerung.
Diese neuartigen Verschlüsselungen werden dann auch sicher sein, wenn der Quantencomputer kommt.
Das Teilsummenproblem ist für ihn deshalb so interessant, weil es vermutlich auch für einen Quantencomputer eine harte Nuss ist. „Das Zerlegen in Primfaktoren, auf dem fast die gesamte gängige Verschlüsselung basiert, kann von einem Quantencomputer schnell erledigt werden. Das wissen wir heute bereits, auch wenn es ihn noch nicht gibt“, sagt May.
Doch das Teilsummenproblem bedeutet auch für einen Quantencomputer langwierige Berechnungen. Deshalb konstruiert Alexander May Verschlüsselungsverfahren, die er mithilfe logischer Argumentation mit dem Teilsummenproblem verbindet. „Diese neuartigen Verschlüsselungen werden dann auch sicher sein, wenn der Quantencomputer kommt“, sagt er.
