¿Cómo obtener el valor X de Y?
La verificación de validez de coordenadas ECDSA x, y no parece funcionar
X = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
código pitón,
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
arriba del código python para obtener dos posibles valores y de x
de la misma manera, ¿cómo obtener posibles valores de x de y?,
¿Hay alguna fórmula o script disponible?
Mi pregunta es cómo obtener el valor x de y
si valor y
Y = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
por encima del valor de y cómo obtener el valor de x
Publiqué esta respuesta en BitcoinTalk , pero la copiaré aquí para aquellos que no quieran perseguir enlaces. El siguiente es un pegado directo de ese enlace:
Si puede, instalar Sage y usarlo en lugar de Python le hará la vida mucho más fácil. Hay un cuaderno de ejemplo en bitcoin.ninja que hace algunas cosas ECDSA en la curva de Bitcoin.
Para responder directamente a su pregunta, podemos obtener x de y básicamente de la misma manera que obtuvo y de x. Para ver esto, analicemos por qué funciona su método.
De nuestra ecuación de curva tenemos que Y = y^2 = x^3 + 7. Puede calcular Y fácilmente a partir de x, luego está resolviendo Y = y^2 para y. Por el pequeño teorema de Fermat podemos escribir 1 = y^(p - 1) = Y^(p - 1)/2. Escriba Q = (p - 1)/2; entonces tenemos Y^Q = 1, entonces Y^(Q + 1) = Y = y^2, entonces Y^((Q + 1)/2) = y. Resulta que (Q + 1)/2 = (p + 1)/4, por lo que pudiste resolver y usando un exponente de (p + 1)/4. Note que esto depende crucialmente de que p sea 3 mod 4; de lo contrario (p + 1)/4 no sería un número entero y no podríamos calcularlo. Afortunadamente, nuestra elección de p satisface esto.
¡OK! Así que hagamos lo análogo para x. Escribamos X = x^3 = y^2 - 7. X se puede calcular fácilmente a partir de y, por lo que debemos resolver X = x^3. Escriba Q = (p - 1)/3; entonces X^Q = x^(p - 1) = 1, entonces X^(Q + 1) = Q = x^3, entonces X^((Q + 1)/3) = x. Resulta que (Q + 1)/3 = (p + 2)/9. Esta vez dependemos crucialmente de que p sea 7 mod 9, para que sea un número entero. ¡Afortunadamente lo es! Ahí vas.
TL;DR use (p + 2)/9 en lugar de (p + 1)/4.
Ah, y para obtener las otras dos raíces cúbicas, multiplicas por una raíz cúbica no trivial de 1. (Al igual que tú multiplicando por -1 en tu código original). Una de esas raíces cúbicas es 0x7ae96a2b657c07106e64479eac3434e99cf0497512f58995c1396c28719501ee.
Aquí hay un código de Python análogo al tuyo. Toma uno de sus valores de salida y y devuelve el valor de entrada x como 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)
Su salida es
xcubed = 0x4866d6a5ab41ab2c6bcc57ccd3735da5f16f80a548e5e20a44e4e9b8118c26eb
x1 = 0xc994b69768832bcbff5e9ab39ae8d1d3763bbf1e531bed98fe51de5ee84f50fb
x2 = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
x3 = 0xbcace2e99da01887ab0102b696902325872844067f15e98da7bba04400b88fcb
Como complemento a la respuesta correcta de Andrew, cuando ejecuto su código Python aparece x = pow(xcubed, (p + 2) / 9, p)un error TypeError: pow() 3rd argument not allowed unless all arguments are integers, que está relacionado con el hecho de que el exponente (p + 2) / 9es un punto flotante (debido a la división en Python). Para evitar este error, puede usar el pequeño teorema de Fermat en el propio exponente :
(p + 2) / 9se convierte en:
(p + 2) * pow(9, -1, p)que se convierte en:
(p + 2) * pow(9, -1 + (p - 1), p) % pque se simplifica a:
(p + 2) * pow(9, p - 2, p) % p
El código de Andrew se vería así:
x = pow(xcubed, (p + 2) * pow(9, p - 2, p) % p , p)
De esta manera, evita la división involucrada (p + 2) / 9y, en cambio, solo está haciendo multiplicaciones y exponenciaciones en números grandes.
David Grayson