эллиптическая кривая sec256k1 и её точка генерат

[Martensito]

В описании эллиптической кривой sec256k1 есть точка генератора
координаты
G(x) = 55066263022277343669578718895168534326250603453777594175500187360389116729240
G(y) = 32670510020758816978083085130507043184471273380659243275938904335757337482424

И у меня в связи с одним проектом, возник вопрос. Каким образом находится данная точка. Может это просто случайная точка или есть какой-то алгоритм её поиска. и почему эта , а не какая либо другая из огромного количества точек. Если у кого-то есть какая нибудь информация, возможно какие-то знания или мысли по этому поводу, прошу поделиться.

[ON LY]

Так точку G ещё никто не искал   Вы женаты?
А попробуйте задать этот же вопрос ChatGpt, по моему он болий лимений все внятно обьяснил). Сюда это копировать думаю не имеет смысла, сами разберетесь.

[amaclin1]

ChatGPT выдает вот такой ответ:

Почему именно эта точка?
Стандарт SEC2 (Standards for Efficient Cryptography Group) задал G как точку, полученную по детерминированной процедуре: начиная с x = 1, перебирались значения x до тех пор, пока не была найдена подходящая точка на кривой с желаемыми свойствами (большой порядок, надёжная структура подгруппы).

Но по-моему он врёт. По-моему, именно эта точка (а не какая-то другая) была выбрана "никто не знает как, а если кто-то знает, тому секир-башка"

Короче, спросите у ИИ. Он какие-то выкладки даёт, но у меня лично нет достаточных знаний в вопросе, чтобы подтвердить или опровергнуть.

[Martensito]

ChatGPT выдает вот такой ответ:

Почему именно эта точка?
Стандарт SEC2 (Standards for Efficient Cryptography Group) задал G как точку, полученную по детерминированной процедуре: начиная с x = 1, перебирались значения x до тех пор, пока не была найдена подходящая точка на кривой с желаемыми свойствами (большой порядок, надёжная структура подгруппы).

Но по-моему он врёт. По-моему, именно эта точка (а не какая-то другая) была выбрана "никто не знает как, а если кто-то знает, тому секир-башка"

Короче, спросите у ИИ. Он какие-то выкладки даёт, но у меня лично нет достаточных знаний в вопросе, чтобы подтвердить или опровергнуть.

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

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

[satscraper]

ChatGPT выдает вот такой ответ:

Почему именно эта точка?
Стандарт SEC2 (Standards for Efficient Cryptography Group) задал G как точку, полученную по детерминированной процедуре: начиная с x = 1, перебирались значения x до тех пор, пока не была найдена подходящая точка на кривой с желаемыми свойствами (большой порядок, надёжная структура подгруппы).

Но по-моему он врёт. По-моему, именно эта точка (а не какая-то другая) была выбрана "никто не знает как, а если кто-то знает, тому секир-башка"

Похоже вы правы насчёт "никто не знает как".

Вот что поэтому поводу говорит Pieter Wuille ^{напомню, это один из ведущих хотя уже бывшийразработчик Bitcoin Core}:

т.е - неизвестно как она была выбрана.

Дальше говорит что при X ∈ G выражение x³+7 имеет квадратный корень по модулю р. ^{Ну, это понятно и без него}.И один из этих корней был выбран как Y^{тоже понятно}.

[Ctrl_A]

ChatGPT выдает вот такой ответ:

Почему именно эта точка?
Стандарт SEC2 (Standards for Efficient Cryptography Group) задал G как точку, полученную по детерминированной процедуре: начиная с x = 1, перебирались значения x до тех пор, пока не была найдена подходящая точка на кривой с желаемыми свойствами (большой порядок, надёжная структура подгруппы).

Но по-моему он врёт. По-моему, именно эта точка (а не какая-то другая) была выбрана "никто не знает как, а если кто-то знает, тому секир-башка"

Короче, спросите у ИИ. Он какие-то выкладки даёт, но у меня лично нет достаточных знаний в вопросе, чтобы подтвердить или опровергнуть.

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

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

При последовательном переборе точка x = 1,  y = 29896722852569046015560700294576055776214335159245303116488692907525646231534 не выбрана. Не понятно, зачем нужен большой порядок, что значит надёжная структура (какой-то) подгруппы. Кто-то перебирал до 5.5*10^76 ? ChatGPT врёт.

А если точка G = 1 с координатой x = 55066263022277343669578718895168534326250603453777594175500187360389116729240 выбрана случайно, то как объяснить "случайность" точек (n ± 1) / 2, у которых координата x = 00000000000000000000000000086918276961810349294276103416548851884759982251107 ?
10 ^ -27 - весьма маленькая вероятность случайности.

Моё мнение, при выборе отталкивались от точек (n ± 1) / 2, назначив для них х = (см. выше).

Так что, по всему выходит, кому-то секир-башка.

[Martensito]

При том что явно ни кто не перебирал все возможные х , так над этими х ещё нужно было совершить операцию типа
X^(p-1)/q по mod p  где q все возможные делители ( р-1) и что бы это х не было равно 1 по модулю р и только тогда х считалось не тривиальной крипто устойчивой точкой.

[ON LY]

При том что явно ни кто не перебирал все возможные х , так над этими х ещё нужно было совершить операцию типа
X^(p-1)/q по mod p  где q все возможные делители ( р-1) и что бы это х не было равно 1 по модулю р и только тогда х считалось не тривиальной крипто устойчивой точкой.

Перебрать все возможные х, боюсь невозможно, нашей жизни точно не хватит)
Gpt не врет, """то что координаты G выглядят как случайные огромные числа — это нормально. На самом деле, если бы выбрали другой x, мы получили бы другой «случайный» генератор. Все они были бы одинаково «хороши» с криптографической точки зрения."""

[Martensito]

При том что явно ни кто не перебирал все возможные х , так над этими х ещё нужно было совершить операцию типа
X^(p-1)/q по mod p  где q все возможные делители ( р-1) и что бы это х не было равно 1 по модулю р и только тогда х считалось не тривиальной крипто устойчивой точкой.

Перебрать все возможные х, боюсь невозможно, нашей жизни точно не хватит)
Gpt не врет, """то что координаты G выглядят как случайные огромные числа — это нормально. На самом деле, если бы выбрали другой x, мы получили бы другой «случайный» генератор. Все они были бы одинаково «хороши» с криптографической точки зрения."""

На сколько " случайно " можно было выбрать х = 55066263022277343669578718895168534326250603453777594175500187360389116729240

[ON LY]

На сколько " случайно " можно было выбрать х = 55066263022277343669578718895168534326250603453777594175500187360389116729240

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

[Martensito]

На сколько " случайно " можно было выбрать х = 55066263022277343669578718895168534326250603453777594175500187360389116729240

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

Причем здесь теория заговора и я не ищу уязвимость я просто хочу разобраться в данной теме
И по вашим словам могли выбрать любую другую точку, но почему-то не выбрали x = 1,  y = 29896722852569046015560700294576055776214335159245303116488692907525646231534

[ON LY]

Причем здесь теория заговора и я не ищу уязвимость я просто хочу разобраться в данной теме
И по вашим словам могли выбрать любую другую точку, но почему-то не выбрали x = 1,  y = 29896722852569046015560700294576055776214335159245303116488692907525646231534

Давайте определимся, "выбрали" или "перебирали", если выбрали - то я не знаю почему, а если перебирали, то это первая случайная подходящая точка, (а может не первая)

[Martensito]

Причем здесь теория заговора и я не ищу уязвимость я просто хочу разобраться в данной теме
И по вашим словам могли выбрать любую другую точку, но почему-то не выбрали x = 1,  y = 29896722852569046015560700294576055776214335159245303116488692907525646231534

Давайте определимся, "выбрали" или "перебирали", если выбрали - то я не знаю почему, а если перебирали, то это первая случайная подходящая точка, (а может не первая)

Наверное всё таки"выбрали", потому что слово "перебирали" к 55066263022277343669578718895168534326250603453777594175500187360389116729240 немного не подходит
И вопрос остаётся открытым почему "выбрали" и как именно "выбрали"

[Ctrl_A]

Удивительное дело - дебаты о возникновении координат единичного ключа активно продолжаются, хотя в своём крайнем посте я доказал, что эта точка не назначена (не выбрана) и не определена перебором, а ВЫЧИСЛЕНА из других точек, для которых, в свою очередь, координата x просто назначена вручную относительно "малым" числом.
Повторю здесь свой пост более подробно.
Как известно, приватные ключи определены в ограниченном поле целых чисел по модулю N =  115792089237316195423570985008687907852837564279074904382605163141518161494337 ≈ 2^256 (от 1 до N - 1 включительно). Единичный ключ P(1) - это искомая точка G. Поскольку координаты точек по модулю удовлетворяют уравнению y^2 = x^3 + 7, то для каждого возможного x существует две точки y: ± корень(x^3 + 7). Т.к. все координаты определены в поле по модулю p = 2**256 - 2**32 - 977, то отрицательное число y становится положительным при взятии по модулю p: -y (mod p) = p - y. Таким образом определяются симметричные относительно нуля точки: P(k) = (x, y) и - P(k) = P(-k) = (x, - y) = (x, p - y). В этом случае у обеих точек одна и та же координата х. Во всём пространстве N есть две замечательные точки, это ( N - 1) / 2 и (N + 1) / 2. Замечательны они тем, что симметричны относительно нуля, находятся ровно посередине поля N и расстояние между ними = 1. Теперь самое интересное: у них координата x = 00000000000000000000000000086918276961810349294276103416548851884759982251107. Т.е. она примерно в 10^27 раз меньше, чем случайно взятое число из диапазона [1; p). Если методом случайного или неслучайного перебора определять значение координаты x для G, то никакой жизни не хватит, чтобы получить тукую "маленькую" координату для серединных ключей. Отсюда вывод: КООРДИНАТА X ДЛЯ ТОЧЕК ( N - 1) / 2 и (N + 1) / 2 ВЫБРАНА ВРУЧНУЮ, а G УЖЕ ПОТОМ ВЫЧИСЛЕНА ИЗ НИХ. Каким образом?
Как уже сказано, расстояние между этими точками = 1, следовательно, G  =  P((N + 1) / 2) - P((N - 1) / 2). Но поскольку они равны друг другу с отрицательным знаком, то G = 2 * P((N + 1) / 2). Т.е. для получения G нужно точку (N + 1) / 2 умножить на 2 или просто сложить с самой собой.
Функция на Python-е для сложения ключей выглядит следующим образом:

def EC_Add(P, Q):
    p = 115792089237316195423570985008687907853269984665640564039457584007908834671663
    px = int(P[2:66], 16)
    py = int(P[66:], 16)
    qx = int(Q[2:66], 16)
    qy = int(Q[66:], 16)
    if (px == qx) and (py == qy):
        dydx = (3 * px**2) * pow(2 * py, -1, p)
    else:
        dydx = (qy - py) * pow(qx - px, -1, p)
    x = (dydx**2 - px - qx) % p
    y = (dydx * (px - x) - py) % p
    return '04' + hex(x)[2:].zfill(64) + hex(y)[2:].zfill(64)

Подставляйте сюда назначенные данные серединных точек и вычисляйте на здоровье свою точку G.

[Martensito]

Если координата х = 00000000000000000000000000086918276961810349294276103416548851884759982251107 ВЫБРАНА В РУЧНУЮ  то она всё равно подбиралась таким образом чтобы координата х для генератора G обладала определёнными свойствами и одно из них чтобы Х в степени ( р-1)/q по модулю р не было равно 1, где q - ВСЕ возможные делители (р-1).
 И мне не очень верится что вот прям попали с первого раза.
Так что прсто назначили не подходит, а подбирали и по какому-то алгоритму

[Ctrl_A]

Если координата х = 00000000000000000000000000086918276961810349294276103416548851884759982251107 ВЫБРАНА В РУЧНУЮ  то она всё равно подбиралась таким образом чтобы координата х для генератора G обладала определёнными свойствами и одно из них чтобы Х в степени ( р-1)/q по модулю р не было равно 1, где q - ВСЕ возможные делители (р-1).
 И мне не очень верится что вот прям попали с первого раза.
Так что прсто назначили не подходит, а подбирали и по какому-то алгоритму

Ваш оригинальный вопрос звучал так: "Каким образом находится данная точка (G)?"
Ответ: эта точка однозначно классическим способом вычисляется из точек (n ± 1) / 2, которые в свою очередь определяются ВРУЧНУЮ. Этим выделенным определением я хотел показать, что они являются изначальными и не вычислялись из других точек. И с чего это вдруг Вы решили, что это было сделано с первого раза? Вообще, какая разница, с первого раза или с пятого, десятого и т.д. Хотя в 2009 г вряд ли перебрали очень много чисел.
Назовите указанное Вами число q (ВСЕ возможные делители (р-1)), попробуем поперебирать (методом тыка или с функцией random) и назначить свою точку.

[Martensito]

Делитель q  , например для р =101 имеют такие значения 1, 2,4,5,10,20,25,50,100 . Все эти значения необходимо подставить в выражение (x**((p-1)//q)) %p =! 1для каждого х от0 до 100
Какие значения q для  р=115792089237316195423570985008687907852837564279074904382605163141518161494337 я не знаю и думаю их нахождения и запись, займёт много времени и места. Если вы сможете это сделать буду очень благодарен.

И когда будет найдено значение х удовлетворяющее этим условиям его необходимо подставить в уравнение кривой y**2=x**3+3x+10 если is on curve  то вот она точка генератор если нет то искать дальше

[viljy]

Цитата из https://habr.com/ru/articles/335906/

Вычисляем порядок N эллиптической кривой.
Выбираем порядок n подгруппы. Чтобы алгоритм сработал, число должно быть простым и быть делителем N.
Вычисляем кофактор h = N / n.
Выбираем на кривой случайную точку P.
Вычисляем G = hP.
Если G равно 0, то возвращаемся к шагу 4. В противном случае мы нашли генератор подгруппы с порядком n и кофактором h.

Кому это интересно и охота вникать вот в это все, то есть такая книжка Н.Коблиц "Введение в эллиптические кривые и модулярные формы"