Topic: Математика и алгоритмы биткоина. - page 7. (Read 17492 times)

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

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

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

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

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

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

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

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)

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

Правильно?

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