RUB » RUBIN » 

Sie sind hier

Neue Verschlüsselungstechniken

Neue Verschlüsselungstechniken

Schwere mathematische Probleme als Basis

von Julia Weiler  

29. März 2016

 

IT-Sicherheitsexperten träumen von unangreifbaren Verschlüsselungsverfahren. Vision oder Fantasterei?

Einen Rucksack so zu packen, dass der Inhalt einen möglichst hohen Nutzen erfüllt, ist mathematisch gesehen nicht trivial – zumindest bei einem sehr großen Rucksack. Solche Probleme können die Basis für Verschlüsselungstechniken sein.

Der Start in den Urlaub beginnt für viele Menschen mit einer Herausforderung: Wie sollen all die Sachen in den Koffer, die Tasche oder den Rucksack passen? Mathematisch gesehen ist es tatsächlich nicht trivial, einen Algorithmus zu finden, der einen Rucksack so vollpackt, dass die Gegenstände darin zusammengenommen einen möglichst hohen Nutzen erfüllen.

„Die Entscheidung, eine Zahnbürste mitzunehmen, fällt sicher leicht“, sagt Prof. Dr. Eike Kiltz vom Lehrstuhl für Kryptographie (Abb. 1). „Sie ist klein und hat einen hohen Nutzen. Aber was ist mit dem Föhn? Nehme ich den auch mit?“

Abb. 1© RUB, Roberto Schirdewahn

Eike Kiltz entwickelt kryptografische Verfahren basierend auf schweren Problemen der Mathematik.

Hinter dem Rucksackbeispiel steckt ein schweres mathematisches Problem, für das Wissenschaftler seit über hundert Jahren keine effiziente Lösung gefunden haben. Allerdings wäre der Rucksack in ihrer Variante des Problems bedeutend größer als im wahren Leben.

Eike Kiltz beschäftigt sich mit genau solchen schweren Problemen der Mathematik. Basierend auf ihnen entwickelt er neue Verschlüsselungs- und Authentifizierungsverfahren, die quasi nicht zu knacken sind. „Wenn jemand es schaffen würde, die Verfahren zu brechen, könnte er auch ein mathematisches Problem lösen, an dem die schlausten Köpfe der Welt seit 100 oder 200 Jahren arbeiten“, vergleicht Kiltz.

Mit diesem Ansatz wählt der Wissenschaftler eine ganz andere Herangehensweise als üblich. Normalerweise werden neue kryptografische Verfahren nach dem Ad-hoc-Prinzip konzipiert. Kiltz erklärt: „Jemand denkt sich ein Verfahren aus, dann versuchen andere, es zu brechen. Schaffen sie es nicht, heißt es, dass es sicher ist.“

Die Bochumer Mathematiker basieren ihre Sicherheitsalgorithmen stattdessen auf Probleme, die schon seit ein paar hundert Jahren ungelöst sind. Die Algorithmen gestalten sie dabei so effizient, dass sie sich in Kleinstgeräte implementieren lassen, zum Beispiel in einen elektronischen Garagentoröffner. „Man hat lange gedacht, dass das nicht geht, weil die Chips in diesen Geräten nicht leistungsstark genug sind“, so Kiltz. 2011 veröffentlichte seine Gruppe jedoch ein Prototypverfahren, das genau das konnte.

Nun arbeiten die Forscher daran, die Verfahren noch effizienter und für neue kryptografische Fragestellungen nutzbar zu machen. Großes Potenzial räumen sie dabei der sogenannten gitterbasierten Kryptografie ein. Sie fußt auf folgendem schweren mathematischen Problem: Stellen wir uns ein Gitter vor (Abb. 2), das an einer Stelle einen Nullpunkt besitzt. Überall dort, wo sich zwei Linien kreuzen, liegen weitere Punkte, die wir Kreuzungspunkte nennen. Frage: Welcher Kreuzungspunkt liegt am nächsten beim Nullpunkt?

Abb. 2© RUB

Das Gitterproblem: Welcher der blauen Punkte liegt am nächsten an dem rot markierten Nullpunkt des Gitters? Bei einem 500-dimensionalen Gitter ist dieses Problem nicht mehr effizient zu lösen.

Für ein zweidimensionales Gitter ist dieses Problem leicht zu lösen; auch in einem dreidimensionalen Gitter könnten wir die Antwort relativ schnell finden. Aber je mehr Dimensionen hinzukommen, desto schwieriger wird die Aufgabe. Mit rund 500 Dimensionen lässt sich das Problem nicht mehr effizient lösen.

Je nachdem wie man die Parameter wählt, fällt das Gitterproblem in die Klasse der sogenannten NP-vollständigen Probleme. Diese umfasst die schwersten Probleme der Mathematik, zu denen auch das oben beschriebene Rucksackproblem gehört sowie eine Vielzahl weiterer Vertreter. Sie wären eine ideale Grundlage für möglichst sichere neue Verschlüsselungstechniken.

Für ihre Arbeit wählen die Mathematiker jedoch eine leicht vereinfachte Version des Gitterproblems. Die Aufgabe lautet dann nicht: Finde denjenigen Kreuzungspunkt im Gitter, der am nächsten zum Nullpunkt liegt. Sondern: Finde einen beliebigen Kreuzungspunkt, der in einem engen Radius um den Nullpunkt liegt.

Die Wissenschaftler testen dabei verschiedene Parameter, die das Gitterproblem ein wenig leichter oder schwerer machen, und versuchen, darauf basierend einen kryptografischen Algorithmus zu erarbeiten, der sich auch auf kleinen Geräten implementieren lassen würde.

Gitterbasierte Verfahren zur Authentifizierung haben die RUB-Forscher schon relativ weit entwickelt. „Wir sind fast im Endstadium“, fasst Eike Kiltz zusammen. Authentifizierungsprotokolle werden immer dann gebraucht, wenn ein Objekt seine Identität beweisen muss, zum Beispiel der elektronische Garagenöffner. Schließlich muss sichergestellt sein, dass ein bestimmter Öffner nur das zugehörige Tor entriegelt. Im Protokoll könnte das so funktionieren: Der Öffner authentifiziert sich beim Garagentor, indem er beweist, dass er ein internes Geheimnis kennt, zum Beispiel einen Kreuzungspunkt nahe dem Nullpunkt im Gitter.

Kryptografische Protokolle sind aber nicht nur für die Authentifizierung nötig; auch Verschlüsselungen sind im Alltag ständig im Einsatz. Wenn zum Beispiel zwei Personen eine geheime Botschaft über das Internet austauschen wollen oder eine Smartcard mit dem Kartenlesegerät kommunizieren möchte, muss die Nachricht verschlüsselt sein, damit Dritte sie nicht mitlesen können.

Für diesen Zweck könnten gitterbasierte Verfahren ebenfalls nützlich sein. Allerdings sind die darauf basierenden Verschlüsselungsprotokolle derzeit noch nicht effizient genug, um sie auf kleinen Geräten zu implementieren. Ein paar Jahre Arbeit müssten sie noch investieren, schätzt Eike Kiltz.

Mit einer eierlegenden Wollmilchsau vergleicht der Mathematiker die gitterbasierten Verfahren, weil sie so vielfältig einsetzbar sind. Sie taugen sowohl zur Verschlüsselung als auch zur Authentifizierung, funktionieren auf kleinen Geräten und würden sogar vor Angriffen durch Quantencomputer schützen (siehe „Kryptografie im Zeitalter der Quantencomputer“), falls es diese eines Tages gäbe.

Neben ihrer anwendungsorientierten Arbeit betreiben die RUB-Mathematiker auch Grundlagenforschung. Sie versuchen, die Gitter mathematisch zu verstehen. Was macht das Gitterproblem so einzigartig schwer, dass alle bisherigen Techniken bei der Lösung versagen? Das ist eine der Fragen, die die Forscher umtreibt. Die Erkenntnisse könnten eines Tages in die anwendungsorientierte Arbeit einfließen.

Interview mit Eike Kiltz

http://rubin.rub.de/de/arbeiten-am-aeussersten-rand-der-theorie

Kontakt zum Fachbereich

Prof. Dr. Eike Kiltz
Lehrstuhl für Kryptographie
Horst Görtz Institut für IT-Sicherheit
Ruhr-Universität Bochum
Tel.: 0234 32 25513
E-Mail: eike.kiltz@rub.de

Download hochauflösender Bilder

Markieren Sie die gewünschten Bilder und akzeptieren Sie unsere Nutzungsbedingungen.
Der Download der gewählten Bilder erfolgt als ZIP-Datei.

Nutzungsbedingungen
Die Verwendung der Bilder ist nur im Kontext der Berichterstattung zu
RUBIN – Wissenschaftsmagazin der RUB und unter Angabe der entsprechenden Copyrights für die Presse frei.



Ich akzeptiere die Nutzungsbedingungen.