Цифровые подписи: ECDSA, EdDSA, Schnorr

Шифрование прячет содержимое, но не доказывает авторство. Транзакция в блокчейне наоборот вся на виду, и от криптографии тут нужно одно: доказать, что списать монеты распорядился именно владелец ключа. Это цифровая подпись. Разберём ECDSA, EdDSA и Schnorr, увидим, как один повтор случайного числа выдаёт закрытый ключ, что такое малигибельность ECDSA и зачем нужны мультиподписи, пороговые, кольцевые и слепые схемы.

Идея

Цифровая подпись переворачивает асимметрию. В шифровании ты брал чужой открытый ключ, чтобы спрятать сообщение для владельца закрытого. В подписи наоборот: владелец закрытого ключа создаёт подпись, а проверяет её любой открытым ключом. Подпись даёт три вещи разом: авторство (подписал тот, у кого ключ), целостность (сообщение не тронули после подписи) и неотказуемость (подписавший не скажет «это не я»).

Тут важно не спутать подпись с HMAC из урока про хеши. HMAC симметричен: тег считают и проверяют одним общим ключом, поэтому проверяющий сам мог его подделать, неотказуемости нет. Подпись асимметрична: проверить может кто угодно открытым ключом, а создать только владелец закрытого. В блокчейне нужно именно это, ведь подпись транзакции проверяют тысячи незнакомых узлов, и общего секрета с ними у тебя нет.

ECDSA: подпись на secp256k1

Bitcoin и Ethereum подписывают транзакции через ECDSA на кривой secp256k1. Схема стоит на скалярном умножении из прошлого урока. Пусть d это закрытый ключ, Q = dG открытый, n это порядок генератора.

Подпись сообщения с хешем e = H(m):

1. Выбери случайное k из диапазона 1..n (вот тут вся опасность, см. ниже).
2. Посчитай точку R = kG и возьми r = R.x mod n.
3. Посчитай s = k⁻¹·(e + r·d) mod n.
4. Подпись это пара (r, s).

Проверка по открытому Q: посчитать u₁ = e·s⁻¹, u₂ = r·s⁻¹, восстановить точку u₁·G + u₂·Q и убедиться, что её x-координата равна r. Закрытый ключ в проверку не входит, и в этом весь смысл.

Своя реализация ECDSA в бою опасна, поэтому подпишем и проверим через k256:

# Cargo.toml
[dependencies]
k256 = { version = "0.13", features = ["ecdsa"] }
rand_core = { version = "0.6", features = ["getrandom"] }

use k256::ecdsa::signature::{Signer, Verifier};
use k256::ecdsa::{Signature, SigningKey, VerifyingKey};
use rand_core::OsRng;

fn main() {
    let signing_key = SigningKey::random(&mut OsRng); // закрытый ключ d
    let verifying_key = VerifyingKey::from(&signing_key); // открытый ключ Q = dG

    let tx = b"send 10 to Bob";
    let signature: Signature = signing_key.sign(tx); // (r, s)

    // Проверяет любой, у кого есть открытый ключ и сообщение.
    assert!(verifying_key.verify(tx, &signature).is_ok());

    // Подмена сообщения ломает подпись.
    assert!(verifying_key.verify(b"send 10 to Eve", &signature).is_err());
}

Повтор nonce выдаёт ключ

То самое случайное k в ECDSA называют nonce подписи, и оно самое хрупкое место схемы. Если подписать два разных сообщения с одним и тем же k, обе подписи получат одинаковый r (ведь R = kG тот же). А дальше школьная алгебра: из s₁ = k⁻¹(e₁ + rd) и s₂ = k⁻¹(e₂ + rd) вычитанием находится

k = (e₁ − e₂) / (s₁ − s₂)   (mod n)

а зная k, восстанавливается и закрытый ключ d = (s₁·k − e₁) / r. Один повтор, и ключ в руках атакующего. Заметь: ему не нужно знать сам k, достаточно увидеть два одинаковых r в подписях одного открытого ключа. Это видно прямо в блокчейне, где все подписи лежат открыто.

Покрути виджет. Закрытый ключ d тут зашит, но атакующий его не знает, он видит только две подписи и хеши сообщений. Пока k у обеих подписей один, оба r совпадают, и две строчки алгебры выдают d. Сдвинь k второй подписи, и r разъезжаются, атака разваливается.

хеш сообщения e1: 13хеш сообщения e2: 58nonce k для подписи 1: 7nonce k для подписи 2: 7

Подпись 1

r = 18
s = 81

Подпись 2

r = 18
s = 73

r совпали (18): значит nonce k один и тот же. Дальше нужна только школьная алгебра.

шаг 1k = (e1 − e2)·(s1 − s2)⁻¹ = (13 − 58)·(8)⁻¹ = 7 (mod 101)

шаг 2d = (s1·k − e1)·r⁻¹ = (81·7 − 13)·18⁻¹ = 42 (mod 101)

Закрытый ключ восстановлен: d = 42. Атакующий не знал его, а теперь подпишет от твоего имени что угодно. Из двух подписей и одного повтора nonce.

Поле тут учебно крошечное (порядок 101), в реальной secp256k1 числа на 256 бит, но алгебра ровно эта. Закрытый ключ зашит как d = 42: виджет его не подсказывает атакующему, а выводит из двух подписей. Настоящая защита это детерминированный nonce: k выводят хешем из ключа и сообщения, поэтому два разных сообщения не дадут одинаковый r никогда.

Это не теория. В 2010 году группа fail0verflow вскрыла ключ подписи прошивки PlayStation 3: Sony вместо случайного k поставила фиксированную константу, и две разные прошивки дали одинаковый r. Дальше та же формула, и закрытый ключ Sony стал публичным, после чего любой подписывал код «от Sony» неотличимо от настоящего. В 2013 году похожее случилось с Bitcoin: баг в SecureRandom на Android заставлял кошельки переиспользовать k внутри одной транзакции с несколькими входами. Атакующие выискивали совпадающие r в цепочке и за несколько часов увели около 55 BTC.

Лечение это детерминированный nonce по RFC 6979: k выводят не из генератора случайных чисел, а через HMAC-DRBG из закрытого ключа и хеша сообщения. На одно сообщение и один ключ всегда выходит один и тот же k, на разное сообщение всегда разный. Повтор k на разных сообщениях невозможен по построению, а одно сообщение дважды подписывать безвредно. Генератор случайных чисел при подписи вообще не нужен, и весь класс атак исчезает: именно поэтому в виджете правильная защита это разные k, а не «получше random». k256 делает RFC 6979 по умолчанию, но понимать, отчего тебя спасают, обязательно.

Малигибельность ECDSA

У ECDSA есть вторая особенность, тоньше. Если (r, s) это валидная подпись, то (r, n − s) тоже валидная подпись того же сообщения тем же ключом. Малигибельность (malleability) не даёт подделать смысл, но меняет байты подписи, а значит и хеш транзакции, в который подпись входит.

Для Bitcoin это была дыра: злоумышленник ловил чужую транзакцию в сети, переписывал s на n − s, и она вещалась с другим идентификатором. Исходная и переписанная делали одно и то же, но «исчезала» под новым хешем. На этом строили обвинения вокруг краха биржи Mt. Gox. Чинят это правилом low-s (BIP 146): из двух форм s и n − s ровно одна меньше n/2, и валидной считают только её, вторая отвергается на входе. Подпись становится канонической, у транзакции снова один хеш. EdDSA этой болезнью не страдает, но причина тоньше, чем часто рассказывают. Детерминированность там это свойство процедуры подписи (как именно выбирается nonce), а малигибельность закрывает проверяющий: RFC 8032 требует отвергать подпись, в которой скаляр s не меньше порядка группы L. У каждой подписи остаётся одна каноническая форма, и вторую валидную не сконструировать. По сути это то же правило low-s, только встроенное в стандарт с первого дня, а не прикрученное потом.