Chaum-van Antwerpen

In diesem Abschnitt zeigen wir, daß auch ungewöhnliche, DLP-basierte Signatur-Verfahren auf beliebigen Gruppen und damit auf elliptischen Kurven übertragen werden können. Das folgende Signatur-Verfahren erzeugt ,,unabweisbare'' Signaturen (Undeniable Signatures). Bei diesem Signatur-Verfahren erfordert die Verifikation die Unterstützung des Signierers:

Algorithmus 7.3 (Chaum-van Antwerpen)  

1. Schlüsselpaar-Erzeugung:

   A führt folgende Schritte durch:

   • wähle eine Gruppe $G$ der Ordnung $n$ und ein Element $h\in G$ mit Primordnung $r$;
   • wähle eine Zufallszahl $a$ mit $1<a<r$;
   • berechne $\alpha \leftarrow a\cdot h$.
   As öffentlicher Schlüssel ist $\left( G,h,\alpha \right)$, As geheimer Schlüssel ist $a$.

2. Signatur

   A führt die folgenden Schritte durch:

   • Bilde $M$ (oder einen Hash-Wert von $M$) auf $\mu \in H=\left\langle h\right\rangle$ ab;
   • berechne $\rho \leftarrow a\cdot \mu$;
   As Signatur von $M$ ist $\rho$.

3. Verifikation

   B führt die folgenden Schritte durch:

   • besorge As authentischen, öffentlichen Schlüssel;
   • wähle zwei Zufallszahlen $e_{1},e_{2}\in \mathbb{Z}_{r}^{*}$;
   • berechne $\beta \leftarrow e_{1}\cdot \rho +e_{2}\cdot \alpha$;
   A führt die folgenden Schritte durch:
   • berechne $v\leftarrow \left( a^{-1}\mod r\right) \cdot \beta$;
   B akzeptiert die Signatur genau dann, wenn $e_{1}\cdot \mu +e_{2}\cdot h=v$ ist.

Die Verifikation folgt aus

$$v = \left( a^{-1}\mod r\right) \cdot \beta$$

$$= \left( a^{-1}\mod r\right) \cdot \left( e_{1}\cdot \rho +e_{2}\cdot \alpha \right)$$

$$= a^{-1}e_{1}a\cdot \mu +a^{-1}e_{2}a\cdot h$$

$$= e_{1}\cdot \mu +e_{2}\cdot h$$

Die Kooperation von A ist zwingend erforderlich, ohne As Mithilfe kann B die Signature nicht verifizieren. A könnte seine Kooperation nach belieben verweigern, legitim wäre dies aber nur, wenn eine gefälschte Signatur zur Überprüfung vorläge. A kann aber gefälschte Signaturen als solche durch das Disavowal-Protokoll als solche nachweisen:

Algorithmus 7.4   Sei $\rho \neq a\cdot \mu$

1. Disavowal

   B führt die folgenden Schritte durch:

   • wähle zwei Zufallszahlen $e_{1},e_{2}\in \mathbb{Z}_{r}^{*}$;
   • berechne $\beta _{e}\leftarrow e_{1}\cdot \rho +e_{2}\cdot \alpha$;
   A führt die folgenden Schritte durch:
   • berechne $v_{e}\leftarrow \left( a^{-1}\mod r\right) \beta _{e}$;
   B führt die folgenden Schritte durch:
   • prüfe, ob $v_{e}\neq e_{1}\cdot \mu +e_{2}\cdot h$ ist;
   • wähle zwei Zufallszahlen $f_{1},f_{2}\in \mathbb{Z}_{r}^{*}$;
   • berechne $\beta _{f}\leftarrow f_{1}\cdot \rho +f_{2}\cdot \alpha$;
   A führt die folgenden Schritte durch:
   • berechne $v_{f}\leftarrow \left( a^{-1}\mod r\right) \beta _{f}$;
   B führt die folgenden Schritte durch:
   • prüfe, ob $v_{f}\neq f_{1}\cdot \mu +f_{2}\cdot h$ ist;
   • prüfe schließlich, ob $f_{1}\cdot \left( v_{e}-e_{2}\cdot h\right) =e_{1}\cdot \left( v_{f}-f_{2}\cdot h\right)$ ist.

Der Schlüssel zu diesem Protokoll steckt in dem aller letzten Schritt. Damit überprüft B nämlich, ob As Berechnungen dem Protokoll entsprechen, denn es gilt

$$f_{1}\cdot \left( v_{e}-e_{2}\cdot h\right) = f_{1}\cdot \left( a^{-1}\beta _{e}-e_{2}\cdot h\right)$$

$$= f_{1}\cdot \left( a^{-1}\cdot \left( e_{1}\cdot \rho +e_{2}\cdot \alpha \right) -e_{2}\cdot h\right)$$

$$= f_{1}a^{-1}e_{1}\cdot \rho$$

$$e_{1}\cdot \left( v_{f}-f_{2}\cdot h\right) = e_{1}\cdot \left( a^{-1}\beta _{f}-f_{2}\cdot h\right)$$

$$= e_{1}\cdot \left( a^{-1}\cdot \left( f_{1}\cdot \rho +f_{2}\cdot \alpha \right) -f_{2}\cdot h\right)$$

$$= e_{1}a^{-1}f_{1}\cdot \rho$$