Сегодня мы с вами поговорим о криптографии эллиптической кривой (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))
. В других системах может быть такое, что сам публичный ключ и выступает адресом.