如何通过GMP库获取secp256k1曲线上的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 Public coordinates for the given Private Key:
mpz_init_set_str(x, "7962D45B38E8BCF82FA8EFA8432A01F20C9A53E24C7D3F11DF197CB8E70926DA", 16);
mpz_init_set_str(y, "7A3EF3EBAFC756DC3B24B75292D4CC5D71B170E97044A9858353443A96BAED23", 16);

//Keep it 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 坐标的准确值？

下面的例子给了我：

X Coordinate: 
a6113c216857d96281c2827ad5bb1dc5d6209dfd4dbdc2f2693f5fd4abb453c7

选择 Y：

mpz_pow_ui(x, x, 3);
mpz_add_ui(x, x, 7);
mpz_sqrt(x, x);
mpz_mod(x, x, p);

结果：

EE26F2FA7D6EF1F2A0D437D5A41B2FC1154849B740A9484564B2E063E6EFB987

mpz_mod(x, x, p);
mpz_sqrt(x, x);

结果：

9095E5640A5AA4FBD471782544ADFF72

好多了！这里没有秘密，这是一个真正的公共地址。偶数/奇数..等位于 Y 坐标的末尾。那么我们在哪里得到什么宇宙

X=7962D45B38E8BCF82FA8EFA8432A01F20C9A53E24C7D3F11DF197CB8E70926DA
Y=7A3EF3EBAFC756DC3B24B75292D4CC5D71B170E97044A9858353443A96BAED23

用这个方程？

Answer 1

这是一项困难的操作，没有像

mpz_sqrtm

这样简单的内置GMP功能。要获得立方根，您需要应用模幂。这个概念是计算

x = a(p+1)/3 (mod p),

，其中

a

是要确定其立方根的整数。然而，在模运算中，这是一个不平凡的过程。

mpz_init(x);
mpz_powm_ui(x, a, (mpz_get_ui(p) + 1) / 3, p);

在此代码中，

a

是要求立方根的数字，

x

是对

p

取模的立方根。检查您是否使用 GMP 版本 6.0 或更高版本，因为在以前的版本中可能无法访问

mpz_powm_ui

。类似的方法可以用来计算

y

坐标的平方根。这将为您提供正确的

x

和

y

坐标。由于计算涉及有限域，因此即使过程中的微小变化也可能提供截然不同的答案。