Elliptic Curve DSA
# Elliptic Curve DSA

Der Elliptic Curve Digital Signature Algorithm (ECDSA) ist eine Variante des Digital Signature Algorithm (DSA), die Elliptische-Kurven-Kryptographie verwendet.

## Unterschiede zum normalen DSA-Verfahren

Generell gilt bei der Elliptische-Kurven-Kryptographie die Faustregel, dass die Bitlänge des Erzeugers der verwendeten Untergruppe etwa dem Doppelten des Sicherheitsniveaus $t$ entsprechen sollte. Bei einem Sicherheitsniveau von $t=80$ Bit, bei dem ein Angreifer $2^{80}$ elementare Operationen durchführen muss, um den privaten Schlüssel zu finden, hätte ein DSA-Schlüssel eine Länge von circa 1024 Bit, ein ECDSA-Schlüssel aber nur eine Länge von 160 Bit. Eine Signatur ist jedoch bei beiden Verfahren gleich lang: $4t$ Bit, also 320 Bit für ein Sicherheitsniveau von 80 Bit.

## Schlüsselerzeugung

Alice möchte eine signierte Nachricht an Bob schreiben. Zu Beginn muss man sich auf die Kurvenparameter $(q,FR,a,b,DomainParameterSeed,G,n,h)$ einigen. Die ersten Parameter beschreiben die verwendete Kurve: $q$ ist die Ordnung des Körpers, auf dem die Kurve definiert ist; $FR$ ist die Angabe der verwendeten Basis; $a$ und $b$ sind zwei Körperelemente, die die Gleichung der Kurve beschreiben; $DomainParameterSeed$ ist eine mögliche, zufällig erzeugte Zeichenkette, die vorliegt, wenn die Kurve nachweislich zufällig erzeugt wurde. Weiterhin werden benötigt:

* $G$, ein fester Erzeuger der $n$-Torsionsuntergruppe der Kurve (i. e., $G=(x_{G},y_{G})$);
* $n$, die Ordnung des Punktes $G$, und $h$, der Cofaktor (gleich der Ordnung der Kurve geteilt durch die Gruppenordnung $n$);
* $L_{n}$, die Bitlänge der Gruppenordnung $n$;
* eine kryptologische Hashfunktion HASH, wie z. B. SHA-2.

Um ihr Schlüsselpaar zu generieren, erzeugt Alice als geheimen Schlüssel $d_{A}$ eine zufällige Ganzzahl im Intervall $[1,n-1]$. Der zugehörige öffentliche Schlüssel ist $Q_{A}=d_{A}G$.

## Algorithmus zur Erzeugung einer Signatur

Will Alice eine Nachricht $m$ signieren, geht sie folgendermaßen vor:

* Berechne $e={\textrm {HASH}}(m)$ und definiere $z$ als die $L_{n}$ höchstwertigen Bits von $e$.
* Wähle eine zufällige Ganzzahl $k$ von $[1,n-1]$.
* Berechne $r=x_{1}{\pmod {n}}$, wobei $(x_{1},y_{1})=kG$. Wenn $r=0$, gehe zum Schritt 2 zurück.
* Berechne $s=k^{-1}(z+rd_{A}){\pmod {n}}$. Wenn $s=0$, gehe zum Schritt 2 zurück.
* Die Signatur ist das Paar $(r,s)$.

Wenn $s$ berechnet wird, sollte der Wert $z$, der aus ${\textrm {HASH}}(m)$ stammt, in eine Ganzzahl umgewandelt werden. Dabei ist zu beachten, dass $z$ größer als $n$ sein kann, aber nicht länger.

Es ist entscheidend, dass für verschiedene Signaturen auch verschiedene $k$-Werte verwendet werden, ansonsten kann die Gleichung im Schritt 4 nach dem geheimen Schlüssel $d_{A}$ aufgelöst werden: Aus zwei Signaturen $(r,s)$ und $(r,s')$, die mit demselben, unbekannten $k$ verschiedene bekannte Nachrichten $m$ und $m'$ signieren, kann ein Angreifer $z$ und $z'$ berechnen. Weil $s-s'=k^{-1}(z-z')$ entspricht (alle Operationen in diesem Absatz werden mit modulo $n$ durchgeführt), kann dann auch $k={\frac {z-z'}{s-s'}}$ berechnet werden. Aus $k$ kann der Angreifer wegen $s=k^{-1}(z+rd_{A})$ auch den privaten Schlüssel $d_{A}={\frac {sk-z}{r}}$ berechnen. Dieser Fehler in der Verschlüsselung wurde z. B. verwendet, um die Verschlüsselung in der Spielkonsole PlayStation 3 zu berechnen und damit die Beschränkung auf offiziell veröffentlichte Software auszuhebeln.

## Überprüfung einer Signatur

Wenn Bob die Echtheit einer von Alice erzeugten Signatur prüfen möchte, muss er eine Kopie ihres öffentlichen Schlüssels $Q_{A}$ besitzen. Wenn er sich nicht sicher ist, dass $Q_{A}$ ordnungsgemäß erzeugt wurde, muss er überprüfen, ob es sich wirklich um einen Schlüssel handelt (das neutrale Element wird mit $O$ bezeichnet):

* Überprüfe, ob $Q_{A}$ ungleich $O$ ist und dass die Koordinaten ansonsten valide sind
* Überprüfe, ob $Q_{A}$ auf der Kurve liegt
* Überprüfe, ob $nQ_{A}=O$. Hier wird überprüft, ob $Q_{A}$ ein Vielfaches des Erzeugers $G$ ist. Falls in den Kurvenparametern der Kofaktor $h=1$ ist, kann dieser Schritt weggelassen werden.

Danach führt Bob folgende Schritte durch:

* Überprüfe, ob $r$ und $s$ ganze Zahlen sind und im Intervall $[1,n-1]$ liegen. Wenn dies nicht der Fall ist, ist die Signatur ungültig.
* Berechne $e={\textrm {HASH}}(m)$, wobei HASH die gleiche Funktion wie bei der Erzeugung der Signatur ist. Bezeichne mit $z$ die $L_{n}$ höchstwertigen Bits von $e$.
* Berechne $w=s^{-1}{\pmod {n}}$.
* Berechne $u_{1}=zw{\pmod {n}}$ und $u_{2}=rw{\pmod {n}}$.
* Berechne $(x_{1},y_{1})=u_{1}G+u_{2}Q_{A}$.
* Die Signatur ist gültig, wenn $r=x_{1}{\pmod {n}}$, ansonsten ist sie ungültig.

Mit Hilfe von Straus’ Algorithmus (auch bekannt als Shamir's Trick) kann die Summe zweier skalarer Multiplikationen ($u_{1}G+u_{2}Q_{A}$) schneller berechnet werden.

## Normen und Standards

### ANSI

Der Standard X9.62-2005 des American National Standards Institute ist die maßgebliche Spezifikation von ECDSA, die von den nachfolgend genannten Standards als Referenz verwendet wird.

### NIST

Das US-amerikanische National Institute of Standards and Technology empfiehlt im Standard FIPS 186-4 fünfzehn elliptische Kurven.

### SECG

Die Standards for Efficient Cryptography Group (SECG) ist ein 1998 gegründetes Konsortium zur Förderung des Einsatzes von ECC-Algorithmen, welches im Dokument SEC1 auch den ECDSA spezifiziert.

### ISO/IEC

Die International Organization for Standardization und die International Electrotechnical Commission definiert ECDSA in dem internationalen Standard ISO/IEC 14888-3 (der ältere Standard 15946-2 wurde 2007 zurückzogen). Darin werden neben EC-DSA (die im Standard verwendete Abkürzung) noch die Varianten EC-GDSA (Elliptic Curve German Digital Signature Algorithm), EC-KCDSA (Korean Certificate-based Digital Signature Algorithm), EC-RDSA (Russian Digital Signature Algorithm), EC-SDSA und EC-FSDSA (Schnorr und Full Schnorr Digital Signature Algorithm) spezifiziert.

### BSI

Das Bundesamt für Sicherheit in der Informationstechnik legt in der Technischen Richtlinie TR-03111 Vorgaben und Empfehlungen u. a. für die Implementierung des ECDSA fest.

## Implementierungen

### Open Source

* OpenSSH: Ab Version 5.7 (24. Januar 2011) ist ECDSA und der Schlüsselaustausch via Elliptic Curve Diffie-Hellman (ECDH) aus dem RFC 5656 implementiert.
* OpenSSL: Ab Version 0.9.8 (5. Juli 2005) implementiert.
* BouncyCastle: Ab 10. März 2014
* GnuTLS
* .Net-Framework ab Version 3.5
