如何在secp256k1曲线上获得GMP库的X和Y坐标？

Question

我真的很挣扎，所以我希望有人能为黑暗带来一些光明。 我想只存储公钥的“一半”坐标，并通过数学得到其余的坐标。 可能获得 Y 比 X “便宜”，但从数组的角度来看..无论如何。 所有的钥匙都是有效的，所以这不会是一个问题..至少，我是这么认为的。

最简单的方法可能是通过一个具体的例子：

` //y^2 = x^3 + 7 (mod p) //x = [y^2 - 7]^[(p + 2)/9] mod p //y = +- sqrt[x^3 + 7] mod p

//Private Key => 0x7777777777777777777777777777777777777777777777777777777777777777

mpz_init_set_str(p, "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F", 16);

//The coordinates for the given Private Key:
mpz_init_set_str(x, "7962D45B38E8BCF82FA8EFA8432A01F20C9A53E24C7D3F11DF197CB8E70926DA", 16);
mpz_init_set_str(y, "7A3EF3EBAFC756DC3B24B75292D4CC5D71B170E97044A9858353443A96BAED23", 16);

//Starting with simple: y^2 mod p = (X^3 + 7) mod p

mpz_pow_ui(y, y, 2);
mpz_mod(y1, y, p);
gmp_printf("%Z02X\n", y);

mpz_pow_ui(x, x, 3);
mpz_add_ui(x, x, 7);
mpz_mod(x, x, p);
gmp_printf("%Z02X\n", x);    `

结果： 51A8F9D55FA628BD9E8B970CDA3C19004C1ABFFAB83CB65E48B837A9509A1366 51A8F9D55FA628BD9E8B970CDA3C19004C1ABFFAB83CB65E48B837A9509A1366

到目前为止一切都很好，至少在提醒方面是这样，但是我怎样才能获得 X 或 Y 坐标的准确值？我的问题肯定是无处不在的根源部分。我忘了提到..在C.

我已经尝试过我发现的所有类型的根、幂和模函数，但我太笨了，无法弄清楚..也许一些反转模移位任何魔法都可以解决问题！

提前致谢！

Answer 1

您正在使用椭圆曲线密码学和曲线上的点计算。您想要找到给定私钥的 x 和 y 坐标。

y^2 = x^3 + 7 (mod p)

要获取 x 坐标，首先计算

x3 + 7

，然后找到该数字模

p

的平方根。 C 中的 GMP 库可用于处理巨大的数字和平方根。

mpz_init_set_str(p, "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F", 16);
mpz_init_set_str(y, "7A3EF3EBAFC756DC3B24B75292D4CC5D71B170E97044A9858353443A96BAED23", 16);

// Calculate x^3 + 7 (mod p)
mpz_pow_ui(x, y, 2); // y^2
mpz_sub_ui(x, x, 7); // Subtract 7
mpz_mod(x, x, p);

// Find the cube root of x modulo p
mpz_t x_root;
mpz_init(x_root);
mpz_powm_ui(x_root, x, (mpz_get_ui(p) + 2) / 3, p);

gmp_printf("X Coordinate: %Zx\n", x_root);

您现在知道了 x 坐标。要获得 y 坐标，请取 'x3 + 7 (mod p) 的平方根。可以使用类似的策略：

// Find the square root of x^3 + 7 modulo p
mpz_sqrtm(y, x, p);

gmp_printf("Y Coordinate: %Zx\n", y);

检查结果的有效性，因为根据曲线可能有多个根。