Die Kurve Ed25519

Skalare, Punkte und die eine Operation, auf der ganz Monero beruht

Warum eine Kurve

Wir brauchen eine „Einwegfunktion mit Schloss“: Aus einem Geheimnis lässt sich leicht etwas Öffentliches gewinnen, aber nicht umgekehrt. Und wir wollen mit den öffentlichen Dingen rechnen: sie addieren und mit Zahlen multiplizieren. Eine elliptische Kurve liefert genau das.

Monero verwendet dieselbe Kurve wie die Signaturen von Ed25519 (Daniel J. Bernstein u. a.): eine verdrillte Edwards-Kurve

Ein Punkt ist ein Zahlenpaar (x, y), das die Gleichung erfüllt. Alle Berechnungen laufen modulo der Primzahl p, die „Kurve“ ist also in Wirklichkeit eine Wolke aus etwa 2²⁵⁵ einzelnen Punkten.

Punkte addieren

Punkte lassen sich addieren: P + Q = R, wobei R ebenfalls auf der Kurve liegt. Bei Edwards-Kurven deckt eine einzige Formel alle Fälle ab (bequem und sicher):

Diese Addition verhält sich wie die gewöhnliche: Sie ist kommutativ und assoziativ, es gibt eine „Null“ – den Punkt (0, 1) –, und jeder Punkt hat ein Gegenstück (−x, y).

Mit einer Zahl multiplizieren

Einen Punkt mit x zu multiplizieren heißt, ihn x-mal zu sich selbst zu addieren. Natürlich addiert niemand 2²⁵²-mal: Das Verfahren „Double-and-Add“ braucht nur ~256 Verdopplungen und ~128 Additionen.

Der Basispunkt G und die Ordnung l

Alle verwenden denselben, vorab vereinbarten Basispunkt G. Multipliziert man G mit 1, 2, 3, …, ist man nach l Schritten wieder bei null:

l ist die Ordnung der von G erzeugten Untergruppe. Die Kurve hat insgesamt 8-mal so viele Punkte (8·l); die 8 nennt man den Kofaktor. Dieser Kofaktor ist die Quelle mehrerer Feinheiten in Monero: Du wirst in den Formeln für Einmal-Adressen einen Faktor 8 sehen, und 2017 hätten „Punkte kleiner Ordnung“ für einen Output mehrere Key Images erzeugen können (behoben durch die Prüfung l·I = 0).

Warum das für Schlüssel funktioniert

Nimm ein zufälliges x – das ist ein privater Schlüssel. Berechne P = x·G – das ist ein öffentlicher Schlüssel. P zu veröffentlichen ist sicher. Entscheidend ist, dass Punkte Algebra erlauben:

Die zweite Identität ist die Grundlage des Diffie-Hellman-Schlüsselaustauschs: Alice kennt a und sieht B = b·G; Bob kennt b und sieht A = a·G. Beide können denselben Punkt a·B = b·A = ab·G berechnen, ein Außenstehender aber nicht. Darauf bauen die Einmal-Adressen auf.

Die erste Identität ist die Grundlage der Pedersen-Commitments: In Punkten versteckte Beträge lassen sich addieren.

Einen Punkt in 32 Bytes kodieren

Ein Punkt wird kompakt gespeichert: Man schreibt die Koordinate y (255 Bit, Little-Endian) und setzt die Parität von x in das oberste Bit des letzten Bytes. x wird aus y über die Kurvengleichung zurückgewonnen (bis auf das Vorzeichen – das liefert das Bit). Das sind die 32 Bytes, die du in Hex siehst, wenn du dir einen öffentlichen Monero-Schlüssel ansiehst.

Der Basispunkt G wird zum Beispiel so geschrieben:

5866666666666666666666666666666666666666666666666666666666666666

(sein y = 4/5 mod p, und x ist gerade).

Code

Eine minimale JavaScript-Implementierung mit BigInt – aus xmrcrypto.js, das alle Tools dieser Seite verwenden:

const P = (1n << 255n) - 19n;
const L = (1n << 252n) + 27742317777372353535851937790883648493n;
const D = mod(-121665n * inv(121666n));

// points in extended coordinates (X:Y:Z:T), x = X/Z, y = Y/Z
function add(p, q) {
  const A = mod((p.Y - p.X) * (q.Y - q.X));
  const B = mod((p.Y + p.X) * (q.Y + q.X));
  const C = mod(2n * D * p.T * q.T);
  const Dd = mod(2n * p.Z * q.Z);
  const E = B - A, F = Dd - C, G = Dd + C, H = B + A;
  return { X: mod(E * F), Y: mod(G * H), Z: mod(F * G), T: mod(E * H) };
}

// scalar multiplication: double-and-add
function mul(k, p) {
  let r = ZERO, q = p;
  while (k > 0n) { if (k & 1n) r = add(r, q); q = add(q, q); k >>= 1n; }
  return r;
}