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

[Destrodream]

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

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

Группа это пространство чего-либо (например пространство векторов, или точек или слонов), для которых вы определяете операцию сложения. В применении к элептической кривой группа - это множество наборов из трех точек, лежащих на прямой в точке пересечения этой прямой с кривой. "Сумма" этих точек равна нулю (это определение их сложения, которое обладает всеми свойствами сложения). Если взять все-все точки кривой - группа получится бесконечной (т.к. на ней бесконечное кол-во троек точек дающих по определению сложения в группе - ноль. У бесконечных групп - порядок группы не определен. Но мы можем взять не все точки кривой, а только некоторое конечное количество точек. Тогда порядок группы станет конечным и будет определяться правилом выбора тех точек которые мы выберем для построения группы. То есть мы берем из всех "троеточий" только некоторые, которые удовлетворяют конкретному правилу (например берем только троекточие от пересечения с осью Х). Тогда наша группа будет состоять из одного троеточия и ее порядок будет равен 1.

О том как получить порядок группы над конечном полем я напишу чуть позже (сначала разберемся с тем что такое поле). Но сразу спойлер - почему Base Point в ненаглядном взяли такой какой взяли - я не скажу. Примерно вот так это мотивирует светоч:

https://bitcointalk.org/index.php?topic=553091.msg6020830#msg6020830

А сейчас - спать пора.

[Destrodream]

Короткий ответ:

Почему порядок подгруппы в secp256k1 выбран числом 0xffffffff ffffffff ffffffff fffffffe baaedce6 af48a03b bfd25e8c d0364141 ? Кто его придумал?

1. Множитель конечной группы P выбран последним простым числом меньше чем 2^256  :

p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F (115792089237316195423570985008687907853269984665640564039457584007908834671663)

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

ffffffff ffffffff ffffffff fffffffe baaedce6 af48a03b bfd25e8c d0364141  (115792089237316195423570985008687907852837564279074904382605163141518161494337)

тоже простое число, но чутка поменьше, потому что у кривой "откусили" начало.



Этот порядок - определяет кол-во точек на исходной элептической кривой.
Выбран он так, чтобы длинна ключей не превышала 512 бит (т.е. сумма любых двух точке на кривой не вылезет за 512 бит) и при этом кол-во точек было очень большим.

Как посчитать порядок группы эллиптической кривой над конечным полем?

2. Наверное логичнее задавать порядок группы изначально чем его считать. Если посмотреть на уравнение которым описывается кривая - оно содержит в себе mod P, вот P - это и есть простое число, которое определяет кол-во точек и порядок группы. Если группу урезать, то кол-во точек уменьшится.

[amaclin1]

потому что у кривой "откусили" начало.

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

[Destrodream]

потому что у кривой "откусили" начало.

А "кривая" на самом деле не кривая (тропинка в лесу, берёза на склоне, итд), а как-то
рассыпанный по плоскости горох?

Ну вообще-то это кривая. Ее визуализация на плоскости - выглядит как горох, но тем не менее это кривая. Просто мы начинаем пытаться понять с рассмотрения непрерывной кривой, а потом ее дескретизируем оператором mod P т.к. вычисления все наши ограничены целыми числами.

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

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

Разумным ограничением будет переопределение кривой не в евклидовом пространстве, а в простренстве конечного числа целых чисел, подчиняющихся какому-либо правилу, которое не позволяет координатам ни при каких условиях превысить заданной границы (чтобы длина нашего публичного ключа не росла бесконечно). Это легко сделать, если во первых ограничить себя только целыми числами и вспомнить про операцию mod (остаток от деления) на какое-нибудь простое число. Почему простое? Потому что использование простого числа дает возможность определить операцию деления через умножение, поскольку результатов деления может быть ровно два - 1 и само число). Итак уравнение элептической кривой (которое записано как Y^2=X3+AX+B) мы перепишем в форме:
Y^2 mod P = (X^3 + AX + B) mod P

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

Решения такого уравнения, например, для P = 3, А = 0 B =0  будут выглядеть примерно так: (1,1), (2,2), (3,0) и потом, если подставлять X>3, точки на плоскости начинают повторяться, всегда внутри квадрата 0-3 - советую посчитать решения руками для разных наборов P,A и B и нарисовать в тетрадке, чтобы понять, что из-за целочисленного деления - не важно какое х и y я буду брать - точек строго ограниченное количество и они симметричны относительно оси Х, а самое главное - точек всегда ровно P (в моем примере - 3). Если мы вместо P = 3 возьмем P = 5 - точек будет 5. 

[amaclin1]

Ну вообще-то это кривая. Ее визуализация на плоскости - выглядит как горох, но тем не менее это кривая.

Да мне-то понятно. Когда читаю. Но вот стоит отвлечься - и опять все из головы вылетает,
то есть уже самостоятельно я это не сформулирую правильно.

Для лирического отступления я бы предложил людям нарисовать эллиптическую кривую на обычном
тетрадном листе в клеточку. Почему бы и нет? Взять P=13, N = 11 и G какое-нибудь выбрать.
А потом посчитать - если мы secp256k1 захотим так на листочке нарисовать - то влезет ли этот
листочек в размеры нашей Вселенной (видимой её части)?

[Destrodream]

Ну вообще-то это кривая. Ее визуализация на плоскости - выглядит как горох, но тем не менее это кривая.

Да мне-то понятно. Когда читаю. Но вот стоит отвлечься - и опять все из головы вылетает,
то есть уже самостоятельно я это не сформулирую правильно.

Для лирического отступления я бы предложил людям нарисовать эллиптическую кривую на обычном
тетрадном листе в клеточку. Почему бы и нет? Взять P=13, N = 11 и G какое-нибудь выбрать.
А потом посчитать - если мы secp256k1 захотим так на листочке нарисовать - то влезет ли этот
листочек в размеры нашей Вселенной (видимой её части)?

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

[amaclin1]

Я бы хотел сказать что "да это все легко", но это не так, точно не мне.

Теорию групп мы в восьмом классе школы начали изучать. Очень красивый раздел математики,
на мой взгляд только теория множеств ещё красивее. Насколько я ненавидел дифференциальное
и интегральное исчисление - настолько я проникся теорией групп, хоть особенно сильно в жизни
и не применял.

Ну как не применял? Мы же все время на компьютере это применяем - например, при сложении
16-битных чисел мы не просто над числами операцию сложения производим, а операцию сложения
в группе вычетов по модулю 2¹⁶. Ну а на 64-битных процессорах - в группе по модулю 2⁶⁴

Эллиптическая криптография - вообще достаточно недавно появилась - всего-то 20-30 лет назад.
Ну и там основная фишка в проблеме факторизации - умножать числа просто, а разложить число
на множители - хервам.

[kzv]

Короткий ответ:

Почему порядок подгруппы в secp256k1 выбран числом 0xffffffff ffffffff ffffffff fffffffe baaedce6 af48a03b bfd25e8c d0364141 ? Кто его придумал?

1. Множитель конечной группы P выбран последним простым числом меньше чем 2^256  :

p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F (115792089237316195423570985008687907853269984665640564039457584007908834671663)

Скорее всего вы правы. Везде еще пишут, что
FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F = 2²⁵¹ - 1 = 2²⁵⁶ - 2³² - 2⁹ - 2⁸ - 2⁷ - 2⁶ - 2⁴ - 1
Но я что-то нигде не нашел доказательства того, что это число простое. Но тут думаю можно поверить. В википедии кстати пишут что это Число Мерсенна и типа равно 2²⁵¹ - 1 Однако там же в вике в статье про этого Мерсенна, про число 2²⁵¹ - 1 ничего не известно.
Короче тут поверю на слово: это наиболее близкое простое к 2²⁵⁶

Это и есть порядок группы, если брать все элементы из группы.

Тут фэйл!
Число "p" это размер конечного поля. Этот размер не равен порядку группы (хотя по Теорема Хассе эти числа близки). Порядок группы вычисляется алгоритмом Шуфа, в который входными данными идут: параметры эллиптической кривой и этот самый размер поля.

Однако, все решили не брать, а брать только элементы начиная с определенной точки G (я писал - я хз как именно эту точку выбрали). То количество точек станет меньше, и их останется

ffffffff ffffffff ffffffff fffffffe baaedce6 af48a03b bfd25e8c d0364141  (115792089237316195423570985008687907852837564279074904382605163141518161494337)

тоже простое число, но чутка поменьше, потому что у кривой "откусили" начало.

Пальцем в небо и опять фэйл в каждой строчке.
1. Точку G взяли не совсем с потолка, а по определенному правилу, следуя определенной логике. Смотрите конец моего поста.
2. Я лично не уверен, что число ffffffff ffffffff ffffffff fffffffe baaedce6 af48a03b bfd25e8c d0364141 простое. Есть доказательство?
С простыми числами всегда так: в общем случае чтобы проверить является ли число простым, придется перебрать все простые числа которые могут быть делителями. А когда перебирать придется 2 в степени дохуя, то как вы надеюсь понимаете, перебор займет времени тоже чуть более чем овердохуя.
Хотя злые языки говорят, что есть алгоритмы которые умеют довольно шустро проверять число на простоту. Так что тут поверю на слово опять.

Этот порядок - определяет кол-во точек на исходной элептической кривой.

Выбран он так, чтобы длинна ключей не превышала 512 бит (т.е. сумма любых двух точке на кривой не вылезет за 512 бит) и при этом кол-во точек было очень большим.

Фэйл.
Как я уже выше написал и повторю еще раз: порядок группы не выбирается, он вычисляется. А число ffffffff ffffffff ffffffff fffffffe baaedce6 af48a03b bfd25e8c d0364141 это не порядок группы, а порядок подгруппы. В общем случае (в 99.99% случаев) эти порядки не совпадают. Порядок подгруппы связан с порядком эллиптической кривой теоремой Лагранжа, согласно которой порядок подгруппы — это делитель порядка исходной группы.

Как посчитать порядок группы эллиптической кривой над конечным полем?

2. Наверное логичнее задавать порядок группы изначально чем его считать. Если посмотреть на уравнение которым описывается кривая - оно содержит в себе mod P, вот P - это и есть простое число, которое определяет кол-во точек и порядок группы. Если группу урезать, то кол-во точек уменьшится.

Фэйл почти в каждом слове (

Внимание, правильный ответ

В биткоине для криптографии выбрана кривая secp256k1 группы SECG. Почему именно эта кривая? Просто Сатоши Накомото так захотел и все! Гевин вроде говорит, что они че-то там обсуждали, но я что-то сомневаюсь. Либо Гевин и есть Сатоши. Тогда все сходится. Но сейчас не об этом...

Итак в выбранной кривой параметры можно скопипастить из библиотеки OpenSSL. Эта библиотека, как это ни странно, существовала задолго до биткоина и эта либа долго входила в зависимости первых версий битка. Вот эти параметры

p = 0xffffffff ffffffff ffffffff ffffffff ffffffff ffffffff fffffffe fffffc2f
a = 0
b = 7
X_G = 0x79be667e f9dcbbac 55a06295 ce870b07 029bfcdb 2dce28d9 59f2815b 16f81798
Y_G = 0x483ada77 26a3c465 5da4fbfc 0e1108a8 fd17b448 a6855419 9c47d08f fb10d4b8
n = 0xffffffff ffffffff ffffffff fffffffe baaedce6 af48a03b bfd25e8c d0364141
h = 1

Теперь, глядя на эти параметры и вдумчиво читая статью на хабре, можно сделать некоторые выводы... Но сначала еще одна выдержка из статьи.
В статье есть глава "Поиск базовой точки". В этой главе дан пошаговый алгоритм: как искать базовую точку G ! Вот этот алгоритм:
1. Вычисляем порядок N эллиптической кривой
2. Выбираем порядок n подгруппы. Чтобы алгоритм сработал, число "n" должно быть простым и быть делителем числа "N"
3. Вычисляем кофактор h = N / n
4. Выбираем на кривой случайную точку P
5. Вычисляем G = h * P
6. Если G = 0 равно 0, то возвращаемся к шагу 4. В противном случае мы нашли генератор подгруппы с порядком "n" и кофактором h

Вот теперь можно еще раз проследить за логикой чуваков, которые вставили магические параметры в OpenSSL откуда эти параметры скопипастил Сатоши. Думаю логика была такая:
1. У нас универсальная либа, давайте добавим кривую где y² = x³ + 7
2. Возьмем какой-нибудь польшой размер поля. 256 бит вроде достаточно много.
Деление по модулю p (которое необходимо для операций сложения и умножения) может выполняться быстрее, если в качестве p выбрать простое число, близкое к степени числа 2. Значит возьмем максимальное 256-битное простое число
p = 0xffffffff ffffffff ffffffff ffffffff ffffffff ffffffff fffffffe fffffc2f
3. Вычислим порядок получившейся группы.
Получается
N = 0xffffffff ffffffff ffffffff fffffffe baaedce6 af48a03b bfd25e8c d0364141
4. Хотелось бы чтобы число точек в подгруппе было максимальным. Нам повезло, потому что N - получилось простым числом и мы можем выбрать кофактор = 1 и тогда порядок подгруппы будет равен порядку группы! Получаем
n = 0xffffffff ffffffff ffffffff fffffffe baaedce6 af48a03b bfd25e8c d0364141
h = 1
5. Внимание, магия!
Выбираем на кривой случайную точку P. Поскольку кофактор = 1, то G = P

То есть у кривой secp256k1 группы SECG есть замечательное свойство: абсолютно любая точка на кривой secp256k1 группы SECG, генерирует подгруппу с кофактором 1!

[amaclin1]

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

[fxpc]

Короткий ответ:

Почему порядок подгруппы в secp256k1 выбран числом 0xffffffff ffffffff ffffffff fffffffe baaedce6 af48a03b bfd25e8c d0364141 ? Кто его придумал?

1. Множитель конечной группы P выбран последним простым числом меньше чем 2^256  :

p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F (115792089237316195423570985008687907853269984665640564039457584007908834671663)

Скорее всего вы правы. Везде еще пишут, что
FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F = 2²⁵¹ - 1 = 2²⁵⁶ - 2³² - 2⁹ - 2⁸ - 2⁷ - 2⁶ - 2⁴ - 1
Но я что-то нигде не нашел доказательства того, что это число простое. Но тут думаю можно поверить. В википедии кстати пишут что это Число Мерсенна и типа равно 2²⁵¹ - 1 Однако там же в вике в статье про этого Мерсенна, про число 2²⁵¹ - 1 ничего не известно.
Короче тут поверю на слово: это наиболее близкое простое к 2²⁵⁶

Вот доказательства:
https://ru.wikipedia.org/wiki/Критерий_Поклингтона
https://safecurves.cr.yp.to/proof/115792089237316195423570985008687907853269984665640564039457584007908834671663.html

Primality proof for n = 115792089237316195423570985008687907853269984665640564039457584007908834671663:
Take b = 2.

b^(n-1) mod n = 1.

205115282021455665897114700593932402728804164701536103180137503955397371 is prime.
b^((n-1)/205115282021455665897114700593932402728804164701536103180137503955397371)-1 mod n = 30133174243114333125352536507925183895021889065932097717961225114769139489295, which is a unit, inverse 38738227534097492269493948901333532538630784921480042032654553727346127695815.

(205115282021455665897114700593932402728804164701536103180137503955397371) divides n-1.

(205115282021455665897114700593932402728804164701536103180137503955397371)^2 > n.

n is prime by Pocklington's theorem.

[kzv]

Вот доказательства:
https://ru.wikipedia.org/wiki/Критерий_Поклингтона
https://safecurves.cr.yp.to/proof/115792089237316195423570985008687907853269984665640564039457584007908834671663.html

Primality proof for n = 115792089237316195423570985008687907853269984665640564039457584007908834671663:
Take b = 2.

b^(n-1) mod n = 1.

205115282021455665897114700593932402728804164701536103180137503955397371 is prime.
b^((n-1)/205115282021455665897114700593932402728804164701536103180137503955397371)-1 mod n = 30133174243114333125352536507925183895021889065932097717961225114769139489295, which is a unit, inverse 38738227534097492269493948901333532538630784921480042032654553727346127695815.

(205115282021455665897114700593932402728804164701536103180137503955397371) divides n-1.

(205115282021455665897114700593932402728804164701536103180137503955397371)^2 > n.

n is prime by Pocklington's theorem.

Спасибо.
А число 0xffffffff ffffffff ffffffff fffffffe baaedce6 af48a03b bfd25e8c d0364141 так же проверить можно?

[fxpc]

Вот доказательства:
https://ru.wikipedia.org/wiki/Критерий_Поклингтона
https://safecurves.cr.yp.to/proof/115792089237316195423570985008687907853269984665640564039457584007908834671663.html

Primality proof for n = 115792089237316195423570985008687907853269984665640564039457584007908834671663:
Take b = 2.

b^(n-1) mod n = 1.

205115282021455665897114700593932402728804164701536103180137503955397371 is prime.
b^((n-1)/205115282021455665897114700593932402728804164701536103180137503955397371)-1 mod n = 30133174243114333125352536507925183895021889065932097717961225114769139489295, which is a unit, inverse 38738227534097492269493948901333532538630784921480042032654553727346127695815.

(205115282021455665897114700593932402728804164701536103180137503955397371) divides n-1.

(205115282021455665897114700593932402728804164701536103180137503955397371)^2 > n.

n is prime by Pocklington's theorem.

Спасибо.
А число 0xffffffff ffffffff ffffffff fffffffe baaedce6 af48a03b bfd25e8c d0364141 так же проверить можно?

Конечно, переведи в dec и вставь вместо *

Code:

https://safecurves.cr.yp.to/proof/*.html

[zan0za]

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

А это точно что абсолютно любое число может быть приватным ключем, может есть еще какие то ограничения?

[amaclin1]

А это точно что абсолютно любое число может быть приватным ключем, может есть еще какие то ограничения?

от 1 до 0xFFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFE BAAE DCE6 AF48 A03B BFD2 5E8C D036 4140 включительно
(в десятичную систему переводите сами, мне удобнее видеть это число в шестнадцатеричной системе)

Числа вне этого диапазона можно тоже считать приватными ключам, потому что все математические операции
делаются после взятия остатка от деления на 0xFFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFE BAAE DCE6 AF48 A03B BFD2 5E8C D036 4141

[zan0za]

А это точно что абсолютно любое число может быть приватным ключем, может есть еще какие то ограничения?

от 1 до 0xFFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFE BAAE DCE6 AF48 A03B BFD2 5E8C D036 4140 включительно
(в десятичную систему переводите сами, мне удобнее видеть это число в шестнадцатеричной системе)

Числа вне этого диапазона можно тоже считать приватными ключам, потому что все математические операции
делаются после взятия остатка от деления на 0xFFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFE BAAE DCE6 AF48 A03B BFD2 5E8C D036 4141

Я думал что должно быть ограничение на чет/не чет или что не должно быть остатка от деления например на 16 и.т.д.
А как тогда получается что все адреса в биткоине начинаются на 1 или 3?
Как потом из числа формируется биткоин адрес в котором присутстуют символы которые не входят в список шестнадцатиричных значений - от A до F?

[fxpc]

Я думал что должно быть ограничение на чет/не чет или что не должно быть остатка от деления например на 16 и.т.д.
А как тогда получается что все адреса в биткоине начинаются на 1 или 3?
Как потом из числа формируется биткоин адрес в котором присутстуют символы которые не входят в список шестнадцатиричных значений - от A до F?

Держи нас в курсе, хотя нет, не держи, всем похуй. Как получается? Магия блять. Сатоши потомок Гарри Гуддини. Тебе религия запрещает поискать ответы на свои вопросы на форуме или в гугле? Этот топик не для тех кто не в состоянии вбить поисковый запрос, здесь обсуждаются более сложные алгоритмы.

[kzv]

Я тут почитал про цифровую подпись еще. Подписывание сообщение у большинства нормальных людей проходит следующим образом:
1. Берем случайное целое k число от 1 до n-1 где n - порядок группы (в биткоине 0xFFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFE BAAE DCE6 AF48 A03B BFD2 5E8C D036 4141)
2. Вычисляем

P = k*G = random(1, 0xFFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFE BAAE DCE6 AF48 A03B BFD2 5E8C D036 4140) * 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8

3. Из результата вычислений пункта 2 (из числа P) берем первые 32 байта - это типа координата X точки P или назовем это X_p
4. Вычисляем первые 32 байта подписи

r = X_p mod n = первые32байта(k*G) mod n = первые32байта(random(1, 0xFFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFE BAAE DCE6 AF48 A03B BFD2 5E8C D036 4140) * 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8) mod 0xFFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFE BAAE DCE6 AF48 A03B BFD2 5E8C D036 4141

5. Вычисляем вторые 32 байта подписи. Только тут понадобится сообщение и приватный ключ подписывающего.
5.1. Хэшируем сообщение
z = sha256(message)
5.2. Вычисляем "мультипликативную инверсию" числа k. Для этого надо решить уравнение
( k^-1 * k ) mod n = 1
или

( k^-1 * random(1, 0xFFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFE BAAE DCE6 AF48 A03B BFD2 5E8C D036 4140) ) mod 0xFFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFE BAAE DCE6 AF48 A03B BFD2 5E8C D036 4141 = 1

Я хз, как это уравнение решать, но как-то оно довольно быстро решается и из него находят k^-1
5.3 Вычисляем вторую часть подписи с помощью закрытого ключа D_a

s = k^-1 * (z + D_a * r) mod n =  k^-1 * (sha256(message) + D_a * первые32байта(random(1, 0xFFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFE BAAE DCE6 AF48 A03B BFD2 5E8C D036 4140) * 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8) mod 0xFFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFE BAAE DCE6 AF48 A03B BFD2 5E8C D036 4141

Такой вот неочевидный алгоритм, кто-то его придумал и он работает. Как видно в алгоритме участвуют два секретных ключа: случайное число k и приватный ключ D_a.

Алярм 1: если кто-то узнает или подберет k, то он вычислит приватный ключ D_a !!!111

D_a = r^-1 * (s * k - z) mod n = первые32байта_подписи^-1 * (вторые32байта_подписи * k - sha256(message)) mod 0xFFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFE BAAE DCE6 AF48 A03B BFD2 5E8C D036 4140

Алярм2: если подписать два разных сообщения с одним и тем же (не случайным) k, то опять можно вычислить приватный ключ D_a !!!111
Сначала вычисляем k

k = (z1 - z2) * (s1 - s2)^-1 mod n = (sha256(message1) - sha256(message2)) * (вторые32байта_подписи1 - вторые32байта_подписи2)^-1 mod 0xFFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFE BAAE DCE6 AF48 A03B BFD2 5E8C D036 4140

Ну а когда вычислим k, то см. Алярм1.

А теперь на сладкое: большинство программ и сервисов для одних и тех же приватного ключа и сообщения, на выходе всегда дают разную валидную цифровую подпись. Оно и понятно, ибо в алгоритме k - должно быть случайным...
А вот биткоин всегда дает одну и туже подпись для одинаковых сообщений и приватного ключа! То есть число k в биткоине не случайное, а вычисляемое.

Я когда это понял, даже офигел: как так, биткоин не следует стандарту? Но порывшись в исходниках разных либ и самого битка обнаружил, что все таки есть еще один стандарт который называется "Deterministic ECDSA" https://tools.ietf.org/html/rfc6979#section-3

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

Кстати, насколько я понял, сообщения и транзакции клиент биткоина тоже подписывает по разному...
Перед тем как хэшировать сообщение, к сообщению добавляется "магическая фраза" типа "Bitcoin signed message\n". А перед тем как хэшировать транзакцию никаких магических фраз не добавляется. Думаю это такая защита для дурака: чтобы никто не мог с помощью кошелька вместо сообщения подписать транзакцию ))

[amaclin1]

Ну ты, блин, семимильными шагами идешь в правильном направлении.
Придраться не к чему, только чуть дополню.

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

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

Там просто берется дайджест сообщения = 256 бит которые сами являются хэшом каких-то данных
Конкатенируется (то есть дописывается в хвост) приватный ключ. И эти 512 бик хэшируются HMAC-ом и sha256
Или наоборот сперва ключ потом дайджест? Ну почитайте сами. Можно вообще через символ брать то и другое
как зубья у расчески.

Вы спросите почему не хэшировать только sha256? Зачем еще hmac какой-то приплели? Тут я сам не очень
понимаю в чем подвох, но смысл такой, что sha256 - блочный алгоритм хэширования и из-за этого обладающий
проблемами при хэшировании вот таких вот кусков, где одна часть известна. Эту проблему с некоторых пор
даже в биткойне заметили. Асик-буст как раз на этом построен. То есть без hmac у нас падает расчетная сложность
брутфорса. А хорошие криптографы такого не любят.

Короче, число `k` для подписывания можно вычислять любым изъебистым способом. Я, например, не парюсь
и в своих программах беру 128 бит от приватного ключа и 128 бит от дайждеста. Если мой приватный ключ подберут
и сопрут 46 центов с кошелька - я не очень расстроюсь. Но если вы хотите обеспечить в своей программе все по
криптографическому стандарту - юзайте RFC 6979.

[n00by]

Я хз, как это уравнение решать, но как-то оно довольно быстро решается и из него находят k^-1

Это не уравнение. к - это точка на эл.кривой. Обратная ей точка это координата y с противоположным знаком. Нужно только знать к. В той "научно-популярной", как выразился @amaclin, есть геометрический пример как найти эту точку. Я тут много скриптов понаписывал и поотлаживал скрипты многих алгоритмов, используемых в крипте.

Кстати, можно много напридумывать всякого с этим вот k^-1. Я вот увлекся сейчас битовой сложностью sha(256)->hash(160). Там есть где поискать красоты обычной математики.

[n00by]

Вы спросите почему не хэшировать только sha256? Зачем еще hmac какой-то приплели? Тут я сам не очень
понимаю в чем подвох, но смысл такой, что sha256 - блочный алгоритм хэширования и из-за этого обладающий
проблемами при хэшировании вот таких вот кусков, где одна часть известна. Эту проблему с некоторых пор
даже в биткойне заметили. Асик-буст как раз на этом построен.

Не совсем так. sha256 "хеширует" (да простит меня Лобачевский), вычисляет новое большое по определенному алгоритму. Входящее сообщение бьется на блоки по 64 байта (8х8 бит), котрые сами по себе представляют int. Затем происходит сложение/умножение по модулю int каждого такого числа, но 64 раза. В итоге получем на выходе ряд чисел (8х которые и дают нам хэш.

АсикБус немного по-другому работает и устроен то по другому. Он что-то сродни вот этой вот штуки: https://en.bitcoin.it/wiki/Mini_private_key_format