Математика Биткойна: Практика

В предыдущей статье мы рассмотрели теоретические основы эллиптической криптографии и поняли, как она работает в принципе. Теперь осталось только применить эти знания на практике: давайте разберемся, как это используется в биткойн-протоколе.

Секретные ключи и открытые ключи

Итак, мы теперь понимаем, как работает дискретная математика эллиптических кривых, и знаем, что в Биткойне используется вариант эллиптической криптографии secp256k1. Teперь можем разобраться с тем, откуда вообще берутся секретные и открытые ключи и как они вообще связаны друг с другом и с биткойн-адресами. Если коротко, в ECDSA секретный ключ — это просто случайное число между 1 и значением порядка. Открытый же ключ получается из секретного при помощи операции скалярного умножения базовой точки на значение секретного ключа. В виде уравнения:

Открытый ключ = секретный ключ * базовая точка

Это показывает, что максимально возможное количество секретных ключей (и, следовательно, биткойн-адресов) — конечно, и равно порядку. Так стало быть, на всех их может не хватить?! Не совсем так: вспомним, что порядок — это действительно большое число — оно невообразимо больше, чем общее число элементарных частиц во всей Вселенной.

Как работает это уравнение в реальности? Вычисление открытого ключа разбивается на ряд операций удвоения точек и сложения точек, начиная с базовой точки.

Напомним, мы работаем с дискретной математикой эллиптических кривых, где сложение точек p + q, чтобы найти их сумму r определяется покомпонентно следующим образом:

c = (qy — py) / (qx — px)
rx = c2 — px — qx
ry = c (px — rx) — py

A операция «удвоения» точки р выглядит следующим образом:

c = (3px2 + a) / 2py
rx = c2 — 2px
ry = c (px — rx) — py

Объем вычислений на реальном примере был бы нереально сложным, но мы можем попробовать на примере с небольшими числами, чтобы увидеть, как это работает. Итак, возьмем уравнение кривой Биткойна, но вместо нереально огромных значений порядка, модуля и базовой точки, которые применяются в Биткойне, будем использовать маленькие числа.

Реальный пример из «игрушечной» криптографии

Итак, для удобства создадим себе собственную мини-биткойн-криптографию, например, такую:

Уравнение кривой: y2 = x3 + 7
Модуль: 67
Базовая точка: (2, 22)
Порядок: 79

Чтобы показать, что мы не лыком шиты, выберем себе «абсолютно случайный» секретный ключ (из 79 возможных). Ну, пусть это будет 2.

Давайте найдем к нему публичный ключ. Так как мы выбрали простейший «секретный» ключ со значением = 2, нам для этого потребуется лишь одна операция удвоения базовой точки. Очень удобно. Расчет выглядит следующим образом:

c = (3 * 22 + 0) / (2 * 22) mod 67
c = (3 * 4) / (44) mod 67
c = 12 / 44 mod 67

Здесь мы должны провести небольшой трюк, который ранее не объяснялся. Как нам выполнить операцию деления в контексте конечного поля, где результат должен быть целочисленным? Для этого мы должны умножить 12 на величину, обратную к 44. Находить обратную величину в контексте конечных полей не так просто (если хотите изучить этот вопрос подробнее, смотрите здесь), поэтому пока что вам придется поверить мне на слово, что:

44-1 = 32

Далее все довольно просто:

c = 12 * 32 mod 67
c = 384 mod 67
c = 49

rx = (492 — 2 * 2) mod 67
rx = (2401 — 4) mod 67
rx = 2397 mod 67
rx = 52

ry = (49 * (2 — 52) — 22) mod 67
ry = (49 * (-50) — 22) mod 67
ry = (-2450 — 22) mod 67
ry = -2472 mod 67
ry = 7

Итак, мы определили, что для секретного ключа 2 публичным ключом будет точка (52, 7). Ну, наконец-то! Столько вычислений, и все ради такого-то простого «открытия».

И при всем при том, эта операция — переход от секретного к публичному ключу — по сложности просто ничто по сравнению с попыткой работать в обратном направлении: вывести секретный ключ из публичного ключа. Если для нашего «игрушечного» примера, мы, поднатужившись, еще можем это сделать, в случае с реальной криптографией нас ждет облом. Хотя получить секретный ключ из публичного теоретически и возможно, это является вычислительно невозможным из-за огромных чисел-параметров, используемых в реальной эллиптической криптографии.

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

Как и секретный ключ, публичный ключ тоже, как правило, представляется в виде шестнадцатеричного числа. Погодите-ка, скажете вы — мы ведь только что узнали, что этот ключ — точка, а не скаляр? Как же его представить в виде одного числа? В несжатом формате публичный ключ — это просто записанные подряд два 256-битных числа, являющиеся его х и у координатами. Мы также можем воспользоваться свойством симметрии эллиптической кривой для получения сжатого публичного ключа — в этом формате он содержит лишь значение координаты х и информацию о том, на какой половине кривой находится точка — на нижней, или на верхней. Из этой информации мы можем восстановить обе координаты, подставив в уравнение кривой.

Подписываем данные секретным ключом

Теперь, когда у нас есть своя собственная пара секретный/публичный ключ (пусть и в игрушечном микро-пространстве эллиптической криптографии), давайте уже наконец подписывать какие-нибудь данные!

Эти данные могут быть любой длины. Обычно первым шагом является хэширование данных, чтобы получить уникальное число, содержащее такое же количество битов (256), как и порядок кривой. Здесь, для простоты, мы пропустим шаг хеширования и сделаем вид, что нам нужно просто подписать набор данных z. Обозначим через G базовую точку, через n — порядок, а d — закрытый ключ. Алгоритм создания подписи выглядит следующим образом:

1. Выберите некоторое целое k в пределах от 1 до n-1.
2. Рассчитайте точку (х, у) = k * G, используя скалярное умножение.
3. Найти r = х mod n. Если r = 0, вернитесь к шагу 1.
4. Найти s = (z + r * D) / k mod n. Если S = 0, вернитесь к шагу 1.
5. Пара (r, s) является нашей подписью

Напомним, в шаге 4, если придется прибегнуть к делению (что в реальной жизни почти всегда происходит), числитель следует умножить на обратную знаменателю величину. А на начальном шаге 1 важно, чтобы k не повторялось в разных подписях, и чтобы его не могла угадать третья сторона. То есть k должен быть либо случайным либо созданным детерминированным процессом, который хранится в тайне от третьих лиц. В противном случае можно было бы вычислить секретный ключ, начиная с шага 4, так как s, z, r, k и n всем известны.

Давайте выберем в качестве наших данных число 17 и подпишем его нашим супер-секретным ключом 2. Итак:

z = 17 (данные)
n = 79 (порядок)
G = (2, 22) (базовая точка)
d = 2 (секретный ключ)

1. Выберем случайное число:

k = rand(1, n — 1)
k = rand(1, 79 — 1)
k = 3 (что, это действительно случайное число!? Ну ладно, ладно, скажем что это тоже «игрушечный» рэндом!)

2. Рассчитаем точку.

Это делается таким же образом, как ранее при вычислении публичного ключа — для краткости опустим подробную арифметику сложения и удвоения.

(x, y) = 3G
(x, y) = G + 2G
(x, y) = (2, 22) + (52, 7)
(x, y) = (62, 63)
x = 62
y = 63

3. Находим r :

r = x mod n
r = 62 mod 79
r = 62

4. Находим s :

s = (z + r * d) / k mod n
s = (17 + 62 * 2) / 3 mod 79
s = (17 + 124) / 3 mod 79
s = 141 / 3 mod 79
s = 47 mod 79
s = 47

Обратите внимание, что выше мы смогли разделить на 3, так как результат был целым числом. В реальной жизни придется искать обратную величину и т.п. – тяжелая вычислительная рутина.

5. Получили подпись:

Нашей подписью является пара (r, s) = (62, 47).

Как и в случае секретных и публичных ключей, эта подпись также обычно представляется в виде шестнадцатеричной строки.

Проверка подписи публичным ключом

Ну хорошо, подпись-то мы получили, что теперь?

Теперь у нас есть данные и наша подпись этих данных. Третья сторона, которая знает наш публичный ключ, может получить наши данные и подпись, и убедиться, что именно мы являемся отправителями. Давайте посмотрим, как это работает.

Обозначив наш открытый ключ Q, шаги для проверки подписи будут следующими:

1. Убедитесь, что r и s находятся в диапазоне от 1 до n-1.
2. Рассчитайте w = s-1 mod n
3. Рассчитайте u = z * w mod n
4. Рассчитайте v = r * w mod n
5. Рассчитайте точку (x, y) = uG + vQ
6. Убедитесь, что r = x mod n. Если это не так, то подпись недействительна.

Почему эти шаги работают? Мы опускаем здесь формальное доказательство, но вы можете прочитать подробности здесь. Давайте просто прогоним алгоритм вручную и посмотрим, что выйдет. Напомним, наши переменные:

z = 17 (данные)
(r, s) = (62, 47) (подпись)
n = 79 (порядок)
G = (2, 22) (базовая точка)
Q = (52, 7) (публичный ключ)

1. Убедимся, что что r и s находятся в диапазоне от 1 до n-1.

r: 1 <= 62 < 79
s: 1 <= 47 < 79

Да, верно.

2. Рассчитаем w :

w = s-1 mod n
w = 47-1 mod 79
w = 37

3. Рассчитаем u :

u = zw mod n
u = 17 * 37 mod 79
u = 629 mod 79
u = 76

4. Рассчитаем v :

v = rw mod n
v = 62 * 37 mod 79
v = 2294 mod 79
v = 3

5. Рассчитаем точку (х, у):

(x, y) = uG + vQ

Это самая веселая часть. Давайте разберем операции удвоения и сложения в uG и vQ отдельно.

uG = 76G
uG = 2(38G)
uG = 2( 2(19G) )
uG = 2( 2(G + 18G) )
uG = 2( 2(G + 2(9G) ) )
uG = 2( 2(G + 2(G + 8G) ) )
uG = 2( 2(G + 2(G + 2(4G) ) ) )
uG = 2( 2(G + 2(G + 2( 2(2G) ) ) ) )

Зацените: с помощью ловкой группировки, мы сводим 75 последовательных операций сложения к всего-то шести операциям удвоения и двум — сложения. И это еще мы работаем на «игрушечных» примерах — представьте себе число операций в «настоящей» криптографии. Или лучше даже не представляйте — не исключено, что просто свихнетесь.

Продолжаем наше захватывающее представление:

uG = 2( 2(G + 2(G + 2( 2( 2(2, 22) ) ) ) ) )
uG = 2( 2(G + 2(G + 2( 2(52, 7) ) ) ) )
uG = 2( 2(G + 2(G + 2(25, 17)  ) ) )
uG = 2( 2(G + 2( (2, 22) + (21, 42) ) ) )
uG = 2( 2(G + 2(13, 44) ) )
uG = 2( 2( (2, 22) + (66, 26) ) )
uG = 2( 2(38, 26) )
uG = 2(27, 40)
uG = (62, 4)

И теперь, все то же для vQ:

vQ = 3Q
vQ = Q + 2Q
vQ = Q + 2(52, 7)
vQ = (52, 7) + (25, 17)
vQ = (11, 20)

Посчитав, складываем их вместе:

(x, y) = uG + vQ
(x, y) = (62, 4) + (11, 20)
(x, y) = (62, 63)

Уфф, кажется закончили. Надеюсь, нигде не ошиблись. Сразу видно, что больше всего работы именно на шаге 5. Осталась уже просто ерунда.

6. Наконец, убедимся, что r = x mod n

r = x mod n
62 = 62 mod 79
62 = 62

Ура, наша подпись действительна!

Заключение

Для тех из вас, кто испугался всех этих страшных уравнений в тексте, и быстренько прокрутил статью до конца, что же мы только что узнали?

Мы выработали некоторую интуицию относительно взаимосвязей, которые существуют между публичными и секретными ключами. Мы увидели, как даже на простейших, «игрушечных» примерах, математика создания эллиптических подписей и их проверки быстро усложняется. Теперь мы можем по достоинству оценить огромную сложность вычислений, которые возникают, когда параметры являются огромными 256-битными числами. Мы увидели, как хитрое применение простых математических процедур создает «односторонние» функции, необходимые для сохранения информационной асимметрии. Именно эта асимметрия позволяет нам доказать права собственности на биткойны, не раскрывая при этом своих секретных ключей.

Если вы прошли через это практическое занятие, то обрели некоторую уверенность в надежности системы — при условии, что знание наших секретных ключей надежно защищено от посторонних.

Как минимум, теперь можно понять, почему так часто повторяется, что права собственности на биткойны «гарантированы математикой».

Если вы хорошо проштудировали эти примеры, то они должны дать вам достаточно уверенности, чтобы сделать следующий шаг и попробовать сделать подобные расчеты самостоятельно (что касается модульной арифметики, то этот калькулятор сильно упрощает жизнь). Мы обнаружили, что прохождение шагов подписания и проверки данных вручную обеспечивает более глубокое понимание той криптографии, которая превращает Биткойн в уникальную форму собственности, непохожую на все, что было до него.

: Coindesk

Aвтор: Eric Rykwalder

Источник: bitnovosti.com