Сегодня мы с вами поговорим о криптографии эллиптической кривой (elliptic-curve cryptography, ECC) и конкретно о том, как она используется в Ethereum.
Это запись по следам видеоурока, который можно найти на YouTube:
Эта запись также доступна в канале Telegram “DEV: Рубиновые тона”, а обсудить же эту тему можно в нашем чате Telegram.
Зачем ECC нужна в Ethereum?
Первый вопрос, который может возникнуть у пытливого читателя: зачем вообще всё это надо? Что ж, это весьма логичный вопрос! Дело в том, что (применительно к Ethereum) любая транзакция должна быть подписана пользователем. Мы должны подтвердить, что, условно говоря, вот этот денежный перевод со своего кошелька делаю действительно я, а не какой-то неизвестный товарищ. Если говорить из общих соображений, то подпись транзакции подразумевает высчитывание её хэша и последующее шифрование получившегося хэша с помощью закрытого ключа (private key) пользователя. Закрытый ключ, как подсказывает название, известен лишь самому юзеру, и в общем целом это называется “ассиметричное шифрование”, то есть шифруем одним, дешифруем другим.
Принимающая сторона берёт транзакцию и тоже высчитывает её хэш, после чего расшифровывает присланную подпись. Расшифровка происходит с помощью открытого ключа пользователя, который может быть известен кому угодно. Если хэши совпали, то всё хорошо, если нет — где-то есть проблема. Кроме того, мы знаем, что в том же Solidity есть функция ecrecover, которая может сказать, кто именно подписал сообщение.
Другой пример — это использование ассиметричного шифрования для так называемого handshake, когда две стороны вырабатывают общий ключ. Этот ключ используется во время обмена данными (например, по https). Про это мы говорили в лекции по RSA.
Из всего этого мы делаем простой вывод: наличие открытого и закрытого ключа принципиально важно для криптовалют и не только. И вот тут-то мы задаёмся другим вопросом: а откуда эти ключи взять и как сделать их надёжными? В частности, нам нужно, чтобы на основе известного закрытого ключа можно было легко посчитать открытый, но ни в коем случае не наоборот, иначе закрытые ключи пользователей будут скомпрометированы! Собственно говоря, над этой проблемой, в том числе, и работают криптографы. Один вариант — использовать старый добрый RSA, где ключами выступают обычные числа (только очень большие). Но мир не стоит на месте, и поэтому был придуман другой подход, который и основывается на эллиптической кривой. Он быстрее, надёжнее и менее ресурсозатратен, что особенно важно для маломощных устройств.
Какие ещё кривые?..
Таким образом, мы поняли, зачем вообще этот ECC нужен: мы можем использовать некие эллиптические кривые, чтобы создавать надёжные ключи, которые затем используются для шифрования и дешифрования. Но что же это за кривые такие? В общем случае у таких кривых довольно длинное уравнение, но в крипте мы работаем с кривыми Вейерштрасса, которые попроще. Описываются они следующим уравнением: y ** 2 = x ** 3 + a * x + b.
** — это операция возведения в степень. a и b — это параметры кривой, которые подбираются криптографами и могут варьироваться в зависимости от стандарта. Важно то, что эти параметры известны абсолютно всем, они не являются секретными и описаны прямо в стандарте. К примеру, для Bitcoin и Ethereum используется кривая под названием secp256k1, параметры которой равны 0 и 7 соответственно, то есть уравнение же превращается в y ** 2 = x ** 3 + 7.
Как выглядят эллиптические кривые и как меняются в зависимости от параметров, можно посмотреть вот на этой визуализации. В частности, можно видеть, что эта кривая симметрична относительно оси Х, что довольно важно (есть у неё и ряд других свойств, о которых позже).
Также следует отметить, что эти кривые строятся на конечном поле Fp (оно называется поле Галуа), где p — это простое число. Если говорить простым языком, то кривая не бесконечна, а лежит в квадрате размером p x p. В стандартах, используемых в реальных системах, число p очень большое. К примеру, для кривой secp256k1 значение p равно 2 ** 190 - 1, и это совершенно гигантское число. Это нужно для того, чтобы мы могли сгенерировать очень много потенциальных ключевых пар. Поэтому фактически мы можем сказать, что наше уравнение трансформируется в y ** 2 = x ** 3 + 7 (mod p), где mod — остаток от деления.
Ещё один важный момент заключается в том, что в ECC мы работаем только с целыми числами, поэтому на нашей кривой нас интересуют только точки, чьи координаты x и y целые. Кстати, проверить, принадлежит ли точка кривой можно очень легко: для этого нужно решить уравнение x ** 3 + 7 - y ** 2 = 0 (опять таки с mod p). Если равенство нулю есть, то точка лежит на кривой.
Получение открытого ключа на кривой
На поле Галуа, где лежит кривая, можно выполнять математические операции над точками: так, две произвольные точки можно складывать и результатом будет другая точка на кривой. Это, на самом деле, принципиально важный момент, связанный с получением открытого ключа. Как именно сложение происходит визуально, можно увидеть вот на этом сервисе. В частности, на нём вы увидите две точки (оранжевую и синюю), через которые проведена прямая. Третья точка чёрного цвета, где эта прямая пересекает кривую, и есть результат сложения. Только заметьте, что эта точка инвертирована относительно оси X и финальный результат оказывается по другую сторону.
Какие используются формулы для сложения точек, вы можете посмотреть в умных книжках, но нас это не сильно интересует. Важно то, что этот подход мы можем использовать для получения открытого ключа.
Алгоритм выглядит следующим образом:
На кривой задаётся изначальная точка
G, которая называется генераторной. Про неё ещё потом скажу пару слов, но важно то, что для конкретного алгоритма эта точка известна абсолютно всем: к примеру, дляsecp256k1её координаты равны02 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798. Вы можете спросить, почему тут только одна координата, хотя мы работаем с осями X и Y, но про это будет позднее. Пока просто поверьте, что это координаты точки по двум осям, только в сжатом виде.Мы можем сложить эту точку саму с собой: как ни странно, это тоже допустимо. В результате мы получим новую точку
A, которую можно записать простым выражениемA = G + G. Ну, а коль скоро у нас есть сложение, то и умножение мы тоже можем сделать, то естьA = 2 * G. Кстати, на мой скромный взгляд, во многих руководствах вот этому моменту вообще не уделяется внимания. Часто пишут в духе “возьмём две точки, проведём прямую, получим третью”. Но, пардон, изначально-то генераторная точка одна — откуда тогда взялась ещё и вторая?Затем мы можем посчитать точку
Bпутём сложенияGс уже посчитанной точкойA.B = G + A = G + 2 * G = 3 * G.Guess what: мы можем продолжать эту операцию сколько угодно раз. Проделайте эти вычисления самостоятельно вот на этом онлайн-калькуляторе, введя параметры
a = 0,b = 7,p = 17(совсем крошечное поле для простоты, но помните, что в реальной жизни оно гигантское). Затем просто задайте координаты для обеих точек в(15, 13)(в калькуляторе эти точки названыPиQ, но суть не меняется), и вы увидите, что результатом сложения выступит точка(2, 10). Потом можете повторить сложение(15, 13)и(2, 10), и так далее.
Вспоминается старый анекдот: куда мы попадём, если будем долго бурить землю на экваторе? Видимо, в сумасшедший дом. Тут можно задать тот же вопрос: где мы окажемся, если будем повторять это умножение и, самое главное, нафига вообще это нужно?
Ответ на первый вопрос очень простой: в конце концов мы окажемся в какой-то точке на кривой, обозначенной
P, у которой также есть координатыxиy, причём выражены они тоже целыми числами.Ответ на второй вопрос тоже не сильно сложный: координаты финальной точки
Pбудут выступать открытым ключом. Да, это два числа, а ключ вроде как один, но мы можем просто слепить их воедино. К примеру, для Ethereum каждая координата имеет размерность 256 бит, значит две координаты дают размерность 512 бит — это и есть размер открытого ключа в несжатом виде.
Ладно, а где тогда закрытый ключ? А закрытый ключ, дорогие друзья, — это то число, на которое мы умножаем G. Скажем, в примере выше у нас получилось, что B = 3 * G, значит закрытый ключ k равен 3. Естественно, это очень простой пример, а в реальности же закрытые ключи лежат в диапазоне от 1 до 2 ** 256 - 1, то есть опять же числа нереально здоровые. Закрытый ключ можно получить хотя бы из мнемонической фразы, которая пропущена через тот же keccak256. Так как этот алгоритм хэширования гарантирует, что выходное шестнадцатиричное число будет меньше, чем 2 ** 256, то нас это прекрасным образом устраивает (хотя схемы могут быть сложнее).
Закрытый и открытый ключи
А главная замута здесь вот в чём. Посчитать открытый ключ по формуле P = k * G — это достаточно простая и быстрая операция, которая выполняется за время log2(k). Но вот сделать обратную операцию и узнать закрытый ключ по известному открытому, то есть сделать что-то вроде k = P / G — это задача на данный момент практически невыполнимая, если, конечно, используются достаточно большие числа. Эта проблема называется Elliptic Curve Discrete Logarithm Problem (ECDLP); эффективного решения она не имеет, что гарантирует надёжность алгоритма. Опять же, говоря простым языком, даже если мы знаем начальную и финальную точку на кривой, мы в душе не знаем, сколько потребовалось “прыжков” для того, чтобы в этой финальной точке оказаться.
Подгруппы точек на кривой
Все точки на эллиптической кривой можно разделить на так называемые циклические подгруппы. В разных вариантах кривой (эти варианты зависят от изначальных параметров) может быть разное количество подгрупп, которое выражается числом h. Это число называется ко-фактор (cofactor). Например, для secp256k1 кофактор равен 1, то есть все точки лежат в одной подгруппе.
Общее количество вообще всех точек во всех подгруппах называется порядок кривой и выражается числом n. Для уже известной нам кривой secp256k1 значение n равно (внимание) FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141 — это в виде hexadecimal. То есть вот столько там есть возможных точек и, соответственно, ключей.
Почему важны все эти кофакторы? Потому что генераторная точка G может сгенерировать любую другую точку в рамках своей подгруппы, если сделать достаточно большое количество “прыжков” (то есть умножений). Частным случаем является умножение на 0 — там получается бесконечность и такая точка нам, конечно, не подходит. Таким образом, для кривой secp256k1 мы можем попасть в каждую другую точку из генераторной. Собственно, G выбрана умными людьми специально, чтобы из неё можно было попасть в наибольшее количество других точек. Именно поэтому следует использовать уже готовые и протестированные кривые, а не придумывать собственную.
Сжатие координат
И последний момент, связанный со сжатием координат (x, y) для наших открытых ключей. Дело в том, что у кривой Вейерштрасса есть другое любопытное свойство: на каждую координату там приходится максимум две точки, что проиллюстрировано на этом рисунке.
Больше того, выходит, что если есть две точки с одинаковыми координатами по оси X, то по для одной точки по Y будет чётная координата, а для другой — нечётная. Неплохо, да? Это значит, что для каждой точки мы можем оставить только её координату по X, а Y выразить как чёт-нечёт, то есть занять фактически лишь один бит. Таким образом, мы можем сжать 512-битную пару (x, y) до 257 бит!
“Расжать” координату по Y можно по формулам y1 = mod_sqrt(x ** 3 + ax + b, p) и y2 = p - mod_sqrt(x ** 3 + ax + b, p), где mod_sqrt — это квадратный корень с операцией модуля, который считается по алгоритму Тонелли-Шенкса, но обычно это не столь важно для разработчиков в Ethereum. Получив две координаты по Y мы просто выбираем либо чётную, либо нечётную. Хитро, что и говорить.
Заключение
Подведём итог. Для того, чтобы посчитать открытый ключ с помощью ECC, нам требуется:
Выбрать кривую, например,
secp256k1. Выбранная кривая влияет на параметрыaиb, у неё есть известная генераторная точка, а также известный порядок и кофактор.Каким-то образом создать закрытый ключ
k(выбрать случайное число, использовать мнемоническую фразу или как-то ещё).Умножить
Gнаkи получить финальные координаты точкиP, открытого ключа.
В Ethereum, кстати, потом происходит интересная штука, так как полученный открытый ключ хэшируется, а последние 20 байт (160 бит) этого хэша становятся адресом аккаунта, которому этот публичный ключ соответствует. Так как хэш представляет собой числа hexadecimal, то и адрес тоже является шестнадцатиричным числом. А это значит, что мы можем превратить его в обычное число uint256, если вдруг такая необходимость есть: uint256(uint160(some_address)). В других системах может быть такое, что сам публичный ключ и выступает адресом.