Einführung - Moderne Kryptographie - page 3

Sicherheitsdefinitionen, die dies aufgriffen, entstanden zu Beginn der 1980-er Jahre, vor
allem mit den Arbeiten von Shafi Goldwasser und Silvio Micali sowie Andrew Chi-Chih
Yao [85, 170]. Diese Arbeiten taten einen dritten wichtigen Schritt für die Kryptographie
hin zu einer mathematisch und informatisch fundierten Wissenschaft. Man spricht seit
dieser Zeit von algorithmischer Sicherheit .

1.3 Beweisbare Sicherheit

Der Übergang von Shannons informationstheoretischem Sicherheitsbegriff zum algorith-
mischen Sicherheitsbegriff bringt eine grundlegende Schwierigkeit mit sich. Denn will man
zeigen, dass ein kryptographisches Verfahren algorithmisch sicher ist, muss man nachwei-
sen, dass es unter Einsatz beschränkter Rechenressourcen nicht gebrochen werden kann.
Solche Nachweise sind aber - das zeigt die lange Geschichte der Komplexitätstheorie -
nur schwer zu erbringen, um genau zu sein, kein solcher Nachweis ist bislang gelungen.
Kryptographen führen deshalb keine absoluten Beweise über algorithmische Sicherheit,
sondern stützen ihre Verfahren auf Annahmen ab, die besagen, dass bestimmte Probleme
schwer lösbar sind, das heißt, dass es keine ezienten Algorithmen (Polynomzeitalgorith-
men) zur Lösung dieser Probleme gibt. Übliche Annahmen sind zum Beispiel, dass das
Faktorisieren großer Zahlen oder die Berechnung des diskreten Logarithmus schwierige
Probleme sind. Sicherheitsbeweise sind dann Reduktionsbeweise ,d.h.,manzeigt,dassdie
Unsicherheit des betrachteten kryptographischen Verfahrens die Ungültigkeit der Annah-
me nach sich zöge. Wird ein solcher Reduktionsbeweis geführt, spricht man davon, dass
das Verfahren beweisbar sicher ist.
Man vergegenwärtige sich, dass die angesprochenen Reduktionsbeweise keine unbe-
dingte Sicherheit bieten, denn die gemachten Annahmen sind letztlich unbewiesene und
(nach dem Stand der Wissenschaft) nur sehr schwer zu beweisende Annahmen. Selbst
wenn man beweisen könnte, dass P

= NP gilt - eines der größten offenen Probleme
der Theoretischen Informatik -, würden die üblicherweise in der Kryptographie gemach-
ten Annahmen nicht automatisch gelten. Dennoch gelten diese Annahmen als plausibel
und bieten damit ein brauchbares Fundament für die Sicherheit kryptographischer Ver-
fahren. Auf Reduktionsbeweise gänzlich zu verzichten, würde uns wieder in den völlig
unbefriedigenden Zyklus der klassischen Kryptographie zurückwerfen: Ein kryptographi-
sches Verfahren vorschlagen, hoffen, dass kein Angriff gefunden wird und gegebenenfalls
ein neues Verfahren vorschlagen.

1.4 Was wird in diesem Buch (nicht) behandelt?

Wie der Titel des Buches sagt, soll eine Einführung in die moderne Kryptographie ge-
geben werden, etwa in dem Umfang, wie sie in einer einsemestrigen Vorlesung möglich
ist. Die moderne Kryptographie hat jedoch deutlich mehr zu bieten als das, was in einer
derartigen Einführung behandelt werden kann.
Wir befassen uns in diesem Buch mit den klassischen und grundlegenden kryptogra-
phischen Sicherheitszielen: Geheimhaltung (Vertraulichkeit) sowie Integrität und Authen-
tizität von Nachrichten. Wir werden einige moderne, in der Praxis eingesetze Verfahren