Jump to navigation

Logo RUB
  • Energie
  • Studium
  • Forschung
  • Transfer
  • News
  • Über uns
  • Einrichtungen
 
MENÜ
  • RUB-STARTSEITE
  • News
  • Wissenschaft
  • Studium
  • Transfer
  • Leute
  • Hochschulpolitik
  • Kultur und Freizeit
  • Vermischtes
  • Servicemeldungen
  • Serien
  • Dossiers
  • Bildergalerien
  • Presseinformationen
    • Abonnieren
  • RUB in den Medien
    • Abonnieren
  • Rubens
  • Rubin
    • Abonnieren
    • Printarchiv
  • Archiv
  • English
  • Redaktion

Newsportal - Ruhr-Universität Bochum

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.
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.
© Roberto Schirdewahn
Effiziente Algorithmen

Neue Verschlüsselungstechniken dank schwerer mathematischer Probleme

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

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. „Sie ist klein und hat einen hohen Nutzen. Aber was ist mit dem Föhn? Nehme ich den auch mit?“

Rucksackproblem seit über 100 Jahren ungelöst

Hinter dem Rucksack-Beispiel 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.

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

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 Prototyp-Verfahren, das genau das konnte.

Effiziente Algorithmen für Kleinstgeräte

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, 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?

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.
© RUB

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.

Fast im Endstadium

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.

Gitterbasierte Verfahren vielfältig einsetzbar

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, 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.

Angeklickt
  • Interview mit Eike Kiltz
Download hochauflösender Bilder
Der Download der gewählten Bilder erfolgt als ZIP-Datei.
Bildzeilen und Bildnachweise finden Sie nach dem Entpacken in der enthaltenen HTML-Datei.
Nutzungsbedingungen
Die Verwendung der Bilder ist unter Angabe des entsprechenden Copyrights für die Presse honorarfrei. Die Bilder dürfen ausschließlich für eine Berichterstattung mit Bezug zur Ruhr-Universität Bochum verwendet werden, die sich auf die Inhalte des Artikels bezieht, der den Link zum Bilderdownload enthält.
Ich akzeptiere die Nutzungsbedingungen.
Dokumentedownload
  • Artikel als PDF-Datei
Veröffentlicht
Dienstag
29. März 2016
10.36 Uhr
Von
Julia Weiler (jwe)
Dieser Artikel ist am 1. Juli 2016 in Rubin IT-Sicherheit 2016 erschienen. Die gesamte Ausgabe können Sie hier als PDF kostenlos downloaden.
Weitere Rubin-Artikel sind hier zu finden.
Share
Teilen

IT-Sicherheit

Die digitale Vernetzung durchdringt inzwischen fast alle Bereiche des Lebens. Schutzmechanismen zu entwickeln ist eine vordringliche Aufgabe.

Mehr aus dem Dossier
Das könnte Sie auch interessieren
Hardware auf einem Tisch
IT-Sicherheit

Intelligente Affen

Das Wissenschaftlerteam
Kryptografie

Sicherheit mit Sollbruchstelle

IT-Sicherheitsforscher Thorsten Holz mit einem Comic-Heft in der Hand
Exzellenzcluster CASA

Ein Comic über IT-Sicherheit

Derzeit beliebt
KI: Das Bochumer Team mit Projektleiter Peter Salden, Nadine Lordick, Jonas Loschke und Maike Wiethoff (von links)
Künstliche Intelligenz

Bochumer Projekt schafft Klarheit zu KI-Tools für NRW-Hochschulen

Viktoria Däschlein-Gessner
Chemie

ERC Consolidator Grant für Viktoria Däschlein-Gessner

Ein junger Mann mit schwarzem Kapuzenpulli sitzt in einer Hörsaalreihe und lächelt.
Politik und Studium

Dienstag Bachelorarbeit abgeben, Sonntag Bundestagsmandat gewinnen

 
Mehr Wissenschaft
Ressort
 
Zur Startseite
News
  • A-Z
  • N
  • K
Logo RUB
Impressum | Kontakt
Ruhr-Universität Bochum
Universitätsstraße 150
44801 Bochum

Datenschutz
Barrierefreiheit
Impressum
Schnellzugriff
Service und Themen
Anreise und Lagepläne
Hilfe im Notfall
Stellenangebote
Social Media
Facebook
Twitter
YouTube
Instagram
Seitenanfang y Kontrast N
Impressum | Kontakt