RSA-Signaturverfahren

Mallory kann die Nachrichten von Alice an Bob abfangen. Er kann die verschlüsselten Nachrichten zwar nicht entschlüsseln, aber einfach Teile löschen und den gekürzten Text anschließend an Bob weitersenden. Wenn Bob die Chiffre entschlüsselt, wird er entweder ein Buchstabenpuzzle ohne jeglichen Sinn erhalten, wodurch Mallorys Manipulation enttarnt wäre. Gelingt es Mallory jedoch, ganze Wörter zu entfernen, so erscheint der Text sinnentstellt bei Bob und dieser erkennt unter Umständen gar nicht, dass Mallory am Werk war.

Um das zu verhindern sollten Alice und Bob die Nachricht signieren, was einer Umkehrung der RSA-Verschlüsselung gleich kommt.

Algorithmus 4.0 (RSA-Public-Key-Signaturverfahren)
(1) Zur Signierung führt Alice die folgenden Schritte aus:

(a) Alice berechnet die Signatur: $sig = m^d\ mod\ n$

(b) Alice übermittelt die Signatur sig an Bob.

(2) Zur Verifizierung und zum Erhalt der Nachricht führt Bob die folgenden Schritte aus:

(a) Bob besorgt sich den authentischen öffentlichen Schlüssel (n, e) von Alice.

(b) Bob berechnet $m = sig^e\ mod\ n$. Wenn $sig^e\ mod\ n$ kein plausibler Klartext ist, wird die Signatur abgelehnt, andernfalls wird sie akzeptiert und $sig^e\ mod\ n$ als m anerkannt.

(3) In einem Streitfall zwischen Alice und Bob kann ein neutraler Richter überprüfen, ob $sig^e\ mod\ n = m$ gilt.

Wenn man das Signaturprotokoll so anwendet, wie es oben beschrieben ist, ergibt sich das Problem, dass die Signatur die gleiche Länge besitzt, wie das zu unterzeichnende Dokument, was auch bedeutet, dass ein ziemlich hoher Zeitbedarf zur Signierung nötig ist. Der Vorteil bei dem Verfahren ist jedoch, dass sogenanntes „Message Recovery“ besteht. Dies bedeutet, dass die Originalnachricht bei der Verifizierung aus der Signatur wieder gewonnen werden kann.

$sig = m^d\ mod\ n$
$sig^e\ mod\ n = (m^d)^e\ mod\ n = m$

RSA wird gewöhnlich in Blöcken verschlüsselt, da für die Nachricht m gelten muss m < n. Mallory hat daher unter Umständen die Möglichkeit, einzelne Blöcke der Signatur zu entfernen, so dass sich beim Entschlüsseln dennoch ein sinnvoller, vermutlich aber sinnentstellter Text ergibt. Der Angriff ist also noch nicht abgewehrt.

Eine mögliche Lösung für das Problem besteht in der Verwendung von sog. Hashfunktion, mit deren Hilfe es möglich ist, Nachrichten nahezu beliebiger Länge auf eine durch die Hashfunktion festgelegte Größe zusammenzufassen. Dieses Zusammenfassen kann auch als „message digest“ bezeichnet werden.
$H(m) = h\$
Anschließend sollte der gebildete Hashwert, also die gehashte Nachricht mit oben beschriebenem Protokoll signiert werden, was dank der Kürze der kryptographischen Prüfsumme meist deutlich schneller möglich ist und überdies noch Speicherplatz spart. Dieses Vorgehen kann man als Hash-and-Sign-Verfahren bezeichnen.

Wichtig ist hierbei zu erwähnen, dass es sich bei Hashfunktion vermutlich um Einwegfunktionen handelt, die nicht effizient umkehrbar sind.

Folglich sollte Alice neben dem signierten Hashwert auch die ursprüngliche Nachricht (Urbild) an Bob senden.

Nach dem Erhalt der Nachricht von Alice empfiehlt es sich für Bob zunächst die Signatur von Alice zu verifizieren. Dazu kann Bob die Signatur mit Alices öffentlichem Schlüssel dechiffrieren, worauf er den Signaturhashwert erhält. Um zu überprüfen, ob die Originalnachricht oder die Signatur von Mallory verändert wurde, hat er die Möglichkeit, aus dem unverschlüsselten Klartext ebenfalls einen Hashwert zu bilden. Dazu sollte Bob, um ein verwertbares Ergebnis zu erhalten, die gleiche Hashfunktion, die auch Alice verwendet hat, anwenden. Die Information, welche Hashfunktion von Alice verwendet wurde, ist in der Regel neben dem Hashwert in der Signatur enthalten. Anschließend kann Bob die Hashwerte vergleichen. Stimmen sie überein, wurde nichts verändert.
Die Hashfunktion SHA-1 (Secure Hash Algorithm), die einen Hashwert von 160 Bit erzeugt, wird heutzutage häufig bei der digitalen Signatur eingesetzt.

Frage:
Wie könnte es Alice mit den bereits kennen gelernten Methoden erreichen, dass Mallory auch den mitgesendeten Klartext nicht lesen kann?

Lösung anzeigen

Lösung verstecken

Zunächst sollte Alice die Nachricht signieren und anschließend sowohl Nachricht als auch Signatur mit dem öffentlichen Schlüssel von Bob verschlüsseln. Man spricht hier auch von einem kryptographischen Umschlag.
Dabei ist die Reihenfolge entscheidend, wie an folgendem einfachen Beispiel deutlich wird.

Betrachtet man einen Brief, so ist es einleuchtend, dass man diesen unterschreibt, bevor man ihn in den Umschlag steckt, denn umgekehrt könnte man den Brief einfach aus dem unterschriebenen Umschlag herausnehmen und einen anderen Brief hineinstecken.
Gleiches gilt auch für die Kryptographie.

Um Problemen bei der Signierung vorzubeugen, sollten Alice und Bob zur Signatur ein gesondertes Schlüsselpaar generieren, so dass für Alice, wie auch für Bobs Schlüssel gilt:

$n_{Signieren}< t\ und\ n_{Verschluesseln}\ge t\ ; t \in \N$, wobei t in Absprache zwischen Alice und Bob festgelegt wird.

Die gerade vorgestellte digitale Signatur stellt eine zentrale Ergänzung zur RSA-Verschlüsselung dar, weil die digitale Signatur dazu beiträgt, die generellen Ziele der Kryptografie zu erfüllen.
Mit der digitalen Signatur lässt sich durch zusätzliche normale RSA-Verschlüsselung Vertraulichkeit erreichen. Darüber hinaus ist in der Regel die von Alice und Bob gewünschte Authentizität gewährleistet, wobei man hier einmal die Teilnehmerauthentizität (peer entity authentication) und die Nachrichtenauthentizität (message authentication ) unterscheiden kann. Ersteres garantiert, dass ein Teilnehmer eindeutig identifiziert werden kann und Zweiteres stellt sicher, dass der Ursprung einer Nachricht zweifelsfrei ermittelt werden kann. Darüber hinaus können Dateien nicht unbemerkt verändert werden, was das Ziel der Integrität erfüllt. Zuletzt ist gegenüber einem unabhängigen Dritten auch eindeutig nachweisbar, dass eine Datei die B von A erhalten hat, wirklich von A stammt, somit ist auch Verbindlichkeit gegeben.

Doch wer gewährleistet eigentlich, dass die Schlüsselpaare, die verwendet werden, auch wirklich den realen Personen gehören, für die sie sich ausgeben. Auf das Beispiel bezogen: Wer kann sicherstellen, dass Bob auch wirklich den öffentlichen Schlüssel von Alice erhalten hat und sich dahinter nicht Mallory verbirgt (vgl. Man-in-the-middle-Attacke)? Klaus Schmeh drückt es in seinem Buch „Kryptografie“ so aus; „Das Problem [...] ist, dass man einem öffentlichen Schlüssel nicht ansieht, wem er gehört“ .

Die Frage, wie man dem öffentlichen Schlüssel dennoch ansehen kann, von wem er stammt, wird auf der nächsten Seite beantwortet.




zurück zur Übersicht

---