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

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

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

Итак, мы сейчас осознаем, как работает дискретная математика эллиптических кривых, и знаем, что в Биткойне употребляется вариант эллиптической криптографии 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). Ну, наконец! Столько вычислений, и все ради такого-то обычного «открытия».

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

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

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

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

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

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

  • Изберите некое целое k в границах от 1 до n-1.
  • Высчитайте точку (х, у) = k * G, используя скалярное умножение.
  • Отыскать r = х mod n. Если r = 0, вернитесь к шагу 1.
  • Отыскать s = (z + r * D) / k mod n. Если S = 0, вернитесь к шагу 1.
  • Пара (r, s) является нашей подписью
  • Напомним, в шаге 4, если придется прибегнуть к делению (что в настоящей жизни практически постоянно происходит), числитель следует помножить на оборотную знаменателю величину. А на исходном шаге 1 принципиально, чтоб k не повторялось в различных подписях, и чтоб его не могла угадать 3-я сторона. Другими словами 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).

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

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

    Ну отлично, подпись-то мы получили, что сейчас?

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

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

  • Удостоверьтесь, что r и s находятся в спектре от 1 до n-1.
  • Высчитайте w = s-1 mod n
  • Высчитайте u = z * w mod n
  • Высчитайте v = r * w mod n
  • Высчитайте точку (x, y) = uG + vQ
  • Удостоверьтесь, что 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 поочередных операций сложения к всего-то 6 операциям удвоения и двум — сложения. И это еще мы работаем на «игрушечных» примерах — представьте для себя число операций в «истинной» криптографии. Либо лучше даже не представляйте — не исключено, что просто свихнетесь.

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

    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

    Author: Anonim