El algoritmo ECDSA, secp256k1 para Bitcoin supuestamente usa la ecuación
y ^ 2 = x ^ 3 + 7 mod P
para determinar la validez de un supuesto punto sobre la curva elíptica. Utilizando http://web2.0calc.com/
Al verificar la clave pública 1 que tiene las siguientes cualidades:
x = 55066263022277343669578718895168534326250603453777594175500187360389116729240
y = 32670510020758816978083085130507043184471273380659243275938904335757337482424
Apliqué x ^ 3, luego agregué 7, luego mod P en esa página web. Luego le hice raíz cuadrada y obtuve
180964706334543048141953325634608696715.426683454595872
Que no es y. ¿Cómo estoy haciendo esto mal? Mis resultados sugieren que este punto no es un punto válido en la curva, pero todos saben que lo es. Obviamente soy yo el que está equivocado.
EDITAR: Me gustaría aclarar más la pregunta. Mi pregunta es, ¿cómo se determina realmente (como ejemplo) el valor de Y mientras solo se tiene el valor de X? Bitcoin lo hace, la "Utilidad de direcciones de Bitcoin" también lo hace. Cuando alguien tiene una clave comprimida (que solo contiene la coordenada x), también puede obtener la coordenada y. Utilizar la calculadora de página web antes mencionada no funciona y otros dicen que es "raíz modular". ¿Alguien tiene el código Python 2.7.7 que haría esto o tiene una forma relativamente simple de explicar cómo lograr todo esto? Gracias.
El formato de texto sin formato de esta ecuación solo tiene sentido cuando comprende la teoría detrás de ella. y ^ 2 = x ^ 3 + 7 mod P
significa "hacer todas las matemáticas en esta ecuación usando el campo de números finitos con definición P". Es mejor que se escriba (y^2 = x^3 +7) mod p
.
Para simplificar las matemáticas, simplemente restemos un lado del otro para ver si eso da como resultado cero. Esto nos permite evitar las raíces. Aquí hay un código que usa el shell interactivo de Python, por ejemplo, python
desde un símbolo del sistema):
>>> x = 55066263022277343669578718895168534326250603453777594175500187360389116729240
>>> y = 32670510020758816978083085130507043184471273380659243275938904335757337482424
>>> p = 115792089237316195423570985008687907853269984665640564039457584007908834671663
>>> (x**3 + 7 - y**2) % p
0
A partir de su valor X, puede obtener 2 posibles valores Y.
y^2 == (Y * Y) == (-Y * -Y) (mod p)
Dependiendo del formato de la clave pública en la entrada de la transacción de bitcoin, puede averiguar contra qué Y desea validar.
Si la clave pública comienza con 04, entonces Y ya está presente en la clave pública y no necesita hacer ningún cálculo para encontrar Y
Si la clave pública comienza con 02, entonces el valor Y que desea es un número par.
Si la clave pública comienza con 03, entonces el valor Y que desea es un número impar.
Usando tu ejemplo para X,
X = 55066263022277343669578718895168534326250603453777594175500187360389116729240
Calculo que los posibles valores de Y son,
Y1 = 32670510020758816978083085130507043184471273380659243275938904335757337482424
Y2 = 83121579216557378445487899878180864668798711284981320763518679672151497189239
Elija su Y según el formato de la clave pública en la entrada de la transacción de bitcoin.
código pitón,
p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
x = 55066263022277343669578718895168534326250603453777594175500187360389116729240
ysquared = ((x*x*x+7) % p)
print "ysquared= %s " % ysquared
y = pow(ysquared, (p+1)/4, p)
print "y1 = %s " % y
print "y2 = %s " % (y * -1 % p)
Prefiero ver mis números en formato hexadecimal, así que aquí está el mismo resultado de ejemplo que hexadecimal.
X = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
Y1 = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
Y2 = 0xb7c52588d95c3b9aa25b0403f1eef75702e84bb7597aabe663b82f6f04ef2777
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)
Una transacción de ejemplo que contiene la clave pública X,Y1 (0279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798)
https://2xoin.com/tx/8e2c570498680261040ceffdd15e67dda6c00a885d1e5484f220125f3a5e2c56
Al momento de escribir, no hubo transacciones usando la clave pública X, Y2
Para profundizar en la respuesta de David, la parte más difícil es en realidad la raíz cuadrada. Es solo el número que después de elevar al cuadrado el módulo P termina siendo el resultado que tenía antes. Esa es una raíz cuadrada modular, y no la calculará fácilmente usando aritmética regular (a diferencia de las sumas, multiplicaciones o potencias modulares).
Esta sección de artículos de wikipedia tiene más información: http://en.wikipedia.org/wiki/Quadratic_residue#Prime_or_prime_power_modulus
También puede decodificar desde b64 Q29udGFjdCBtZSBhdCBhZGl0ZWMzNUBnbWFpbC5jb20= the: x = 55066263022277343669578718895168534326250603453777594175500187360389116729240
y = 32670510020758816978083085130507043184471273380659243275938904335757337482424
Apliqué x ^ 3, luego agregué 7, luego mod P en esa página web. Luego le hice raíz cuadrada y obtuve
180964706334543048141953325634608696715.426683454595872
David A. Harding
mti2935