Benutzer:Bananenfalter/GMR (Signaturverfahren)

Weblinks

Wikibooks: Beweisarchiv: Sicherheit des GMR-Signatursystems – Lern- und Lehrmaterialien

Alter Artikel

GMR ist ein digitales Signaturverfahren, das nach seinen Erfindern Shafi Goldwasser, Silvio Micali und Ronald L. Rivest benannt ist.

Wie auch RSA beruht GMR auf der Faktorisierungsannahme, dass es bijektive Funktionen gibt, die schnell zu berechnen sind, bei denen die Berechnung der Umkehrfunktion jedoch sehr aufwändig ist.
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.

Das Verfahren im Einzelnen

Man benötigt ein kollisionsresistentes Permutationspaar mit Geheimnis $f_{0}^{},f_{1}^{}$ mit dem Definitionsbereich $D$ . Der Besitzer des Geheimnisses kann die Umkehrfunktionen $f_{0}^{-1}$ und $f_{1}^{-1}$ leicht berechnen. Für alle anderen ist das schwer.

Um eine einzige Nachricht zu signieren muss der Sender eine Referenz aus $D$ zufällig wählen und authentisch veröffentlichen. Um eine n bit lange Nachricht $m_{1},m_{2},...,m_{n}$ zu signieren berechnet er die Signatur $f_{m_{1}}^{-1}(f_{m_{2}}^{-1}(..f_{m_{n}}^{-1}(R)..))$ . Der Empfänger kann die Umkehrfunktion davon berechnen und das Ergebnis mit der Referenz vergleichen.

Offensichtlich besteht das Problem darin, für jede Nachricht eine neue Referenz zu veröffentlichen. Dies wird mit Referenzbäumen realisiert.

Notizen

http://www.infosec.pku.edu.cn/course/2004/GMR84.pdf – Originalpaper http://www.semper.org/sirene/publ/FoPf_91GMR.VIS91.ps.gz

Permutationspaar:

{\begin{aligned}f_{0}(x)&\colon ={\begin{cases}x^{2}\mod n,&{\text{falls }}x^{2}\mod n<{\frac {n}{2}},\\-x^{2}\mod n&{\text{ sonst.}}\end{cases}}\\f_{1}(x)&\colon ={\begin{cases}4\cdot x^{2}\mod n,&{\text{falls }}4\cdot x^{2}\mod n<{\frac {n}{2}},\\-4\cdot x^{2}\mod n&{\text{ sonst.}}\end{cases}}\end{aligned}}

Verifizieren beginnend mit MSB
einfach zu berechnen

Umkehrpermutation:

{\begin{aligned}f_{0}^{-1}(x)&\colon ={\begin{cases}{\sqrt {x}}\mod n,&{\text{falls }}{\sqrt {x}}<{\frac {n}{2}},\\-{\sqrt {x}}\mod n&{\text{sonst.}}\end{cases}}\\f_{1}^{-1}(x)&\colon ={\begin{cases}2^{-1}{\sqrt {x}}\mod n,&{\text{falls }}2^{-1}{\sqrt {x}}<{\frac {n}{2}},\\-2^{-1}{\sqrt {x}}\mod n&{\text{sonst.}}\end{cases}}\end{aligned}}

Signieren beginnend mit LSB
Wurzelziehen mod n ist schwer, Berechnung nur mittels Kenntnis von p, q prim mit n = p · q

Probleme:

Jedes Zwischenergebnis ist die korrekte Signatur der bis dahin verkürzten Nachricht. → präfixfreie Nachricht
Einmalreferenzen $R$ müssen authentisch sein. → Referenzenbaum

Handbook of Cryptography, S.468 ff.

GMR ist Einmal-Signatur-Schema → durch Erweiterung mit Referenzbaum kann man mehrere Nachrichten signieren
eher theoretischer Natur, aber trotzdem praktisch umsetzbar → Sirene: Fox/Pfitzmann
kollisionsfreie Permutation: es ist praktisch unmöglich ein Paar x,y \in D, x \neq y zu finden, für welches f_0(x) = f_1(y)
Einwegpermutation mit Falltür: unter Kenntnis einer Zusatzinformation (hier p, q) ist es effizient möglich f_0^{-1} und f_1^{-1} zu bestimmen.
Wenn ein Angreifer die Umkehrpermutation berechnen könnte, dann wäre es leicht eine Kollision zu finden: wähle x, berechne z = f_0(x) und y = f_1^{-1}(z), dann ist f_0(x) = f_1(y).

Wahl von p und q: p \equiv 3 \pmod 4 und q \equiv 7 \pmod 8 – notwendig, da sonst nicht gewährleistet ist, dass die Permutation kollisionsresistent ist (siehe Beweis) → Sicherheit kann auf Faktorisierungsannahme zurückgeführt werden

Parameter:

R

… zufällig gewählter Verifikationsparameter (Referenz, eine binäre Zeichenkette)

\left(f_{0},f_{1},R\right)

… öffentlicher Verifikationsschlüssel

\left(f_{0}^{-1},f_{1}^{-1}\right)

… privater Signierschlüssel

Eine binäre Zeichenkette $m=m_{1}|m_{2}|m_{3}|\dots |m_{t}$ kann mit dem Verifikationsparameter $R$ signiert werden. Man beachte dabei die umgekehrte Reihenfolge, in der die einzelnen Zeichen bearbeitet werden:

sig_{R}(m)=f_{m_{1}}^{-1}\left(f_{m_{2}}^{-1}\left(f_{m_{3}}^{-1}\left(\dots f_{m_{t}}^{-1}\left(R\right)\dots \right)\right)\right)

Der Signierer sendet Nachricht und Signatur $\left(m,sig_{R}(m)\right)$ an den Empfänger. Dieser kann nun die Signatur überprüfen:

R^{\prime }=f_{m_{t}}\left(\dots f_{m_{3}}\left(f_{m_{2}}\left(f_{m_{1}}\left(sig_{R}(m)\right)\right)\right)\dots \right)

R^{\prime }\ {\stackrel {\mathrm {?} }{=}}\ R

Ist die berechnete Referenz $R^{\prime }$ gleich dem Verifikationsparameter $R$ , so kann davon ausgegangen werden, dass die Nachricht $m$ vom Besitzer des privaten Schlüssels signiert und seit dem nicht verändert wurde. Die Authentizität des Signierers muss auf andere Weise sichergestellt werden, zum Beispiel indem öffentliche Schlüssel zertifiziert werden.

Der Verifikationsparameter $R$ sollte erst mit der Nachricht veröffentlicht werden, da es für einen Angreifer sonst über einen längeren Zeitraum mit entsprechend hohem Rechenaufwand möglich sein könnte, eine Kollision und somit eine andere Nachricht zu finden, welche bei gleichem Verifikationsparameter die gleiche Signatur erzeugt. [Quelle!?]

Referenzbaum

authentication trees
öffentlicher Binärbaum mit $2^{k}$ Blattknoten
(vorerst) nicht-öffentliche $2^{k}$ zufällige Referenzen $R_{i}$

Erstellen eines Referenzbaumes:

Wähle zufällige Wurzelreferenz $r$ und weitere Referenzen $r_{0}$ und $r_{1}$ .
Erstelle mittels GMR Signatur für Verkettung von $r_{0}$ und $r_{1}$ mit dem Verifikationsparameter $r$ : $sig_{r}(r_{0}|r_{1})$
Wähle zufällige Referenzen $r_{00}$ und $r_{01}$ . Signiere diese mit dem Verifikationsparameter $r_{0}$ : $sig_{r_{0}}(r_{00}|r_{01})$
Und so weiter: Dies kann für jeden Ast beliebig oft wiederholt werden. Immer werden zwei neue zufällig gewählte Referenzen $r_{j0},r_{j1}$ mit der übergeordneten Referenz $r_{j}$ signiert. Um $2^{k}$ Blattknoten zu erhalten muss der Binärbaum $k$ Ebenen haben.

Es muss mindestens die Wurzelreferenz öffentlich bekannt sein. Neue Äste können bei Bedarf erstellt werden. Soll eine Nachricht signiert werden, dann wählt man eine der noch nicht veröffentlichten Referenzen $R_{i}$ . Diese wird mit einem noch nicht verwendeten Blattknoten als Verifikationsparamter signiert: $sig_{R_{i}}(r_{i})$ . Um eine Signatur zu überprüfen benötigt der Verifizierer immer mindestens die Referenzen und deren Signaturen des gesamten Astes vom Wurzelknoten bis zum entsprechenden Blattknoten sowie den Verifikationsparameter für die Nachricht $R_{i}$ und dessen Signatur $sig_{R_{i}}(r_{i})$ . $R_{i}$ und dessen Signatur werden, wie im Fall ohne Referenzbäume immer erst mit der Nachricht veröffentlicht.

→ Beispiel

Referenzbaum…