Systemweite Parameter

Alle Benutzer können diese Parameter gemeinsam nutzen:

• Eine Gruppe ${\displaystyle G}$ primer Ordnung ${\displaystyle q=|G|}$. Diese ist zyklisch, sei ${\displaystyle g}$ ein Generator
• Eine kryptografische Hash-Funktion ${\displaystyle H}$ mit Wertebereich ${\displaystyle [0,q-1]}$.

Schnorr schlägt vor, eine Untergruppe ${\displaystyle G}$ von ${\displaystyle Z_{p}^{*}}$ für ein primes ${\displaystyle p}$ zu wählen. Um eine Untergruppe von ${\displaystyle Z_{p}^{*}}$ zu finden, muss (p-1), die Ordnung von ${\displaystyle Z_{p}^{*}}$, in Primzahlen faktorisiert werden. Dann kann (p-1) als ${\displaystyle q=|G|}$ mal einem Cofaktor h geschrieben werden. Wenn g ein Generator von ${\displaystyle Z_{p}^{*}}$ ist, kann ein Generator von ${\displaystyle G}$ als ${\displaystyle g^{h}}$ bestimmt werden.

Die Länge des privaten Schlüssels und der Signatur werden allein durch die Ordnung der Untergruppe ${\displaystyle q=|G|}$ bestimmt.

Privater Schlüssel zur Signaturerstellung

Der private Schlüssel besteht aus einer zufällig gewählten Zahl

• ${\displaystyle x}$ mit ${\displaystyle 0<x<q}$

Öffentlicher Schlüssel zur Prüfung der Signatur

Der öffentliche Schlüssel ${\displaystyle x}$ ist das entsprechende Gruppenelement ${\displaystyle y}$:

• ${\displaystyle y=g^{x}}$

Für elliptische Kurven formuliert

Wir betrachten eine elliptische Kurve der Ordnung q über GF(p). Der Generator G ist ein Punkt auf der Kurve und es sei ${\displaystyle Y=x\cdot G}$ der öffentliche Schlüssel.

1. Wähle ${\displaystyle k}$ zufällig mit ${\displaystyle 0<k<q}$.
2. Setze ${\displaystyle R:=k\cdot G}$
3. Setze ${\displaystyle e:=H(R_{x}||m)}$. Dabei ist ${\displaystyle ||}$ die Konkatenation und ${\displaystyle R_{x}}$ die ${\displaystyle x}$-Koordinate des Punktes ${\displaystyle R}$.
4. Setze ${\displaystyle s:=(k+xe){\bmod {q}}}$. Falls die Bitlänge von ${\displaystyle e}$ größer als die Bitlänge von ${\displaystyle q}$ ist, werden vor der Berechnung von ${\displaystyle s}$ die überzähligen (rechten) Bits von ${\displaystyle e}$ gestrichen.

Die Unterschrift der Nachricht ${\displaystyle m}$ ist das Tupel ${\displaystyle (e,s)}$ oder ${\displaystyle (R,s)}$.

Mit elliptischer Kurve

1. Berechne ${\displaystyle R=(s\cdot G)-(e\cdot Y)}$
2. Setze ${\displaystyle e_{v}:=H(R_{x}||m)}$
3. Akzeptiere die Unterschrift genau dann, wenn ${\displaystyle e_{v}=e}$ ist.

Wenn die Unterschrift im Format ${\displaystyle (R,s)}$ ist, kann es wie folgt verifiziert werden:

1. Berechne ${\displaystyle R_{v}:=s\cdot G-H((R_{x}||m)\cdot Y}$
2. Akzeptiere die Unterschrift genau dann, wenn ${\displaystyle R_{v}=R}$ ist.

Ein-Partei-Signaturen

1. Der Unterschreiber ist im Besitz von mehreren privaten Schlüsseln ${\displaystyle x_{i}}$, womit auch mehrere öffentliche Schlüssel ${\displaystyle y_{i}}$ existieren
2. Der Unterschreiber berechnet ${\displaystyle s:=(k+x_{1}\cdot e+x_{2}\cdot e+x_{3}\cdot e+\dotsb )}$
3. Beim Verifizieren ist ${\displaystyle r_{v}:=g^{s}\cdot y_{1}^{-e}\cdot y_{2}^{-e}\cdot y_{3}^{-e}\cdot \ldots }$

Batch verification

Wenn mit ${\displaystyle (r,s)}$ unterschrieben wird, so ist es möglich, Signaturen und öffentliche Schlüssel zusammen zu rechnen.

${\displaystyle s:=s_{1}+s_{2}+s_{3}+\dotsb }$

${\displaystyle r:=r_{1}\cdot r_{2}\cdot r_{3}\cdot \ldots }$

${\displaystyle y:=y_{1}\cdot y_{2}\cdot y_{3}\cdot \ldots }$

Dies kann verwendet werden, um mehrere Signaturen gleichzeitig zu verifizieren. Das könnte in der Bitcoin-Blockchain verwendet werden, damit nicht alle Nodes alle Transaktionen validieren müssen.

Bellare-Neven-Verfahren

Eine Lösung ist, dass jede Partei den Hash aller öffentlichen Schlüssel mit-unterschreibt.

1. ${\displaystyle L:=H(y_{1}||y_{2}||y_{3}||\dotsb )}$
2. ${\displaystyle r}$ bleibt das Produkt der einzelnen noncen: ${\displaystyle r:=r_{1}\cdot r_{2}\cdot r_{3}\cdot \ldots }$
3. ${\displaystyle s_{i}}$ ist eine partielle Signatur die jeder für sich berechnet ${\displaystyle s_{i}:=k_{i}+x\cdot H(L,y_{i},r,m)}$
4. die danach zusammen addiert werden: ${\displaystyle s:=s_{1}+s_{2}+s_{3}+\dotsb }$

Mit ${\displaystyle g^{s}=r\cdot y_{1}^{-H(L,y_{1},r,m)}\cdot y_{2}^{-H(L,y_{2},r,m)}\cdot y_{3}^{-H(L,y_{3},r,m)}\cdot \ldots }$ kann man es verifizieren.

MuSig

1. ${\displaystyle L:=H(y_{1}||y_{2}||y_{3}||\dotsb )}$
2. ${\displaystyle a_{i}:=H(L||y_{i})}$
3. ${\displaystyle y:=y_{1}^{a_{1}}\cdot y_{2}^{a_{2}}\cdot y_{3}^{a_{3}}\cdot \ldots }$ so dass: ${\displaystyle y:=g^{x_{1}\cdot a_{1}+x_{2}\cdot a_{2}+x_{3}\cdot a_{3}+\dotsb }}$
4. ${\displaystyle r:=r_{1}\cdot r_{2}\cdot r_{3}\cdot \ldots }$ so dass: ${\displaystyle r:=g^{k_{1}+k_{2}+k_{3}+\dotsb }}$ Man sollte ${\displaystyle r_{i}}$ erst mit den anderen Parteien teilen, wenn man ein Commitment auf deren ${\displaystyle r_{i}}$ erhalten hat.
5. ${\displaystyle c:=H(y||r||m)}$
6. ${\displaystyle s_{i}:=r_{i}+ca_{i}x_{i}}$
7. ${\displaystyle s:=s_{1}+s_{2}+s_{3}+\dotsb }$

Dieses Verfahren hat den Vorteil, dass nur die involvierten Parteien die einzelnen öffentlichen Schlüssel kennen müssen. Ein Außenstehender kann mit dem kombinierten öffentlichen Schlüssel bestätigen, dass es sich um eine valide Signatur handelt. Besonders bei Blockchain-Anwendungen, in denen Privatsphäre wertvoll und Speicherplatz knapp ist, könnte das Schnorr-Verfahren, am Beispiel der Bitcoin-Blockchain bis zu 25 % Speicherplatz einsparen.

Anforderung an die Zufallszahlen

Aus den obigen Ausführungen folgt, dass sich die Zufallszahlen k, die zur Berechnung der Signatur verwendet werden, keinesfalls wiederholen dürfen. Würde eine Zufallszahl zur Signatur zweier unterschiedlicher Nachrichten verwendet, könnte der private Schlüssel x aus öffentlich bekannten Werten berechnet werden. Damit könnten dann Signaturen von einem Angreifer gefälscht werden. Weiterhin dürfen die Zufallszahlen für den Angreifer nicht berechenbar sein, da er sonst x berechnen könnte.