Bitcoin Forum

Поясните пожалуйста. Я перегуглил и пересмотрел все и вся. Но нигде и никто конкретно не объясняет как происходит сложение точки на кривой с самой собой. Много воды и мало конкретики.

Согласно тому, что я нашел некомпрес паблик это координаты xy
Получаются они путем сложения совершенно определенных координат xy с самими собой КОЛИЧЕСТВОМ раз равным размеру приват ключа.

на пальцах:

координаты
G(x) = 55066263022277343669578718895168534326250603453777594175500187360389116729240
G(y) = 32670510020758816978083085130507043184471273380659243275938904335757337482424

приват кей, пусть будет в децимал и для наглядности = 10 или в бинари 1010
Если мы используем известные библиотеки преобразования и решим получить паблик от децимальных 10
то получим паблик с децимальными координатами
x = 72488970228380509287422715226575535698893157273063074627791787432852706183111
y = 62070622898698443831883535403436258712770888294397026493185421712108624767191

Я не разбираюсь ПОКА в формулах сложения, еще темный лес, меня не это интересует - меня интересует вот эта фраза - КОЛИЧЕСТВОМ РАВНЫМ размеру приват ключа.
С десяткой получить вычисления сложения точек просто, но если реальный приват будет 2^255 - то сколько времени должно занять вычисление???
Однако любой софт это делает также быстро как и для вычисления десятки. Еще я встречал, что количество сложений не может быть более 256 (или 512 раз)
А значит всего скорее вычисление идет как то по бинарному моду НО КАК?

Кто нибудь может объяснить какое именно количество раз складываются точки и как это зависит от приват кея?

Спасибо!

Доступно о криптографии на эллиптических кривых (https://habr.com/ru/post/335906/) - эту статью смотрели?

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

конкретно про биткоин никто ничего не говорит.

Просто на пальцах, сколько раз умножаем точку - как это зависит от приватки - это все опускается. 

Дык, вот же (https://habr.com/ru/post/335906/):

Публичный ключ H - это точка на эллиптической кривой над конечным полем, получаемая путём операции скалярного умножения приватного ключа - скаляра d и базовой точки G, то есть, H = dG.

Если приватный ключ равен 1, то публичный ключ от этого приватного ключа равен 1G, для приватного ключа 2 публичный равен 2G и т. д.

а если приватный ключ равен 2^256?

Это число не подходит для приватного ключа. Приватный ключ должен быть меньше порядка группы n. Для secp256k1 n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141, что меньше чем 2²⁵⁶.

ок, 2 в 255. Что тогда? Ты же понимаешь что не может быть вычислений такого количества. Я собсно все в первом посте это написал, и как я понимаю, ты тоже не знаешь как считается точка.

Да всем по барабану как оно считается. Есть отлаженные либы на всех возможных ЯП. Вы диплом что ли пишете? Кому сильно надо - берет исходники и читает. На сях трушные прогеры обычно нормально код комментят.

ЗЫ: от сюда (https://ru.wikipedia.org/wiki/%D0%94%D0%BB%D0%B8%D0%BD%D0%BD%D0%B0%D1%8F_%D0%B0%D1%80%D0%B8%D1%84%D0%BC%D0%B5%D1%82%D0%B8%D0%BA%D0%B0) может плясать начинать?

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

Умножение на приватник - это умножение на любое число от 1 до FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141
В принципе можно умножать и на бОльшее число, но результатом умножения все равно будет число от 1 до FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141
Я так понял, что основной-то вопрос не в этом, а в том: как именно, каким алгоритмом идет умножение.

Ну можно начать гуглить с выделенных на этой картинке слов тогда:
https://i.imgur.com/mSQVIm9.jpg

я все это знаю. более того ПИСАЛ даже про этот алгоритм выше.

но кто КОНКРЕТНО может ответить КАК умножается? Здесь же раздел для кодеров? КАК вы умножаете? Не отсылка к переведенной статье а как реально умножается? раздел кодеров, а никто не знает?

Форум про биток. Раздел кодеров. Кодеры в битке умножают с помощью либы опенссл. Как умножают кодеры в опенссл - лучше наверно спросить у них на гитхабе.

ЗЫ походу дела вот это алгоритм в опенссл (https://github.com/openssl/openssl/blob/master/crypto/ec/ec_mult.c#L117) используется: https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication#Montgomery_ladder

Классная статья, лучше всех, которые довелось видеть до этой! После НГ надо обязательно внимательно прочесть.


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

Например (аналогично смотрите в статье), 23 * G = 2^4 * G + 2^2 * G + 2^1 * G + 1 * G = G4 + G2 + G1 + G0, где
G4 = G3 + G3 (G3 = G2 + G2), G2 = G1 + G1, G1 = G0 + G0, G0 = G.

Теперь, почему полученные числа не превысят значений больше 78 разрядов, смотрите раздел "Поле целых чисел по модулю p".

Сложение на эллиптических кривых - это не просто привычное для всех арифметическое сложение. Здесь сложение определяется пересечением кривой y^2 = x^3 + 7 прямой линией, используя замечательное свойство кривой: любая прямая (не вертикальная), пересекающая кривую в двух точках, всегда будет пересекать ее и в третьей точке (за исключением касательной, которая пересечёт её ровно в ещё одной точке).
О сложении смотрите разделы "Геометрическое сложение" и "Алгебраическое сложение".

Публичный ключ - это произведение базовой точки и приватного ключа. Для ключа = 1 получаем базовую точку:
x = 79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798 (dec = 55066263022277343669578718895168534326250603453777594175500187360389116729240)
y = 483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8 (dec = 32670510020758816978083085130507043184471273380659243275938904335757337482424)

Чтобы умножить базовую точку на ключ = 2^255, нужно всего-навсего 255 раз провести операцию удвоения (сложения с самой собой), начиная со сложения базовой точки G. Это любому компьютеру сделать под силу за доли секунды.

все было неплохо до этого момента.
почему 255? ты по степени посчитал? а что делать если у меня ключ 2^255-1 (просто минус, не степень. это будет число 57896044618658097711785492504343953926634992332820282019728792003956564819967)? как ты его считать будешь?

Почему считал по степени 255.
Если ключ = 2^1 = 2, то публ. ключ = G1 = 2 * G0 = (G0 + G0), G0 = G (одно удвоение)
Если ключ = 2^2 = 4, то публ. ключ = 4 * G0 = 2 * G1 = G1 + G1 = (G0 + G0) + (G0 + G0)  (два удвоения)
...
Если ключ = 2^255, то публ. ключ = 2^255 * G0 = 2^254 * (G0 + G0) = 2^254 * G1 = 2^253 * (G1 + G1) = 2^253 * [(G0 + G0) + (G0 + G0)] = ...   (255 удвоений)

----------------------------------------
Ключ = 2^255 - 1.
Если решать задачу в лоб для ключа = 2^255 - 1, всё оказывается достаточно просто:
2^255 - 1 = 2^254 + 2^253 + 2^252 + ... + 2^2 + 2^1 + 2^0
Складывайте 255 слагаемых и будет Вам счастье.

Если пойти немного более сложным путём (но всё равно, простым) и строго придерживаться правила сложения, то получается ещё гораздо проще:
(2^255 - 1) * G = 2^255 * G + (-G),
где -G = (x, -y), если G = (x, y)
Далее опять смотрите раздел "Алгебраическое сложение".

P.S.
(Частный случай) любое число до 2^256 может быть единственным образом представлено суммой ортогональных многочленов со степенью не более 255.

сча в браузере поискал на этой странице галуа или galois . Ну вы даете бля

Довольно один раз вычислить все точки от одного удвоения G до 255 удвоений и затем лишь складывать эти готовые точки в зависимости от приватника. А не вычислять все полностью каждый раз. Например для простоты маленькое число приватник: 100000000000001000000100000000000000001 здесь надо сложить 4 уже вычисленные точки, G+17G+24G+38G т.е. 3 сложения. Удвоений делать не нужно, если все уже посчитано давно. Поэтому быстро.

ваще не понимают
https://bitcointalk.org/index.php?topic=5389003.msg59554567#msg59554567

При использовании N = 2 в качестве основания степени максимальное количество слагаемых - 255 (не 256 !), соответственно, максимальное количество сложений - 254.
Если использовать N больше двойки, макс. количество слагаемых будет уменьшаться. Например, для 3 - 162, для 16 - 64, для 1024 - 26, для 1 048 576 = 2^20 - 13. В последнем случае база публичных ключей содержит 12 648 435 элементов и в памяти компьютера занимает 3,750 GB.
Для современного компьютера это не проблематично (в моём натыкано 8 модулей по 16 GB каждый).

Ради интереса "склепал" программку на Python-е. Сравнение по скорости стандартной библиотеки и "склёпанной" не в пользу последней. :(
Использование словаря / разложение по степеням - неоптимальные варианты?
Хотя при больших N и относительно небольших числах в качестве ключей результат противоположный.

Программка (без защиты от кривых рук):

import math
import datetime
import binascii, ecdsa

# --------------------------- Разложение числа по степеням другого числа ---------------------------

def pow_num(a, b):
    R = []
    M = int(round((math.log(a) / math.log(b)), 0))
    if b**M > a: M = M - 1
    for i in range(M + 1):
        k = M - i
        p = a // (b ** k)
        if p * b ** k > a:
            R.append(0)
        else:
            R.append(p)
            a = a - p * b ** k
    R.reverse()
    return R

# ----------------------------------- Сложение публичных ключей ------------------------------------

def EC_Add(P, Q):
    if P == '0': return Q
    if Q == '0': return P
    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, p - 2, p)
    else:
        dydx = (qy - py) * pow(qx - px, p - 2, 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)

# ---------------------------- Публичный ключ из приватного (библиотека) ---------------------------

def U_pub(x):
    hexPrv = hex(x)[2:].zfill(64)
    sk = ecdsa.SigningKey.from_string(binascii.unhexlify(hexPrv.encode()), curve=ecdsa.SECP256k1)
    vk = sk.get_verifying_key()
    return '04' + binascii.hexlify(vk.to_string()).decode()

# --------------------------------------------------------------------------------------------------

# p = 115792089237316195423570985008687907853269984665640564039457584007908834671663
Max = 115792089237316195423570985008687907852837564279074904382605163141518161494336
# P1 = '0479be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798483ada7726a3c 4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8'

N = int(input('Введите основание для разложения по степеням : '))

Pow = pow_num(Max, N)

N_p = len(Pow) # количество степеней (0 включительно)

D_N = dict()

for i in range(N_p - 1):
    for k in range(N - 1):
        D_N[str(k + 1).zfill(len(str(N))) + str(i).zfill(len(str(N_p)))] = U_pub((k + 1)*N**i)

N1 = Pow[-1]

for k in range(N1):
    D_N[str(k + 1).zfill(len(str(N))) + str(N_p - 1).zfill(len(str(N_p)))] = U_pub((k + 1)*N**(N_p - 1))

print('Размер базы :', len(D_N))
print('Макс. к-во слагаемых :', N_p)

PK_0 = int(input('Введите приватный ключ: ("0" - завершение программы) '))
if PK_0 > Max: PK_0 = int(str(PK_0)[:77])

while PK_0 != 0:

    MM = int(input('Введите число итераций : '))

    date_1 = datetime.datetime.today()

    for k in range(MM):
        PK = PK_0 + k
        Pow_key = pow_num(PK, N)
        P = '0'
        for m in range(len(Pow_key)):
            if Pow_key[m] != 0:
                Q = D_N[str(Pow_key[m]).zfill(len(str(N))) + str(m).zfill(len(str(N_p)))]
                P = EC_Add(P, Q)

    date_2 = datetime.datetime.today()
    print('продолжительность :', date_2 - date_1)

    print('Key =', PK, '; P =', P)

    date_1 = datetime.datetime.today()

    for k in range(MM):
        PK = PK_0 + k
        P = U_pub(PK)

    date_2 = datetime.datetime.today()
    print('продолжительность :', date_2 - date_1)

    print('Key =', PK, '; P =', P)

    PK_0 = int(input('Введите приватный ключ: ("0" - завершение программы) '))
    if PK_0 > Max: PK_0 = int(str(PK_0)[:77])

P.S.
Претензии по качеству софта не принимаются - я не программист.

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

Сумма:
1) F000...............0000
2) 0100...............0000
3) 00F0...............0000
4) 0003...............0000
................................
61) 0000...............A000
62) 0000...............0B00
63) 0000...............0030
64) 0000...............0008

Зная публичные ключи для каждого из указанных слагаемых, искомый публичник для Key будет просто равен их сумме.
Максимальное число слагаемых - 64.
Поскольку интересны только 15 значений (от 1 до F), общая база ключей составит всего 15*64 = 960 элементов.
Пока писал "пробную" программку, пришла идея для уменьшения числа слагаемых (увеличения скорости расчёта)
разбивать приватник не по одному элементу, а по четыре:
Получаем сумму:
1) F1F30000...................00000000
2) 0000BE4B...................00000000
.................................................
15) 00000000...................2D9F0000
16) 00000000...................0000AB38

В этом случае максимальное число слагаемых составит всего 16, а общее количество публичных ключей в базе = 16^4 * 16 - 16 = 1 048 560
(- 16 означает игнорирование "нулевых" значений).

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

Программка второго варианта (без защиты от кривых рук):

import binascii, ecdsa
import datetime

# ----------------------------------- Сложение публичных ключей ------------------------------------

def EC_Add(P, Q):
    if P == '0': return Q
    if Q == '0': return P
    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, p - 2, p)
    else:
        dydx = (qy - py) * pow(qx - px, p - 2, 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)

# --------------------- Публичный ключ от произвольного числа HEX (библиотека) ---------------------

def U_pub(x):
    sk = ecdsa.SigningKey.from_string(binascii.unhexlify(x.encode()), curve=ecdsa.SECP256k1)
    vk = sk.get_verifying_key()
    return '04' + binascii.hexlify(vk.to_string()).decode()

# --------------------------------------------------------------------------------------------------


Max = 115792089237316195423570985008687907852837564279074904382605163141518161494336

simbols = '0123456789abcdef'

Base_pub = dict()

print('Ждите, идёт создание базы публичных ключей ...')

for i in range(16):
    for k in range(16):
        for m in range(16):
            for n in range(16):
                for q in range(16):
                    if (str(simbols[k:k + 1]) + str(simbols[m:m + 1]) + str(simbols[n:n + 1]) + str(simbols[q:q + 1])) != '0000':
                        Base_pub[str(i * 4 + 1).zfill(2) + str(simbols[k:k + 1]) + str(simbols[m:m + 1]) + str(simbols[n:n + 1]) + str(simbols[q:q + 1])] = U_pub('0' * (i * 4) + (simbols[k:k + 1] + simbols[m:m + 1] + simbols[n:n + 1] + simbols[q:q + 1] + '0' * (60 - i * 4)))

print('Ключей в базе :', len(Base_pub))

PK_0 = int(input('Введите приватный ключ: ("0" - завершение программы) '))
if PK_0 > Max: PK_0 = int(str(PK_0)[:77])

while PK_0 != 0:

    MM = int(input('Введите число итераций : '))

    date_1 = datetime.datetime.today()

    for k in range(MM):
        PK = PK_0 + k
        hexPrv = hex(PK)[2:66].zfill(64)

        Priv_set = set()

        P = '0'

        for i in range(16):
            if hexPrv[i * 4:i * 4 + 4] != '0000':
                Priv_set.add(Base_pub[str(i * 4 + 1).zfill(2) + hexPrv[i * 4:i * 4 + 4]])

        for i in Priv_set:
            P = EC_Add(P, i)

    date_2 = datetime.datetime.today()
    print('продолжительность :', date_2 - date_1)

    print('Key =', PK, '; P =', P)

    date_1 = datetime.datetime.today()

    for i in range(MM):
        PK = PK_0 + k
        P = U_pub(hex(PK)[2:66].zfill(64))

    date_2 = datetime.datetime.today()
    print('продолжительность :', date_2 - date_1)

    print('Key =', PK, '; P =', P)

    PK_0 = int(input('Введите приватный ключ: ("0" - завершение программы) '))
    if PK_0 > Max: PK_0 = int(str(PK_0)[:77])

P.S.
Претензии по качеству софта не принимаются - я не программист.

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

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

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

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

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

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

По 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 применить можно. Но для точного ответа надо досконально знать эту тему. Может, это уже работает в современных библиотеках? С ответом напряг, программисты, похоже, здесь не живут.

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

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


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


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

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

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


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

да


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

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