Komplexität und Einwegfunktionen - Kryptologie - page 79

Anwendung: Verschlüsselung. Die Nachricht

N

soll an den Teilnehmer T ver-

verschickt. Nur T kennt f − 1
T

( N )

schickt werden. Dazu wird f T und kann daher

f − 1
T

(

f T ( N )) berechnen. Nicht einmal der Absender kann

N

aus f T ( N ) zurück-

N gewinnen (wenn er etwa vergessen hat), weil f T eine Einwegfunktion ist.

Anwendung: Signatur. Teilnehmer T will die Nachricht

N

signieren. Dazu be-

rechnet T den Ausdruck f − 1
T

, f − 1
T

( N ) ( N ( N )) und verschickt . Jeder kann durch

Anwenden von f T die Unterschrift verifizieren.
In der Praxis wird nicht die Nachricht

N , die sehr groß sein kann, signiert, son-

dern ein Hashwert h . Dabei ist h eine geeignete, kollisionsresistente Hash-

funktion. Der Vorteil des Einsatzes von Hashfunktionen besteht darin, dass die
Signatur eine feste Länge hat, unabhängig von der signierten Datenmenge.
An dieser Stelle wird auch klar, warum die Hashfunktion kollisionsresistent sein
muss. Könnte ein Angreifer eine Kollision erzeugen, also x , y mit h

( N )

,so
könnte er versuchen, den arglosen Teilnehmer T dazu zu bewegen, die harmlos
aussehende Nachricht x zu signieren, und hätte dann eine gültige Unterschrift
für die Nachricht y , von der T nichts weiß.

(

x

)=

h

(

y

)

Bemerkung

Ein Signaturschema liefert Integrität und Authentizität , wie sie im nächsten Ka-
pitel beschrieben werden. Darüber hinaus können auch juristische Kategorien
wie

• Willenserklärung,
• Unwiderruflichkeit,

• Rechtsverbindlichkeit

realisiert werden.

Wichtig ist dabei, eine unlösliche Verknüpfung zwischen den Teilnehmern T
und der zugehörigen öffentlichen Abbildung f T herzustellen. Beispielsweise
muss verhindert werden, dass ein Angreifer eine gefälschte Abbildung f T -
etwa auf eine Webseite - plaziert, die für T 's Abbildung gehalten wird (man
vgl. hierzu auch das Problem mit dem Mann in der Mitte auf Seite 169). Das
ist ein nichttriviales, technisches Problem, das unter dem Stichwort Public-Key-
Infrastruktur behandelt wird.

Aufgaben

4.1 Führen Sie den Beweis des Satzes 4.4 in allen Details aus.

4.2 Bestimmen Sie die Laufzeit des üblichen Algorithmus für die Division mit
Rest.