Komplexität und Einwegfunktionen - Kryptologie - page 57

4 Komplexität und
Einwegfunktionen

Für die Sicherheit mancher moderner kryptografischer Systeme ist es entschei-
dend, dass das Faktorisieren großer natürlicher Zahlen als schwierig anzusehen
ist. Wir werden im vorliegenden Kapitel ein Maß für diesen etwas schwammigen
Begriff schwierig erläutern. Dazu betrachten wir die Komplexität von algorithmisch
behandelbaren Problemen.
Die Komplexität eines Algorithmus schätzt die Laufzeit des Algorithmus für große
Eingabewerte asymptotisch unter Verwendung des Landau-Symbols O ab. So wird
ein Vergleich der Schwierigkeitsgrade von mathematischen Problemen möglich.
Weil wir aber nur Aussagen über die Laufzeiten im Unendlichen gewinnen, sind
damit keine Aussagen über den praktischen Nutzen verbunden. Für solche Aus-
sagen müssen genauere Untersuchungen durchgeführt werden.
Für die Kryptologie besonders interessant ist die Frage, ob es Probleme mit ge-
wissen Zusatzeigenschaften gibt, die beweisbar nur in nicht-polynomialer Zeit ge-
löst werden können und daher als schwierig einzustufen sind. Diese Frage ist eng
mit einer weiteren, bisher ungelösten Frage verbunden: Sind die Komplexitäts-
klassen P und NP gleich? Sehr vereinfacht ausgedrückt gibt es in der Klasse NP
vermutlich mathematische Probleme, die viel schwieriger zu lösen sind als die
Probleme der Klasse P .
Wir bestimmen explizit die Laufzeiten der Addition und Multiplikation ganzer
Zahlen und Polynome, der Divison mit Rest für ganze Zahlen und Polynome
wie auch die Laufzeiten des euklidischen Algorithmus und der Bestimmung von
Inversen von Elementen aus der primen Restklassengruppe Z n - es sind dies die

grundlegenden Operationen, die in der Kryptologie durchgeführt werden.
Einwegfunktionen sind Funktionen, die im Sinne der Komplexität leicht berechnet,
aber nur schwer invertiert werden können. Solche Funktionen sind die Basis für
alle asymmetrischen kryptografischen Systeme.

4.1 Komplexität

Wir werden die Laufzeit von Algorithmen mit dem asymptotischen Verhalten
von Funktionen vergleichen. Dazu betrachten wir vorab reellwertige Funktionen
und fragen nach ihremVerhalten im Unendlichen . Wir erinnern zunächst an einige
Begriffe aus der Analysis.