ECDSA

Was ist ECDSA?

ECDSA (Elliptic Curve Digital Signature Algorithm) ist ein asymmetrisches kryptografisches Signaturverfahren, das auf elliptischen Kurven basiert.

Das Verfahren kann auf verschiedenen elliptischen Kurven eingesetzt werden. Beispiele dafür sind secp256k1, secp256r1 (NIST P-256) oder secp384r1.

Bitcoin verwendet ECDSA auf der Kurve secp256k1. Die Eigenschaften dieser Kurve und die Ableitung von Public Keys werden auf der secp256k1-Seite genauer behandelt.

ECDSA verwendet ein Schlüsselpaar aus einem Private Key und einem Public Key.

Mit dem Private Key kann eine digitale Signatur erzeugt werden. Mit dem zugehörigen Public Key kann jeder überprüfen, ob diese Signatur gültig ist.

Eine digitale Signatur dient als kryptografischer Nachweis, dass bestimmte Daten mit dem zugehörigen Private Key signiert wurden. Gleichzeitig ist sie fest an die signierten Daten gebunden, sodass jede nachträgliche Änderung die Signatur ungültig macht.

Eine gültige Signatur beweist daher sowohl die Herkunft der signierten Daten als auch deren Integrität seit der Signaturerzeugung.

Asymmetrisches Verfahren

Signieren

Private Key

c6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5

Nachricht

Signatur

—

—

Prüfen

Public Key

0244112159a51b68b54784fe2913bf9f58e537d3a743b92a58b501fe1a248adcea

Nachricht

Signatur

—

—

Zuerst in Signieren eine Signatur erzeugen, dann Prüfen klicken.

ECDSA verwendet zwei unterschiedliche Schlüssel:

Mit dem Private Key wird eine Signatur erzeugt.
Mit dem Public Key kann diese Signatur überprüft werden.

Die Signatur ist dabei nicht nur an den Schlüssel, sondern auch an die signierten Daten gebunden.

Erzeuge zunächst eine Signatur für die Nachricht „BitcoinVonInnen“. Die Prüfung mit dem Public Key ist anschließend erfolgreich.

Ändere danach die Nachricht und prüfe erneut.

Obwohl derselbe Public Key und dieselbe Signatur verwendet werden, schlägt die Prüfung nun fehl. Bereits eine kleine Änderung an den signierten Daten führt zu einer anderen kryptografischen Prüfsumme und macht die Signatur ungültig.

Dadurch kann ein Empfänger nicht nur überprüfen, wer signiert hat, sondern auch erkennen, ob die signierten Daten seit der Signatur verändert wurden.

Wie verwendet Bitcoin ECDSA?

In der vereinfachten Darstellung verwendet Bitcoin ECDSA, um nachzuweisen, dass eine Transaktion von demjenigen autorisiert wurde, der den Private Key zum auszugebenden UTXO kennt.

Der Ausgangspunkt ist ein UTXO. Er enthält Ausgabebedingungen mit einem hinterlegten Public Key. Um ihn auszugeben, erstellt die Wallet eine neue Transaktion und signiert die Transaktionsdaten mit ECDSA.

Jeder Node empfängt die Transaktion und prüft, ob die Signatur zu genau diesen Transaktionsdaten und zu dem im UTXO hinterlegten Public Key passt. Ist die Prüfung erfolgreich, gilt die Transaktion als autorisiert.

ECDSA schützt damit nicht die Bitcoin selbst, sondern den kryptografischen Nachweis, wer einen UTXO ausgeben darf und welche Transaktion dabei autorisiert wurde. Die Konsensregeln akzeptieren einen Spend nur dann, wenn dieser Nachweis erfolgreich erbracht wird.

Wie entsteht eine ECDSA-Signatur?

Der Signatur-Hash entsteht in Bitcoin durch das SIGHASH-Verfahren. Die Wallet wählt den Input-Index und den SIGHASH-Typ, serialisiert die ausgewählten Transaktionsfelder und bildet daraus per Double SHA-256 den 32-Byte Signatur-Hash z.

SIGHASH-Vorlage anklicken für Details.

Für die Erzeugung einer ECDSA-Signatur werden drei Eingaben benötigt:

der Signatur-Hash z
der Private Key d
eine einmalig verwendete Nonce k

Der Signatur-Hash z ist die eigentliche Nachricht, die ECDSA verarbeitet. Er wird zusammen mit dem Private Key d und der Nonce k an den Signaturalgorithmus übergeben.

Die Nonce k ist eine zusätzliche Zahl, die für jede Signatur neu erzeugt wird. Sie sorgt dafür, dass ECDSA aus denselben Eingabedaten unterschiedliche Signaturen erzeugen kann und ist ein wichtiger Bestandteil der Sicherheit des Verfahrens.

ECDSA-Parameter

Signatur-Hash = z
Private Key = d
Nonce = k

Parameter anklicken für Details.

Anschließend verwendet ECDSA den Signatur-Hash z, den Private Key d und die Nonce k, um zwei neue Werte zu berechnen:

Diese beiden Zahlen bilden gemeinsam die eigentliche ECDSA-Signatur.

ECDSA Signieren

r oder s anklicken für Details.

Bereits kleine Änderungen an den geschützten Transaktionsdaten führen zu einem anderen Signatur-Hash und damit zu anderen Werten für r und s. Die ursprüngliche Signatur wird dadurch ungültig.

In Bitcoin werden r und s anschließend in das DER-Format serialisiert. Diese DER-kodierte Signatur wird zusammen mit dem jeweiligen SIGHASH-Typ im ScriptSig oder im Witness gespeichert.

DER-Signatur + SIGHASH

3045022100b0acecba455bde22ca9b610e6908c0e1e27a31862cbad3bb334f754451ce580f02203cb514d3dc7f4614097c26d2d4f8d0072a9ce072bf939f4432f030f3e36ae2f701

SEQUENCE
Länge
INTEGER r
Länge r
Padding r
r
INTEGER s
Länge s
s
SIGHASH

DER- oder SIGHASH-Anteil anklicken für Details.

Die einzelnen Werte in den Diagrammen können angeklickt werden. Die Detailansichten erklären ihre Herkunft und ihre Rolle innerhalb des ECDSA-Signaturvorgangs.

Wie genau entsteht (r,s) beim Signieren?

Die eigentliche ECDSA-Signatur entsteht aus drei Eingaben:

dem Signatur-Hash z
dem Private Key d
einer einmalig verwendeten Nonce k

Aus diesen Werten berechnet ECDSA die beiden Signaturbestandteile r und s.

Wie entsteht r?

Zunächst multipliziert ECDSA die Nonce k mit dem Generatorpunkt G der Kurve secp256k1. Das Ergebnis dieser Punktmultiplikation ist ein Punkt R auf der Kurve.

Für die Signatur wird anschließend nur die x-Koordinate dieses Punktes verwendet. Aus ihr wird durch die Operation mod n der erste Signaturbestandteil r berechnet.

Wichtig ist dabei die Unterscheidung zwischen Zahlen und Punkten:

k ist eine Zahl (Nonce).
G ist der Generatorpunkt der Kurve.
R ist der Punkt, der durch die Punktmultiplikation R = k × G entsteht.
r ist wieder eine Zahl und wird aus der x-Koordinate von R berechnet.

ECDSA wechselt hier zwischen zwei Welten: Zahlen werden als Skalare verwendet, während Punktmultiplikationen auf der elliptischen Kurve stattfinden.

Dieselbe Punktmultiplikation wird auch bei der Erzeugung von Public Keys verwendet. Ein Public Key entsteht als P = d × G, während ECDSA für die Signatur die Nonce verwendet und R = k × G berechnet.

Die Schreibweise mod n bedeutet, dass das Ergebnis auf den Zahlenbereich der Gruppenordnung n abgebildet wird. Dadurch entsteht ein gültiger Signaturwert, der später zusammen mit s die ECDSA-Signatur bildet.

Wie entsteht s?

Nachdem ECDSA r berechnet hat, wird daraus der zweite Teil s erzeugt.

Dafür kombiniert ECDSA vier Werte:

den Signatur-Hash z
den Private Key d
die Nonce k
den zuvor berechneten Wert r

Die Berechnung erfolgt nach der Formel:

s = k⁻¹(z + r·d) mod n

Im Gegensatz zu r entsteht s nicht direkt aus einem Punkt auf der elliptischen Kurve.

Während r aus der x-Koordinate des Kurvenpunkts R = k × G abgeleitet wird, entsteht s ausschließlich durch arithmetische Operationen im Zahlenraum von ECDSA.

Dabei verknüpft s alle wichtigen Bestandteile des Signaturvorgangs miteinander:

den signierten Inhalt (z)
den Private Key (d)
die Nonce (k)
den zuvor berechneten Wert r

Dadurch hängt die fertige Signatur sowohl von den signierten Daten als auch vom verwendeten Schlüssel und der verwendeten Nonce ab.

Bereits eine Änderung an einem dieser Werte führt zu einem anderen Ergebnis für s und damit zu einer anderen Signatur.

Die Schreibweise k⁻¹ bezeichnet das multiplikative Inverse der Nonce k im Zahlenraum modulo n.

Das mod n am Ende reduziert das Ergebnis auf den gültigen Zahlenbereich der Kurve secp256k1. Mehr zur Kurve, zum Generatorpunkt G und zur Punktmultiplikation auf der secp256k1-Seite.

Zusammen bilden die beiden Werte r und s die vollständige ECDSA-Signatur.

Im nächsten Schritt werden r und s in das DER-Format serialisiert.

Wie werden r und s gespeichert?

Die Werte r und s bilden die eigentliche ECDSA-Signatur.

Bitcoin speichert diese beiden Zahlen jedoch nicht direkt in einer Transaktion. Stattdessen werden sie zunächst in das DER-Format (Distinguished Encoding Rules) serialisiert.

Dabei werden r und s als ASN.1-Integer kodiert und im DER-Format zu einer gemeinsamen Bytefolge serialisiert. Anschließend wird ein Byte für den verwendeten SIGHASH-Typ angehängt.

DER-Signatur + SIGHASH

3045022100b0acecba455bde22ca9b610e6908c0e1e27a31862cbad3bb334f754451ce580f02203cb514d3dc7f4614097c26d2d4f8d0072a9ce072bf939f4432f030f3e36ae2f701

SEQUENCE
Länge
INTEGER r
Länge r
Padding r
r
INTEGER s
Länge s
s
SIGHASH

DER- oder SIGHASH-Anteil anklicken für Details.

Das Ergebnis ist die bekannte hexadezimale Darstellung einer Bitcoin-Signatur.

Die fertige Signatur wird anschließend zusammen mit weiteren Nachweisdaten in ScriptSig oder im Witness gespeichert.

Wie verifiziert man eine ECDSA-Signatur?

Für die Verifikation benötigt ECDSA:

den Signatur-Hash z
den Public Key P
den Signaturbestandteil r
den Signaturbestandteil s

Im Gegensatz zur Signaturerzeugung werden weder der Private Key noch die Nonce benötigt.

Stattdessen rekonstruiert ECDSA aus den bekannten Werten einen Punkt auf der Kurve und überprüft, ob daraus derselbe Wert r entsteht, der in der Signatur enthalten ist.

Der Public Key P ist keine einzelne Zahl, sondern ein Punkt auf der elliptischen Kurve mit den Koordinaten (x,y). Deshalb arbeitet die Verifikation nicht nur mit Zahlen, sondern auch mit Punktoperationen auf der Kurve.

Die Verifikation beginnt mit dem multiplikativen Inversen von s und leitet daraus die Hilfswerte u₁ und u₂ ab. Daraus wird der Kurvenpunkt R = u₁G + u₂P rekonstruiert. Aus seiner x-Koordinate entsteht r', das mit dem Signaturwert r verglichen wird.

Dabei gilt:

G ist der Generatorpunkt der Kurve.
P ist der Public Key.
R ist der rekonstruierte Kurvenpunkt.

Die Verifikation funktioniert, weil die Mathematik der elliptischen Kurve dafür sorgt, dass bei einer korrekt erzeugten Signatur derselbe Punkt rekonstruiert wird, aus dem ursprünglich r entstanden ist.

Eine gültige Signatur beweist damit, dass:

die Signatur zum angegebenen Public Key gehört,
die signierten Daten seit der Signatur nicht verändert wurden,
und die Signatur nur von jemandem erzeugt werden konnte, der den zugehörigen Private Key kennt.

Wann kann ein Private Key berechnet werden?

Szenario	Bekannt	Angriffswahrscheinlichkeit	Warum?
HASH160(P) bekannt	HASH160(P)	≈256 Bit	Public Key unbekannt
Public Key bekannt	P=dG	≈256 Bit	ECDLP
Public Key + Signatur	P,r,s,z	≈256 Bit	d und k unbekannt
Viele Signaturen	…	≈256 Bit	kein zusätzlicher Hebel
Nonce wiederverwendet	gleiches k	0 Bit	d ableitbar

Für klassische Computer bleibt die Sicherheit von ECDSA praktisch unverändert, selbst wenn Public Keys, Signaturen oder viele Signaturen veröffentlicht werden.

Kennt ein Angreifer lediglich einen Public-Key-Hash (HASH160(P)), einen vollständigen Public Key (P = dG) oder sogar mehrere Signaturen desselben Schlüssels, existiert weiterhin kein bekannter Weg, den Private Key effizient zu berechnen.

Ist der Public Key bekannt, entspricht die Berechnung des Private Keys dem sogenannten Elliptic Curve Discrete Logarithm Problem (ECDLP). Für die Bitcoin-Kurve secp256k1 gilt dieses Problem als praktisch unlösbar.

Erst die Wiederverwendung derselben Nonce k für zwei unterschiedliche Signaturen führt dazu, dass der Private Key mathematisch berechnet werden kann. In diesem Fall fällt die Sicherheit unmittelbar auf 0 Bit.

Warum reichen öffentliche Informationen nicht aus?

Bekannt

PPublic Key

rerster Signaturbestandteil

szweiter Signaturbestandteil

zSignatur-Hash

Unbekannt

dPrivate Key

kNonce

s = k⁻¹(z + rd) mod n

d = (sk − z) · r⁻¹ mod n

k = (z + rd) · s⁻¹ mod n

Zur Berechnung von d wird weiterhin k benötigt.
Zur Berechnung von k wird weiterhin d benötigt.
Beide unbekannten Werte hängen voneinander ab.

dbrauchtk·kbrauchtd

P+r+s+z≠Private Key berechenbar

Aus einer einzelnen Signatur entsteht deshalb keine eindeutige Lösung. Öffentliche Informationen wie Public Keys, Signaturen oder Signatur-Hashes reichen nicht aus, um den Private Key zu berechnen.

Warum ist die Nonce so wichtig?

Die Sicherheit von ECDSA hängt entscheidend davon ab, dass für jede Signatur eine eigene Nonce k verwendet wird.

Werden zwei unterschiedliche Nachrichten mit derselben Nonce signiert, entstehen mehrere Gleichungen mit denselben unbekannten Werten. Dadurch kann zunächst die Nonce und anschließend der Private Key berechnet werden.

Moderne Bitcoin-Implementierungen verwenden deshalb deterministische Nonces nach RFC6979. Dabei wird die Nonce aus dem Private Key und dem Signatur-Hash z abgeleitet, sodass für unterschiedliche Nachrichten automatisch unterschiedliche Nonces entstehen. Die konkrete Implementierung erfolgt in der Bitcoin-secp256k1-Bibliothek.

Die Nonce ist daher einer der kritischsten Bestandteile bei ECDSA.

Können Quantencomputer einen Private Key berechnen?

Die Diskussion um Quantencomputer unterscheidet sich von der klassischen Sicherheit von ECDSA.

Während klassische Computer den Private Key nicht effizient aus einem Public Key berechnen können, könnte ein ausreichend leistungsfähiger Quantencomputer theoretisch Shor's Algorithmus anwenden.

Shor's Algorithmus greift direkt das Problem an, auf dem die Sicherheit von ECDSA basiert:

gegeben: P = d × G
 
gesucht: d

Dafür muss jedoch ein vollständiger Public Key bekannt sein.

Ist lediglich ein Public-Key-Hash (HASH160(P)) veröffentlicht, wie bei vielen noch nicht ausgegebenen Bitcoin-UTXOs, besitzt Shor kein direktes Angriffsziel.

In der Forschung wird deshalb häufig zwischen veröffentlichten Public Keys und lediglich veröffentlichten Public-Key-Hashes unterschieden.

Die dafür erforderlichen Quantencomputer existieren derzeit nicht. Zwar können heutige Quantencomputer bereits einzelne Quantenoperationen ausführen, sie erzeugen jedoch noch zu viele Fehler. Ohne umfangreiche Fehlerkorrektur würden sich diese Fehler schneller ansammeln, als ein komplexer Algorithmus wie Shor abgeschlossen werden könnte.

Aus diesem Grund sprechen Forscher häufig von fehlertoleranten Quantencomputern. Gemeint sind Quantencomputer, die trotz unvermeidbarer physikalischer Fehler über lange Zeiträume zuverlässig rechnen können.

Quantencomputer stellen daher heute keine praktische Bedrohung für Bitcoin dar. Die Diskussion beschreibt vielmehr ein mögliches zukünftiges Szenario und ist einer der Gründe für die Forschung an quantenresistenter Kryptographie.