c2h5ohx (OP)
Newbie
Offline
Activity: 16
Merit: 0
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
August 04, 2021, 08:48:40 PM |
|
Подскажите, как взять квадратный (кубический) корень в эллиптической кривой биткоина в порядке для закрытых ключей? И можно ли это сделать?
|
|
|
|
~DefaultTrust
Copper Member
Sr. Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif) ![*](https://bitcointalk.org/Themes/custom1/images/star.gif) ![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 1554
Merit: 489
Stop the war!
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
August 05, 2021, 08:41:10 AM Merited by Symmetrick (1) |
|
Подскажите, как взять квадратный (кубический) корень в эллиптической кривой биткоина в порядке для закрытых ключей? И можно ли это сделать?
Как для любого другого 256-битного числа Не знаю, может есть в готовых либах, но вот тут например чел квадратный корень объясняет как можно извлечь "своими руками": http://zonakoda.ru/zadacha-o-dlinnom-korne.html
|
Do not trust bitcointalk fascists: leonello; Snork1979; ivan1975
|
|
|
c2h5ohx (OP)
Newbie
Offline
Activity: 16
Merit: 0
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
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
|
|
|
|
~DefaultTrust
Copper Member
Sr. Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif) ![*](https://bitcointalk.org/Themes/custom1/images/star.gif) ![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 1554
Merit: 489
Stop the war!
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
August 05, 2021, 03:11:03 PM |
|
y = pow(x, (p+1)/4, p)
Что делает третий аргумент в функции pow?
|
Do not trust bitcointalk fascists: leonello; Snork1979; ivan1975
|
|
|
c2h5ohx (OP)
Newbie
Offline
Activity: 16
Merit: 0
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
August 05, 2021, 03:21:43 PM |
|
y = pow(x, (p+1)/4, p)
Что делает третий аргумент в функции pow? модуль. а как же без него? ![Smiley](https://bitcointalk.org/Smileys/default/smiley.gif) Почему вас не заинтересовал второй параметр, а только третий...?! ps: Люди кто понимает, прошу откликнуться.
|
|
|
|
~DefaultTrust
Copper Member
Sr. Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif) ![*](https://bitcointalk.org/Themes/custom1/images/star.gif) ![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 1554
Merit: 489
Stop the war!
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
August 05, 2021, 03:45:05 PM |
|
модуль.
Квадратный корень из 64 по модулю >= 8 будет равен восьми всегда, нет?
|
Do not trust bitcointalk fascists: leonello; Snork1979; ivan1975
|
|
|
c2h5ohx (OP)
Newbie
Offline
Activity: 16
Merit: 0
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
August 08, 2021, 06:56:50 AM |
|
модуль.
Квадратный корень из 64 по модулю >= 8 будет равен восьми всегда, нет? а из 0x111111111111111111 сколько будет?
|
|
|
|
A-Bolt
Legendary
Offline
Activity: 2325
Merit: 2363
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
August 08, 2021, 09:32:18 AM |
|
а из 0x111111111111111111 сколько будет?
import math
k = 0x111111111111111111 p = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141 print(hex( math.floor( math.sqrt(k)) % p ) )
Только учтите, что операция взятия корня из числа, которое не является квадратом целого числа, при преобразовании к целому ведёт к потере точности. В примере выше результат получается такой: 0x4219528b5, а квадрат 0x4219528b5 равен 0x111111110f132b0ff9, а не исходному 0x111111111111111111 за счёт потери точности при преобразовании к целому. Поэтому, я надеюсь, вы хорошо понимаете зачем вам это надо. Ну, и как уже выше было замечено, если известно, что всегда k < p, то операцию модуля можно выкинуть.
|
|
|
|
c2h5ohx (OP)
Newbie
Offline
Activity: 16
Merit: 0
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
August 09, 2021, 06:55:52 AM |
|
берем порядок 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f извлекаем корень из 0x111111111111111111, получаем 0xe8a9ff3cbc2c327380ccfa8449c4b065575e01fd918b1f54743758db98ecb3dbL операция возведения в квадрат.. 0xe8a9ff3cbc2c327380ccfa8449c4b065575e01fd918b1f54743758db98ecb3dbL^2= 0xffffffffffffffffffffffffffffffffffffffffffffffeeeeeeeeedeeeeeb1eL 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f- 0xffffffffffffffffffffffffffffffffffffffffffffffeeeeeeeeedeeeeeb1eL= 0x111111111111111111 так получается с любой циферкой при 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f а вот.. при 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141 никак не выходит ![Sad](https://bitcointalk.org/Smileys/default/sad.gif)
|
|
|
|
A-Bolt
Legendary
Offline
Activity: 2325
Merit: 2363
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
August 09, 2021, 08:16:06 AM |
|
берем порядок 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f извлекаем корень из 0x111111111111111111, получаем
0xe8a9ff3cbc2c327380ccfa8449c4b065575e01fd918b1f54743758db98ecb3dbL
В результате какой последовательности операций получен этот результат?
|
|
|
|
c2h5ohx (OP)
Newbie
Offline
Activity: 16
Merit: 0
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
August 09, 2021, 08:48:32 AM Last edit: August 09, 2021, 11:05:12 AM by xandry |
|
берем порядок 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
Legendary
Offline
Activity: 2325
Merit: 2363
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
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) корнем? Но это ведь операция возведения в степень по модулю. Вы придумали свою терминологию: корень с порядком, и рассчитываете, что вас кто-то поймёт?
|
|
|
|
c2h5ohx (OP)
Newbie
Offline
Activity: 16
Merit: 0
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
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. корень - есть возведение в степень.
|
|
|
|
~DefaultTrust
Copper Member
Sr. Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif) ![*](https://bitcointalk.org/Themes/custom1/images/star.gif) ![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 1554
Merit: 489
Stop the war!
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
August 09, 2021, 02:17:11 PM |
|
спецификация ecdsa. корень - есть возведение в степень.
Какбэ это задолго до ecdsa придумали, что корень - это возведение в степень )) Только квадратным корнем общепринято считать возведение в степень 1/2, кубическим в степень 1/3 и т.д. Это в школе проходят. (0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f + 1) /4 ну явно не равно 1/2 или 1/3. Если конечно деление не по модулю в каком-то экзотическом конечном поле из дробных чисел...
|
Do not trust bitcointalk fascists: leonello; Snork1979; ivan1975
|
|
|
~DefaultTrust
Copper Member
Sr. Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif) ![*](https://bitcointalk.org/Themes/custom1/images/star.gif) ![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 1554
Merit: 489
Stop the war!
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
August 09, 2021, 03:12:18 PM |
|
Хорошие ссылки. В первой ссылке есть теория, из нее я наконец понял что автор топика сделать пытается... Короче, чтобы найти y по известному x в уравнении (1) y 2 = x 3 + ax + b надо, понятное дело, уметь брать корень квадратный. В конечном поле целых чисел корень надо искать по модулю. (2) y 2 = x 3 + 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)
|
Do not trust bitcointalk fascists: leonello; Snork1979; ivan1975
|
|
|
c2h5ohx (OP)
Newbie
Offline
Activity: 16
Merit: 0
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
August 09, 2021, 05:08:01 PM |
|
Подскажите чайнику-автору , есть ли возможность вычислить квадратный корень, в итоге?
|
|
|
|
~DefaultTrust
Copper Member
Sr. Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif) ![*](https://bitcointalk.org/Themes/custom1/images/star.gif) ![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 1554
Merit: 489
Stop the war!
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
August 09, 2021, 05:33:42 PM |
|
Подскажите чайнику-автору , есть ли возможность вычислить квадратный корень, в итоге?
Дык вроде можно
|
Do not trust bitcointalk fascists: leonello; Snork1979; ivan1975
|
|
|
c2h5ohx (OP)
Newbie
Offline
Activity: 16
Merit: 0
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
August 09, 2021, 06:33:35 PM |
|
Подскажите чайнику-автору , есть ли возможность вычислить квадратный корень, в итоге?
Дык вроде можно Ну и как это реализовать? К примеру, корень из 2
|
|
|
|
A-Bolt
Legendary
Offline
Activity: 2325
Merit: 2363
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
August 09, 2021, 06:41:33 PM |
|
Ну и как это реализовать?
Там же в самом конце страницы есть ссылка на готовую реализацию на Питоне. Только она под второй Питон. Если надо под третий, то вот: 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 (OP)
Newbie
Offline
Activity: 16
Merit: 0
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
August 10, 2021, 05:48:11 AM |
|
Спасибо всем огромное! Выручили, работает!
|
|
|
|
|