Komplexitätstheorie und Kryptologie

Eine Einführung in Kryptokomplexität

verfasst von: Jörg Rothe

Verlag: Springer Berlin Heidelberg

Buchreihe : eXamen.press

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

Während die moderne Kryptologie mathematisch strenge Konzepte und Methoden aus der Komplexitätstheorie verwendet, ist die Forschung in der Komplexitätstheorie wiederum oft durch Fragen und Probleme motiviert, die aus der Kryptologie stammen. Das vorliegende Buch hebt die enge Verflechtung dieser verwandten (doch oft separat behandelten) Gebiete hervor, deren Symbiose man als „Kryptokomplexität" bezeichnen könnte.

Der Autor führt in verständlicher Weise in dieses faszinierende Gebiet der Kryptokomplexität ein - von den Grundlagen bis hin zur aktuellen Forschung. Neben der Bereitstellung der nötigen mathematischen Begriffe enthält dieses Buch zahlreiche Abbildungen, Übungsaufgaben, Beispiele, ein ausführliches Sachwortverzeichnis und eine umfassende Bibliographie. Es präsentiert einige zentrale Themen und Herausforderungen der derzeitigen Forschung und ist sehr gut für Studierende der Informatik, Mathematik oder Ingenieurswissenschaften ab den höheren Semestern eines Bachelorstudiums geeignet.

Inhaltsverzeichnis

Frontmatter

1. Einladung zur Kryptokomplexität

Zusammenfassung

Dieses Buch führt in zwei Gebiete ein, Komplexitätstheorie und Kryptologie, die eng miteinander verwandt sind, sich aber recht unabhängig voneinander entwickelt haben. Neben anderen Gebieten wie etwa der Zahlentheorie verwendet die moderne Kryptologie die mathematisch strengen Konzepte und Methoden der Komplexitätstheorie. Umgekehrt ist die aktuelle Forschung in der Komplexitätstheorie oft durch Fragen und Probleme motiviert, die in der Kryptologie auftreten. Das vorliegende Buch trägt diesem Trend Rechnung, und sein Gegenstand könnte daher treffend als ,,Kryptokomplexität“ bezeichnet werden, eine Art Symbiose dieser beiden Gebiete.

2. Grundlagen der Informatik und Mathematik

Zusammenfassung

Eine Sprache der Niederlande ist Holländisch. Eine Sprache des Lebens ist der genetische Code. Und eine Sprache der Natur und der Wissenschaften ist die Mathematik. Die Begriffe, Resultate und Methoden der Komplexitätstheorie und der Kryptologie – wie auch vieler anderer (natur-)wissenschaftlicher Gebiete – können am präzisesten und am elegantesten in der Sprache der Mathematik formuliert werden. Dieses Kapitel stellt kurz jene Gebiete der theoretischen Informatik und Mathematik vor, die für die in diesem Buch behandelten komplexitätstheoretischen und kryptologischen Themen relevant sind. Die erforderlichen Konzepte werden mit mathematischer Strenge eingeführt und so einfach wie möglich erklärt, dabei aber so detailliert, wie es für das Verständnis nötig ist. Insbesondere werden die wichtigsten Grundlagen der Algorithmik, der formalen Sprachen und der Berechenbarkeitstheorie, der Logik, Algebra, Zahlentheorie, Graphentheorie und der Wahrscheinlichkeitstheorie zur Verfügung gestellt. Dieses Kapitel kann ebenso gut vorerst übersprungen und später erneut aufgesucht werden, wann immer das notwendig erscheint.

3. Grundlagen der Komplexitätstheorie

Zusammenfassung

Die erste und wichtigste Aufgabe der Komplexitätstheorie ist es, die Berechnungskomplexität von Problemen (oder, synonym dazu, ihre "Härte") so genau wie möglich zu bestimmen. Betrachte die durch S={x2^|x|x|x ∈ {0,1}*} definierte Menge, deren Elemente Wörter über dem Alphabet {0,1,2} sind. Wie "hart" ist S? Wie schwer ist es also, algorithmisch zu entscheiden, ob ein gegebenes Eingabewort zu S gehört oder nicht? Die erste Antwort ist: Nun, es kommt darauf an!

4. Grundlagen der Kryptologie

Zusammenfassung

Kryptographie ist die Kunst und Wissenschaft davon, wie man Texte und Nachrichten so verschlüsselt, dass eine nicht authorisierte Entschlüsselung verhindert wird. Kryptoanalyse ist die Kunst und Wissenschaft vom Brechen vorhandener Kryptosysteme, d.h., ihr Ziel ist es, die verwendeten Entschlüsselungsschlüssel zu bestimmen und die verschlüsselten Nachrichten unerlaubt zu entschlüsseln. Kryptologie umfasst diese beiden Gebiete, die Kryptographie und die Kryptoanalyse.

5. Hierarchien über NP

Zusammenfassung

In diesem Kapitel, das sich wieder der Komplexitätstheorie zuwendet, werden einige wichtige Hierarchien eingeführt, die auf NP basieren, wie etwa die boolesche Hierarchie über NP und die Polynomialzeit-Hierarchie. Es werden vollständige Probleme in den Stufen dieser Hierarchien identifiziert und die Beziehungen zwischen diesen Hierarchien sowie ihre Eigenschaften erkundet. Zu den Problemen, die vollständig für die Stufen der booleschen Hierarchie über NP sind, gehören zum Beispiel ,,exakte“ Varianten NP-vollständiger Optimierungsprobleme und kritische Graphprobleme. Als Beispiele für Probleme, die in den Stufen der Polynomialzeit- Hierarchie vollständig sind, werden Varianten von NP-vollständigen Problemen betrachtet, die sich durch eine feste Zahl alternierender längenbeschränkter Quantoren darstellen lassen. Im Zusammenhang damit wird der Begriff der alternierenden Turingmaschine eingeführt. Außerdem wird in diesem Kapitel die Low-Hierarchie in NP eingeführt, die ein Maßstab für die Komplexität von NP-Problemen ist, die anscheinend weder in P noch NP-vollständig sind. Als ein Beispiel solcher Probleme wird später, in Kapitel 6, gezeigt, dass das Graphisomorphie-Problem low ist.

6. Randomisierte Algorithmen und Komplexitätsklassen

Zusammenfassung

Dieses Kapitel behandelt randomisierte Algorithmen und die entsprechenden probabilistischen Komplexitätsklassen. Randomisierte Algorithmen sind oft effizienter als die besten bekannten deterministischen Algorithmen für dasselbe Problem, zahlen dafür jedoch den Preis, Fehler zu machen. Dies ist das Thema in Abschnitt 6.1, in dem ausgewählte deterministische und randomisierte Exponentialzeit-Algorithmen für das Erfüllbarkeitsproblem vorgestellt werden.

7. RSA-Kryptosystem, Primzahltests und das Faktorisierungsproblem

Zusammenfassung

In den letzten beiden Kapiteln, die sich wieder der Kryptographie zuwenden, werden einige grundlegende kryptographische Protokolle behandelt. Die Sicherheit solcher Protokolle beruht gewöhnlich auf der Annahme, dass bestimmte Probleme aus der Zahlentheorie und Algebra ,,widerspenstig“, also schwer zu lösen sind. Um also diese Kryptosysteme und Protokolle beschreiben und ihre Sicherheit diskutieren zu können, benötigen wir einige zahlentheoretische, algebraische und komplexitätstheoretische Begriffe, Methoden und Resultate.

8. Weitere Public-Key-Kryptosysteme und Protokolle

Zusammenfassung

In diesem Kapitel werden verschiedene wichtige Kryptosysteme und kryptographische Protokolle vorgestellt. Die meisten sind Public-Key-Kryptosysteme, doch in Abschnitt 8.1 beginnen wir mit der Einführung des Schüsseltausch-Protokolls von Diffie und Hellman, das in der symmetrischen Kryptographie sehr nützlich ist. Das Diffie–Hellman-Protokoll löst das Problem der Verteilung eines gemeinsamen geheimen Schlüssels in einem symmetrischen Kryptosystem über einen unsicheren Kanal. Es ist das erste solche Protokoll in der offenen Literatur, siehe die bibliographischen Anmerkungen in Abschnitt 7.6. Wie bereits erwähnt öffnete die Arbeit von Diffie und Hellman auch der Public-Key-Kryptographie die Tür, welche nicht mehr verlangt, dass Alice und Bob sich auf einen gemeinsamen geheimen Schlüssel einigen müssen, bevor sie verschlüsselte Nachrichten austauschen können.

Backmatter

Titel: Komplexitätstheorie und Kryptologie
verfasst von: Jörg Rothe
Verlag: Springer Berlin Heidelberg
Electronic ISBN: 978-3-540-79745-6
Print ISBN: 978-3-540-79744-9
DOI: https://doi.org/10.1007/978-3-540-79745-6