Как получить значение X из Y?
Проверка правильности координат ECDSA x, y не работает
Х = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
код питона,
p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
x = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
ysquared = ((x*x*x+7) % p)
print "ysquared= %s " % hex(ysquared)
y = pow(ysquared, (p+1)/4, p)
print "y1 = %s " % hex(y)
print "y2 = %s " % hex(y * -1 % p)
Output
Y1 = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
Y2 = 0xb7c52588d95c3b9aa25b0403f1eef75702e84bb7597aabe663b82f6f04ef2777
print hex((x**3 + 7 - y1**2) % p) // output 0
print hex((x**3 + 7 - y2**2) % p) // output 0
выше код python, чтобы получить два возможных значения y из x
как то же самое, как получить возможные значения x из y?,
Доступна ли какая-либо формула или сценарий
Мой вопрос в том, как получить значение x из y
если у значение
Y = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
выше значения y, как получить значение x
Я разместил этот ответ на BitcoinTalk , но скопирую его здесь для тех, кто не хочет гоняться за ссылками. Ниже приведена прямая вставка из этой ссылки:
Если вы можете, установка sage и использование его вместо Python значительно облегчит вам жизнь. На сайте bitcoin.ninja есть пример блокнота, который делает некоторые вещи ECDSA на кривой биткойна.
Чтобы напрямую ответить на ваш вопрос, мы можем получить x из y в основном так же, как вы получили y из x. Чтобы убедиться в этом, давайте рассмотрим, почему ваш метод работает.
Из нашего уравнения кривой мы получаем Y = y^2 = x^3 + 7. Вы можете легко вычислить Y из x, тогда вы решаете Y = y^2 для y. По малой теореме Ферма мы можем написать 1 = y^(p-1) = Y^(p-1)/2. Напишите Q = (p - 1)/2; тогда у нас есть Y ^ Q = 1, поэтому Y ^ (Q + 1) = Y = y ^ 2, поэтому Y ^ ((Q + 1)/2) = y. Как оказалось, (Q + 1)/2 = (p + 1)/4, поэтому вы смогли найти y, используя показатель степени (p + 1)/4. Обратите внимание, что это в решающей степени зависит от того, является ли p равным 3 mod 4; иначе (p + 1)/4 не было бы целым числом, и мы не смогли бы это вычислить. К счастью, наш выбор p удовлетворяет этому.
ХОРОШО! Итак, давайте проделаем аналогичную вещь для x. Давайте напишем X = x^3 = y^2 - 7. X можно легко вычислить из y, поэтому нам нужно решить X = x^3. Запишите Q = (p - 1)/3; тогда X ^ Q = x ^ (p - 1) = 1, поэтому X ^ (Q + 1) = Q = x ^ 3, поэтому X ^ ((Q + 1)/3) = x. Оказывается, (Q + 1)/3 = (p + 2)/9. На этот раз мы в решающей степени зависим от p, равного 7 mod 9, чтобы это было целым числом. К счастью, это так! Так вот.
TL;DR используйте (p + 2)/9 вместо (p + 1)/4.
Да, и чтобы получить два других кубических корня, вы умножаете их на нетривиальный кубический корень из 1. (Похоже на умножение на -1 в исходном коде.) Один из таких кубических корней — 0x7ae96a2b657c07106e64479eac3434e99cf0497512f58995c1396c28719501ee.
Вот код Python, аналогичный вашему. Он принимает одно из ваших выходных значений y и возвращает входное значение x как x2.
## Input
y = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
## Field parameters
# Field modulus
p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
# Cube root of 1
beta = 0x7ae96a2b657c07106e64479eac3434e99cf0497512f58995c1396c28719501ee
## Actual code
xcubed = (y*y - 7) % p
print "xcubed = 0x%x" % xcubed
x = pow(xcubed, (p + 2) / 9, p)
print "x1 = 0x%x" % x
print "x2 = 0x%x" % (x * beta % p)
print "x3 = 0x%x" % (x * beta * beta % p)
Его вывод
xcubed = 0x4866d6a5ab41ab2c6bcc57ccd3735da5f16f80a548e5e20a44e4e9b8118c26eb
x1 = 0xc994b69768832bcbff5e9ab39ae8d1d3763bbf1e531bed98fe51de5ee84f50fb
x2 = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
x3 = 0xbcace2e99da01887ab0102b696902325872844067f15e98da7bba04400b88fcb
В качестве дополнения к правильному ответу Эндрю, когда я запускаю его код Python , x = pow(xcubed, (p + 2) / 9, p)я получаю сообщение об ошибке TypeError: pow() 3rd argument not allowed unless all arguments are integers, связанное с тем, что показатель степени (p + 2) / 9представляет собой число с плавающей запятой (из-за деления в Python). Чтобы избежать этой ошибки, вы можете использовать Маленькую теорему Ферма о самом показателе степени :
(p + 2) / 9становится:
(p + 2) * pow(9, -1, p)который становится:
(p + 2) * pow(9, -1 + (p - 1), p) % pчто упрощает до:
(p + 2) * pow(9, p - 2, p) % p
Тогда код Эндрю будет выглядеть так:
x = pow(xcubed, (p + 2) * pow(9, p - 2, p) % p , p)
Таким образом, вы избегаете деления (p + 2) / 9и вместо этого просто выполняете умножение и возведение в степень больших чисел.
Дэвид Грейсон