Dark ITSec

GMR

GMR ist ein digitales Signaturverfahren, das nach seinen Erfindern Shafti Goldwasser, Silvio Micali und Ronald L. Rivest benannt ist. Wie auch RSA beruht GMR auf der Faktorisierungsannahme.
Im Gegensatz zu RSA lässt sich für GMR jedoch beweisen, dass es selbst bei einem adaptiven aktiven Angriff nicht möglich ist, auch nur eine neue Signatur zu fälschen.

Die Signierung beruht auf der Tatsache, daß es Funktionen gibt, die zwar relativ einfach zu berechnen sind, deren Umkehrfunktionen aber ohne bestimmte Zusatzinformationen kaum berechenbar sind. So sind z.B. die Primfaktoren großer Zahlen in einer annehmbaren Zeit (noch) nicht berechenbar. GMR verwendet nun eine Familie solcher Funktionen zum Signieren. Um eine Nachricht zu signieren, wählt man zuerst eine zufällige Referenz R, auf diese wendet man dann eine von der Nachricht m (und dem Schlüssel) abhängige Funktion an und erhält s(m)=f_m^-1(R) als Signatur. Zum Berechnen dieser Umkehrfunktion braucht man dabei zwei Primzahlen p und q, die noch weitere Zusatzbedingungen erfüllen müssen. Um diese Signatur zu testen, wendet man nun die Ursprungsfunktion, zu deren Berechnung man nicht p und q, sondern nur deren Produkt n benötigt, auf die Nachricht an (siehe Abbildung). Als Ergebnis muß dann das R herauskommen, das mit übermittelt werden muß, d.h. R = f_m(s(m)). Da man nicht für jede Nachricht eine eigene Funktion haben will, wird die Nachricht im Binärformat dargestellt und eine Funktion für das Bit 0 und eine für das Bit 1 gewählt. Um nun den Vorteil von GMR, beliebig lange Nachrichten signieren zu können, auszunutzen, verkettet man diese Funktionen, z.B. ist f₁₁₀(x):=f₁(f₁(f₀(x))).

Bei der Konstruktion der Funktionen muß darauf geachtet werden, daß diese kollisionsfrei sind. Kollisionsfrei bedeutet, daß es fast unmöglich ist, Kollisionen zu finden, ohne ein bestimmtes Geheimnis zu kennen. Eine Kollision findet statt, wenn zwei unterschiedliche Nachrichten mit unterschiedlichen Argumenten das gleiche Ergebnis liefern, d.h. f₀(x)=f₁(y). Mit Hilfe einer Kollision kann man aber n faktorisieren und damit das Geheimnis herausfinden.

Als Funktionen werden

und

definiert. Das Quadrieren ist eine ziemlich einfache Operation, wohingegen das Wurzelziehen modulo n ohne Kenntnis von p und q kaum möglich ist. Mit Kenntnis von p und q können allerdings die Wurzeln modulo p und modulo q berechnet werden, woraus sich mit dem Chinesischem Restealgorithmus die Wurzel modulo n berechnen läßt. Der Definitionsbereich der Funktionen muß allerdings noch eingeschränkt werden, da sonst durch die Modulo-Rechnung eine Zahl mehrere Wurzeln haben kann.
Deshalb wird der Bereich eingegrenzt: Dn{x€ Z |(x/n)=1, x<n/2}

Beispiel
Wir wählen p=3 und q=7, da dies die kleinsten Zahlen sind, die die Bedingungen erfüllen. Daraus folgt n=p*q=21. Hieraus ergibt sich ein Definitionsbereich von D₂₁={-10; -5; -4; -1; 1; 4; 5; 10}. Verschlüsselt werden soll hier die Nachricht m=110. Wir wählen die Referenz R=4. Somit ist die Signatur der Nachricht s(110)=f₁₁₀^-1(R) = f₀^-1(f₁^-1(f₁^-1(4))). Wenn man dies nun durchrechnet ergibt sich 4 -> 1 -> 4 -> -5. Diese letzte Zahl (-5) wird nun zusammen mit der Nachricht und R (wird auch signiert) übermittelt. Der Empfänger benötigt außerdem n aus einem öffentlichen Verzeichnis. Nun berechnet dieser f₁₁₀(s(110))=f₁(f₁(f₀(-5))). Wenn er nun als Ergebnis unser R (also 4) erhält, weiß er, daß die Signatur gültig ist, und damit nicht verändert wurde und von dem richtigem Absender stammt. Er rechnet hierfür: -5 -> 4 -> 1 -> 4, und somit ist die Signatur bestätigt.

Sicherheit:
Die Sicherheit von GMR beruht - wie die von vielen anderen Verfahren - im Wesentlichen auf der Richtigkeit der bisher nicht bewiesenen Faktorisierungsannahme. Diese Annahme besagt, daß die Faktorisierung großer Zahlen sehr schwierig ist, was man sich hier zu Nutze macht. Im Gegensatz zu vielen anderen Verfahren (z.B. RSA) ist - wenn die Annahme gilt - aber seine Sicherheit bewiesen. Es existieren also bei richtiger Anwendung keine praktikablen Angriffsmethoden.