ECDSA-Public-Key-Recovery: Recovery-ID, v und ecrecover

Kurz gesagt. Aus einer ECDSA-Signatur (r, s) und dem Hash e der Nachricht ergibt sich der öffentliche Schlüssel des Signierers als Q = r⁻¹(s·R − e·G), wobei R der Kurvenpunkt mit der x-Koordinate r ist. Solche Punkte gibt es bis zu vier, deshalb hängt der Signierer eine Recovery-ID an: ein Bit für die Parität der y-Koordinate von R und, theoretisch, eines dafür, ob R.x modulo n reduziert wurde. Ethereum kodiert sie als v (27/28 bei Nachrichten, chainId·2 + 35 + yParity bei Legacy-Transaktionen, yParity bei typisierten Transaktionen), Bitcoin als Header-Byte einer kompakten 65-Byte-Signatur (27 bis 42). Die Wiederherstellung liefert immer irgendeinen Schlüssel, solange die Eingabe wohlgeformt ist: Eine Prüfung wird daraus erst, wenn du das Ergebnis mit der Adresse oder dem Schlüssel vergleichst, den du erwartet hast. Das Precompile ecrecover von Ethereum gibt bei fehlerhafter Eingabe nichts zurück, was Solidity in address(0) umwandelt, und es akzeptiert sowohl s als auch n − s.

Die Mathematik

Beim Signieren wählt ECDSA eine Nonce k, berechnet R = kG und setzt r = R.x mod n sowie s = k⁻¹(e + r·d) mod n. Stellst du die zweite Gleichung mit Q = dG um, erhältst du

s·k = e + r·d → s·R = e·G + r·Q → Q = r⁻¹(s·R − e·G).

Rechts ist alles bekannt außer R selbst, und die Signatur enthält nur dessen x-Koordinate, reduziert modulo n. Um R zu rekonstruieren, braucht ein Verifizierer:

• Die Parität von R.y. Zu einem gegebenen x gibt es zwei Punkte, (x, y) und (x, p − y); einer davon hat ein gerades y.
• Ob R.x ≥ n ist. Bei secp256k1 ist die Primzahl p des Körpers etwas größer als die Gruppenordnung n, eine x-Koordinate in [n, p) wäre also reduziert worden. Die Wahrscheinlichkeit dafür ist (p − n)/p, etwa 2⁻¹²⁷; in der Praxis kommt das nie vor, und das v von Ethereum kann es nicht einmal ausdrücken.

Das ist die Recovery-ID: recid = 2·[R.x ≥ n] + (R.y mod 2), spezifiziert in SEC 1 v2.0 §4.1.6 (SEC 1). Vollständig ausgeschrieben in Python, ohne versteckte Schritte:

def recover(e: int, r: int, s: int, recid: int):
    """Return the public key Q with s = k^-1 (e + r*d), or None if recid does not name a curve point."""
    if not (0 < r < n and 0 < s < n):
        raise ValueError("r and s must be in [1, n-1]")
    x = r + (recid >> 1) * n          # recid 2 and 3: R.x was >= n and got reduced
    if x >= p:
        return None
    alpha = (x * x * x + 7) % p
    y = pow(alpha, (p + 1) // 4, p)   # p % 4 == 3, so this is a square root if one exists
    if y * y % p != alpha:
        return None                   # r is not the x-coordinate of any point
    if y & 1 != recid & 1:
        y = p - y                     # recid bit 0 is the parity of R.y
    R = (x, y)
    r_inv = pow(r, -1, n)
    return add(mul(s * r_inv % n, R), mul(-e * r_inv % n, G))   # Q = r^-1 (sR - eG)


def eth_address(Q):
    k = keccak.new(digest_bits=256, data=Q[0].to_bytes(32, "big") + Q[1].to_bytes(32, "big"))
    return "0x" + k.hexdigest()[-40:]


def eth_personal_digest(message: bytes) -> int:
    data = b"\x19Ethereum Signed Message:\n" + str(len(message)).encode() + message
    return int.from_bytes(keccak.new(digest_bits=256, data=data).digest(), "big")

Bis auf die Konstanten und die Abkürzung bei der Quadratwurzel ist nichts davon spezifisch für secp256k1; die Wiederherstellung funktioniert auch mit P-256. Das Verfahren ist eine Konvention der Bitcoin- und Ethereum-Ökosysteme, keine Eigenschaft der Kurve; JOSE, TLS und WebAuthn übertragen oder zertifizieren Schlüssel stattdessen.

Ethereum: eine Signatur aus cast, von Hand wiederhergestellt

Für den Testaufbau wurde mit Foundry 1.8.5 ein Wegwerfschlüssel erzeugt und damit eine Nachricht nach der Semantik von personal_sign signiert (EIP-191):

KEY=$(cast wallet new --json | python3 -c "import json,sys; print(json.load(sys.stdin)['data'][0]['private_key'])")
ADDR=$(cast wallet address --private-key "$KEY")
SIG=$(cast wallet sign --private-key "$KEY" "hello from ecdsa.com")
cast wallet verify --address "$ADDR" "hello from ecdsa.com" "$SIG"
python3 eth_recover.py "hello from ecdsa.com" "$SIG" "$ADDR"

eth_recover.py zerlegt die 65 Byte in r, s und v, probiert alle vier Recovery-IDs aus und wendet die Wiederherstellung dann mit derselben Signatur auf eine leicht abgewandelte Nachricht an:

address: 0x22baE48F42D493eDcF82ddB7e47480B7233917b3
signature: 0x150e0d6f3cc85f603300fe1801bc4397021a51495c53186f15ecb05f9e57dcbe2a17a5521f6c42792fc22a98754e5c01dd26ac42009e8d24d3cb713a8fe96fed1c
Validation succeeded. Address 0x22baE48F42D493eDcF82ddB7e47480B7233917b3 signed this message.
r=0x150e0d6f3cc85f603300fe1801bc4397021a51495c53186f15ecb05f9e57dcbe
s=0x2a17a5521f6c42792fc22a98754e5c01dd26ac42009e8d24d3cb713a8fe96fed
v=28  (s is low)
recid 0: 0xb1775d58a680572a45fe5d6ba094c56b0b748c9d
recid 1: 0x22bae48f42d493edcf82ddb7e47480b7233917b3  <- v - 27
recid 2: no point (x = r + n is not below p)
recid 3: no point (x = r + n is not below p)
matches the signer: True
same signature, other message -> 0x994ba1aaf9e6b96710727d919140aff23f56407c

Daraus lassen sich zwei Dinge mitnehmen. Die falsche Recovery-ID liefert einen anderen gültigen Schlüssel, keinen Fehler; ein Verifizierer, der v rät, „stellt“ also anstandslos den Schlüssel von jemand anderem „wieder her“. Und dieselbe Signatur über eine andere Nachricht (ecdsa.org statt ecdsa.com) ergibt noch eine weitere wohlgeformte Adresse. Bei falschen Daten schlägt die Wiederherstellung nicht fehl; erst der Vergleich mit einem erwarteten Signierer macht daraus eine Prüfung.

Was ecrecover zurückgibt

Contracts rufen das Precompile an der Adresse 0x01 mit 128 Byte Eingabe auf: zuerst der Hash, dann v, r und s als 32-Byte-Wörter. Im Testaufbau gingen mit cast call fünf Eingaben an das Precompile eines lokalen anvil-Knotens:

as signed (v, r, s)                0x00000000000000000000000022bae48f42d493edcf82ddb7e47480b7233917b3
twin (55-v, r, n-s)                0x00000000000000000000000022bae48f42d493edcf82ddb7e47480b7233917b3
v = 29                             0x
s + 1                              0x000000000000000000000000412fbd6e833de18577db8f41022c54e852192b34
s = 0                              0x

• Der Zwilling (v zwischen 27 und 28 getauscht, s durch n − s ersetzt) ergibt denselben Signierer. EIP-2 hat High-S-Signaturen von Transaktionen für ungültig erklärt, das Precompile aber unverändert gelassen: Es werde „weiterhin hohe s-Werte akzeptieren“. Bei jedem Contract, der die Signatur-Bytes als Kennung verwendet, etwa um einen signierten Gutschein als eingelöst zu markieren, ist mit dem Zwilling ein Replay möglich. Markiere die Nachricht (eine Nonce oder den Digest) als verwendet, niemals die Signatur.
• Fehlerhafte Eingaben (v außerhalb von 27/28, s = 0) erzeugen eine leere Ausgabe. ecrecover in Solidity macht daraus address(0); laut Dokumentation gibt die Funktion „bei einem Fehler null“ zurück. Kann der erwartete Signierer jemals address(0) sein (ein nicht gesetzter Eigentümer, ein fehlender Mapping-Eintrag), kommt jede ungültige Signatur durch.
• Ein verändertes s ergibt eine zufällig aussehende Adresse, wie im Python-Test.

Die übliche Abhilfe für alle drei Fälle ist ECDSA.recover von OpenZeppelin (Contracts 5.6.1): Die Funktion lehnt ein s über n/2 mit ECDSAInvalidSignatureS ab, ein Nullergebnis mit ECDSAInvalidSignature und in ihrer Überladung für bytes alles, was nicht genau 65 Byte lang ist. Smart-Contract-Wallets haben überhaupt keinen Schlüssel, der sich wiederherstellen ließe; sie werden über ERC-1271 geprüft, wie in Sign-In with Ethereum beschrieben.

Die vielen Formen von v

Wo das Recovery-Bit steht, hängt davon ab, was signiert wurde:

Im Testaufbau wurde mit viem 2.57.7 signiert und geprüft, wie die Wiederherstellungsfunktionen von viem mit den Varianten umgehen:

for (const [label, sig] of [
  ["65-byte", signature],
  ["64-byte compact", compact],
  ["63 bytes", signature.slice(0, -4)],
  ["v = 29", signature.slice(0, -2) + "1d"],
]) {
  try {
    const who = await recoverMessageAddress({ message, signature: sig });
    console.log(`recover ${label.padEnd(16)} ${who === account.address ? "signer" : who}`);
  } catch (e) {
    console.log(`recover ${label.padEnd(16)} ${e.shortMessage ?? e.message.split("\n")[0]}`);
  }
}

// The same recovery with noble: the recovery bit travels separately from the 64-byte (r, s).
const digest = hashMessage(message, "bytes");
const rs = Buffer.from(signature.slice(2, 130), "hex");
const pub = secp256k1.Signature.fromBytes(rs, "compact").addRecoveryBit(parsed.yParity).recoverPublicKey(digest);
console.log(`noble recovers    ${pub.toHex(true)} (compressed public key)`);

signer            0xa9650f6049917850af00B8e7Ffc386d9A3e18C08
signature         65 bytes, v=27, yParity=0
EIP-2098 compact  64 bytes, top bit of byte 32 = yParity: true
recover 65-byte          signer
recover 64-byte compact  invalid signature length
recover 63 bytes         invalid signature length
recover v = 29           Invalid yParityOrV value
noble recovers    036a079737b9587224344944600570a311f21b3b06f5c920b24bcd95e993afd7e0 (compressed public key)
legacy tx, chain 1: v=38 (yParity 1)
EIP-1559 tx, chain 1: v=28, yParity=1

recoverMessageAddress von viem akzeptiert keinen 64-Byte-String nach EIP-2098; wandle ihn vorher mit compactSignatureToSignature um, sonst bekommst du invalid signature length. Ein unpassendes v führt zu Invalid yParityOrV value. Das v = 38 der Legacy-Transaktion ist 1·2 + 35 + 1. Für die EIP-1559-Transaktion meldet viem der Bequemlichkeit halber v = 28, die signierte Transaktion selbst enthält aber nur yParity. Ebenso streng bei Längen ist web3.py in Python: Expected 65, but got 64 bytes.

Ein echter Bug aus der Arbeit an diesem Testaufbau: Wer die Parität mit v ^ 1 umdreht, macht aus 27 eine 26 und aus 28 eine 29, weil 27 ungerade ist. Rechne mit yParity = v − 27 (oder mit (v − 35) mod 2 bei EIP-155) und wandle erst an der Schnittstelle nach außen zurück.

Bitcoin: kompakte Nachrichtensignaturen

signmessage von Bitcoin Core erzeugt dieselbe Art von Signatur, mit einem vorangestellten Header-Byte. Mit einem Wegwerfschlüssel im Regtest-Modus:

SIG=$($CLI signmessagewithprivkey "$WIF" "$MSG")
$CLI verifymessage "$ADDR" "$SIG" "$MSG"
python3 btc_recover.py "$MSG" "$SIG"      # recover by hand, then build three variants

address: mvzrMJdGFmYPJw79zHz5i2WqMHdwchtbr1
signature: H6uRgJJnTugkk5XeUQl+eE1oY5/L6yZZORJHwTn1ohJdFOWEPPUvL6oHzDx2lAeoI+l1d3ipt5sw3TmF/tkpz60=
verifymessage: true
65 bytes: header 31 -> recid 0, compressed key: True, s is low
recovered public key: 03b7b74bd1e7c935c284dbb71b48649f1ff6a5cb939d615061204271a61f4232e1
its regtest P2PKH address: mvzrMJdGFmYPJw79zHz5i2WqMHdwchtbr1
other recid (header 32)              verifymessage: false
uncompressed header (27)             verifymessage: false
high-S twin (header 32, n - s)       verifymessage: true

Der Digest ist ein doppelter SHA-256-Hash über "\x18Bitcoin Signed Message:\n", die Länge der Nachricht und die Nachricht selbst. Header 31 bedeutet recid 0 und einen komprimierten Schlüssel; wird er auf 27 geändert, ergibt sich derselbe Punkt, aber dessen unkomprimierte Kodierung wird zu einer anderen Adresse gehasht, und die Prüfung schlägt fehl. Wie ecrecover hat auch die Nachrichtenprüfung von Bitcoin Core den High-S-Zwilling akzeptiert: Low-S ist eine Relay-Regel für Transaktionen, keine Regel für Nachrichten. Für SegWit- und Taproot-Adressen reicht dieses Format nicht aus; Bitcoin-Nachrichten signieren und BIP-322 behandelt die Header-Varianten, bei denen sich Wallets uneinig sind, und das neuere Format.

Recovery-ID für HSM- und KMS-Signaturen ergänzen

Hardware-Sicherheitsmodule und Cloud-KMS signieren einen Digest und geben ein DER-kodiertes (r, s) zurück: ohne Recovery-ID und ohne Zusage zu Low-S. Um einen solchen Schlüssel für Ethereum zu verwenden, leitest du seine Adresse einmalig aus dem öffentlichen Schlüssel ab; dann normalisierst du bei jeder Signatur s und suchst die Parität, mit der sich dein eigener Schlüssel wiederherstellen lässt. Der Testaufbau simuliert das HSM mit einem Schlüssel von pyca/cryptography, der nur vorab gehashte Digests signiert:

"""Turn a DER ECDSA signature without a recovery id (what HSMs and cloud KMS return) into an Ethereum signature."""
import sys

from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import ec
from cryptography.hazmat.primitives.asymmetric.utils import Prehashed, decode_dss_signature

from recover import eth_address, eth_personal_digest, n, recover

# Stand-in for the HSM: a secp256k1 key that signs a 32-byte digest and returns DER, nothing else.
hsm_key = ec.generate_private_key(ec.SECP256K1())
public = hsm_key.public_key().public_numbers()
expected = eth_address((public.x, public.y))     # what you would derive once from GetPublicKey


def hsm_sign_digest(digest: bytes) -> bytes:
    return hsm_key.sign(digest, ec.ECDSA(Prehashed(hashes.SHA256())))   # any 32-byte digest


message = sys.argv[1].encode()
e = eth_personal_digest(message)
der = hsm_sign_digest(e.to_bytes(32, "big"))
r, s = decode_dss_signature(der)
print(f"DER signature: {len(der)} bytes, s is {'high' if s > n // 2 else 'low'}")
if s > n // 2:
    s = n - s                                     # EIP-2: transactions need low-S; normalize everything
for recid in (0, 1):                              # find the parity that recovers our own key
    Q = recover(e, r, s, recid)
    if Q and eth_address(Q) == expected:
        break
else:
    raise SystemExit("neither recovery id matches the key")
sig = r.to_bytes(32, "big") + s.to_bytes(32, "big") + bytes([27 + recid])
print(f"address {expected}\nrecid {recid}\nsignature 0x{sig.hex()}")

DER signature: 71 bytes, s is high
address 0x3bf48296556c8b52217d22066c7239c50f2102e6
recid 1
signature 0x052fbd197e707e99a4c38648b4a65fb674b15c93025878c55b3950f876bb5cf634aa76d1ffe274696a3d94ba225ae72ab73af4292a0681dc7262dc8ef9495d071c
Validation succeeded. Address 0x3bf48296556c8B52217D22066C7239C50F2102E6 signed this message.

Der Wrapper Prehashed(hashes.SHA256()) teilt der Bibliothek nur mit, dass die Eingabe bereits ein 32-Byte-Digest ist; der Digest selbst ist Keccak-256, wie Ethereum es verlangt. Beide Paritäten auszuprobieren ist hier unbedenklich, weil das Ergebnis mit einer einzigen bekannten Adresse verglichen wird. Beachte die DER-Länge von 71 Byte in diesem Durchlauf gegenüber 72 in einem anderen: DER lässt führende Nullbytes weg und fügt eines hinzu, wenn das oberste Bit gesetzt ist; deshalb scheitern Puffer mit fester Größe (ECDSA-Signaturformate). Dasselbe Vorgehen gilt für Schlüssel vom Typ ECC_SECG_P256K1 in AWS KMS; Google Cloud KMS liefert für secp256k1 bereits Low-S, aber ebenfalls keine Recovery-ID.

Wann die Wiederherstellung das richtige Werkzeug ist

Die Wiederherstellung spart 33 bis 65 Byte pro Signatur; deshalb nutzt Ethereum sie für jede Transaktion. Zugleich ändert sie, was eine Signatur beweist. Mit einem übertragenen Schlüssel prüft ein Verifizierer „dieser Schlüssel hat diese Nachricht signiert“. Mit Wiederherstellung berechnet er „irgendein Schlüssel hat diese Nachricht signiert“ und muss dann entscheiden, ob dieser Schlüssel akzeptabel ist – meist, indem er eine Adresse ableitet und sie mit einer Allowlist, einem gespeicherten Eigentümer oder dem vom Benutzer angegebenen from vergleicht. Code, der den Vergleich auslässt, prüft gar nichts.

Außerhalb von Blockchains gibt es selten einen Grund dafür. Protokolle, die eine Schlüssel-ID oder ein Zertifikat mitführen können (JWT kid, TLS, X.509), sollten das tun; der Verifizierer schlägt dann genau einen Schlüssel nach, statt dem zu vertrauen, was die Mathematik gerade liefert.

Häufige Fehler

• Wiederherstellen ohne Vergleich. „Signatur gültig“ ins Log schreiben, sobald ecrecover erfolgreich ist. Aus jeder wohlgeformten Signatur lässt sich irgendetwas wiederherstellen.
• address(0) als Signierer akzeptieren, direkt oder über eine nicht initialisierte Variable.
• Replay-Schutz über die Signatur-Bytes. Der High-S-Zwilling ist eine zweite, ebenso gültige Signatur für dieselbe Nachricht.
• v raten. Wer beide Paritäten ausprobiert und diejenige nimmt, die „einen“ Schlüssel liefert, macht aus der Prüfung die Suche nach irgendeinem beliebigen Schlüssel; probiere beide nur dann aus, wenn du anschließend mit einer einzigen erwarteten Adresse vergleichst.
• Das Falsche hashen. personal_sign stellt das Präfix \x19Ethereum Signed Message:\n und die Länge als Dezimalzahl voran; EIP-712 verwendet \x19\x01 und zwei Struct-Hashes. Eine Wiederherstellung mit dem falschen Digest liefert ohne Fehlermeldung eine falsche Adresse. Die Unterschiede beschreibt EIP-191 vs. EIP-712.
• Nicht passende Formate zwischen 65-Byte-Signaturen, 64-Byte-Signaturen nach EIP-2098 und DER-Signaturen. Wandle an der Schnittstelle explizit um und ergänze bei Ausgaben von HSM und KMS die Recovery-ID wie oben gezeigt.

Quellen

• SEC 1 v2.0: Elliptische-Kurven-Kryptografie, §4.1.6 (Operation zur Wiederherstellung des öffentlichen Schlüssels)
• Ethereum: EIP-2, EIP-155, EIP-191, EIP-2098, Solidity: mathematische und kryptografische Funktionen
• OpenZeppelin Contracts ECDSA.sol
• Bitcoin: BIP-137 (Format des Signatur-Headers)
• Verwendete Bibliotheken: Foundry 1.8.5 (cast, anvil), Bitcoin Core 31.1, viem 2.57.7, @noble/curves 2.4.0, pycryptodome 3.23.0