Récupération de clé publique ECDSA : recid, v et ecrecover

En bref. À partir d’une signature ECDSA (r, s) et du condensat du message e, la clé publique du signataire est Q = r⁻¹(s·R − e·G), où R est le point de la courbe dont la coordonnée x vaut r. Il existe jusqu’à quatre points de ce type ; le signataire joint donc un identifiant de récupération : un bit pour la parité de la coordonnée y de R et, en théorie, un autre qui indique si R.x a été réduit modulo n. Ethereum l’encode dans v (27/28 dans les messages, chainId·2 + 35 + yParity dans les transactions historiques, yParity dans les transactions typées), Bitcoin dans l’octet d’en-tête d’une signature compacte de 65 octets (de 27 à 42). La récupération renvoie toujours une clé pour une entrée bien formée : elle ne devient une vérification que si vous comparez le résultat avec l’adresse ou la clé attendue. Le contrat précompilé ecrecover d’Ethereum ne renvoie rien sur une entrée mal formée, ce que Solidity convertit en address(0), et il accepte aussi bien s que n − s.

Le calcul

Pour signer, ECDSA choisit un nonce k, calcule R = kG, pose r = R.x mod n et s = k⁻¹(e + r·d) mod n. En réarrangeant la seconde équation avec Q = dG, on obtient

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

Tout ce qui figure à droite est connu, sauf R lui-même, et la signature ne contient que sa coordonnée x, réduite modulo n. Pour reconstruire R, un vérificateur a besoin de deux informations :

• La parité de R.y. Pour un x donné, il existe deux points, (x, y) et (x, p − y) ; l’un des deux a un y pair.
• Savoir si R.x ≥ n. Sur secp256k1, le nombre premier p qui définit le corps est un peu plus grand que l’ordre du groupe n ; une coordonnée x comprise dans [n, p) aurait donc été réduite. La probabilité est de (p − n)/p, soit environ 2⁻¹²⁷ : cela n’arrive jamais en pratique, et le v d’Ethereum ne permet même pas de l’exprimer.

C’est cela, l’identifiant de récupération : recid = 2·[R.x ≥ n] + (R.y mod 2), spécifié dans SEC 1 v2.0 §4.1.6 (SEC 1). Le voici écrit en Python, sans rien cacher :

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")

Rien ici n’est propre à secp256k1, hormis les constantes et le raccourci pour la racine carrée ; la récupération fonctionne aussi sur P-256. C’est une convention des écosystèmes Bitcoin et Ethereum, pas une propriété de la courbe : JOSE, TLS et WebAuthn transmettent ou certifient plutôt les clés.

Ethereum : une signature produite par cast, récupérée à la main

Le laboratoire a généré une clé jetable avec Foundry 1.8.5 et signé un message selon la sémantique de personal_sign (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 découpe les 65 octets en r, s et v, essaie les quatre identifiants de récupération, puis applique la récupération à la même signature avec un message légèrement différent :

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

Deux enseignements à en tirer. Un mauvais identifiant de récupération donne une autre clé valide, et non une erreur : un vérificateur qui devine v « récupérera » sans broncher quelqu’un d’autre. Et la même signature sur un autre message (ecdsa.org au lieu de ecdsa.com) donne encore une autre adresse bien formée. La récupération n’a aucun mode d’échec face à des données erronées ; seule la comparaison avec un signataire attendu en fait un contrôle.

Ce que renvoie ecrecover

Les contrats appellent le contrat précompilé situé à l’adresse 0x01 avec 128 octets : le condensat, puis v, r et s sous forme de mots de 32 octets. Le laboratoire lui a soumis cinq entrées sur un nœud anvil local avec cast call :

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

• La signature jumelle (v basculé entre 27 et 28, s remplacé par n − s) donne le même signataire. EIP-2 a rendu invalides les signatures de transaction high-S, mais n’a pas touché au contrat précompilé, qui « continuera d’accepter les valeurs de s élevées ». Tout contrat qui utilise les octets de la signature comme identifiant, par exemple pour marquer un bon signé comme utilisé, est exposé au rejeu avec la jumelle. Marquez comme utilisé le message (un nonce ou le condensat), jamais la signature.
• Une entrée mal formée (v hors de 27/28, s = 0) produit une sortie vide. La fonction ecrecover de Solidity la convertit en address(0) ; sa documentation indique qu’elle renvoie « zéro en cas d’erreur ». Si le signataire attendu peut un jour valoir address(0) (un propriétaire non défini, une entrée de mapping absente), toute signature invalide passe.
• Un s modifié donne une adresse d’apparence aléatoire, comme dans le test en Python.

La correction habituelle pour ces trois cas est ECDSA.recover d’OpenZeppelin (Contracts 5.6.1), qui rejette un s supérieur à n/2 avec ECDSAInvalidSignatureS, un résultat nul avec ECDSAInvalidSignature et, dans sa surcharge bytes, tout ce qui ne fait pas 65 octets. Les portefeuilles de contrat intelligent n’ont aucune clé à récupérer : ils se vérifient avec ERC-1271, comme l’explique Sign-In with Ethereum.

Les multiples formes de v

L’emplacement du bit de récupération dépend de ce qui a été signé :

Le laboratoire a signé avec viem 2.57.7 et vérifié comment ses fonctions de récupération traitent ces variantes :

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

La fonction recoverMessageAddress de viem n’accepte pas une chaîne EIP-2098 de 64 octets ; convertissez-la d’abord avec compactSignatureToSignature, sinon vous obtenez invalid signature length. Un v aberrant donne Invalid yParityOrV value. Le v = 38 de la transaction historique vaut 1·2 + 35 + 1. Pour la transaction EIP-1559, viem indique v = 28 par commodité, mais la transaction signée elle-même ne porte que yParity. En Python, web3.py est tout aussi strict sur les longueurs : Expected 65, but got 64 bytes.

Un vrai bogue rencontré en écrivant ce laboratoire : inverser la parité avec v ^ 1 transforme 27 en 26 et 28 en 29, car 27 est impair. Travaillez avec yParity = v − 27 (ou (v − 35) mod 2 pour EIP-155) et ne revenez à v qu’aux frontières du code.

Bitcoin : signatures de message compactes

La commande signmessage de Bitcoin Core produit le même type de signature, précédée d’un octet d’en-tête. Avec une clé jetable en regtest :

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

Le condensat est un double SHA-256 de "\x18Bitcoin Signed Message:\n", de la longueur du message et du message. L’en-tête 31 signifie recid 0 et une clé compressée ; le remplacer par 27 permet de récupérer le même point, mais c’est alors l’encodage non compressé qui est haché, ce qui donne une autre adresse : la vérification échoue. Comme ecrecover, la vérification de message de Bitcoin Core a accepté la jumelle high-S : low-S est une règle de relais des transactions, pas une règle des messages. Pour les adresses SegWit et Taproot, ce format ne suffit pas ; Signer un message Bitcoin et BIP-322 présente les variantes d’en-tête sur lesquelles les portefeuilles divergent, ainsi que le format plus récent.

Ajouter un identifiant de récupération aux signatures HSM et KMS

Les modules de sécurité matériels (HSM) et les KMS cloud signent un condensat et renvoient un couple (r, s) encodé en DER : pas d’identifiant de récupération, et aucune garantie low-S. Pour utiliser une telle clé avec Ethereum, dérivez une fois pour toutes son adresse à partir de la clé publique, puis, pour chaque signature, normalisez s et trouvez la parité qui permet de récupérer votre propre clé. Le laboratoire simule le HSM avec une clé pyca/cryptography qui ne signe que des condensats déjà calculés :

"""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.

L’enveloppe Prehashed(hashes.SHA256()) indique seulement à la bibliothèque que l’entrée est déjà un condensat de 32 octets ; le condensat lui-même est un Keccak-256, comme l’exige Ethereum. Essayer les deux parités est sans danger ici, car le résultat est comparé à une seule adresse connue. Notez la longueur DER de 71 octets dans cette exécution, contre 72 dans une autre : DER supprime les octets nuls de tête et en ajoute un lorsque le bit de poids fort est à 1, ce qui explique pourquoi les tampons de taille fixe cassent (Formats de signature ECDSA). La même procédure s’applique aux clés AWS KMS ECC_SECG_P256K1 ; Google Cloud KMS renvoie déjà du low-S pour secp256k1, mais toujours sans identifiant de récupération.

Quand la récupération est le bon outil

La récupération économise de 33 à 65 octets par signature, ce qui explique pourquoi Ethereum l’utilise pour chaque transaction. Elle change aussi ce que prouve une signature. Avec une clé transmise, un vérificateur contrôle que « cette clé a signé ce message ». Avec la récupération, il calcule qu’« une certaine clé a signé ce message » et doit ensuite décider si cette clé est acceptable, généralement en dérivant une adresse et en la comparant à une liste d’autorisation, à un propriétaire enregistré ou au from que revendique l’utilisateur. Un code qui saute la comparaison ne vérifie rien.

En dehors des blockchains, il y a rarement une raison de l’utiliser. Les protocoles capables de transporter un identifiant de clé ou un certificat (JWT kid, TLS, X.509) devraient le faire ; le vérificateur recherche alors exactement une clé au lieu de se fier à ce que produit le calcul.

Erreurs fréquentes

• Récupérer sans comparer. Journaliser « signature valide » dès que ecrecover réussit. Toute signature bien formée permet de récupérer quelque chose.
• Accepter address(0) comme signataire, directement ou via une variable non initialisée.
• Protection contre le rejeu fondée sur les octets de la signature. La jumelle high-S est une seconde signature, tout aussi valide, du même message.
• Deviner v. Essayer les deux parités et accepter celle qui récupère « une » clé transforme la vérification en recherche de n’importe quelle clé ; n’essayez les deux que si vous comparez ensuite le résultat à une seule adresse attendue.
• Hacher la mauvaise donnée. personal_sign ajoute le préfixe \x19Ethereum Signed Message:\n et la longueur en décimal ; EIP-712 utilise \x19\x01 et deux condensats de structure. Récupérer avec le mauvais condensat donne une mauvaise adresse, sans erreur. Les différences sont détaillées dans EIP-191 vs EIP-712.
• Formats incompatibles entre signatures de 65 octets, de 64 octets EIP-2098 et DER. Convertissez explicitement à la frontière et, pour la sortie d’un HSM ou d’un KMS, ajoutez l’identifiant de récupération comme indiqué plus haut.

Sources

• SEC 1 v2.0 : Elliptic Curve Cryptography, §4.1.6 (opération de récupération de la clé publique)
• Ethereum : EIP-2, EIP-155, EIP-191, EIP-2098, Solidity : fonctions mathématiques et cryptographiques
• OpenZeppelin Contracts ECDSA.sol
• Bitcoin : BIP-137 (format de l’en-tête de signature)
• Bibliothèques utilisées : Foundry 1.8.5 (cast, anvil), Bitcoin Core 31.1, viem 2.57.7, @noble/curves 2.4.0, pycryptodome 3.23.0