Восстановление открытого ключа ECDSA: recid, v и ecrecover

Коротко. По подписи ECDSA (r, s) и хешу сообщения e открытый ключ подписанта вычисляется как Q = r⁻¹(s·R − e·G), где R — точка кривой, у которой координата x равна r. Таких точек может быть до четырёх, поэтому подписант прикладывает к подписи идентификатор восстановления (recovery id): один бит задаёт чётность координаты y точки R, а второй, теоретически, сообщает, была ли координата R.x приведена по модулю n. Ethereum кодирует его в v (27/28 в сообщениях, chainId·2 + 35 + yParity в транзакциях старого формата, yParity в типизированных транзакциях), Bitcoin — в байте заголовка 65-байтной компактной подписи (от 27 до 42). Для корректных входных данных восстановление всегда возвращает какой-то ключ: проверкой оно становится, только когда вы сравниваете результат с ожидаемым адресом или ключом. Прекомпилированный контракт ecrecover в Ethereum на некорректных входных данных ничего не возвращает (Solidity превращает это в address(0)) и принимает как s, так и n − s.

Математика

Подписывая сообщение, ECDSA выбирает nonce k (одноразовое секретное число), вычисляет R = kG и задаёт r = R.x mod n и s = k⁻¹(e + r·d) mod n. Если преобразовать второе уравнение с учётом Q = dG, получим

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

В правой части известно всё, кроме самой точки R, а подпись содержит только её координату x, приведённую по модулю n. Чтобы восстановить R, проверяющей стороне нужно знать:

• Чётность R.y. Заданному x соответствуют две точки, (x, y) и (x, p − y); у одной из них координата y чётная.
• Выполняется ли R.x ≥ n. На secp256k1 простой модуль поля p немного больше порядка группы n, поэтому координата x из диапазона [n, p) оказалась бы приведена по модулю. Вероятность этого — (p − n)/p, около 2⁻¹²⁷; на практике такого не бывает, а v в Ethereum не может даже выразить этот случай.

Это и есть идентификатор восстановления: recid = 2·[R.x ≥ n] + (R.y mod 2), как определено в SEC 1 v2.0 § 4.1.6 (SEC 1). Вот то же самое на Python, без скрытых шагов:

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

Специфичны для secp256k1 здесь только константы и быстрый способ извлечь квадратный корень; восстановление работает и на P-256. Это соглашение экосистем Bitcoin и Ethereum, а не свойство кривой; JOSE, TLS и WebAuthn вместо этого передают ключи явно или заверяют их сертификатами.

Ethereum: подпись из cast, восстановленная вручную

В эксперименте мы сгенерировали одноразовый ключ в Foundry 1.8.5 и подписали сообщение по правилам 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 разбивает 65 байт на r, s и v, перебирает все четыре идентификатора восстановления, а затем восстанавливает ключ по той же подписи, но для немного другого сообщения:

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

Отсюда два вывода. Неверный идентификатор восстановления даёт другой корректный ключ, а не ошибку, поэтому проверяющая сторона, которая угадывает v, спокойно «восстановит» кого-то другого. А та же подпись под другим сообщением (ecdsa.org вместо ecdsa.com) восстанавливает ещё один адрес правильного формата. На неверных данных восстановление не завершается ошибкой; проверкой его делает только сравнение с ожидаемым подписантом.

Что возвращает ecrecover

Контракты вызывают прекомпилированный контракт по адресу 0x01 и передают ему 128 байт: хеш, затем v, r и s в виде 32-байтных слов. В эксперименте мы отправили ему пять наборов входных данных на локальном узле anvil с помощью cast call:

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

• Двойник (v заменён с 27 на 28 или наоборот, s заменён на n − s) восстанавливает того же подписанта. EIP-2 сделал подписи транзакций с high-S недействительными, но не тронул прекомпилированный контракт: он «will keep accepting high s-values» (и дальше будет принимать большие значения s). Если контракт использует байты подписи как идентификатор, например чтобы пометить подписанный ваучер как погашенный, двойник позволяет провести ту же операцию повторно. Помечайте как использованное сообщение (nonce или дайджест), но никогда не саму подпись.
• Некорректные входные данные (v вне 27/28, s = 0) дают пустой результат. ecrecover в Solidity превращает его в address(0); в документации сказано, что функция возвращает «zero on error» (ноль при ошибке). Если ожидаемым подписантом когда-либо может оказаться address(0) (незаданный владелец, отсутствующая запись в mapping), проходит любая недействительная подпись.
• Изменённое значение s восстанавливает случайный на вид адрес, как и в тесте на Python.

Обычное решение для всех трёх случаев — ECDSA.recover из OpenZeppelin (Contracts 5.6.1): функция отклоняет s больше n/2 с ошибкой ECDSAInvalidSignatureS, нулевой результат — с ошибкой ECDSAInvalidSignature, а в перегрузке для bytes — любую длину, кроме 65 байт. У кошельков на смарт-контрактах вообще нет ключа, который можно было бы восстановить; их подписи проверяют по ERC-1271, как описано в статье Sign-In with Ethereum.

Разные формы v

Где хранится бит восстановления, зависит от того, что подписано:

В эксперименте мы подписали сообщение с помощью viem 2.57.7 и проверили, как функции восстановления этой библиотеки обрабатывают разные варианты:

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 из viem не принимает 64-байтную строку EIP-2098: сначала преобразуйте её с помощью compactSignatureToSignature, иначе получите ошибку invalid signature length. Недопустимое значение v приводит к ошибке Invalid yParityOrV value. У транзакции старого формата v = 38, то есть 1·2 + 35 + 1. Для транзакции EIP-1559 viem для удобства сообщает v = 28, но сама подписанная транзакция содержит только yParity. Библиотека web3.py для Python так же строго проверяет длину: Expected 65, but got 64 bytes.

Реальная ошибка, которую мы допустили, пока готовили этот эксперимент: если инвертировать чётность через v ^ 1, 27 превращается в 26, а 28 — в 29, потому что 27 нечётно. Работайте с yParity = v − 27 (или (v − 35) mod 2 для EIP-155) и преобразуйте значение обратно только на границе системы.

Bitcoin: компактные подписи сообщений

signmessage в Bitcoin Core создаёт подпись того же вида, но с байтом заголовка в начале. С одноразовым ключом в 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

Дайджест — двойной SHA-256 от "\x18Bitcoin Signed Message:\n", длины сообщения и самого сообщения. Заголовок 31 означает recid 0 и сжатый ключ; если заменить его на 27, восстановится та же точка, но адрес будет вычислен по хешу несжатой формы ключа и окажется другим, поэтому проверка не пройдёт. Как и ecrecover, проверка сообщений в Bitcoin Core приняла двойника с high-S: low-S — правило ретрансляции транзакций, а не правило для сообщений. Для адресов SegWit и Taproot этого формата недостаточно; в статье Подпись сообщений Bitcoin и BIP-322 разобраны варианты заголовка, в которых кошельки расходятся, и более новый формат.

Как добавить идентификатор восстановления к подписям HSM и KMS

Аппаратные модули безопасности (HSM) и облачные KMS подписывают дайджест и возвращают (r, s) в кодировке DER: без идентификатора восстановления и без гарантий насчёт low-S. Чтобы использовать такой ключ в Ethereum, один раз вычислите его адрес из открытого ключа, а затем для каждой подписи нормализуйте s и найдите чётность, при которой восстанавливается именно ваш ключ. В эксперименте роль HSM играет ключ pyca/cryptography, который подписывает только готовые дайджесты:

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

Обёртка Prehashed(hashes.SHA256()) лишь сообщает библиотеке, что на вход подан готовый 32-байтный дайджест; сам дайджест — Keccak-256, как того требует Ethereum. Перебирать обе чётности здесь безопасно, потому что результат сравнивается с одним известным адресом. Обратите внимание на длину DER: 71 байт в этом запуске и 72 в другом. DER отбрасывает ведущие нулевые байты и добавляет один, если установлен старший бит, поэтому буферы фиксированного размера ломаются (форматы подписей ECDSA). Та же процедура подходит для ключей AWS KMS ECC_SECG_P256K1; Google Cloud KMS для secp256k1 уже возвращает подписи с low-S, но идентификатора восстановления в них всё равно нет.

Когда восстановление — подходящий инструмент

Восстановление экономит от 33 до 65 байт на каждой подписи, поэтому Ethereum применяет его в каждой транзакции. Но оно же меняет то, что доказывает подпись. Если ключ передаётся вместе с подписью, проверяющая сторона устанавливает: «этот ключ подписал это сообщение». При восстановлении она вычисляет «какой-то ключ подписал это сообщение» и затем должна решить, подходит ли ей этот ключ: обычно для этого из ключа вычисляют адрес и сравнивают его со списком разрешённых адресов, с сохранённым владельцем или с адресом from, который заявляет пользователь. Код, который пропускает сравнение, ничего не проверяет.

За пределами блокчейнов для восстановления редко находится причина. Протоколам, которые могут передать идентификатор ключа или сертификат (kid в JWT, TLS, X.509), следует это делать: тогда проверяющая сторона ищет ровно один ключ, а не доверяет тому, что выдала математика.

Типичные ошибки

• Восстановление без сравнения. Запись «подпись верна» в журнал сразу после того, как ecrecover отработал без ошибки. Любая корректная подпись что-нибудь да восстанавливает.
• Принятие address(0) в качестве подписанта, напрямую или через неинициализированную переменную.
• Защита от повторного использования по байтам подписи. Двойник с high-S — вторая, столь же действительная подпись того же сообщения.
• Угадывание v. Если перебирать обе чётности и принимать ту, что восстанавливает «какой-нибудь» ключ, проверка превращается в поиск любого ключа вообще; перебирайте обе, только если затем сравниваете результат с одним ожидаемым адресом.
• Хеширование не тех данных. personal_sign добавляет префикс \x19Ethereum Signed Message:\n и длину в десятичной записи; EIP-712 использует \x19\x01 и два хеша структур. Восстановление с неверным дайджестом без всякой ошибки даёт неверный адрес. Различия разобраны в сравнении EIP-191 или EIP-712.
• Несовпадение форматов 65-байтных подписей, 64-байтных подписей EIP-2098 и подписей DER. Преобразуйте их явно на границе систем, а к подписям от HSM и KMS добавляйте идентификатор восстановления, как показано выше.

Источники

• SEC 1 v2.0: криптография на эллиптических кривых (Elliptic Curve Cryptography), § 4.1.6 (операция восстановления открытого ключа)
• Ethereum: EIP-2, EIP-155, EIP-191, EIP-2098, Solidity: математические и криптографические функции
• OpenZeppelin Contracts ECDSA.sol
• Bitcoin: BIP-137 (формат заголовка подписи)
• Использованные библиотеки и инструменты: Foundry 1.8.5 (cast, anvil), Bitcoin Core 31.1, viem 2.57.7, @noble/curves 2.4.0, pycryptodome 3.23.0