secp256k1

Was ist secp256k1?

secp256k1 ist eine standardisierte elliptische Kurve über einem endlichen Primkörper.

Sie definiert eine Menge gültiger Punkte und Rechenregeln für diese Punkte. Bitcoin verwendet diese mathematische Struktur, um aus Private Keys Public Keys abzuleiten und ECDSA- sowie Schnorr-Signaturen zu erzeugen und zu prüfen.

Der Name setzt sich aus mehreren Teilen zusammen:

sec: Standards for Efficient Cryptography
p: Kurve über einem endlichen Primkörper
256: Feldgröße in Bit
k1: Koblitz-Kurvenparameter

secp256k1 ist damit kein Signaturalgorithmus und keine Hash-Funktion. Sie beschreibt die mathematische Struktur, auf der Verfahren wie ECDSA und Schnorr arbeiten.

ECC

Elliptic Curve Cryptography

secp256k1

Kurve

elliptische Kurve

Mathematische Basis für Schlüsselraum und Punkte

Public-Key-Ableitung

d × G

Private Key → Punkt auf der Kurve

Signaturalgorithmen

auf derselben Kurve

ECDSASchnorr

Die Parameter von secp256k1

secp256k1 besteht nicht nur aus einer elliptischen Kurve, sondern aus mehreren mathematischen Parametern. Gemeinsam legen sie fest, auf welchen Zahlen gerechnet wird, welche Punkte gültig sind und welche Punktmenge für kryptographische Berechnungen verwendet wird.

Primkörper Fₚ

Welche Zahlen sind erlaubt?

Kurvengleichung

Welche Punkte sind gültig?

Gruppenordnung n

Wie viele Punkte besitzt die erzeugte Gruppe?

Der Primkörper

Der Primkörper legt den Zahlenraum fest, in dem secp256k1 arbeitet.

Für Bitcoin gilt

p = 2^{256} - 2^{32} - 977

Dadurch können Koordinaten ausschließlich Werte zwischen

0

und

p-1

annehmen.

Alle Rechnungen innerhalb von secp256k1 erfolgen modulo $p$ . Dadurch bleiben sämtliche Ergebnisse stets innerhalb dieses endlichen Zahlenraums.

Die Primzahl

p = 2^{256} - 2^{32} - 977

wurde bewusst gewählt. Sie liegt nur wenig unter $2^{256}$ und ermöglicht besonders effiziente Berechnungen auf moderner Computerhardware.

Die vollständige Primzahl lautet

115.792.089.237.316.195.423.570.985.008.687.907.853.269.984.665.640.564.039.457.584.007.908.834.671.663

Was bedeutet „mod p“?

Modulo führt Ergebnisse wieder in den Zahlenbereich des Primkörpers zurück.

Beispiel mit

p=5

0 mod 5 = 0
1 mod 5 = 1
2 mod 5 = 2
3 mod 5 = 3
4 mod 5 = 4
 
5 mod 5 = 0
6 mod 5 = 1
7 mod 5 = 2
8 mod 5 = 3
9 mod 5 = 4
 
10 mod 5 = 0

Jede Zahl außerhalb des erlaubten Bereichs wird durch mod p wieder in den Wertebereich des Primkörpers „zurückgefaltet“. Dadurch liegen alle Ergebnisse stets zwischen 0 und p−1 also hier 4.

Bei secp256k1 funktioniert dieselbe Rechnung lediglich mit einer wesentlich größeren Primzahl.

Die Kurvengleichung

Die Kurvengleichung legt fest, welche Koordinatenpaare gültige Punkte der elliptischen Kurve sind.

Für secp256k1 lautet sie

y^2 \equiv x^3 + 7 \pmod p

Das Symbol $\equiv \pmod p$ bedeutet, dass beide Seiten der Gleichung im Primkörper $\mathbb{F}_p$ berechnet und miteinander verglichen werden.

Ein Koordinatenpaar $(x,y)$ gehört genau dann zur Kurve, wenn

(y^2 \bmod p)=((x^3+7)\bmod p)

gilt.

Alle Koordinatenpaare, die diese Bedingung erfüllen, sind gültige Kurvenpunkte. Alle anderen gehören nicht zur Kurve.

Prüfung eines Kurvenpunkts

Die Visualisierung oben zeigt die Kurve über dem kleinen Primkörper

p=223.

Für den markierten Punkt

(x,y)=(89,127)

prüfen wir die Kurvengleichung

y^2 \equiv x^3+7 \pmod{223}.

Linke Seite:

y^2 = 127^2 = 16\,129

Anschließend wird das Ergebnis modulo $223$ reduziert:

16\,129 = 72 \cdot 223 + 73

Damit bleibt der Rest

16\,129 \bmod 223 = 73.

Rechte Seite:

x^3+7=89^3+7=704\,969+7=704\,976

Anschließend wird das Ergebnis modulo $223$ reduziert:

704\,976 = 3\,161 \cdot 223 + 73

Damit bleibt der Rest

704\,976 \bmod 223 = 73.

Beide Seiten liefern somit denselben Wert:

73 \equiv 73 \pmod{223}

Damit erfüllt das Koordinatenpaar $(89,127)$ die Kurvengleichung und ist ein gültiger Punkt der elliptischen Kurve.

Bitcoin verwendet exakt dieselbe Methode, allerdings mit der wesentlich größeren Primzahl

p=2^{256}-2^{32}-977.

Die Gruppenordnung n

Nicht alle gültigen Kurvenpunkte werden in Bitcoin beliebig verwendet.

Aus dem Generatorpunkt $G$ entsteht durch wiederholte Punktaddition eine große zyklische Gruppe.

Die Anzahl der Punkte dieser Gruppe wird durch die Gruppenordnung $n$ beschrieben.

Für secp256k1 gilt

n = 115.792.089.237.316.195.423.570.985.008.687.907.852.837.564.279.074.904.382.605.163.141.518.161.494.337

oder näherungsweise

n \approx 2^{256}.

Diese Zahl spielt eine zentrale Rolle, weil

Private Keys zwischen $1$ und $n-1$ liegen,
Skalarmultiplikationen modulo $n$ erfolgen,
auch ECDSA und Schnorr modulo $n$ rechnen.

Der Primkörper $p$ legt den Zahlenraum der Koordinaten fest.

Die Gruppenordnung $n$ legt den Zahlenraum der Skalare fest, also der Private Keys und vieler kryptographischer Berechnungen.

Warum gibt es die Gruppenordnung?

Ausgehend vom Generatorpunkt $G$ entstehen durch wiederholte Punktaddition immer neue Punkte:

1 · G = G
2 · G
3 · G
4 · G
⋮
n - 1 · G
n · G = O

Nach genau $n$ Schritten erreicht man den Punkt im Unendlichen $O$ , das neutrale Element der Gruppe.

Wird anschließend weitergezählt, beginnt der Zyklus erneut:

(n + 1) · G = G
(n + 2) · G = 2 · G
(n + 3) · G = 3 · G
⋮

Deshalb werden Skalare wie Private Keys oder Signaturwerte modulo $n$ betrachtet. Jeder beliebig große Skalar entspricht letztlich einem eindeutigen Wert zwischen

1

und

n-1.

Punkte auf secp256k1

Ein Punkt auf secp256k1 besteht aus zwei Koordinaten:

P = (x, y)

Beide Koordinaten sind Elemente des endlichen Primkörpers $\mathbb{F}_p$ . Sämtliche Berechnungen werden daher modulo der Primzahl $p$ durchgeführt.

Ein Koordinatenpaar ist nur dann ein gültiger Kurvenpunkt, wenn es die Kurvengleichung erfüllt:

y^2 \equiv x^3 + 7 \pmod p

Nicht jedes beliebige Koordinatenpaar gehört somit zur Kurve.

Neben den Punkten mit konkreten $x$ - und $y$ -Koordinaten existiert ein weiterer besonderer Punkt: der Punkt im Unendlichen.

Punktnegation

Zu jedem Kurvenpunkt

P = (x, y)

existiert ein negierter Punkt:

-P = (x, -y \bmod p)

Da die Berechnungen im endlichen Körper $\mathbb{F}_p$ stattfinden, wird auch die negative $y$ -Koordinate modulo $p$ dargestellt.

Für $y \neq 0$ gilt:

-y \bmod p = p-y

Damit lautet der negierte Punkt:

-P = (x, p-y)

Der ursprüngliche Punkt und sein negierter Punkt besitzen dieselbe $x$ -Koordinate. Ihre $y$ -Koordinaten ergänzen sich modulo $p$ zu $0$ :

y + (p-y) \equiv 0 \pmod p

Beide Punkte erfüllen die Kurvengleichung, da durch das Quadrieren das Vorzeichen verschwindet:

(-y)^2 = y^2

Für eine gültige $x$ -Koordinate existieren daher normalerweise zwei mögliche Kurvenpunkte:

P = (x, y)

und

-P = (x, p-y)

Werden diese beiden Punkte addiert, heben sie sich gegenseitig auf:

P + (-P) = \mathcal{O}

Die Punktnegation ist später auch für komprimierte öffentliche Schlüssel relevant.

Da zu einer $x$ -Koordinate zwei mögliche $y$ -Koordinaten gehören können, muss zusätzlich angegeben werden, welcher der beiden Punkte gemeint ist.

Warum wird aus −127 wieder 96?

Im endlichen Körper $\mathbb{F}_{223}$ werden Koordinaten immer modulo $223$ dargestellt.

Die Zahl $-127$ liegt außerhalb des üblichen Darstellungsbereichs von $\mathbb{F}_{223}$ :

0,1,\ldots,222

Deshalb wird $-127$ modulo $223$ reduziert. Dazu addiert man $223$ :

-127 + 223 = 96

Damit gilt:

-127 \equiv 96 \pmod{223}

Die Werte $-127$ und $96$ bezeichnen also dieselbe Restklasse modulo $223$ .

Für den Punkt

P=(89,127)

ergibt die Negation zunächst:

-P=(89,-127)

Im endlichen Körper wird die negative $y$ -Koordinate anschließend in ihre kanonische Darstellung zwischen $0$ und $222$ überführt:

-P=(89,96)

Der Punkt „rutscht“ daher nicht wirklich von einem negativen in einen positiven Bereich. Die beiden Schreibweisen $-127$ und $96$ beschreiben modulo $223$ denselben Wert.

Punkt im Unendlichen

Der Punkt im Unendlichen wird üblicherweise mit

\mathcal{O}

bezeichnet.

Der Name „Punkt im Unendlichen“ ist historisch bedingt und kann etwas irreführend sein. Tatsächlich handelt es sich nicht um einen besonders weit entfernten Punkt, sondern um das neutrale Element der Punktaddition.

Er besitzt keine gewöhnlichen $x$ - und $y$ -Koordinaten und kann nicht direkt in die Kurvengleichung eingesetzt werden.

Stattdessen wird er als zusätzliches Element definiert, damit die Punkte auf der Kurve zusammen mit der Punktaddition eine mathematische Gruppe bilden.

Der Punkt im Unendlichen ist das neutrale Element dieser Gruppe.

Für jeden Kurvenpunkt $P$ gilt:

P + \mathcal{O} = P

und

\mathcal{O} + P = P

Seine Funktion entspricht damit der Rolle der Zahl $0$ bei der gewöhnlichen Addition:

a + 0 = a

Der Punkt im Unendlichen entsteht außerdem, wenn ein Punkt zu seinem negierten Punkt addiert wird:

P + (-P) = \mathcal{O}

Geometrisch verläuft die Gerade durch einen Punkt und seinen negierten Punkt vertikal. Sie schneidet die Kurve an keinem weiteren endlichen Punkt.

Das Ergebnis dieser Punktaddition wird daher als Punkt im Unendlichen definiert.

Warum ergibt P + (−P) den Punkt im Unendlichen?

Bei der gewöhnlichen Addition gilt:

5 + (-5) = 0

Die beiden Zahlen heben sich gegenseitig auf. Das Ergebnis ist das neutrale Element der normalen Addition: die Zahl $0$ .

Bei elliptischen Kurven funktioniert die Punktaddition nach demselben Prinzip.

Zu jedem Punkt $P$ existiert ein inverser Punkt $-P$ . Werden beide addiert, heben sie sich ebenfalls gegenseitig auf:

P + (-P) = \mathcal{O}

Das Ergebnis ist jedoch nicht die Zahl $0$ , sondern der Punkt im Unendlichen $\mathcal{O}$ .

Der Punkt im Unendlichen übernimmt bei der Punktaddition genau dieselbe Rolle wie die Zahl $0$ bei der gewöhnlichen Addition.

Deshalb gilt für jeden Kurvenpunkt:

P + \mathcal{O} = P

Der Punkt im Unendlichen ist also kein besonders weit entfernter Punkt und besitzt auch keine Koordinaten. Er ist ein zusätzlich definiertes Gruppenelement, das als neutrales Element der Punktaddition dient.

Punktoperationen

Auf den Punkten einer elliptischen Kurve werden keine gewöhnlichen Zahlenoperationen ausgeführt.

Stattdessen existieren eigene Operationen, mit denen aus einem oder mehreren Kurvenpunkten neue Kurvenpunkte berechnet werden.

Die wichtigsten Operationen sind:

Punktaddition

P + Q = R

Zwei verschiedene Kurvenpunkte ergeben einen neuen Punkt.

Punktverdopplung

2·

2P = P + P

Sonderfall der Addition: ein Punkt wird mit sich selbst addiert.

Skalarmultiplikation

k·

Wiederholte Addition, typisch per Double-and-Add. Grundlage für Q = dG.

Alle Berechnungen erfolgen im endlichen Primkörper $\mathbb{F}_p$ und damit modulo $p$ .

Punktaddition

Bei der Punktaddition werden zwei Kurvenpunkte

P=(x_1,y_1)

und

Q=(x_2,y_2)

zu einem neuen Kurvenpunkt

R=P+Q

addiert.

Für zwei unterschiedliche Punkte mit

x_1 \neq x_2

wird zunächst die Steigung $\lambda$ berechnet:

\lambda = \frac{y_2-y_1}{x_2-x_1} \pmod p

Da Division im endlichen Körper nicht unmittelbar möglich ist, wird durch das multiplikative Inverse des Nenners multipliziert:

\lambda = (y_2-y_1)(x_2-x_1)^{-1} \pmod p

Anschließend werden die Koordinaten des Ergebnispunkts berechnet:

x_3 = \lambda^2-x_1-x_2 \pmod p

y_3 = \lambda(x_1-x_3)-y_1 \pmod p

Damit lautet der neue Punkt:

R=(x_3,y_3)

Das Ergebnis einer gültigen Punktaddition liegt erneut auf der elliptischen Kurve.

Ein Sonderfall tritt ein, wenn $Q=-P$ gilt (siehe Punktnegation). Dann heben sich beide Punkte gegenseitig auf:

P+(-P)=\mathcal{O}

Das Ergebnis ist der Punkt im Unendlichen $\mathcal{O}$ .

Was passiert bei der Punktaddition eigentlich?

Bei der Punktaddition werden nicht einfach die Koordinaten von $P$ und $Q$ miteinander addiert.

Es gilt also normalerweise nicht:

P+Q=(x_1+x_2,\;y_1+y_2)

Stattdessen berechnet man zunächst aus beiden Punkten eine Steigung $\lambda$ .

Diese Steigung wird anschließend verwendet, um die Koordinaten eines neuen Punkts $R$ zu bestimmen:

R=P+Q

Die Formeln sind so aufgebaut, dass der berechnete Punkt $R$ wieder auf derselben elliptischen Kurve liegt.

Anschaulich kann man sich die Rechnung deshalb so merken:

Zwei Kurvenpunkte $P$ und $Q$ werden ausgewählt.
Aus ihren Koordinaten wird die Steigung $\lambda$ berechnet.
Aus $\lambda$ entstehen die neuen Koordinaten $(x_3,y_3)$ .
Das Ergebnis ist ein weiterer gültiger Kurvenpunkt $R$ .

Die Division in der Formel ist dabei keine gewöhnliche Division. Im endlichen Körper $\mathbb{F}_p$ wird stattdessen mit dem modularen Inversen des Nenners multipliziert.

Punktverdopplung

Bei der Punktverdopplung wird ein Punkt mit sich selbst addiert:

R=P+P

oder verkürzt:

R=2P

Da beide Ausgangspunkte identisch sind, kann für die Berechnung der Steigung nicht die gewöhnliche Formel der Punktaddition verwendet werden.

Für eine Kurve der Form

y^2=x^3+ax+b

lautet die Steigung bei der Punktverdopplung:

\lambda = \frac{3x_1^2+a}{2y_1} \pmod p

Bei secp256k1 gilt:

a=0

Daher vereinfacht sich die Formel zu:

\lambda = \frac{3x_1^2}{2y_1} \pmod p

Im endlichen Körper wird erneut mit dem modularen Inversen gerechnet:

\lambda = 3x_1^2(2y_1)^{-1} \pmod p

Die Koordinaten des Ergebnispunkts werden anschließend wie bei der Punktaddition berechnet:

x_3 = \lambda^2-2x_1 \pmod p

y_3 = \lambda(x_1-x_3)-y_1 \pmod p

Damit gilt:

2P=(x_3,y_3)

Die Punktverdopplung ist somit kein grundsätzlich anderer Vorgang, sondern ein Sonderfall der Punktaddition.

Skalarmultiplikation

Bei der Skalarmultiplikation wird ein Kurvenpunkt wiederholt mit sich selbst addiert.

Für eine ganze Zahl $k$ und einen Punkt $P$ gilt:

kP = \underbrace{P+P+\dots+P}_{k\text{-mal}}

Beispielsweise:

3P=P+P+P

5P=P+P+P+P+P

Die Skalarmultiplikation ist keine gewöhnliche Multiplikation der Koordinaten.

Es gilt daher nicht:

kP=(kx,ky)

Stattdessen wird die Punktaddition wiederholt angewendet.

Eine direkte Berechnung durch $k$ einzelne Additionen wäre bei großen Zahlen jedoch zu langsam. Deshalb wird die Skalarmultiplikation mit einem effizienteren Verfahren ausgeführt, das Punktverdopplungen und Punktadditionen kombiniert.

Ein häufig verwendetes Verfahren ist Double-and-Add.

Dabei wird der Skalar $k$ binär dargestellt. Für jedes Bit wird der aktuelle Punkt verdoppelt. Ist das jeweilige Bit gesetzt, wird zusätzlich der Ausgangspunkt addiert.

Für

k=13

gilt beispielsweise:

13=8+4+1

und damit:

13P=8P+4P+P

Warum werden bei der Skalarmultiplikation plötzlich Punkte addiert?

Die Skalarmultiplikation führt keine neue Art von Berechnung ein.

Sie kombiniert lediglich die beiden zuvor vorgestellten Operationen:

Punktverdopplung, um schnell die Zweierpotenzen eines Punkts zu erzeugen.
Punktaddition, um die benötigten Punkte miteinander zu kombinieren.

Für

k=13

lautet die Binärdarstellung:

13 = 1101_2 = 8 + 4 + 1

Zunächst entstehen durch wiederholte Punktverdopplung:

P \rightarrow 2P \rightarrow 4P \rightarrow 8P

Da in der Binärdarstellung von $13$ nur die Bits für $8$ , $4$ und $1$ gesetzt sind, werden anschließend genau diese Punkte addiert:

13P = 8P + 4P + P

Die Addition erfolgt dabei schrittweise:

8P + 4P = 12P

12P + P = 13P

Die Skalarmultiplikation besteht also vollständig aus Punktverdopplungen und Punktadditionen. Es wird keine neue mathematische Operation benötigt.

Die Skalarmultiplikation ist die zentrale Operation der Kryptografie mit secp256k1.

Aus einem privaten Schlüssel $d$ und dem Generatorpunkt $G$ wird der öffentliche Schlüssel berechnet:

Q=dG

Die Berechnung von $Q$ aus $d$ und $G$ ist effizient.

Die umgekehrte Berechnung des privaten Schlüssels $d$ aus $Q$ und $G$ gilt dagegen bei ausreichend großen Parametern als praktisch nicht durchführbar. Dieses Problem wird als elliptisches Kurven-Diskreter-Logarithmus-Problem bezeichnet.

Generatorpunkt $G$

Der Generatorpunkt $G$ ist ein fest definierter Punkt auf der elliptischen Kurve secp256k1.

Alle Bitcoin-Implementierungen verwenden denselben Generatorpunkt. Er ist Bestandteil der Spezifikation der Kurve und kein geheimer Wert.

Seine Koordinaten lauten:

G = (x_G,\;y_G)

mit

x_G = 79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798

als Dezimalzahl

55.066.263.022.277.343.669.578.718.895.168.534.326.250.603.453.777.594.175.500.187.360.389.116.729.240

und

y_G = 483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8

als Dezimalzahl

32.670.510.020.758.816.978.083.085.130.507.043.184.471.273.380.659.243.275.938.904.335.757.337.482.424

Da diese Zahlen jeweils 256 Bit lang sind, werden sie üblicherweise in hexadezimaler Schreibweise dargestellt.

Der Generatorpunkt bildet den Ausgangspunkt für die Berechnung jedes öffentlichen Schlüssels.

Aus einem privaten Schlüssel $d$ wird durch Skalarmultiplikation der öffentliche Schlüssel berechnet:

Q=dG

Dabei bedeutet

dG

nicht die gewöhnliche Multiplikation zweier Zahlen.

Stattdessen wird der Generatorpunkt $G$ mithilfe der zuvor erklärten Punktoperationen wiederholt mit sich selbst kombiniert.

Intern besteht die Berechnung ausschließlich aus Punktverdopplungen und Punktadditionen.

Beispielsweise gilt:

5G = G + G + G + G + G

oder effizienter:

5G = 4G + G

Für große Werte von $d$ kommt das Double-and-Add-Verfahren zum Einsatz. Dabei werden zunächst durch Punktverdopplungen die Zweierpotenzen des Generatorpunkts erzeugt:

G,\;2G,\;4G,\;8G,\;16G,\;\dots

Anschließend werden entsprechend der Binärdarstellung des privaten Schlüssels nur die benötigten Punkte addiert.

Die Berechnung des öffentlichen Schlüssels aus $d$ und $G$ ist sehr effizient.

Die umgekehrte Aufgabe, den privaten Schlüssel $d$ allein aus dem öffentlichen Schlüssel $Q$ und dem bekannten Generatorpunkt $G$ zu bestimmen, gilt dagegen als praktisch nicht durchführbar.

Dieses mathematische Problem wird als Elliptic Curve Discrete Logarithm Problem (ECDLP) bezeichnet und bildet die Sicherheitsgrundlage von Bitcoin.

Vom Private Key zum Public Key

Ein Bitcoin-Schlüsselpaar besteht aus einem privaten und einem öffentlichen Schlüssel.

Der Private Key muss geheim bleiben und dient zum Erzeugen digitaler Signaturen.

Der Public Key wird aus dem Private Key berechnet und kann ohne Sicherheitsrisiko veröffentlicht werden.

Die Berechnung erfolgt mithilfe der zuvor vorgestellten Skalarmultiplikation auf der elliptischen Kurve secp256k1.

Der Private Key $d$

Der Private Key ist eine zufällig gewählte ganze Zahl.

Er muss im Bereich

1 \le d < n

liegen.

Dabei bezeichnet $n$ die Gruppenordnung des Generatorpunkts $G$ :

als Dezimalzahl

115.792.089.237.316.195.423.570.985.008.687.907.852.837.564.279.074.904.382.605.163.141.518.161.494.337

hexadezimal

FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

und näherungsweise

n \approx 2^{256}.

Da $n$ nahezu $2^{256}$ entspricht, existieren ungefähr $2^{256}$ mögliche Private Keys.

Ein Private Key wird üblicherweise hexadezimal dargestellt.

Beispielsweise:

1E99423A4ED27608A15A2616F7D3C4D7F6FBA6C9C4A8F2E9B5D89C6E7A3F9A42

Der Private Key ist lediglich eine Zahl. Erst durch die Skalarmultiplikation mit dem Generatorpunkt entsteht daraus ein öffentlicher Schlüssel.

Public Key = d × G

Der öffentliche Schlüssel wird aus dem Private Key $d$ und dem Generatorpunkt $G$ berechnet:

Q=dG

Dabei bedeutet

dG

nicht die gewöhnliche Multiplikation zweier Zahlen.

Stattdessen wird der Generatorpunkt mithilfe der zuvor erklärten Punktoperationen skaliert.

Intern besteht die Berechnung ausschließlich aus:

Punktverdopplungen
Punktadditionen

Je nach Binärdarstellung des Private Keys werden unterschiedlich viele Punktverdopplungen und Punktadditionen ausgeführt.

Private Key d

256 Bit

hexadezimal

1E99423A4ED27608A15A2616F7D3C4D7F6FBA6C9C4A8F2E9B5D89C6E7A3F9A42

Dezimal

13.840.170.145.645.816.737.842.251.483.233.475.794.309.135.176.820.001.688.593.814.109.035.218.049.602

d als 256 Bits

MSB links · nur Bit = 1 wird addiert

2^255

00011110100110010100001000111010

2^224

2^223

01001110110100100111011000001000

2^192

2^191

10100001010110100010011000010110

2^160

2^159

11110111110100111100010011010111

2^128

2^127

11110110111110111010011011001001

2^96

2^95

11000100101010001111001011101001

2^64

2^63

10110101110110001001110001101110

2^32

2^31

01111010001111111001101001000010

2^0

134× Bit = 1→ addiere 2^i·G122× Bit = 0→ überspringen

Double-and-Add

≈ 255 Verdopplungen · 134 Additionen

Für jede Binärstelle mit Wert 1 entsteht ein eigener Vielfachen-Term. Die Zweierpotenzen von G entstehen durch wiederholte Punktverdopplung.

2^252·G2^251·G2^250·G2^249·G…2^6·G2^1·G

Q = Σ 2^i·Güber 134 gesetzte Bits i

Public Key Q = d·G

Kurvenpunkt

x = 5BB211C482237F713A1457710D9FE38E1F15FFDB1E17257897FCE67DAD579F59

y = 4EBF74C48AE39E27D29938B2563CDF4043DE3940CB284FEE4369F20EF6244DF7

Das Ergebnis der Berechnung ist wiederum ein Punkt auf der elliptischen Kurve:

Q=(x,y)

Private Key d (Hex)

Komprimierte Public Keys

Ein Public Key besteht ursprünglich aus den beiden Koordinaten

(x,y)

und benötigt daher 65 Byte.

Da zu jeder gültigen $x$ -Koordinate nur zwei mögliche $y$ -Koordinaten existieren (siehe Punktnegation), muss nicht der vollständige Wert von $y$ gespeichert werden.

Stattdessen genügt ein Präfix, das angibt, welche der beiden Möglichkeiten verwendet wird:

02 für eine gerade $y$ -Koordinate
03 für eine ungerade $y$ -Koordinate

Ein komprimierter Public Key besitzt daher die Form:

02 || x

oder

03 || x

Er benötigt nur noch 33 Byte.

Aufbau eines komprimierten Public Keys

Aus dem Beispiel-Private-Key

1E99423A4ED27608A15A2616F7D3C4D7F6FBA6C9C4A8F2E9B5D89C6E7A3F9A42

entsteht der Kurvenpunkt

x = 5BB211C482237F713A1457710D9FE38E1F15FFDB1E17257897FCE67DAD579F59
y = 4EBF74C48AE39E27D29938B2563CDF4043DE3940CB284FEE4369F20EF6244DF7

Da die $y$ -Koordinate ungerade ist, wird das Präfix 03 verwendet:

03 || 5BB211C482237F713A1457710D9FE38E1F15FFDB1E17257897FCE67DAD579F59

Der vollständige komprimierte Public Key lautet damit:

035BB211C482237F713A1457710D9FE38E1F15FFDB1E17257897FCE67DAD579F59

x = 89 / 222

X-only Public Keys

Mit Taproot (BIP340) wurde eine weitere Darstellung eingeführt.

Dabei wird ausschließlich die $x$ -Koordinate gespeichert:

Die Parität der $y$ -Koordinate wird dabei nicht mehr übertragen.

Stattdessen wird immer die Variante mit gerader $y$ -Koordinate verwendet.

Dadurch besteht ein X-only Public Key nur noch aus 32 Byte.

Intern existiert weiterhin ein vollständiger Kurvenpunkt

(x,y),

gespeichert wird jedoch ausschließlich die $x$ -Koordinate.

x = 89 / 222

Diese Darstellung wird ausschließlich für Schnorr-Signaturen und Taproot verwendet.

Was ist das Elliptic Curve Discrete Logarithm Problem?

Aus einem Private Key lässt sich der Public Key effizient berechnen:

Q=dG

Die umgekehrte Richtung ist jedoch das eigentliche Sicherheitsprinzip von Bitcoin. Gegeben sind lediglich der Public Key

Q

und der Generatorpunkt

G.

Gesucht ist der Private Key

d.

Diese Aufgabe wird als Elliptic Curve Discrete Logarithm Problem (ECDLP) bezeichnet.

Bis heute ist kein effizienter Algorithmus bekannt, der den Private Key aus einem Public Key berechnen kann.

Die einzige bekannte allgemeine Vorgehensweise besteht darin, mögliche Werte für $d$ auszuprobieren:

1 · G = Q ?
2 · G = Q ?
3 · G = Q ?
4 · G = Q ?
...

Da es ungefähr

2^{256}

bzw.

115.792.089.237.316.195.423.570.985.008.687.907.853.269.984.665.640.564.039.457.584.007.913.129.639.936

mögliche Private Keys gibt, ist ein vollständiges Durchprobieren aller Möglichkeiten praktisch unmöglich.

Versuch k = 1

Warum hilft auch extrem schnelle Hardware nicht?

Angenommen, alle Computer der Welt könnten zusammen 1.000.000.000.000.000.000.000.000 = 10²⁴ Private Keys pro Sekunde überprüfen. Dann würden sie in einem Jahr ungefähr 3,15 × 10³¹ Schlüssel testen. Dem gegenüber stehen jedoch rund 1,16 × 10⁷⁷ mögliche Private Keys. Selbst mit dieser unrealistisch hohen Geschwindigkeit würde ein vollständiges Durchprobieren etwa 3,7 × 10⁴⁵ Jahre dauern. Nehmen wir zusätzlich an, jeder einzelne Versuch benötige lediglich ein Mikrojoule: 1 Versuch = 0,000001 Joule Bei $10^{24}$ Versuchen pro Sekunde entspräche das einer dauerhaften Leistung von 10¹⁸ Watt = 1.000.000 Terawatt und einem jährlichen Stromverbrauch von ungefähr 8,76 × 10⁹ Terawattstunden Das wäre mehr als das Hunderttausendfache der gesamten heutigen weltweiten Stromerzeugung, und die angenommene Energiemenge pro Versuch ist bereits außerordentlich optimistisch.

Abgrenzung zu ECDSA und Schnorr

Die in diesem Kapitel beschriebene elliptische Kurvenkryptographie ist kein Signaturverfahren.

Sie stellt lediglich die mathematische Grundlage bereit, auf der Bitcoin seine kryptographischen Verfahren aufbaut.

Darauf aufbauend verwendet Bitcoin zwei digitale Signaturverfahren:

ECDSA für ältere Ausgabetypen
Schnorr-Signaturen seit dem Taproot-Upgrade

Beide Verfahren nutzen dieselben Private und Public Keys sowie dieselbe elliptische Kurve secp256k1. Sie unterscheiden sich jedoch darin, wie digitale Signaturen erzeugt und überprüft werden.

Was ist secp256k1?

Die Parameter von secp256k1

Der Primkörper

Die Kurvengleichung

Die Gruppenordnung n

Punkte auf secp256k1

Punktnegation

Punkt im Unendlichen

Punktoperationen

Punktaddition

Punktverdopplung

Skalarmultiplikation

Generatorpunkt $G$

Vom Private Key zum Public Key

Der Private Key $d$

Public Key = d × G

Komprimierte Public Keys

X-only Public Keys

Was ist das Elliptic Curve Discrete Logarithm Problem?

Abgrenzung zu ECDSA und Schnorr

Weiterführende Informationen

Grundlagen und Spezifikationen

Bitcoin

Interaktive Visualisierung

Was ist secp256k1?

Die Parameter von secp256k1

Der Primkörper

Die Kurvengleichung

Die Gruppenordnung n

Punkte auf secp256k1

Punktnegation

Punkt im Unendlichen

Punktoperationen

Punktaddition

Punktverdopplung

Skalarmultiplikation

Generatorpunkt GGG

Vom Private Key zum Public Key

Der Private Key ddd

Public Key = d × G

Komprimierte Public Keys

X-only Public Keys

Was ist das Elliptic Curve Discrete Logarithm Problem?

Abgrenzung zu ECDSA und Schnorr

Weiterführende Informationen

Grundlagen und Spezifikationen

Bitcoin

Interaktive Visualisierung

Generatorpunkt $G$

Der Private Key $d$