Как взять корень в порядке для закрытых ECDSA

[c2h5ohx]

Подскажите, как взять квадратный (кубический) корень в эллиптической кривой биткоина в порядке для закрытых ключей? И можно ли это сделать?

[~DefaultTrust]

Подскажите, как взять квадратный (кубический) корень в эллиптической кривой биткоина в порядке для закрытых ключей? И можно ли это сделать?

Как для любого другого 256-битного числа
Не знаю, может есть в готовых либах, но вот тут например чел квадратный корень объясняет как можно извлечь "своими руками": http://zonakoda.ru/zadacha-o-dlinnom-korne.html

[c2h5ohx]

p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
x = 64
y = pow(x, (p+1)/4, p)
print y
(y=8)

вопрос, как взять корень квадратный из 64 при p = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141

[~DefaultTrust]

y = pow(x, (p+1)/4, p)

Что делает третий аргумент в функции pow?

[c2h5ohx]

y = pow(x, (p+1)/4, p)

Что делает третий аргумент в функции pow?

модуль. а как же без него? Почему вас не заинтересовал второй параметр, а только третий...?!

ps: Люди кто понимает, прошу откликнуться.

[~DefaultTrust]

модуль.

Квадратный корень из 64 по модулю >= 8 будет равен восьми всегда, нет?

[c2h5ohx]

модуль.

Квадратный корень из 64 по модулю >= 8 будет равен восьми всегда, нет?

а из 0x111111111111111111 сколько будет?

[A-Bolt]

а из 0x111111111111111111 сколько будет?

Code:

import math

k = 0x111111111111111111
p = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
print(hex( math.floor( math.sqrt(k)) % p ) )

Только учтите, что операция взятия корня из числа, которое не является квадратом целого числа, при преобразовании к целому ведёт к потере точности.

В примере выше результат получается такой: 0x4219528b5, а квадрат 0x4219528b5 равен 0x111111110f132b0ff9, а не исходному 0x111111111111111111 за счёт потери точности при преобразовании к целому.

Поэтому, я надеюсь, вы хорошо понимаете зачем вам это надо.

Ну, и как уже выше было замечено, если известно, что всегда k <  p, то операцию модуля можно выкинуть.

[c2h5ohx]

берем порядок 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
извлекаем корень из 0x111111111111111111, получаем

0xe8a9ff3cbc2c327380ccfa8449c4b065575e01fd918b1f54743758db98ecb3dbL

операция возведения в квадрат..

0xe8a9ff3cbc2c327380ccfa8449c4b065575e01fd918b1f54743758db98ecb3dbL^2=
0xffffffffffffffffffffffffffffffffffffffffffffffeeeeeeeeedeeeeeb1eL

0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f-
0xffffffffffffffffffffffffffffffffffffffffffffffeeeeeeeeedeeeeeb1eL=

0x111111111111111111

так получается с любой циферкой при 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f

а вот.. при 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141 никак не выходит

[A-Bolt]

берем порядок 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
извлекаем корень из 0x111111111111111111, получаем

0xe8a9ff3cbc2c327380ccfa8449c4b065575e01fd918b1f54743758db98ecb3dbL

В результате какой последовательности операций получен этот результат?

[c2h5ohx]

берем порядок 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
извлекаем корень из 0x111111111111111111, получаем

0xe8a9ff3cbc2c327380ccfa8449c4b065575e01fd918b1f54743758db98ecb3dbL

В результате какой последовательности операций получен этот результат?

p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
x = 0x111111111111111111
y = pow(x, (p+1)/4, p)
print hex(y)

Но очень надо корень с порядком для закрытых ключей..!

К примеру...
Корень из 0x14ea15b59bf61ec94588L будет

cc=pow(0xbd058aada7bc0b85b2ad8fab552157b470d840f4583c22b3f0218ebb69f1b775L,2,
    0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141)
print hex(cc)

[A-Bolt]

p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
x = 0x111111111111111111
y = pow(x, (p+1)/4, p)
print hex(y)

Но очень надо корень с порядком для закрытых ключей..!

Я уже перестал что-либо понимать.
Вы называете результат этой операции pow(x, (p+1)/4, p) корнем? Но это ведь операция возведения в степень по модулю.

Вы придумали свою терминологию: корень с порядком, и рассчитываете, что вас кто-то поймёт?

[c2h5ohx]

p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
x = 0x111111111111111111
y = pow(x, (p+1)/4, p)
print hex(y)

Но очень надо корень с порядком для закрытых ключей..!

Я уже перестал что-либо понимать.
Вы называете результат этой операции pow(x, (p+1)/4, p) корнем? Но это ведь операция возведения в степень по модулю.

Вы придумали свою терминологию: корень с порядком, и рассчитываете, что вас кто-то поймёт?

все верно. Только это не я придумал, спецификация ecdsa. корень - есть возведение в степень.

[~DefaultTrust]

спецификация ecdsa. корень - есть возведение в степень.

Какбэ это задолго до ecdsa придумали, что корень - это возведение в степень ))
Только квадратным корнем общепринято считать возведение в степень 1/2, кубическим в степень 1/3 и т.д. Это в школе проходят.

(0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f + 1) /4 ну явно не равно 1/2 или 1/3. Если конечно деление не по модулю в каком-то экзотическом конечном поле из дробных чисел...

[~DefaultTrust]

Хорошие ссылки. В первой ссылке есть теория, из нее я наконец понял что автор топика сделать пытается...

Короче, чтобы найти y по известному x в уравнении
(1) y² = x³ + ax + b

надо, понятное дело, уметь брать корень квадратный. В конечном поле целых чисел корень надо искать по модулю.

(2) y² = x³ + ax + b = A (mod p)

Если уравнение (2) имеет целочисленное решение (для y по известному x), то число A в формуле (2) называется квадратичный вычет

По первой ссылке Captain-Cryptory есть теорема:

Если

(3) p = 3 (mod 4)

то в конечном поле целых чисел GF(p), уравнение (2) имеет следующее решение:

y = A^(p+1)/4 (mod p)

(В ссылке дана более общая теорема, я привел частный случай для m=1)

Ну и судя по тому, что у автора что-то не получается с этой формулой для p=0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
Я рискну предположить, что указанное p - не удовлетворяет условию (3)

[c2h5ohx]

Подскажите чайнику-автору , есть ли возможность вычислить квадратный корень, в итоге?

[~DefaultTrust]

Подскажите чайнику-автору , есть ли возможность вычислить квадратный корень, в итоге?

Дык вроде можно

[c2h5ohx]

Подскажите чайнику-автору , есть ли возможность вычислить квадратный корень, в итоге?

Дык вроде можно

Ну и как это реализовать? К примеру, корень из 2

[A-Bolt]

Ну и как это реализовать?

Там же в самом конце страницы есть ссылка на готовую реализацию на Питоне.

Только она под второй Питон. Если надо под третий, то вот:

Code:

def modular_sqrt(a, p):
    """ Find a quadratic residue (mod p) of 'a'. p
        must be an odd prime.

        Solve the congruence of the form:
            x^2 = a (mod p)
        And returns x. Note that p - x is also a root.

        0 is returned is no square root exists for
        these a and p.

        The Tonelli-Shanks algorithm is used (except
        for some simple cases in which the solution
        is known from an identity). This algorithm
        runs in polynomial time (unless the
        generalized Riemann hypothesis is false).
    """
    # Simple cases
    #
    if legendre_symbol(a, p) != 1:
        return 0
    elif a == 0:
        return 0
    elif p == 2:
        return 0
    elif p % 4 == 3:
        return pow(a, (p + 1) // 4, p)

    # Partition p-1 to s * 2^e for an odd s (i.e.
    # reduce all the powers of 2 from p-1)
    #
    s = p - 1
    e = 0
    while s % 2 == 0:
        s //= 2
        e += 1

    # Find some 'n' with a legendre symbol n|p = -1.
    # Shouldn't take long.
    #
    n = 2
    while legendre_symbol(n, p) != -1:
        n += 1

    # Here be dragons!
    # Read the paper "Square roots from 1; 24, 51,
    # 10 to Dan Shanks" by Ezra Brown for more
    # information
    #

    # x is a guess of the square root that gets better
    # with each iteration.
    # b is the "fudge factor" - by how much we're off
    # with the guess. The invariant x^2 = ab (mod p)
    # is maintained throughout the loop.
    # g is used for successive powers of n to update
    # both a and b
    # r is the exponent - decreases with each update
    #
    x = pow(a, (s + 1) // 2, p)
    b = pow(a, s, p)
    g = pow(n, s, p)
    r = e

    while True:
        t = b
        m = 0
        for m in range(r):
            if t == 1:
                break
            t = pow(t, 2, p)

        if m == 0:
            return x

        gs = pow(g, 2 ** (r - m - 1), p)
        g = (gs * gs) % p
        x = (x * gs) % p
        b = (b * g) % p
        r = m


def legendre_symbol(a, p):
    """ Compute the Legendre symbol a|p using
        Euler's criterion. p is a prime, a is(
        relatively prime to p (if p divides
        a, then a|p = 0)

        Returns 1 if a has a square root modulo
        p, -1 otherwise.
    """
    ls = pow(a, (p - 1) // 2, p)
    return -1 if ls == p - 1 else ls
	
	

k = 0x2
p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

r = modular_sqrt(k, p)
print(hex(r))

[c2h5ohx]

Спасибо всем огромное! Выручили, работает!