Public keys represent a point on the curve, given a pair of ($x$,$y$) coordinates. In uncompressed form, a public key when encoded as bytes ([1], sec 2.3.4) it would be with the identifier 0x04 prepended to both coordinates: pk := 0x04 || x || y.
However, it’s not required to store the $y$-coordinate in order the use the public key. The compressed form of a public key leaves out $y$ and adds a sign instead, indicating whether $y$ was even or odd.
$y$ is even: pk := 0x02 || x
$y$ is odd: pk := 0x03 || x
This allows us to essentially cut the length required to store a public key in half. In order to use a public key in compressed form for any operations, such as signature verification, we have to recover $y$.
The P384 curve (also known as “secp384r1”), is a prime order short Weierstrass curve with the following defined:
$E: y^2 = x^3 + ax + b$
$\mathbb{Z}_p$, where $p = 2^{384} - 2^{128} - 2^{96} + 2^{32} - 1$ (all operations on the curve are modulo the prime $p$)
$a = -3$ (the same as $p - 3$, so usually precomputed when used in implementations)
$b =$ b3312fa7 e23ee7e4 988e056b e3f82d19 181d9c6e fe814112 0314088f 5013875a c656398d 8a2ed19d 2a85c8ed d3ec2aef
To recover $y$, we start be solving the polynomial (right-hand side of the curve’s equation) by using the defined constant and the $x$-coordinate provided by the compressed public key:
$y^2 = x^3 + (a * x) + b$
In order to get $y$, we need to compute the square root of $y^2$. This is not a straight-forward $\sqrt{y2}$ as it needs to be done modulo the prime. A general algorithm that can be used for this is Tonelli-Shanks ([2]) which works when we have a non-zero $n$ ($y^2$ in this case) and an odd prime $p$ (which is also true for secp384r1).
First we have to check if $y^2$ has a square root at all. Euler’s criterion states that ([3]):
$n^{\frac{p-1}{2}} \equiv 1$ (mod p), then $n$ has a square root
$n^{\frac{p-1}{2}} \equiv -1$ (mod p), then $n$ does not have a square root
This can be checked using the Legendre symbol ([4]) (or Jacobi symbol). The only difference to the Legendre symbol is that we define $0$ as the result if $n^{\frac{p-1}{2}} \equiv 0$ (mod p). In other words, we are checking whether or not $y^2$ is a quadratic residue. If the Legendre symbol of $y^2$ is anything but $1$, we cannot continue. If it is one, it means there is a square root and we can find it using Tonelli-Shanks.
There is a faster way to compute the square of $y^2$ in the case of secp384r1, in that we don’t need the entire Tonelli-Shanks algorithm, just the “easy case”. Because $p \equiv 3$ (mod $4$) holds true for the prime $p$ in secp384r1, the square root can be computed by $y = \sqrt{y^2} = y^2{^{\frac{p+1}{4}}}$. The only thing remaining is checking if $y$ is odd and the first byte of the public key is 0x03, or if $y$ is even and the first byte of the public key is 0x02. If this is not true, then set $y = p - y$. This leaves us with the original $y$-coordinate that was shaved off in the beginning.
In implementations, you can expect to find values like $\frac{p+1}{4}$ and $\frac{p-1}{2}$ precomputed.