# How to expand elliptic curve public key from compressed form?

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?

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)
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.

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).