Вопрос по эллипт кривой, непонятен ОДИН ша

[viljy]

Что-то это не совсем то, что я имел в виду. А именно - полностью убрать операции удвоений из расчета. Таким образом изначально вычисляем 255 фиксированных открытых ключей, начиная от одного удвоения G и заканчивая точкой из 255 удвоений. Эти точки можно вычислить просто в эллиптическом калькуляторе и готовые значения взять. Уж много памяти не должны занять. Значит имеем всего 256 точек (откр. ключей) включая саму точку G. Затем на основании приватника в двоичном формате суммируем только те точки, которым соответствует 1 в соответствующем разряде. Так у нас полностью убраны из расчета удвоения. Значит используются только формулы для суммирования. Должно ли это быть быстрее?

[Ctrl_A]

Что-то это не совсем то, что я имел в виду. А именно - полностью убрать операции удвоений из расчета. Таким образом изначально вычисляем 255 фиксированных открытых ключей, начиная от одного удвоения G и заканчивая точкой из 255 удвоений. Эти точки можно вычислить просто в эллиптическом калькуляторе и готовые значения взять. Уж много памяти не должны занять. Значит имеем всего 256 точек (откр. ключей) включая саму точку G. Затем на основании приватника в двоичном формате суммируем только те точки, которым соответствует 1 в соответствующем разряде. Так у нас полностью убраны из расчета удвоения. Значит используются только формулы для суммирования. Должно ли это быть быстрее?

Именно то, о чём Вы говорите, и реализуется в первой программе, если в качестве основания для разложения по степеням ввести двойку.
В этом случае создаётся база из 256 элементов (пуб. ключи, соответствующие 2^0, 2^1, 2^2, ..., 2^254, 2^255). МЕста в памяти такая база займёт совсем немного, почти ничего. Далее, при вычислении любого пуб. ключа никаких удвоений уже не происходит. Число (приватный ключ) представляется в виде суммы степеней двойки с соответствующими коэффициентами (0 или 1), и пуб. ключ вычисляется в соответствии с этими коэффициентами как сумма элементов базы.
При раскладывании на степени другого числа больше двойки число слагаемых уменьшается, что приводит к росту скорости вычисления пуб. ключа, но в таком случае растёт и размер базы.
Для относительно больших значений приватника библиотека работает быстрее. Для "маленьких" ключей библиотека отстаёт.
Возможны три причины "тормоза". 1-я: медленное разложение приватника в сумму степеней (во второй программе этот шаг отсутствует!). 2-я: использование словаря не самый эффективный способ хранения элементов базы. 3-я: медленно работает функция сложения пуб. ключей. Что скажут программисты?

[cadrus]

При использовании N = 2 ...
... не программист.

Нашёл другой способ вычисления публичного ключа из приватного, в котором последний раскладывать по степеням совсем не обязательно!
Если приватник выражается 64-значным 16-ричным числом, его можно представить как сумму не более 64-х чисел...

Это и есть разложение по степеням, в данно случае по степеням 16-ти.

[Ctrl_A]

Это и есть разложение по степеням, в данно случае по степеням 16-ти.

Да, Вы правы. Любое число может существовать только не иначе как представленным суммой степеней с коэффициентами не более, чем на единицу меньше основания. В данном случае 16-ричное число удобно тем, что оно уже изначально "готово к употреблению", поэтому процесс его разложения на сумму степеней опускается. Конечно, можно такой же финт провернуть и с другим удобным основанием - десятеричным числом, но в этом случае увеличивается число слагаемых, что замедляет вычисление.

[cadrus]

Это и есть разложение по степеням, в данно случае по степеням 16-ти.

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

Почему "опускается"? Чтоб выделить нужные множители, все равно придется прогонять по алгоритму. Или парсить в строковом виде.

[Ctrl_A]

Это и есть разложение по степеням, в данно случае по степеням 16-ти.

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

Почему "опускается"? Чтоб выделить нужные множители, все равно придется прогонять по алгоритму. Или парсить в строковом виде.

Раскладывать в сумму по степеням и прогонять по алгоритму - не одно и тоже, потому и опускается. В первой программе есть и то и другое, причём расклад идёт на выбор для любого натурального числа  для основания, начиная с двойки. Во второй программе только алгоритм выделения для 16-ричного числа.
Вы, наверное, программист, если пользуетесь таким словом как "парсить". Тогда Вам не сложно рассмотреть алгоритм второй программы. Вы увидите, что она работает равносильно программе с разложением по степеням не 16-ти, а 16^4 = 65536. Но там нет и намёка раскладывать приватный ключ по степеням 65536. Есть только алгоритм по выделению из готового числа сразу по четыре знака.

[viljy]

Возможны три причины "тормоза". 1-я: медленное разложение приватника в сумму степеней (во второй программе этот шаг отсутствует!). 2-я: использование словаря не самый эффективный способ хранения элементов базы. 3-я: медленно работает функция сложения пуб. ключей. Что скажут программисты?

По 1 и 2 никакого мнения не имею, т.к. не программист. Насчет 3, как считаете, возможно ли попробовать такой вариант, который используется в curve25519 или ed25519, а именно использование для эксперимента в промежуточных операциях только одной координаты, затем на последнем сложении вычислять вторую? Вроде в curve считают только X, но возможно удобнее будет делать как во втором примере - считать только Y и в конце вычислять X. Конечно х.з. быстрее ли это будет для биткоина, т.к. у него вроде Y вычисляется из X, т.е. надо формулы преобразовывать, кроме того, в выше указанных примерах p гораздо ближе к степени 2 (2^255 - 19) чем p у биткоина (2^256 - 2^32 - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1), и вроде я где-то читал, что поэтому вычисляется быстрее (не уверен что так). Просто интересно возможно ли считать только одну координату и ускорит ли это сложения?

[Ctrl_A]

Возможны три причины "тормоза". 1-я: медленное разложение приватника в сумму степеней (во второй программе этот шаг отсутствует!). 2-я: использование словаря не самый эффективный способ хранения элементов базы. 3-я: медленно работает функция сложения пуб. ключей. Что скажут программисты?

По 1 и 2 никакого мнения не имею, т.к. не программист. Насчет 3, как считаете, возможно ли попробовать такой вариант, который используется в curve25519 или ed25519, а именно использование для эксперимента в промежуточных операциях только одной координаты, затем на последнем сложении вычислять вторую? Вроде в curve считают только X, но возможно удобнее будет делать как во втором примере - считать только Y и в конце вычислять X. Конечно х.з. быстрее ли это будет для биткоина, т.к. у него вроде Y вычисляется из X, т.е. надо формулы преобразовывать, кроме того, в выше указанных примерах p гораздо ближе к степени 2 (2^255 - 19) чем p у биткоина (2^256 - 2^32 - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1), и вроде я где-то читал, что поэтому вычисляется быстрее (не уверен что так). Просто интересно возможно ли считать только одну координату и ускорит ли это сложения?

Особенность кривой Curve25519 заключается в том, что коэффициенты в ней подобраны таким образом, что вычисления проходят быстрее, чем по другим кривым.
https://habr.com/ru/post/247873/

К сожалению, не всё так просто с использованием в вычислениях только одной координаты. Кривая Монтгомери b*y^2=x^3+a*x^2+x (Curve25519 - частный случай этой кривой, где b = 1 и a = 486662) преобразуется в трёхмерный вид с помощью проективной геометрии. Точка выражается через новые координаты X, Z. Вот эти координаты и находятся при сложении / умножении. Координата y, если необходимо, вычисляется уже после.
Здесь кратко по кривой Монтгомери:
https://www.hyperelliptic.org/EFD/g1p/auto-montgom-xz.html
https://trustica.cz/en/2020/02/06/montgomery-curves-in-projective-coordinates/
В последней ссылке формула BY^Z=X^3+AX^Z+XZ^2 - хрень! Правильные формулы - ниже на картинке.

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

Модули p - простые числа. У биткоина p почти в 2 раза больше (~2^256 против ~2^255), наверное, ещё и поэтому разница в скорости.

В первом приближении интуитивно кажется, что проективную геометрию для преобразования биткоиновской кривой y^2 = x^3 + 7 применить можно. Но для точного ответа надо досконально знать эту тему. Может, это уже работает в современных библиотеках? С ответом напряг, программисты, похоже, здесь не живут.

[cadrus]

По одной координате складывать не получится, ибо каждому "x" соответствует две точки, то есть два "y" и тогда будет неоднозначность. Для сложения точек сама формула уравнения не нужна, достаточно только координат и модуля. В случае удвоения точки нужен еще аргумент "a" из афинного представления. Насчет проективных координат - там якобы есть преимущество за счет исключения операции деления, но там реально больше других действий. В библиотеке OpenSSL в третьей версии убрали представление в проективных коолрдинатах. В прошлых версиях было.

[Ctrl_A]

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

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

Также подозреваю, что один и тот-же "y" может быть у трех точек из группы (подтверждения этому не имею).

Ни одна горизонтальная прямая не пересекает кривую в трёх точках. Это легко доказывается исходя из формулы биткоина y^2 = x^3 + 7.

Для сложения точек сама формула уравнения не нужна, достаточно только координат и модуля.

А обе координаты как получить, как не с помощью формулы?

[cadrus]

А обе координаты как получить, как не с помощью формулы?

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

[Ctrl_A]

Вот посмотрите, построил две кривые по формуле биткоина, только с маленькими модулями, 67 и 61 соответственно. Если кривая определена на каком-то "y", то такой-же "y" есть по-любому еще у двух точек. Так происходит не с каждым простым модулем, но это есть, и модуль биткоина не исключение.

img-1
img-2

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

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

Что в Вашем понимании означают "программные методы генерации точек"? Это определение точек кривой без формулы для этой кривой?
И что означает "когда точки уже известны"? Они появились из ниоткуда сами собой без формулы?

[cadrus]

Что в Вашем понимании означают "программные методы генерации точек"? Это определение точек кривой без формулы для этой кривой?

да

И что означает "когда точки уже известны"? Они появились из ниоткуда сами собой без формулы?

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

[witcher_sense]

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

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