Математика и алгоритмы биткоина.

[kzv]

Тут в теме Амаклина зашел разговор об эллиптической криптографии биткоина: как она устроена внутри. Было предложено вынести обсуждение в отдельный топик. Предлагаю обсудить именно в кодерах, потому что тут уместны ссылки на исходники и могут быть предложены альтернативные алгоритмы.
Итак начать предлагаю с поста Амаклина где он ответил на мой вопрос

Как тогда в тетрадке карандашем мне из приватного ключа "1" получить
1. публичный биткоин-ключ,

Это самое простое. Давайте вместе разбираться, оба научимся и другим дорогу покажем.

Мы рассматриваем так называемый secp256k1 криптографический стандарт.
В котором определен константный вектор G вот такой:

x= 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798
y= 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8


Почему именно этот набор цифр? Почему не какой-то другой? Об этом знает только NSA, по крайней
мере я не нашел (да особо и не искал) никаких публичных источников рассказывающих о том, почему
именно это число выбрано и чем оно так приглянулось. Вообще, такое у меня ощущение сложилось, что
этот вопрос все стараются обходить стороной, не связываться и ни дай Бог не привлекать внимания
органов власти и правопорядка США. Ну типа выбрали и выбрали, нам, холопам, не дано знать.

Соотношение между x и y этого вектора укладываются по идее (я не проверял) в уравнение эллиптической кривой
y² = x³+ax+b где a=0, b=7
Почему ноль и семь - я тоже не знаю. Операции сложения и умножения в этом уравнении - обычные арифметические
операции по модулю p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F
Вот тут могу ошибаться, кстати. поправьте если что. Может быть по модулю
n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141
Я так на память не помню, а за вас всю работу делать лень. Помогите мне хотя бы в этом вопросе, а?

Итак. Приватный ключ = 1, чтобы найти публичный ключ надо G умножить на 1
Умножение вектора на число - это не просто умножение на калькуляторе, это как-то хитро вычисляется,
сейчас пока пропустим это, важно что "умножить на один" - это как раз этот самый вектор и получится.

Итак. Публичный ключ для privkey=1 мы вычислили. Даже калькулятор не понадобился.
Его записывают, добавляя 04 (байт равный четырем) в начало. Результат в шестнадцатеричном виде:

04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8

Можете проверить на сайте bitaddress.org  

Наш разговор ушел далеко от изначальной темы. Я бы начал новый топик, но не знаю в каком разделе.
Никакой раздел для этого не подходит. Я в свое время предлагал "Хроники Биткойна", но идея угасла.

Итак, чтобы получить пару биткоин ключей (приватный + публичный), алгоритм будет следующий:
1. Придумываем любое 256-битное число. Это и будет приватный ключ.
2. Умножаем приватный ключ на магическую константу G которая на самом деле вектор с координатами
x= 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798
y= 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8


G*приватный_ключ = публичный ключ.

Теперь остается вопрос: как это умножение устроено?
Понятно, что
G*приватный_ключ = G+G+G+... (сложить столько раз, скольки равен приватный_ключ)

G*1 = G (по определению единицы)

Осталось понять: как вычислить хотя бы
G*2 = G+G

[amaclin1]

Теперь остается вопрос: как это умножение устроено?
Понятно, что
G*приватный_ключ = G+G+G+... (сложить столько раз, скольки равен приватный_ключ)

Ну, складывать по этой формуле мы затрахаемся будем пока солнце не погаснет.
Есть более эффективные процедуры умножения.
Запишем приватный ключ в двоичной системе счисления
Допустим, он равен ...000101011
То есть это G + 2G + 8G + 32G + ...
А это уже гораздо проще вычисляется

[kzv]

Вобщем-то я сам нагуглил ответ на вопрос.

При удвоении мы проводим прямую, касательную к данной эллиптической кривой в точке P, которая, согласно свойствам кривой, должна пересекать ее еще в одной точке R‘. Точка R, симметричная R‘ относительно оси X, и будет считаться точкой удвоения P. На графике это выглядит следующим образом

То есть чтобы найти G*2 надо провести касательную к G
Поскольку график функции известен, то уравнение касательной найдется элементарно

y = f'(x₀)(x-x₀) + f(x₀)

Где
f(x) = sqrt(x³ + 7)
x₀ = 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798

Правильно?

[amaclin1]

Правильно?

А трудно проверить самому что ли?
Пишешь программу, вычисляешь pubkey для privkey=2 и проверяешь совпал ли
результат с тем, который выдает bitaddress.org

(PS. Я не знаю правильно или нет. Я сам задавался этим вопросом, но сейчас не могу
найти тот топик, где мне объясняли. А я не выучил тот урок)

[kzv]

Правильно?

А трудно проверить самому что ли?
Пишешь программу, вычисляешь pubkey для privkey=2 и проверяешь совпал ли
результат с тем, который выдает bitaddress.org

(PS. Я не знаю правильно или нет. Я сам задавался этим вопросом, но сейчас не могу
найти тот топик, где мне объясняли. А я не выучил тот урок)

Это понятно. Напишу на досуге.
Меня сейчас математика заинтересовала...

Если уравнение касательной правильное, то приравняв его к уравнению кривой мы должны получить квадратное уравнение, корнями которого являются публичный и приватный ключи?

 (sqrt(x³ + 7))'|_x0(x-x₀) + sqrt(x₀³ + 7) = sqrt(x³ + 7)

[amaclin1]

Это понятно. Напишу на досуге.
Меня сейчас математика заинтересовала...

Я не знаю. Ты учитывай, что на всех картинках эллиптическую кривую рисуют вот такой "зюкой",
потом давай там линии рисовать обычные и пунктирные...
На самом деле (тм) так как мы уравнение решаем не в действительных числах, а в арифметике по модулю,
то график этого уравнения не вот такая аккуратная "зюка", а точки, как-то случайно разбросанные по плоскости.
По идее, там тоже есть понятие касательных, только оно в мозгу не укладывается.

[n00by]

Блин, ну вы даете.
Вот это должно снять почти все вопросы:
https://habr.com/post/335906/

[fxpc]

Возможно 4 глава прояснит ситуацию
https://github.com/bellaj/Blockchain/blob/6bffb47afae6a2a70903a26d215484cf8ff03859/ecdsa_bitcoin.pdf

[amaclin1]

Блин, ну вы даете.
Вот это должно снять почти все вопросы:
https://habr.com/post/335906/

Да мы нубланы в этом вопросе. Кто ж сомневается? Нельзя объять необъятное и впихнуть невпихуемое.
Читать научно-популярные тексты - это, конечно, здорово.
Но еще перипатетики поняли, что обсуждение даёт очень эффективные результаты.

[Blockchain.Artificial]

Тут в теме Амаклина зашел разговор об эллиптической криптографии биткоина: как она устроена внутри.

Ссылку на эту тему скиньте.

[kzv]

Блин, ну вы даете.
Вот это должно снять почти все вопросы:
https://habr.com/post/335906/

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

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

X_R = M² - 2 * X_P
Y_R = 3 * M * X_P - M³ - Y_P

где

M - это тангенс угла касательной к эллиптической кривой в точке с координатами (X_P, Y_P). То есть производная в этой точке от функции

f(x) = sqrt(x3 + 7)

В статье пишут (лень проверять), что она равна

M = 3 * X²_P / (2 * Y_P)

Продолжаю чтение... )

[Coin-1]

Как тогда в тетрадке карандашем мне из приватного ключа "1" получить
1. публичный биткоин-ключ,

Это самое простое. Давайте вместе разбираться, оба научимся и другим дорогу покажем.

Мы рассматриваем так называемый secp256k1 криптографический стандарт.
В котором определен константный вектор G вот такой:

x= 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798
y= 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8


Почему именно этот набор цифр? Почему не какой-то другой? Об этом знает только NSA, по крайней
мере я не нашел (да особо и не искал) никаких публичных источников рассказывающих о том, почему
именно это число выбрано и чем оно так приглянулось. Вообще, такое у меня ощущение сложилось, что
этот вопрос все стараются обходить стороной, не связываться и ни дай Бог не привлекать внимания
органов власти и правопорядка США. Ну типа выбрали и выбрали, нам, холопам, не дано знать.

Формулы для эллиптических кривых разрабатывают математики-криптографы. Вроде бы, буква "k" в названии "secp256k1" означает, что используется эллиптическая кривая Коблица. Наверно, поэтому Сатоши Накамото при создании Bitcoin выбрал именно эту эллиптическую кривую, а не, например, кривую "NIST P-256", скорее всего, имеющую бэкдор.

Вот хороший англоязычный интернет-ресурс, посвящённый асимметричной криптографии ECDSA:
http://safecurves.cr.yp.to/

Там перечислены и сравниваются характеристики известных элиптических кривых, широко используемых в криптографии.

[Destrodream]

Тут в теме Амаклина зашел разговор об эллиптической криптографии биткоина: как она устроена внутри.

Ссылку на эту тему скиньте.

https://bitcointalk.org/index.php?topic=2431229.220

[kzv]

Так, продолжим чтение статьи хабра...

Я нашел в статье, формулы сложения двух векторов (двух точек, как угодно) в случае когда эллитическая кривая на самом деле никакая не кривая, а набор точек. Как и следовало ожидать, эти формулы абсолютно идентичны обычным (когда кривая это кривая). Просто добавляется деление по модулю числа "p".

X_R= (M² - X_R - X_Q) mod p
Y_R = (Y_P + M * ( X_R - X_P ) ) mod p

Понятие "наклон" тут весьма условно, но формула для него тоже такая же как для настоящего геометрического тангенса касательной, только по модулю.

Если точки P и Q разные, то  M = ( Y_P - Y_Q ) * ( X_P - X_Q )^-1 mod p

Если точки P и Q совпадают, то M = 3*X²_P * (2 * Y_P)^-1 mod p

Итак, чтобы перемножить два числа, нужно провести несколько таких вот операций сложения. Например
G*P = G+G+G+G...[и так P раз]

Ну или число G представить как сумму степеней двойки (перевести в двоичный вид), перегруппировать и получить что-то типа
G*P = 1*2⁵¹²*P + 0*2⁵¹¹*P+...+1*2⁰P

В любом случае, чтобы понять как работает умножение, достаточно понять - как работает сложение.

Со сложением/умножением в общем виде разобрались, идем дальше. Пробуем разобраться конкретно с биткоином и его криптографией.

Внезапно оказывается, что когда от непрерывных уравнений кривых мы переходим к точкам, то этих точек оказывается конечное количество

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

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

Но дальнейшее чтение статьи меня разочаровало... Оказывается, что если умножать на одно и то же число, то результатов умножения будет сильно меньше чем полное количество точек.
На самом деле это очевидно с точки зрения элементарной математики, но блин когда думаешь о каких-то там группах с полями на десерт, то мозги начинают закипать ((
Я лучше на примере опишу, как я понял:
1. В ряду натуральных чисел от 1 до 100, этих чисел 100 штук.
2. Совершенно очевидно, что чисел кратных двойке в этом ряду 50, а чисел кратных 30 всего три и т.д.

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

Как мы знаем, чтобы получить приватный ключ биткоина, надо произвольное число умножить на константу G. Интересный вопрос: чему равен порядок подгруппы порожденной точкой G? Особенно интересен этот вопрос в свете того, что пока непонятно - кто и почему выбрал G таким, какое оно есть...

Продолжаю чтение...

[amaclin1]

Оказывается, что если умножать на одно и то же число, то результатов умножения будет сильно меньше чем полное количество точек.

Не, ну тут вы что-то намудрили.
Количество приватных ключей равно количеству публичных ключей
(про разные формы записи пока разговор не ведем)

[kzv]

Оказывается, что если умножать на одно и то же число, то результатов умножения будет сильно меньше чем полное количество точек.

Не, ну тут вы что-то намудрили.
Количество приватных ключей равно количеству публичных ключей
(про разные формы записи пока разговор не ведем)

Ну я только конспектирую тут эту статью https://habr.com/post/335906/

Сейчас дошел до главы "Скалярное умножение и циклические подгруппы". За что купил, как говорится...

А вот и порядок подгруппы (число возможных публичных ключей) там нашел. Глава "Эксперименты с ECDH"

0xffffffff ffffffff ffffffff fffffffe baaedce6 af48a03b bfd25e8c d0364141

Оказывается Сатоши числа эти не придумывал с потолка, а тупо скопипастил из либы OpenSSL.

[amaclin1]

Ну я только конспектирую тут эту статью https://habr.com/post/335906/
Сейчас дошел до главы "Скалярное умножение и циклические подгруппы". За что купил, как говорится...

Хорошо. Я ту статью не читал. Давайте на примере разберемся
Есть, допустим, группа - множество чисел от 0 до 6 или попросту радуга
{
  красный=0,
  оранжевый=1,
  желтый=2,
  зеленый=3,
  голубой=4,
  синий=5,
  филипетовый=6
}

Определим операцию умножения элемента на число. Для этого ⊕ определим как сложение по модулю
красный ⊕ красный = красный
оранжевый ⊕ желтый = зеленый
зеленый ⊕ синий = оранжевый
и так далее. Ну, а умножение элемента на число - через сложения.
Что такое синий * 3?
Это ( синий ⊕ синий ) ⊕ синий = зеленый ⊕ синий = оранжевый.

Но операцию ⊕ можно определить и иным способом. Как-нибудь изъебнуться с простыми
числами и всякими степенями. Особенно хорошо получается, когда в группе простое
количество элементов. Семь - как раз простое.

[kzv]

Ну я только конспектирую тут эту статью https://habr.com/post/335906/
Сейчас дошел до главы "Скалярное умножение и циклические подгруппы". За что купил, как говорится...

Хорошо. Я ту статью не читал. Давайте на примере разберемся
Есть, допустим, группа - множество чисел от 0 до 6 или попросту радуга
{
  красный=0,
  оранжевый=1,
  желтый=2,
  зеленый=3,
  голубой=4,
  синий=5,
  филипетовый=6
}

Определим операцию умножения элемента на число. Для этого ⊕ определим как сложение по модулю
красный ⊕ красный = красный
оранжевый ⊕ желтый = зеленый
зеленый ⊕ синий = оранжевый
и так далее. Ну, а умножение элемента на число - через сложения.
Что такое синий * 3?
Это ( синий ⊕ синий ) ⊕ синий = зеленый ⊕ синий = оранжевый.

Но операцию ⊕ можно определить и иным способом. Как-нибудь изъебнуться с простыми
числами и всякими степенями. Особенно хорошо получается, когда в группе простое
количество элементов. Семь - как раз простое.

Надо сложение умудриться таким образом определить, чтобы при умножении всегда выполнялось условие:

если A*B = C то A = C * B^-1 и B = C * A^-1

В вашем примере надо определить сумму так, чтобы при умножении

Если 2*4 = X то 2 = X*4^-1 и 4 = X*2^-1

Соответственно нужно доопределить в целых числах от 0 до 6, чему равны эти числа в минус первой степени.

Тут проще будет на словах: договоримся, что если при умножении A на B получается число больше 6, то ответом будет наименьшее из чисел A или B.
Тогда

1 * 4 = 4
2 * 4 = 2+2+2+2 = 2
3 * 4 = 3+3+3+3 = 3
4 * 4 = 4
5 * 4 = 4
6 * 4 = 4

Понятно, что можно определить умножение и по другому, но главное должно оставаться условие: ответ после умножения должен быть кратным одному из множителей.

[Destrodream]

Ну вообще для разных математических абстракций - понятия "сложение", "умножение" и прочие очень разные.

Например сложение целых чисел - мы все знаем. Оно обладает свойством коммутативности, ассоциативности и подчиняется правилу сложения.

Сложение векторов в пространстве - уже сильно отличается от сложения целых чисел, хотя так же коммутативно и ассоциативно (т.е. фундаментально без разницы что с чем складывать и в каком порядке), однако правила сложения уже несколько отличаются, т.к. вектор описывается не одним числом а набором чисел (в зависимости от размерности пространства). На плоскости вектор можно описать двумя числами - координатами конца стрелочки протянутой из нуля. Например у вектора тянущегося под 45% направо вверх будет запись (1,1) или (2,2) и т.п. Умножение вектора на число - это помножение всех "координат", его описывающих на число (если это нарисовать, то это будет выглядеть как удлиннение стрелочки без изменения направления). Умножив вектор (1,1) на 2 получим вектор (2,2).


Сложение в применении к элептической криваой определяется совсем иначе - а именно как поиск решения системы уравнений и инвертирования его знака по оси Y.  Одно уравнение описывает кривую, другое - прямую, проведенные через две точки - но это вы уже видимо поняли.
Складывать, разумеется можно только те точки, которые УЖЕ находятся на кривой (т.е. являются решением уравнения кривой при фиксации X или Y в уравнении кривой. Сложить точки с координатами (1,1) и (0,1) на криваой не получится, т.к. они не лежат на кривой ).

Возникает резонный вопрос - что делать в тех случаях, когда точку надо сложить с самой собой, чтобы через такое сложение можно определить умножение? Сложение точки с самой собой предполагает такую прямую, которая проходит через эту едиственную точку на бесконечно малом участке кривой, то есть - касательную. А уравнение касательной, как известно легко вычисляется, расчетом производной. То есть если мы имеем произвольную точку на кривой, мы считаем ПРОИЗВОДНУЮ элиптического уравнения в этой точке (производная - это уравнение прямой). Потом мы решаем систему уравнений этой прямой и уравнения кривой, инвертируем по знаку и получаем ту точку, которая будет "суммой" A+A или иными словами A*2. Вот так определяется умножение. Чтобы посчитать 3*А - можно прибавить к 2A еще один A.

Как видите, если вчитаться в этот абзац "умножение" на кривой это адский гемморой, но он несколько облегчается, ели организованно использовать память и свести умножение к сложению. Например чтобы посчитать 9A можно посчитать 2A+2A = 4A, потом посчитать 4A+4A = 8A а потом прибавить 1А.

Если А это произвольное число длинной в 256 бит (~10^77), то, чтобы посчитать его произведение на любое другое число (НА КРИВОЙ) потребуется операций сложения не более чем 510. (Если очень надо - можно это доказать).

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

Теперь о криптографии. Допустим есть A - это старотовая точка. И есть B - множитель. Есть так же произведение A * B = C.
Если я вам дам С, то сможете ли вы узнать сколько раз B сложили с самим собой (A), чтобы получить С? Оказывается, что нет, потому что не определено (во всяком случае на данный момент) операции деления и единственная опция поиска A это тупо складывать B с самим собой в надежде получить С.

Ну вот тут мы и подходим к шифрованию.
в моем примере A - это ваш приватный ключ, С - это ваш публичный ключ а B - это стартовая точка на кривой, по которой вы начинаете свое путешествие из точки A в точку C, складывая B c самим собой по правилу сложения которое я описал выше.  

Надо глубже, или так понятно?

[kzv]

Надо глубже, или так понятно?

Честно сказать, я не понял к кому вы обращаетесь своим длинным постом на какую-то отвлеченную тему.
Если можно, давайте конкретно, у меня остались следующие вопросы:
1. Как посчитать порядок группы эллиптической кривой над конечным полем?
2. Почему порядок подгруппы в secp256k1 выбран числом 0xffffffff ffffffff ffffffff fffffffe baaedce6 af48a03b bfd25e8c d0364141 ? Кто его придумал?