RSA-Signaturen

Schlüsselgenerierung Signatur erstellen Signatur prüfen Korrektheit Beispiel Übungen

Die bei dem RSA-System (Ronald Rivest, Adi Shamir, Leonard Adleman) verwendete Transformation zur Verschlüsselung einer Nachricht ist bijektiv und kann deshalb mit nur minimalen Anpassungen für digitale Signaturen verwendet werden: vertauscht man im System die Verwendung von öffentlichem und geheimem Schlüssel, so entspricht dies dem Vorgang des Signierens.

Der Inhaber des geheimen Schlüssels (und nur dieser) kann durch das "Verschlüsseln" einer Nachricht eine Signatur erzeugen, die mittels des öffentlichen Schlüssels, der allgemein verfügbar ist, geprüft werden kann. Diese Signatur ist dabei ebenso lang wie die ursprüngliche Nachricht, welche sich allein aus der Signatur ermitteln lässt. Oft wird dies jedoch nicht benötigt und, um die Signatur zu verkürzen, verwendet man die schon erwähnten Hashverfahren.

Schlüsselgenerierung

Das RSA-System unterscheidet nicht zwischen Schlüsselpaaren für Ver-/Entschlüsselung und denen für Signaturen, sodass man den schon vorgestellten Algorithmus zur Schlüsselgenerierung dafür verwenden kann.

Signatur erstellen

A möchte die Nachricht $\text{[math]}$ mit seinem privaten Schlüssel $\text{[math]}$ signieren. Er berechnet hierfür

\text{[math]}

und erhält die Signatur $\text{[math]}$ der Nachricht $\text{[math]}$ . Dieser Schritt entspricht dem Entschlüsseln im RSA-Kryptosystem. Das Paar $\text{[math]}$ stellt nun die signierte Nachricht dar.

Signatur prüfen

Um sicherzustellen, dass eine Nachricht $\text{[math]}$ wirklich von A signiert wurde und unverändert ist, überprüft B mit dem öffentlichen Schlüssel $\text{[math]}$ von A die Signatur $\text{[math]}$

\text{[math]}

und vergleicht das Ergebnis $\text{[math]}$ mit der empfangenen Nachricht $\text{[math]}$ . Sind beide identisch, so wurde die Nachricht, nachdem A sie signiert hat, nicht verändert.

Korrektheit

Die Korrektheit von RSA-Signaturen ergibt sich unmittelbar aus dem Nachweis über die Korrektheit des RSA-Systems zur Verschlüsselung von Nachrichten:

\text{[math]}

Beispiel

Der erste Schritt zum Signieren der Zeichenkette "RSA ist ein weit verbreitetes Public-Key-Verfahren." ist die Ermittlung des Hashwertes. RSA schreibt hierbei keinen speziellen Algorithmus vor und für dieses Beispiel werden wir der Einfachheit halber die Summe der ASCII-Werte als Hashwert betrachten.

\text{[math]}

Schlüsselgenerierung.
In der Praxis sollte man mindestens einen 768-Bit Schlüssel, besser jedoch 1024 Bits oder mehr verwenden. Für einen $\text{[math]}$ -Bit Schlüssel wählt man die Primzahlen $\text{[math]}$ und $\text{[math]}$ jeweils $\text{[math]}$ Bits lang und zwar so, dass die Differenz $\text{[math]}$ nicht zu klein ist (sonst liegen $\text{[math]}$ und $\text{[math]}$ in der Nähe von $\text{[math]}$ und lassen sich ggf. effizient ermitteln). Dieses Beispiel hingegen benutzt sehr viel kleinere Primzahlen $\text{[math]}$ und $\text{[math]}$ und somit erhalten wir die 25-Bit Zahlen

\text{[math]}

\text{[math]}

Nun wählen wir den öffentlichen Exponenten $\text{[math]}$ zufällig und teilerfremd zu $\text{[math]}$ gemäß der Gleichverteilung, in diesem Fall $\text{[math]}$ . Mit dem erweiterten Euklidischen Algorithmus berechnen wir den geheimen Exponenten $\text{[math]}$ :

\text{[math]}

Daraus folgt, dass $\text{[math]}$ und somit $\text{[math]}$ .

Signatur erstellen.
Die Signatur $\text{[math]}$ zu $\text{[math]}$ unter Verwendung des privaten Schlüssels $\text{[math]}$ ergibt sich als

\text{[math]}

Signatur prüfen.
Die Korrektheit der Signatur s prüfen wir nun wie folgt:

\text{[math]}

Das berechnete Ergebnis ist gleich dem Hashwert der empfangenen Nachricht und die Signatur wird somit als gültig erkannt.

Übungen

Aufgabe 1
Alice benutzt eine RSA-Signatur mit öffentlichem Schlüssel $\text{[math]}$ , um das Dokument $\text{[math]}$ zu signieren und an Bob zu senden. Was ist ihre Signatur und wie verifiziert Bob diese? Ist es sinnvoll, dass Alice ihr Dokument zuerst (mit dem öffentlichen Schlüssel) verschlüsselt und dann das verschlüsselte Dokument signiert und beides (Chiffrat und Signatur) an Bob schickt?

Aufgabe 2
Betrachten Sie Signaturen gemäß dem RSA-Verfahren mit öffentlichem Schlüssel $\text{[math]}$ .

Ein Angreifer möchte zwei verschiedene Dokumente $\text{[math]}$ mit gleicher Unterschrift finden. Ist dieses möglich?
Ein Angreifer kenne nur ein gültiges Dokument/Signatur-Paar $\text{[math]}$ . Wieviele neue gültige Dokument/Signatur-Paare kann er damit erzeugen?

Aufgabe 3
Bei der Fälschung der digitalen Signatur von Alice nach dem RSA-Schema wählt Oskar $\text{[math]}$ , berechnet unter Verwendung des öffentlichen Schlüssels $\text{[math]}$ von Alice $\text{[math]}$ und sendet das Dokument/Unterschriftpaar $\text{[math]}$ an Bob. Ist dieses eine gültige Unterschrift von Alice? Wie sinnvoll ist dieses Vorgehen von Oskar?

Wie kann man diesen Angriff von Oskar vermeiden?

Link zu den Lösungen