Dipl.-Inform. Carsten Eilers

Die Bezeichnungen aus der Beschreibung des RSA-Verfahrens als Konzelationssystem werden zunächst umbenannt:
Aus dem Chiffrierschlüssel c wird der Testschlüssel t, und
aus dem Dechiffrierschlüssel d wird der Signierschlüssel s.

Das Signieren geschieht dann durch modulare Exponentiation mit s, für den Klartextblock m also durch die Berechnung von
m^s mod n.

Das Testen erfolgt durch modulare Exponentiation der Signatur mit t und anschließenden Vergleich des Ergebnisses mit dem dazu gehörenden Textblock. Für den Klartextblock m mit der Signatur m^s also durch
(m^s)^t mod n = m ?

Den Einsatz von RSA als digitalem Signatursystem zeigt Abbildung 1.

Abb. 1: RSA als digitales Signatursystem

Angriffe auf diese Anwendung

Wird RSA wie beschrieben eingesetzt, kann ein Angreifer Signaturen fälschen, indem er rückwärts rechnet: Er wählt eine Signatur, exponentiert sie modular mit t und erhält den passenden Textblock.

Dieser passive Angriff bricht RSA als digitales Signatursystem zwar existenziell, aber nicht selektiv: Der Angreifer kann nicht zu einer gewünschten Nachricht die Signatur fälschen.

Es ist noch ein weiterer passiver Angriff möglich:

Kennt der Angreifer die Signaturen m₁^s und m₂^s unter den Textblöcken m₁ und m₂, kann er durch modulare Multiplikation eine dritte Signatur m₃^s und einen passenden Textblock m₃ berechnen:

m₃^s := m₁^s * m₂^s mod n
und
m₃ := m₁ * m₂ mod n

m₃^s ist eine Signatur von m₃, denn es gilt m₁^s * m₂^s = (m₁ * m₂)^s, da RSA eine multiplikative Struktur besitzt.

Auch dieser Angriff erlaubt kein selektives Brechen, der Angreifer kann sich nicht gezielt eine Nachricht aussuchen, deren Signatur er fälschen möchte. Zum selektiven Brechen ist ein aktiver Angriff notwendig:

1. Der Angreifer wählt den Textblock m₃ nach seinen Wünschen.
2. Er wählt ein beliebiges m₁, zu dem mod n ein multiplikatives Inverses m₁^-1 existiert.
3. Er berechnet m₂ := m₃ * m₁^-1 mod n.
4. Er lässt m₁ und m₂ signieren und
5. erhält m₁^s und m₂^s als Ergebnis zurück.
6. Er berechnet m₃^s := m₁^s * m₂^s mod n

Das entspricht ausgeschrieben bzw. eingesetzt:
m₁^s * m₂^s mod n = m₁^s * (m₃ * m₁^-1)^s mod n
                            = m₁^s * m₃^s * m₁^-1s mod
                            = m₃^s

Die Grundidee dieses Angriffs besteht darin, die gewünschte Nachricht m₃, die der Angreifer signieren lassen möchte, so mit einer vorbereiteten Zufallszahl r^t zu multiplizieren, dass das Opfer sie signiert, ohne den tatsächlichen Inhalt zu erkennen. Der Angreifer muss die erhaltene Signatur dann nur noch durch r dividieren.

Ähnlich erfolgt ein entsprechender Angriff auf RSA als Konzelationssystem: Der Angreifer tarnt den zu entschlüsselnden Schlüsseltextblock durch eine Zufallszahl und lässt ihn entschlüsseln.

Beide Angriffe funktionieren nur, wenn RSA wie beschrieben eingesetzt wird und das Opfer vorgelegte Nachrichten signiert bzw. entschlüsselt, ohne auf ihren Inhalt zu achten. Letzteres ist zum Beispiel dann möglich, wenn ein Programm automatisch agiert.

Wie derartiger Angriffe verhindert werden wird in der nächsten Folge beschrieben. Dann geht es auch um den Einsatz von RSA im Rahmen eines hybriden Verschlüsselungsverfahrens.

Carsten Eilers