Die bisherigen Kapitel haben sich mit der so genannten

symmetrischen Kryptografie

beschäftigt, bei der je zwei Teilnehmer einen Schlüssel benötigen, der vor allen anderen Teilnehmern geheim gehalten werden muss. Wenn man sich ein großes Netzwerk von Teilnehmern vorstellt, in dem eine vertrauliche Kommunikation zwischen je zwei Teilnehmern realisiert werden soll, so hat die Symmetrie unmittelbare Konsequenzen:

1.

Wenn es

N

Teilnehmer gibt, so muss jeder Teilnehmer

N

-1 Schlüssel geheim speichern.

2.

Wenn ein neuer Teilnehmer hinzukommt, müssen alle Teilnehmer ihre Schlüsseldatei aktualisieren.

3.

Sender und Empfänger müssen einen gemeinsamen Schlüssel vereinbaren.

4.

Sender und Empfänger müssen sich gegenseitig darin vertrauen, dass keiner den gemeinsamen Schlüssel preisgibt.

Das wohl bekannteste Beispiel eines Public-Key-Verschlüsselungsverfahrens ist der

RSA-Algorithmus

(so benannt nach seinen drei Erfindern Rivest, Shamir, Adleman im Jahr 1977, [RSA78]). Seine Sicherheit beruht auf der Schwierigkeit, Zahlen zu faktorisieren. Wir geben zunächst einen Überblick über den Algorithmus und stellen anschließend die mathematischen Grundlagen zusammen, die man zum Verständnis dieses Algorithmus benötigt. Die letzten Abschnitte beschäftigen sich mit der Sicherheitsanalyse des RSA.

Wir haben im letzten Abschnitt ein Public-Key-System, nämlich den RSA-Algorithmus kennen gelernt; dessen Sicherheit beruht auf dem Faktorisierungsproblem. Diffie und Hellman, die Erfinder der Public-Key-Kryptografie, haben in ihrer Veröffentlichung von 1976 ein anderes mathematisches Problem benutzt, um ein Public-Key-System, die Diffie-Hellman-Schlüsselvereinbarung, zu entwerfen:

den diskreten Logarithmus

. Dabei handelt es sich um das folgende Problem: Gegeben seien eine Primzahl

p

und zwei ganze Zahlen

g, y

. Gesucht ist eine ganze Zahl

x

mit der Eigenschaft

g

x

mod

p

=

y

. Gesucht ist also der Logarithmus von

y

zur Basis

g

, allerdings nicht über den reellen Zahlen, sondern modulo einer Primzahl, daher auch der Name

diskreter

Logarithmus. Bis heute kennt man keinen effizienten Algorithmus, der dieses Problem lösen kann. Wie die Faktorisierung gilt auch das Problem des diskreten Logarithmus heute als „schwieriges“ Problem.

Bereits in Kapitel 11 wurde erwähnt, dass sich die Diffie-Hellman-Schlüsselvereinbarung, die ElGamal-Verschlüsselung und die ElGamal-Signatur nicht nur auf durchführen lassen, sondern dass man die Verfahren auf beliebige Gruppen verallgemeinern kann. Insbesondere kann man Gruppen auswählen, für die das Problem des diskreten Logarithmus besonders schwer zu lösen ist. Solche Gruppen haben den Vorteil, dass man mit verhältnismäßig kleinen Schlüssellängen auskommt.

Die Sicherheitsbetrachtungen zu den Public-Key-Verschlüsselungsverfahren haben sich bisher auf die Frage beschränkt, ob die Verfahren die

Public-Key- Eigenschaft

erfüllen, das heißt auf die Frage, ob es mäglich ist, aus dem äffentlichen Schlüssel eines Teilnehmers dessen privaten Schlüssel zu berechnen. Für ein sicheres Public-Key-Verschlüsselungsverfahren reicht diese Forderung aber nicht aus. So ist es denkbar, dass ein Angreifer zwar nicht den privaten Schlüssel eines Teilnehmers berechnen kann, aber über einen effizienten Algorithmus verfügt, der alle Nachrichten an diesen Teilnehmer entschlüsseln kann. Die bisherigen Sicherheitsbetrachtungen haben also nur die Sicherheit des privaten Schlüssels analysiert, nicht aber die Sicherheit der Geheimtexte.

Digitale Signaturen sind neben den Public-Key-Verschlüsselungen der zweite wichtige Baustein der asymmetrischen Kryptografie. Wenn man den RSA-Algorithmus betrachtet, bei dem man ein Signaturschema dadurch konstruieren kann, dass man die Anwendungsreihenfolge der Schlüssel vertauscht, so könnte man vermuten, dass man die Sicherheitsbegriffe der Verschlüsselung auch für die Signatur verwenden kann. Dass dem nicht so ist, kann man sich leicht an Hand der ElGamal-Signatur klarmachen: Die Signatur hat eine völlig andere Struktur als die Verschlüsselung. Zu wissen, dass die Verschlüsselung sicher ist, reicht hier nicht aus, um Aussagen über die Sicherheit des Signaturschemas zu machen.