Topic: Вопрос по эллипт кривой, непонятен ОДИН ша&#1 (Read 685 times)

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

да


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

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


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

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

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


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


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

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

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

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

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

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

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

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

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

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

Нашёл другой способ вычисления публичного ключа из приватного, в котором последний раскладывать по степеням совсем не обязательно!
Если приватник выражается 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.
Претензии по качеству софта не принимаются - я не программист.

При использовании 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.
Претензии по качеству софта не принимаются - я не программист.

ваще не понимают
https://bitcointalksearch.org/topic/m.59554567

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

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

Почему считал по степени 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.