1
$\begingroup$

Following this page https://en.bitcoin.it/wiki/Secp256k1, secp256k1 curve's equation is $$y^2=x^3+7$$ Does this mean that I can substitute $G_x$ in the equation to get $G_y$? I think yes and that's how public key compression works, since we don't actually need to store $y$ value because we can compute it at run-time. But after substitution of the generator point of secp256k1 I get wrong equation: $$G_x = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798$$ $$G_y = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8$$ $$G_y^2=G_x^3+7$$ $$106736222501650227577219490950371...=1.66977061698153803977729810299616665e230 + 7$$ The equation is wrong. Where am I going wrong?

$\endgroup$
0

2 Answers 2

2
$\begingroup$

In ECC, all base arithmetic is performed on the $\mathbb F_p$. Secp256k1 used a prime so $\mod p$ is enough for these kind of operations. One needs a big integer library to calculate the arithmetic correctly. Here is a sample code from Sagemath

#secp256k1
p = Integer("0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F")

a = Integer("0x0000000000000000000000000000000000000000000000000000000000000000")
b = Integer("0x0000000000000000000000000000000000000000000000000000000000000007")

K = GF(p)
E = EllipticCurve(K,[a,b])

Gx = Integer(0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798)
Gy = Integer(0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8)
G = E(Gx, Gy)

# Check the base point
assert(Gy^2 % p == (Gx^3 + a * Gx + b) % p)

#Sample public points with compressed 02
Compressed = "02b4632d08485ff1df2db55b9dafd23347d1c47a457072a1e87be26896549a8737"
#Sample public points with compressed 03
#Compressed = "03b1e8e14e794c00c364daa5ff85258ac480a0e21e819e08d5a259553ed911cb15"

print( "Given public key\n", Compressed)

#lift to find point that has the given x coordinate
P = E.lift_x(Integer("0x"+Compressed[2:]))

#Determine the correct y-coordinate.

if (Integer(P[1]) % 2) == 0:
    print("Using compression 02\n", P)
else:
    Q = E(P[0],p-P[1])
    print("Using compression 03\n", Q)

The above code verifies the base point ( well, G = E(Gx, Gy) already has verification on SageMath), and there are two sample public keys to resolve the full point.

Keep in mind that

  • prefix 04 means no compression
  • prefix 02 means compression with $y$ coordinate is even
  • prefix 03 means compression with $y$ coordinate is odd

The above code only handles the cases 02 and 03 not 04.

$\endgroup$
2
$\begingroup$

Where am I going wrong?

The two sides are computed modulo a prime $p$.

For Secp256k1, we have $p = 2^{256}−2^{32}−977 = 115792089237316195423570985008687907853269984665640564039457584007908834671663$

Computing them as integers or reals gives the wrong result, as you have seen.

And, to answer the question you have not asked, to compute $G_y$ from $G_x$, you need to do a modular square-root of $G_x^3 + 7$. It turns out to not be that bad; because $p \equiv 3 \pmod 4$, the modular square roots of $z$ are $z^{(p+1)/4} \bmod p$ and $p - z^{(p+1)/4} \bmod p$, the latter sometimes is expressed as $- z^{(p+1)/4} \bmod p$.

As so, we have $G_y = \pm (G_x^3 + 7)^{(p+1)/4} \bmod p$ (and the compressed point should contain a bit that determines which of the two $G_y$ values to take).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.