Angriff auf stereotype Nachrichten (Menü Einzelverfahren \ RSA-Kryptosystem \ Gitterbasierte Angriffe auf RSA)

Sie können den Angriff über den Dialog Angriff auf stereotype Nachrichten ausführen.

Der Gitterangriff auf stereotype RSA-Nachrichten ermöglicht es, eine dem RSA-Kryptosystem verschlüsselte Nachricht zu entschlüsseln. Stereotyp bedeutet in diesem Fall, dass die verschlüsselte Nachricht einem festen dem Angreifer bekannten Schema entspricht und sich nur ein kleiner Teil unbekannt ist.

Eine weitere Voraussetzung für diesen Angriff ist, dass zur Verschlüsselung der Nachricht ein kleiner öffentlicher Schlüssel e (z.B. 3) verwendet wurde.
Der Angriff kann also zum Beispiel dann durchgeführt werden, wenn stets eine annähernd gleiche Nachricht versendet wird, in der sich nur ein kleiner Teil ändert. (z.B. das Datum, ein Passwort oder eine PIN)

Die Grundidee hinter diesem Angriff besteht darin, die Suche nach dem unbekannten Teil der Nachricht in eine Nullstellensuche umzuformen. Dazu betrachtet man die Verschlüsselungsfunktion des RSA Verfahrens:

me = c (mod N)
Hier bezeichnet m den Klartext der Nachricht und c den Chiffretext. N ist der RSA-Modulus, e der öffentliche Schlüssel. Wenn man nun m zerlegt in einen bekannten Teil mb und den unbekannten Teil x , dann lässt sich die obige Formel umschreiben zu:
(mb + x)e - c = 0 (mod N)

In dieser Gleichung ist x die einzige Unbekannte. Die Nullstelle x0 stellt nun den unbekannten Teil der Nachricht dar. Sie wird bei diesem Angriff unter Zuhilfenahme der Gitterbasenreduktion gesucht.

Coppersmith stellte 1996 in [Cop96b] diesen Angriff als Anwendung des von ihm entwickelten Verfahrens zur Nullstellensuche vor.

Quellen:

[Cop96b]
Coppersmith, Don: Finding a Small Root of a Univariate Modular Equation. In: Advances in Cryptology – EUROCRYPT ’96, Lecture Notes in Computer Science 1070 (1996), S. 155–165