Pages:
Author

Topic: Как взять корень в порядке для закрытых ECDSA (Read 353 times)

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


Конечно можно. Для secp256k1 в силу специфики выбранных для нее параметров  конечное выражение  выглядит довольно просто. Квадратный корень из a вычисляется из такого равенства:

a = ±a(p+1)/4 (mod p) , p ≡ 3 (mod 4)

Рекомендую почитать эту тему и обратить свое внимание  на второй ее пост.

ЁПТ: первоначально ошибся - забыл знак  степени поставить, сейчас равенство правильное.
newbie
Activity: 16
Merit: 0
Спасибо всем огромное! Выручили, работает!
legendary
Activity: 2301
Merit: 2269
Ну и как это реализовать?

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

Только она под второй Питон. Если надо под третий, то вот:
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))
newbie
Activity: 16
Merit: 0
Подскажите чайнику-автору , есть ли возможность вычислить квадратный корень, в итоге?
Дык вроде можно

Ну и как это реализовать? К примеру, корень из 2
copper member
Activity: 1498
Merit: 487
Stop the war!
Подскажите чайнику-автору , есть ли возможность вычислить квадратный корень, в итоге?
Дык вроде можно
newbie
Activity: 16
Merit: 0
Подскажите чайнику-автору , есть ли возможность вычислить квадратный корень, в итоге?
copper member
Activity: 1498
Merit: 487
Stop the war!
Хорошие ссылки. В первой ссылке есть теория, из нее я наконец понял что автор топика сделать пытается...

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

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

(2) y2 = x3 + 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)
copper member
Activity: 1498
Merit: 487
Stop the war!
спецификация ecdsa. корень - есть возведение в степень.
Какбэ это задолго до ecdsa придумали, что корень - это возведение в степень ))
Только квадратным корнем общепринято считать возведение в степень 1/2, кубическим в степень 1/3 и т.д. Это в школе проходят.

(0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f + 1) /4 ну явно не равно 1/2 или 1/3. Если конечно деление не по модулю в каком-то экзотическом конечном поле из дробных чисел...
newbie
Activity: 16
Merit: 0
p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
x = 0x111111111111111111
y = pow(x, (p+1)/4, p)
print hex(y)

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

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

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

все верно. Только это не я придумал, спецификация ecdsa. корень - есть возведение в степень.
legendary
Activity: 2301
Merit: 2269
p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
x = 0x111111111111111111
y = pow(x, (p+1)/4, p)
print hex(y)

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

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

Вы придумали свою терминологию: корень с порядком, и рассчитываете, что вас кто-то поймёт?
newbie
Activity: 16
Merit: 0
берем порядок 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)
legendary
Activity: 2301
Merit: 2269
берем порядок 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
извлекаем корень из 0x111111111111111111, получаем

0xe8a9ff3cbc2c327380ccfa8449c4b065575e01fd918b1f54743758db98ecb3dbL

В результате какой последовательности операций получен этот результат?
newbie
Activity: 16
Merit: 0
берем порядок 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
извлекаем корень из 0x111111111111111111, получаем

0xe8a9ff3cbc2c327380ccfa8449c4b065575e01fd918b1f54743758db98ecb3dbL

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

0xe8a9ff3cbc2c327380ccfa8449c4b065575e01fd918b1f54743758db98ecb3dbL^2=
0xffffffffffffffffffffffffffffffffffffffffffffffeeeeeeeeedeeeeeb1eL

0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f-
0xffffffffffffffffffffffffffffffffffffffffffffffeeeeeeeeedeeeeeb1eL=

0x111111111111111111

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

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

legendary
Activity: 2301
Merit: 2269
а из 0x111111111111111111 сколько будет?

Code:
import math

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

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

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

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

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

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

а из 0x111111111111111111 сколько будет?
copper member
Activity: 1498
Merit: 487
Stop the war!
модуль.

Квадратный корень из 64 по модулю >= 8 будет равен восьми всегда, нет?
newbie
Activity: 16
Merit: 0
y = pow(x, (p+1)/4, p)
Что делает третий аргумент в функции pow?

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

ps: Люди кто понимает, прошу откликнуться.
copper member
Activity: 1498
Merit: 487
Stop the war!
y = pow(x, (p+1)/4, p)
Что делает третий аргумент в функции pow?
newbie
Activity: 16
Merit: 0
p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
x = 64
y = pow(x, (p+1)/4, p)
print y
(y=8)

вопрос, как взять корень квадратный из 64 при p = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
copper member
Activity: 1498
Merit: 487
Stop the war!
Подскажите, как взять квадратный (кубический) корень в эллиптической кривой биткоина в порядке для закрытых ключей? И можно ли это сделать?
Как для любого другого 256-битного числа
Не знаю, может есть в готовых либах, но вот тут например чел квадратный корень объясняет как можно извлечь "своими руками": http://zonakoda.ru/zadacha-o-dlinnom-korne.html
Pages:
Jump to: