Title: Как взять корень в порядке для закрытых ECDSA Post by: c2h5ohx on August 04, 2021, 08:48:40 PM Подскажите, как взять квадратный (кубический) корень в эллиптической кривой биткоина в порядке для закрытых ключей? И можно ли это сделать?
Title: Re: Как взять корень в порядке для закрытых ECDSA Post by: ~DefaultTrust on August 05, 2021, 08:41:10 AM Подскажите, как взять квадратный (кубический) корень в эллиптической кривой биткоина в порядке для закрытых ключей? И можно ли это сделать? Как для любого другого 256-битного числаНе знаю, может есть в готовых либах, но вот тут например чел квадратный корень объясняет как можно извлечь "своими руками": http://zonakoda.ru/zadacha-o-dlinnom-korne.html Title: Re: Как взять корень в порядке для закрытых ECDSA Post by: c2h5ohx on August 05, 2021, 02:21:09 PM p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
x = 64 y = pow(x, (p+1)/4, p) print y (y=8) вопрос, как взять корень квадратный из 64 при p = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141 Title: Re: Как взять корень в порядке для закрытых ECDSA Post by: ~DefaultTrust on August 05, 2021, 03:11:03 PM y = pow(x, (p+1)/4, p) Что делает третий аргумент в функции pow?Title: Re: Как взять корень в порядке для закрытых ECDSA Post by: c2h5ohx on August 05, 2021, 03:21:43 PM y = pow(x, (p+1)/4, p) Что делает третий аргумент в функции pow?модуль. а как же без него? :) Почему вас не заинтересовал второй параметр, а только третий...?! ps: Люди кто понимает, прошу откликнуться. Title: Re: Как взять корень в порядке для закрытых ECDSA Post by: ~DefaultTrust on August 05, 2021, 03:45:05 PM модуль. Квадратный корень из 64 по модулю >= 8 будет равен восьми всегда, нет? Title: Re: Как взять корень в порядке для закрытых ECDSA Post by: c2h5ohx on August 08, 2021, 06:56:50 AM модуль. Квадратный корень из 64 по модулю >= 8 будет равен восьми всегда, нет? а из 0x111111111111111111 сколько будет? Title: Re: Как взять корень в порядке для закрытых ECDSA Post by: A-Bolt on August 08, 2021, 09:32:18 AM а из 0x111111111111111111 сколько будет? Code: import math Только учтите, что операция взятия корня из числа, которое не является квадратом целого числа, при преобразовании к целому ведёт к потере точности. В примере выше результат получается такой: 0x4219528b5, а квадрат 0x4219528b5 равен 0x111111110f132b0ff9, а не исходному 0x111111111111111111 за счёт потери точности при преобразовании к целому. Поэтому, я надеюсь, вы хорошо понимаете зачем вам это надо. Ну, и как уже выше было замечено, если известно, что всегда k < p, то операцию модуля можно выкинуть. Title: Re: Как взять корень в порядке для закрытых ECDSA Post by: c2h5ohx on August 09, 2021, 06:55:52 AM берем порядок 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
извлекаем корень из 0x111111111111111111, получаем 0xe8a9ff3cbc2c327380ccfa8449c4b065575e01fd918b1f54743758db98ecb3dbL операция возведения в квадрат.. 0xe8a9ff3cbc2c327380ccfa8449c4b065575e01fd918b1f54743758db98ecb3dbL^2= 0xffffffffffffffffffffffffffffffffffffffffffffffeeeeeeeeedeeeeeb1eL 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f- 0xffffffffffffffffffffffffffffffffffffffffffffffeeeeeeeeedeeeeeb1eL= 0x111111111111111111 так получается с любой циферкой при 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f а вот.. при 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141 никак не выходит :( Title: Re: Как взять корень в порядке для закрытых ECDSA Post by: A-Bolt on August 09, 2021, 08:16:06 AM берем порядок 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f извлекаем корень из 0x111111111111111111, получаем 0xe8a9ff3cbc2c327380ccfa8449c4b065575e01fd918b1f54743758db98ecb3dbL В результате какой последовательности операций получен этот результат? Title: Re: Как взять корень в порядке для закрытых ECDSA Post by: c2h5ohx on August 09, 2021, 08:48:32 AM берем порядок 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) Title: Re: Как взять корень в порядке для закрытых ECDSA Post by: A-Bolt on August 09, 2021, 09:26:07 AM p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f x = 0x111111111111111111 y = pow(x, (p+1)/4, p) print hex(y) Но очень надо корень с порядком для закрытых ключей..! Я уже перестал что-либо понимать. Вы называете результат этой операции pow(x, (p+1)/4, p) корнем? Но это ведь операция возведения в степень по модулю. Вы придумали свою терминологию: корень с порядком, и рассчитываете, что вас кто-то поймёт? Title: Re: Как взять корень в порядке для закрытых ECDSA Post by: c2h5ohx on August 09, 2021, 09:42:15 AM p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f x = 0x111111111111111111 y = pow(x, (p+1)/4, p) print hex(y) Но очень надо корень с порядком для закрытых ключей..! Я уже перестал что-либо понимать. Вы называете результат этой операции pow(x, (p+1)/4, p) корнем? Но это ведь операция возведения в степень по модулю. Вы придумали свою терминологию: корень с порядком, и рассчитываете, что вас кто-то поймёт? все верно. Только это не я придумал, спецификация ecdsa. корень - есть возведение в степень. Title: Re: Как взять корень в порядке для закрытых ECDSA Post by: ~DefaultTrust on August 09, 2021, 02:17:11 PM спецификация ecdsa. корень - есть возведение в степень. Какбэ это задолго до ecdsa придумали, что корень - это возведение в степень ))Только квадратным корнем общепринято считать возведение в степень 1/2, кубическим в степень 1/3 и т.д. Это в школе проходят. (0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f + 1) /4 ну явно не равно 1/2 или 1/3. Если конечно деление не по модулю в каком-то экзотическом конечном поле из дробных чисел... Title: Re: Как взять корень в порядке для закрытых ECDSA Post by: ~DefaultTrust on August 09, 2021, 03:12:18 PM Хорошие ссылки. В первой ссылке есть теория, из нее я наконец понял что автор топика сделать пытается...
Короче, чтобы найти y по известному x в уравнении (1) y2 = x3 + ax + b надо, понятное дело, уметь брать корень квадратный. В конечном поле целых чисел корень надо искать по модулю. (2) y2 = x3 + ax + b = A (mod p) Если уравнение (2) имеет целочисленное решение (для y по известному x), то число A в формуле (2) называется квадратичный вычет (https://ru.wikipedia.org/wiki/%D0%9A%D0%B2%D0%B0%D0%B4%D1%80%D0%B0%D1%82%D0%B8%D1%87%D0%BD%D1%8B%D0%B9_%D0%B2%D1%8B%D1%87%D0%B5%D1%82) По первой ссылке Captain-Cryptory есть теорема: Если (3) p = 3 (mod 4) то в конечном поле целых чисел GF(p), уравнение (2) имеет следующее решение: y = A(p+1)/4 (mod p) (В ссылке дана более общая теорема, я привел частный случай для m=1) Ну и судя по тому, что у автора что-то не получается с этой формулой для p=0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141 Я рискну предположить, что указанное p - не удовлетворяет условию (3) Title: Re: Как взять корень в порядке для закрытых ECDSA Post by: c2h5ohx on August 09, 2021, 05:08:01 PM Подскажите чайнику-автору , есть ли возможность вычислить квадратный корень, в итоге?
Title: Re: Как взять корень в порядке для закрытых ECDSA Post by: ~DefaultTrust on August 09, 2021, 05:33:42 PM Подскажите чайнику-автору , есть ли возможность вычислить квадратный корень, в итоге? Дык вроде можно (https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%A2%D0%BE%D0%BD%D0%B5%D0%BB%D0%BB%D0%B8_%E2%80%94_%D0%A8%D0%B5%D0%BD%D0%BA%D1%81%D0%B0) Title: Re: Как взять корень в порядке для закрытых ECDSA Post by: c2h5ohx on August 09, 2021, 06:33:35 PM Подскажите чайнику-автору , есть ли возможность вычислить квадратный корень, в итоге? Дык вроде можно (https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%A2%D0%BE%D0%BD%D0%B5%D0%BB%D0%BB%D0%B8_%E2%80%94_%D0%A8%D0%B5%D0%BD%D0%BA%D1%81%D0%B0) Ну и как это реализовать? К примеру, корень из 2 Title: Re: Как взять корень в порядке для закрытых ECDSA Post by: A-Bolt on August 09, 2021, 06:41:33 PM Ну и как это реализовать? Там же в самом конце страницы есть ссылка на готовую реализацию на Питоне (http://eli.thegreenplace.net/2009/03/07/computing-modular-square-roots-in-python). Только она под второй Питон. Если надо под третий, то вот: Code: def modular_sqrt(a, p): Title: Re: Как взять корень в порядке для закрытых ECDSA Post by: c2h5ohx on August 10, 2021, 05:48:11 AM Спасибо всем огромное! Выручили, работает!
|